The Space-Time Cost of Purifying Quantum Computations

• URL: http://arxiv.org/abs/2401.07974v1
• Date: Mon, 15 Jan 2024 21:38:02 GMT
• Title: The Space-Time Cost of Purifying Quantum Computations
• Authors: Mark Zhandry
• Abstract summary: General quantum computation consists of unitary operations and also measurements. intermediate quantum measurements can be deferred to the end of the computation, resulting in an equivalent purely unitary computation. We show that any "black-box" transformation which removes intermediate measurements must significantly blow up either space or time.
• Score: 12.640283469603357
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: General quantum computation consists of unitary operations and also measurements. It is well known that intermediate quantum measurements can be deferred to the end of the computation, resulting in an equivalent purely unitary computation. While time efficient, this transformation blows up the space to linear in the running time, which could be super-polynomial for low-space algorithms. Fefferman and Remscrim (STOC'21) and Girish, Raz and Zhan (ICALP'21) show different transformations which are space efficient, but blow up the running time by a factor that is exponential in the space. This leaves the case of algorithms with small-but-super-logarithmic space as incurring a large blowup in either time or space complexity. We show that such a blowup is likely inherent, demonstrating that any "black-box" transformation which removes intermediate measurements must significantly blow up either space or time.

Related papers

• Temporal Entanglement in Chaotic Quantum Circuits [62.997667081978825]
  The concept of space-evolution (or space-time duality) has emerged as a promising approach for studying quantum dynamics. We show that temporal entanglement always follows a volume law in time. This unexpected structure in the temporal entanglement spectrum might be the key to an efficient computational implementation of the space evolution.
  arXiv  Detail & Related papers  (2023-02-16T18:56:05Z)
• 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)
• Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
  The percolation transition is defined through the appearance of the infinite cluster. We show that the exponentially increasing dimensionality of the Hilbert space makes its covering by finite-size hyperspheres inefficient. Our approach to the percolation transition in compact metric spaces may prove useful for its rigorous treatment in other contexts.
  arXiv  Detail & Related papers  (2022-10-15T13:53:21Z)
• Quantum superpositions of Minkowski spacetime [0.0]
  "Spacetime superpositions" are quantum superpositions of different spacetimes not related by a global coordinate transformation. We consider the quantum-gravitational effects produced by superpositions of periodically identified Minkowski spacetime. We show that the detector's response exhibits discontinuous resonances at rational ratios of the superposed periodic length scale.
  arXiv  Detail & Related papers  (2022-08-25T13:31:05Z)
• Space-Bounded Unitary Quantum Computation with Postselection [0.0]
  This paper shows that it is possible to eliminate intermediate postselections and measurements in space-bounded quantum computation with postselection. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation.
  arXiv  Detail & Related papers  (2022-06-30T08:35:33Z)
• Double Quantization [0.0]
  In a quantum gravity theory, it is expected that the classical notion of spacetime disappears, leading to a quantum structure with new properties. There is not a clear way to describe at the same time a noncommutativity of spacetime and the phase-space noncommutativity of quantum mechanics. We apply our construction to the so-called $lambda$-Minkwoski and $mathbbR3_lambda$ noncommutative spaces.
  arXiv  Detail & Related papers  (2021-12-21T18:04:20Z)
• Eliminating Intermediate Measurements using Pseudorandom Generators [1.218340575383456]
  We show that quantum algorithms of time $T$ and space $Sge log T$ can be simulated by quantum algorithms of time $T cdot mathrmpoly (S)$ and space $ O(Scdot log T)$ with unitary operations and without intermediate measurements.
  arXiv  Detail & Related papers  (2021-06-22T15:47:20Z)
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits [58.720142291102135]
  We simulate a noisy quantum Fourier transform processor with up to 21 qubits. We take into account microscopic dissipative processes rather than relying on digital error models. We show that depending on the dissipative mechanisms at play, the choice of input state has a strong impact on the performance of the quantum algorithm.
  arXiv  Detail & Related papers  (2021-02-08T14:55:44Z)
• The role of boundary conditions in quantum computations of scattering observables [58.720142291102135]
  Quantum computing may offer the opportunity to simulate strongly-interacting field theories, such as quantum chromodynamics, with physical time evolution. As with present-day calculations, quantum computation strategies still require the restriction to a finite system size. We quantify the volume effects for various $1+1$D Minkowski-signature quantities and show that these can be a significant source of systematic uncertainty.
  arXiv  Detail & Related papers  (2020-07-01T17:43:11Z)
• Eliminating Intermediate Measurements in Space-Bounded Quantum Computation [0.0]
  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.
  arXiv  Detail & Related papers  (2020-06-05T16:05:49Z)
• Projection evolution and quantum spacetime [68.8204255655161]
  We discuss the problem of time in quantum mechanics. An idea of construction of a quantum spacetime as a special set of the allowed states is presented. An example of a structureless quantum Minkowski-like spacetime is also considered.
  arXiv  Detail & Related papers  (2019-10-24T14:54:11Z)

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.