Classical simulation and verification of quantum computation using matchgates and magic states

点击翻译按钮获取中文摘要

Quantum computers allow one to explore computational regimes which are believed to be beyond the reach of current classical computing. Therefore, it is unlikely that universal quantum computers can be efficiently simulated by classical probabilistic algorithms. This is in part because the state-of-the-art classical simulators which rely on the power of modern supercomputers struggle to simulate any quantum system beyond 50 qubits. At the same time, certain quantum information processing tasks do not require computational universality. In some scenarios, there are provable benefits, such as an exponential reduction in communication resources for some distributed computing tasks (e.g. Raz 1999) and in quantum cryptography, the ability to communicate with unconditional security against eavesdropping. To realize quantum computation in a circuit model one has to pick a universal gate set. One of the most prominent gatesets which enables universal quantum computation is made of Clifford + T gates. Clifford gates are efficiently classically simulatable, however, when you add a special single-qubit T gate you regain the full power of quantum computation. In 2016, Bravyi et al. introduced a quantity called stabilizer rank. It helps reduce this exponential scaling by significantly decreasing the scaling of resources required to classically simulate quantum systems. The ability to classically simulate generic quantum computations, while unlikely to be possible for a large number of qubits, is of great importance in the noisy intermediate-term quantum computation (NISQ). Another very natural gateset which enables universal quantum computation is made of so-called Matchgates + Magic states. Matchgates are an especially multiflorous class of two-qubit nearest neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions, and one-dimensional spin chains. The goal of the project is to study the analogous notion to stabilizer rank for matchgates - the so-called Gaussian rank and study the computational complexity of approximating this quantity. Currently, nearly nothing is known about Gaussian rank and unlike its stabilizer counterpart, the decompositions of n copies of magic states in terms of Gaussian states for n>3 are not known. This problem presents a unique set of challenges suitable for a strong PhD student and would require a combination of techniques: from numerical exploration for a small number of qubits to proof-based techniques which rely on the unique structural properties of Gaussian states. Computing the exact Gaussian rank for a large number of copies of magic states has a number of important applications for the emerging small-to-medium scale quantum computers. First, it would enable one to verify quantum computations for a non-trivial number of qubits (20-300), which is likely to be the milestoneSecond, it would provide unique insights into the complexity of fermionic linear optics and its abilities to achieve universal quantum computations when supplemented with magic states. Thirdly, it would allow one to design novel quantum error-correcting codes as well as efficient classical decoders.