Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-088 | 9th June 2020 00:19

Eliminating Intermediate Measurements in Space-Bounded Quantum Computation


Authors: Bill Fefferman, Zachary Remscrim
Publication: 9th June 2020 00:24
Downloads: 402


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.

ISSN 1433-8092 | Imprint