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

量子计算的局限性：后量子密码学的方法

基本信息

批准号：
EP/W02778X/1
负责人：
Yixin Shen
金额：
$ 74.55万
依托单位：
Royal Holloway University of London
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2022
资助国家：
英国
起止时间：
2022 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FW02778X%2F1
关键词：
limits Quantum Computing approach via

项目摘要

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.

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