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

量子计算机允许人们探索被认为超出当前经典计算范围的计算机制。因此，通用量子计算机不太可能通过经典概率算法有效地模拟。这在一定程度上是因为依赖于现代超级计算机的最先进的经典模拟器很难模拟超过50个量子比特的任何量子系统。同时，某些量子信息处理任务不需要计算普适性。在某些情况下，有可证明的好处，如一些分布式计算任务的通信资源呈指数级减少（例如Raz 1999），以及在量子密码学中，能够无条件安全地进行通信以防止窃听。 为了在电路模型中实现量子计算，必须选择一个通用的门集。Clifford + T门是实现通用量子计算的最重要的门集之一。克利福德门是有效的经典模拟，然而，当你添加一个特殊的单量子比特T门，你重新获得量子计算的全部力量。2016年，Bravyi等人引入了一个称为稳定器秩的量。它通过显著降低经典模拟量子系统所需的资源规模来帮助降低这种指数规模。经典模拟通用量子计算的能力，虽然不太可能用于大量量子比特，但在有噪声的中期量子计算（NISQ）中非常重要。另一个能够实现通用量子计算的非常自然的门集是由所谓的Matchgates + Magic态组成的。匹配门是一类特别多花的两量子比特最近邻量子门，由一组代数约束定义。它们出现在例如完美匹配的理论图，非相互作用费米子，和一维自旋链。该项目的目标是研究匹配门稳定器秩的类似概念-所谓的高斯秩，并研究近似此数量的计算复杂性。目前，几乎没有什么是已知的高斯秩和不像它的稳定剂对应物，分解的n个副本的魔术状态的高斯状态的n>3是未知的。这个问题提出了一系列独特的挑战，适合一个强大的博士生，并需要技术的组合：从数值探索少量的量子位，以证明为基础的技术，依赖于高斯状态的独特结构特性。计算大量幻态副本的精确高斯秩对于新兴的中小规模量子计算机有许多重要的应用。首先，它将使人们能够验证非平凡数量的量子比特（20-300）的量子计算，这可能是里程碑第二，它将提供对费米子线性光学复杂性的独特见解，以及在补充魔态时实现通用量子计算的能力。第三，它将允许人们设计新的量子纠错码以及有效的经典解码器。

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.