Quantum Information

From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that BQP is in AWPP, where AWPP is a classical complexity class (known to be included in PP, hence PSPACE). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterised by local measurements), efficient computations are contained in AWPP. This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Then, following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, PostBQP, is equal to PP. Given only the assumption of tomographic locality, the inclusion in PP still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativised complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a `classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include NP. This provides some degree of evidence that NP-complete problems cannot be solved efficiently in any theory satisfying tomographic locality and causality. Based on arXiv:1412.8671. Joint work with Jon Barrett.

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

The Elitzur-Vaidman bomb tester allows the detection of a photon-triggered bomb with a photon, without setting the bomb off. This seemingly impossible task can be tackled using the quantum Zeno effect. Inspired by the EV bomb tester, we define the notion of "bomb query complexity". This model modifies the standard quantum query model by measuring each query immediately after its application, and ends the algorithm if a 1 is measured.

We show that the bomb query complexity is asymptotically the square of the quantum query complexity. Moreover, we will show how this characterization inspires a general theorem relating classical and quantum query complexity, and derive new algorithms from this theorem.

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.