AF: Small: Toward Applications and Verification of Early Quantum Computers

University Of Maryland, College Park, College Park MD

Investigators

Abstract

Quantum computers have the potential to solve certain problems much faster than ordinary classical computers, offering the prospect of efficient solutions to problems that would otherwise be intractable. There has recently been significant progress toward the experimental realization of quantum computers, suggesting that devices with tens of well-controlled qubits may be available in the next decade. Therefore, now is a crucial time to investigate how to best take advantage of the limited capabilities of early devices, and to develop methods for verifying that they behave correctly in a regime where they are difficult to simulate classically. A major potential application of quantum computers is the task of simulating quantum physics. Since it is close to the native behavior of quantum computers, quantum simulation has relatively low overhead, so it is likely to be an early practical application. This project will investigate how to best apply quantum simulation using near-term devices. The project team will develop the theory of quantum simulation algorithms more generally, and will explore using quantum simulation to solve other computational problems, studying challenges including quantum state preparation and solutions of differential equations. A significant challenge for early quantum computers is the difficulty of ensuring that they work correctly. This project will investigate methods for certifying the correctness of quantum computations. Since many quantum computations may not have efficiently checkable proofs, the researchers will consider the more general framework of interactive verification, where a classical verifier seeks to establish the correctness of an efficient quantum prover through an exchange of messages. Building on recent progress toward interactive verification under computational assumptions, the project team will investigate the number of rounds of communication needed to perform such verification, explore the power of circuit obfuscation as a tool for interactive verification, and study the impact of varying the power of the prover and verifier (and the interaction between them) on their ability to ensure correctness. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.