Reserach Topic Area 6.2: Complexity-theoretic Foundations for Near-term Quantum Computers
Abstract
The major goals of this project were to pursue a reformulation of computational complexity theory in terms of sampling problems and to use this framework to better characterize the computational power of quantum information processing devices, particularly near-term small-scale quantum computing hardware. Certain problems, such as integer factorization, appear to be exponentially hard for classical computers but solvable in polynomial time on quantum computers. However, there is no proof that classical computers cannot also factor integers in polynomial time. It could be that we just haven t discovered the right classical algorithm yet. Furthermore, even granting that factoring is classically hard, it remains a less than ideal problem for demonstrating the separation in power between quantum and classical computers because the quantum computers needed to run Shor s factoring algorithm are very large and probably fairly far in the future. Recently, it was realized that separations between the power of quantum and classical computers which are both more rigorous and more applicable to near-term quantum hardware can be obtained by considering sampling problems instead of traditional decision problems. That is, the goal of the problem is to sample from some particular probability distribution. In this project, our goal is to build out the complexity theory of sampling and identify specific quantum systems, ideally ones realizable with present-day or near-term laboratory technology, which can efficiently sample from probability distributions that classical computers cannot. A secondary goal of this project was to use the problem of matrix inversion to characterize the complexity of resource limited quantum circuits. Such circuits are quite relevant to present day quantum computer prototypes. We are particularly interested in the power of quantum computers with restricted time (gate count), space (qubits), or depth. In such devices the entire computation must be completed in less than the decoherence time of the individual qubits. Thus the decoherence time divided by the gate time is the maximum depth of quantum circuit that can be executed on such a device. In prior work, we had shown that the matrix inversion problem completely characterizes quantum space complexity. In other words, the matrix inversion problem is the hardest problem solvable by quantum computers with a bound only on the number of qubits (ignoring the number of quantum gates). While this is of theoretical interest, in any realistic experiment we will also have a bounded amount of time. In very recent unpublished work, we have extended this prior work to show that, in fact, we can completely characterize the power of quantum computation with simultaneously restricted time bound and space bound using a suitably parameterized matrix inversion problem.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 11, 2018
- Source ID
- W911NF1710025
Entities
People
- Stephen Jordan
Organizations
- Army Contracting Command
- United States Army
- University of Maryland