(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