Quantum Information, Computation and Logic: Exploring New Connections

Both quantum logic (QL) and quantum information (QI) are based on viewing quantum mechanics in terms of concepts closely tied to information, so QL, should be closely connected to QI. On the whole, these two research fields are pursued by separate communities and so a closer collaboration is likely to yield significant insights into both. While taking a broad view of both fields, the workshop will focus on areas that we feel are most likely to spark significant collaboration and new research initiatives. We will emphasize three areas in particular.

Firstly, QI raises questions about the power of systems governed by different types of theories for performing information-processing tasks, and QI researchers have become interested in characterizing theories by their information processing power. Since QL, broadly construed, is also deeply concerned with characterizing types of theories axiomatically, combining the efforts of these two communities would be fruitful. The QL community is much further along in developing mathematical frameworks for such investigations, while the QI community has explored task-motivated, operational properties in more detail. Both communities have been led to consider structures that are neither quantum nor classical. We expect that bringing together these two approaches will result in more operationally meaningful characterizations of theories, addressing the complaint that some axioms in QL based approaches to quantum mechanics are of unclear operational significance even if they are mathematically natural.

Second, quantum logic might serve as a useful tool for investigating problems in quantum computing. Indeed, it could shed significant light on the power of quantum computation, a question that has occupied many quantum information theorists in recent years. A few attempts to construct logics for quantum computation have been made, but it is not yet clear what the definitive logic of quantum computation is. It is likely that alternative models of quantum computing, especially those based on measurements, might provide a clearer connection between quantum logic and computing.

Thirdly, problems in classical logic, such as the satisfiability problem, play a key role in the theory of computational complexity. These give significant insight into the power of classical computation, enabling questions such as whether P=NP to be posed in a mathematically rigorous form. It seems natural to investigate whether there are analogs of these problems in quantum logic that could play a similar role in quantum computational complexity.

Organizers: 

Matthew Leifer
Howard Barnum