The verification and benchmarking of near-term quantum computations
Abstract
We have recently entered a genuinely new era in quantum computing in which near-term quantum experiments are becoming large enough in scale to solve problems which have no efficient classical algorithm. Unlike problems that are easy to verify, such as decision problems solvable in the complexity class NP, the problems that near-term quantum computers are able to solve will generally take the form of sampling from a complicated distribution over measurement outcomes. Such hard sampling problems are very unlikely to have any efficiently checkable witness that can be used to verify correctness. Consequently, as this era progresses, a key challenge for the field will be to understand how to create bechmarking and validation tools that allow us to verify near-term quantum computations using a small number of samples from a noisy experiment. In this project, we will rigorously analyze existing candidates for the verification of near-term quantum computers to better understand under which noise models they work to provably verify quantum computations. We will also study the computational difficulty of scoring well on such benchmarks in order to characterize the power of near-term quantum experiments.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 25, 2023
- Source ID
- FA95502110008
Entities
People
- William Fefferman
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Chicago