Quantum Foundations

From Feynman diagrams via Penrose graphical notation to quantum circuits, graphical languages are widely used in quantum theory and other areas of theoretical physics. The category-theoretical approach to quantum mechanics yields a new set of graphical languages, which allow rigorous pictorial reasoning about quantum systems and processes. One such language is the ZX-calculus, which is built up of elements corresponding to maps in the computational and the Hadamard basis. This calculus is universal for pure state qubit quantum mechanics, meaning any pure state, unitary operation, and post-selected pure projective measurement can be represented. It is also sound, meaning any graphical rewrite corresponds to a valid equality when translated into matrices.

While the calculus is not complete for general quantum mechanics, I show that it is complete for stabilizer quantum mechanics and for the single-qubit Clifford+T group. This means that within those subtheories, any equality that can be derived using matrices can also be derived graphically.

The ZX-calculus can thus be applied to a wide range of problems in quantum information and quantum foundations, from the analysis of quantum non-locality to the verification of measurement-based quantum computation and error-correcting codes. I also show how to construct a ZX-like graphical calculus for Spekkens' toy bit theory and give its associated completeness proof.

The Church-Turing thesis is one of the pillars of computer science; it postulates that every classical system has equivalent computability power to the so-called Turing machine. While this thesis is crucial for our understanding of computing devices, its implications in other scientific fields have hardly been explored. What if we consider the Church-Turing thesis as a law of nature? In this talk I will present our first results in connection with quantum information theory [1] by showing that computer science laws have profound implications for some of the most fundamental results of quantum theory.  First I will show how they question our knowledge on what a mixed quantum state is, as we identified situations in which ensembles of quantum states defining the same mixed state, indistinguishable according to the quantum postulates, do become distinguishable when prepared by a computer (or any classical system). Then I will introduce a new loophole for Bell-like experiments: if some of the parties in a Bell-like experiment use a computer to decide which measurements to make, then the computational resources of an eavesdropper have to be limited in order to have a proper observation of non-locality.

The study of ground spaces of local Hamiltonians is a fundamental task in condensed matter physics. In terms of computational complexity theory, a common focus in this area has been to estimate a given Hamiltonian’s ground state energy. However, from a physics perspective, it is sometimes more relevant to understand the structure of the ground space itself. In this talk, we pursue the latter direction by introducing the notion of “ground state connectivity” of local Hamiltonians. In particular, we show that determining how “connected” the ground space of a local Hamiltonian is can range from QCMA-complete to NEXP-complete. (Here, QCMA is the same as QMA, but with a classical witness.) As a result, we obtain a natural QCMA-complete problem, a task which has generally proven difficult since the conception of QCMA over a decade ago.