Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
arXiv:2006.03530 · doi:10.1145/3406325.3451051
Abstract
A foundational result in the theory of quantum computation known as the "principle of safe storage" shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that it does not introduce a large overhead in the number of gates, it uses extra ancillary qubits and so is not generally space efficient. It is quite natural to ask whether it is possible to defer measurements to the end of a quantum computation without increasing the number of ancillary qubits. We give an affirmative answer to this question by exhibiting a procedure to eliminate all intermediate measurements that is simultaneously space-efficient and time-efficient. A key component of our approach, which may be of independent interest, involves showing that the well-conditioned versions of many standard linear-algebraic problems may be solved by a quantum computer in less space than seems possible by a classical computer.
arXiv commentMinor tweaks to correspond to published version, to appear in STOC 2021
References in corpus (7)
- The Physical Implementation of Quantum Computation
- Strengths and Weaknesses of Quantum Computing
- On the relationship between continuous- and discrete-time quantum walk
- Exponential improvement in precision for simulating sparse Hamiltonians
- Matchgate and space-bounded quantum computations are equivalent
- Entropic trade-off relations for quantum operations
- Classically-Controlled Quantum Computation