Eliminating intermediate measurements in space-bounded Quantum computation
From MaRDI portal
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.
Cited in
(8)- Quantum circuits with classical channels and the principle of deferred measurements
- scientific article; zbMATH DE number 6820203 (Why is no real title available?)
- The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs
- The computational advantage of MIP* vanishes in the presence of noise
- The computational advantage of MIP* vanishes in the presence of noise
- The space-time cost of purifying quantum computations
- Quantum catalytic space
- Short and useful quantum proofs for sublogarithmic-space verifiers
This page was built for publication: Eliminating intermediate measurements in space-bounded Quantum computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065258)
