In the last few years quantum computation has steadily transitioned from theoretical science to reality. Quantum experiments are improving at a dizzying pace and we have arrived at an exciting era in which quantum computational experiments are pushing the boundaries of what is possible on an efficient classical computer. While these experiments are impressive, their power is still fundamentally restricted due to both limited quantum resources (such as small number of qubits and shallow circuit depth) and uncorrected noise that rapidly overwhelms the quantum signal. The goal of this project is both to characterize the computational power of these existing imperfect quantum experiments, and to expedite the next major step for the field: moving from initial “proof of principle†experiments to the ultimate goal of implementing a quantum speedup that solves a useful computational problem. This is a project that straddles quantum theory and experiment and will help narrow the gap between the two fields. Results from this project will be disseminated to a wide variety of scientific communities outside academia, including in government and industry. Moreover, the project will contribute to sustaining and enhancing the recent worldwide explosion of interest in quantum computation by developing new quantum computing courses and creating new summer research opportunities for the next generation of quantum scientists.
The objectives of this project will be achieved through work on two interrelated research goals. The first is to understand the power of random quantum circuits in the presence of experimentally realistic noise models. The focus will be both on proving new classical hardness results that are robust to noise, as well as developing new classical simulation algorithms tailored to noisy random quantum circuits. The second goal will be to develop new quantum algorithms that can be run on near-term quantum experiments which obtain speedups over similarly resource bounded classical computations. This investigation will build upon prior work of the PI which established new space bounded quantum algorithms for solving useful linear algebraic problems such as inverting a matrix, computing a power of a matrix, and solving the determinant.
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.
