(FoQaCiA): Foundations of quantum computational advantage

在FoQaCiA中，我们将扩展量子算法设计的理论基础。我们的观点是，量子计算未来的成功关键取决于最基本层面的进步，而对量子实现的大规模投资只有在能够利用更多的基础见解和想法的情况下才会获得回报。虽然已知了几种强大的量子算法，但它们采用的基本技术却很少。在很大程度上，如何系统地利用量子进行计算仍有待发现。我们研究了量子现象学的四个领域：(I)量子上下文、非经典和量子优势，(Ii)经典量子计算模拟的复杂性，(Iii)量子电路的算法，和(Iv)容错量子计算的效率。选择这些字段有两个原因。首先，它们的进展对量子计算的物理实现和广泛应用具有重要意义。关于(I)，最简单的量子上下文证明之一，Mermin之星，最近被用来证明(Bravyi，Gosset，König)有界深度量子电路比它们的经典类似物更强大。我们寻求将这一结果扩展到有限深度之外。在(Ii)中，我们通过剔除冗余部分来研究量子加速比--有效的经典可刺激部分。在(Iii)中，我们的目标是利用问题的数论基础，为门和电路综合提供更有效的技术。关于(Iv)，鉴于著名的阈值定理，以及错误阈值现在已知在实验范围内的事实，我们将解决降低容错成本的剩余挑战。选择上述工作领域的第二个原因是挖掘它们以寻找基本的量子力学结构，并找到相关的量子算法用途

In FoQaCiA, we will expand the theoretical basis for the design of quantum algorithms. Our view is that the future success of quantum computing critically depends on advances at the most fundamental level, and that large-scale investments in quantum implementations will only pay off if they can draw on additional foundational insights and ideas. While several powerful quantum algorithms are known, the basic techniques they employ are few and far between. Largely, it remains to be discovered how to systematically harness the quantum for computation. We study four areas of quantum phenomenology: (i) Quantum contextuality, non-classicality, and quantum advantage, (ii) Complexity of classical simulation of quantum computation, (iii) Arithmetic of quantum circuits, and (iv) Efficiency of fault-tolerant quantum computation. These fields are chosen for two reasons. First, their progress is of great importance for the physical realisation and the broad applicability of quantum computation. Regarding (i), one of the simplest proofs of quantum contextuality, Mermin’s star, has recently been employed to prove (Bravyi, Gosset, König) that bounded-depth quantum circuits are more powerful than their classical analogues. We seek to expand this result beyond bounded depth. In (ii), we study the quantum speedup by shaving off the redundant part – the efficiently classically stimulable. In (iii), we aim to provide more efficient techniques for gate and circuit synthesis, utilising the number-theoretic underpinnings of the problem. Regarding (iv), given the celebrated threshold theorem, and the fact that the error threshold is now known to be within reach of experiment, we will tackle the remaining challenge of reducing the cost of fault tolerance. The second reason for selecting the above work areas is to mine them for foundational quantum mechanical structures and find related quantum algorithmic uses