Characterizing the Power of Experimentally Feasible Quantum Computation with Applications to Rigorous Security Guarantees for Quantum-safe Cryptography
Abstract
Since the discovery of Shor s factoring algorithm in the 1990 s, it has been known that quantumcomputers can efficiently factor integers, a problem of great practical relevance with no knownefficient classical algorithm. The importance of this result is impossible to overstate: the ExtendedChurch-Turing hypothesis", the fundamental assumption underlying the universality of the classicalTuring machine, is invalid unless there also exists a classical efficient factoring algorithm. Such analgorithm would be able to break the ubiquitous RSA cryptosystem, falsifying a hardness conjectureproviding basis for the security of the modern internet.Large-scale universal fault-tolerant quantum computers capable of factoring cryptographicallyrelevant integers may still not be experimentally feasible for several years. However, the workundertaken toward building universal quantum computers has already yielded breathtaking experimental progress in high-precision control over individual quantum systems. It is plausible thatpresent-day laboratory devices are already capable of harnessing quantum effects to demonstratetasks beyond the reach of even the fastest classical supercomputers.Rigorously understanding the capabilities of such quantum systems is one of the most pressingchallenges of modern quantum information science, and is the subject of this proposal. We pro-pose investigating new methodology for mathematically characterizing the computational power ofresource-limited experimentally feasible forms of quantum computation.Our objective relates directly to the future of cryptography. We will use these characteriza-tions to gain increased condence that today s candidate post-quantum cryptographic schemes areresilient to quantum attack and separately, to help develop new cryptographic functionality usingthe power of quantum mechanics.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 30, 2018
- Source ID
- FA95501810148
Entities
People
- William Fefferman
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Maryland