Complexity-theoretic foundations of quantum advantage experiments
Abstract
A major milestone on the path towards building scalable quantum computers is the demonstration of “quantum supremacy” or “quantum advantage” – i.e. the experimental demonstration of a quantum computation which is beyond the reach of classical computers. These experiments are being used to certify the computational power of prototype quantum computers and as a means of diagnosing errors in these devices. However there are major gaps between the idealized theoretical underpinnings of these experiments and their highly noisy experimental implementations. Additionally, going forward there is the exciting possibility that these experiments will have practical cryptographic applications such as certified random number generation, in addition to their use as benchmarking tools. Here we propose to build the complexity-theoretic foundations of highly noisy quantum advantage experiments. In particular we will focus on (i) understanding the extent to which these devices have beyond-classical computational power, closing the remaining gaps between theory and experiment related to noise, and (ii) exploring potential applications of quantum advantage experiments such as certified random number generation. If successful, the research outcomes will advance our understanding of quantum computation and quantum cryptography, allow for the more accurate benchmarking and evaluation of prototype quantum computers, and enable new cryptographic capabilities from near-term quantum devices.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 21, 2022
- Source ID
- FA95502110392XX0
Entities
People
- Adam Bouland
Organizations
- Air Force Office of Scientific Research
- Stanford University
- United States Air Force