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

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