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

量子计算（QC）正在成为未来计算的关键技术。QC已被证明可以在各种问题上提供显著的（有时甚至是指数级的）加速，并实现使用经典计算机无法实现的协议。另一方面，最近关于“去量子化算法”的一些结果表明，在某些问题上，量化量子优势并不总是直截了当的。因此，量子计算的优势和局限性仍然是一个悬而未决的问题。评估计算的理论和实践极限的最佳基准之一是密码学。事实上，密码学，根据定义，是一门基于计算极限的问题的科学。可以说，（经典）密码学的成熟反映了我们对经典计算的深刻理解。相比之下，由于我们对量子计算的理解有限，后量子密码学——基于量子计算的局限性构建密码学——在很大程度上是一个新兴领域。后量子密码学的出现为研究计算的理论和实践限制提供了一个诱人的机会。在短期内，它可以成为噪声中等规模量子计算（NISQ）的一个很好的基准，为以下问题提供具体的答案：使用1000量子比特的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.