(FoQaCiA): Foundations of quantum computational advantage

在FoQaCiA中，我们将扩展量子算法设计的理论基础。我们的观点是，量子计算未来的成功关键取决于最基本层面的进步，只有在能够利用额外的基础见解和想法的情况下，对量子实现的大规模投资才会得到回报。虽然已知有几种强大的量子算法，但它们采用的基本技术却很少。在很大程度上，如何系统地利用量子进行计算仍有待发现。我们研究了量子现象学的四个领域：(i)量子情境性，非经典性和量子优势，（ii）量子计算经典模拟的复杂性，（iii）量子电路的算法，以及（iv）容错量子计算的效率。选择这些字段有两个原因。首先，他们的进展对量子计算的物理实现和广泛适用性具有重要意义。关于(1)，量子情境性最简单的证明之一，Mermin 's star，最近被用来证明（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