Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

• URL: http://arxiv.org/abs/2006.03530v2
• Date: Wed, 3 Mar 2021 21:18:02 GMT
• Title: Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
• Authors: Bill Fefferman (University of Chicago), Zachary Remscrim (University of Chicago)
• Abstract summary: We show that it is possible to defer measurements to the end of a quantum computation without increasing the number of ancillary qubits. A key component of our approach 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Efficient inference of quantum system parameters by Approximate Bayesian Computation [0.0]
  We propose the Approximate Bayesian Computation (ABC) algorithm, which evades likelihood by sampling from a library of measurement data. We apply ABC to interpret photodetection click-patterns arising when probing in real time a two-level atom and an optomechanical system. Our work demonstrates that fast parameter inference may be possible no matter the complexity of a quantum device and the measurement scheme involved.
  arXiv  Detail & Related papers  (2024-06-30T15:10:05Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer. The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
  arXiv  Detail & Related papers  (2024-03-25T15:47:35Z)
• Instantaneous nonlocal quantum computation and circuit depth reduction [7.148511452018054]
  Two-party quantum computation is a computation process with bipartite input and output, in which there are initial shared entanglement. In the first part, we show that a particular simplified subprocedure, known as a garden-hose gadget, cannot significantly reduce the entanglement cost. In the second part, we show that any unitary circuit consisting of layers of Clifford gates and T gates can be implemented using a circuit with measurements of depth proportional to the T-depth of the original circuit.
  arXiv  Detail & Related papers  (2023-06-15T17:57:50Z)
• Sample-size-reduction of quantum states for the noisy linear problem [0.0]
  We show that it is possible to reduce a quantum sample size in a quantum random access memory (QRAM) to the linearithmic order. We achieve a shorter run-time for the noisy linear problem.
  arXiv  Detail & Related papers  (2023-01-08T05:53:17Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.