The limits of Quantum Computing: an approach via Post-Quantum Cryptography

量子计算(QC)正在成为未来计算的关键技术。QC已被证明在各种问题上提供了显著的-有时甚至是指数级的-加速，并启用了使用传统计算机无法实现的协议。另一方面，最近关于“去量子化算法”的一些结果表明，在某些问题上量化量子优势并不总是简单的。因此，量子计算的优势和局限性仍然是一个悬而未决的问题。评估计算理论和实践极限的最佳基准之一是密码学。事实上，根据定义，密码学是一门将问题建立在计算极限之上的科学。可以说，(经典)密码学的成熟反映了我们对经典计算的深刻理解。相比之下，后量子密码学-基于量子计算极限构建密码学-由于我们对量子计算的有限理解，在很大程度上是一个新兴领域。后量子密码学的出现为研究计算的理论和实践极限提供了一个诱人的机会。在短期内，它可以构成噪音中等规模量子计算(NISQ)的一个很好的基准，为以下问题提供具体的答案：使用1000 Qbit的NISQ设备，量子算法能否击败任何有用的经典算法？从长远来看，有关量子计算机局限性的更基本的问题需要得到解答。除了已知的量子算法可以提供的指数和平方加速比之外，这些算法最有希望的方面之一是提供类似的运行时间，同时大大减少内存使用。内存可以说是经典计算机最受限制的方面之一。例如，模拟量子系统的指数记忆爆炸表明，理解量子记忆的局限性是至关重要的。后量子密码学为研究量子计算的这一方面提供了大量的问题，并回答了一些问题，如：量子计算能否为一些现实生活中的问题提供指数级的内存改进？我假设，格子和代码，这些基本的数学对象，将在回答我提出的问题方面发挥主要作用。晶格已经成为量子计算和密码学的中心对象。格和码在后量子密码学中起着至关重要的作用，其中有三个问题尤为重要：最短向量问题(SVP)、学习误差问题(LWE)和伴随式译码问题。这些问题从根本上是关于量子计算的局限性，并表明格子和代码足够难，足以成为量子硬的，但结构足以提供非平凡的原语。SVP和LWE不仅在密码学中发挥作用，而且在量子计算中也发挥着作用。重要的搜索问题，如二面体隐子群问题，涉及到这两个问题。最近在经典量子计算验证方面的一项突破依赖于LWE。LWE甚至使经典各方能够参与安全的量子计算和通信协议。因此，提高对SVP和LWE的理解将使量子计算和密码学社区受益。此外，格子算法中的一些最新改进来自于代码，显示了一起研究格子和代码而不是单独研究代码的好处。

Quantum computing (QC) is emerging as a critical technology for the future of computing. QC has been shown to provide significant - sometimes even exponential - speedups on various problems, and enable protocols that would be impossible using classical computers. On the other hand, some recent results on ''dequantized algorithms'' show that it is not always straightforward to quantify the quantum advantage on some problems. As a result, the strengths and limitations of quantum computing are still an open problem. One of the best benchmarks to evaluate the theoretical and practical limits of computing is cryptography. Indeed, cryptography is, by definition, the science of basing problems on the limits of computation. Arguably, the maturity of (classical) cryptography reflects our deep understanding of classicalcomputation. In contrast, post-quantum cryptography - building cryptography based on the limits of quantum computing - is very much an emerging field due to our limited understanding of quantum computing.The emergence of post-quantum cryptography presents a tantalizing opportunity to study the theoretical and practical limits of computing. In the near-term, it can constitute a great benchmark for noisy intermediate-scale quantum computing (NISQ), providing concrete answers to questions such as: can a quantum algorithm beat any useful classical algorithm using a NISQ device of 1,000 qbits? In the longterm, more fundamental questions about the limits of quantum computers need to be answered. Beyond the known exponential and quadratic speedups that quantum algorithms can offer, one of the most promising aspects of those algorithms is to offer comparable running times with much reduced memory usage. Memory is arguably one of the most limiting aspects of classical computers. The exponential memory blowup of simulating quantum systems, for example, suggests that understanding the limits of quantum memories is essential. Post-quantum cryptography provides ample problems to study this aspect of quantum computing and answer questions such as: can quantum computing provide exponential memory improvements for some real-life problems?I posit that lattices and codes, fundamental mathematical objects, will play a major role in answering the questions I have put forward. Lattices have emerged as a central object for both quantum computing and cryptography. Lattices and codes play a crucial role in post-quantum cryptography, with three problems standing out as particularly relevant: the shortest vector problem (SVP), the Learning witherror problem (LWE) and the syndrome decoding problem. These problems are fundamentally about the limit of quantum computing and suggest that lattices and codes are hard enough to be quantum hard but structured enough to provide nontrivial primitives. The SVP and LWE play not only a role in cryptography but also in quantum computing. Important search problems such as the dihedral hidden subgroup problem involve both problems. A recent breakthrough in the classical verification of quantum computations relies on LWE. LWE even enables classical parties to participate in secure quantum computation and communications protocols. Therefore, improvements in the understanding of SVP and LWE will benefit both the quantum computing and cryptography community. Furthermore, some recent improvements in lattice algorithms, that come from codes, show the benefit of studying lattices and codes together rather than separately.