Space-Bounded Unitary Quantum Computation with Postselection

• URL: http://arxiv.org/abs/2206.15122v2
• Date: Tue, 13 Sep 2022 06:02:54 GMT
• Title: Space-Bounded Unitary Quantum Computation with Postselection
• Authors: Seiichiro Tani
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. 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, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.

Related papers

• The Space-Time Cost of Purifying Quantum Computations [12.640283469603357]
  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.
  arXiv  Detail & Related papers  (2024-01-15T21:38:02Z)
• 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)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Quantum Logarithmic Space and Post-selection [0.4588028371034406]
  Post-selection is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005) Our main result shows the identity $sf PostBQL=$, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection ($sf PostBQL$) We also show that $sf$ coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.
  arXiv  Detail & Related papers  (2021-05-06T14:02:01Z)
• Sampling and the complexity of nature [0.0]
  I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. I shed light on how and under which conditions quantum sampling devices can be tested or verified. An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths.
  arXiv  Detail & Related papers  (2020-12-14T19:35:27Z)
• Quantum advantage for computations with limited space [6.327095331866255]
  We consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$- by quantum circuits, leveraging custom two-qubit gates.
  arXiv  Detail & Related papers  (2020-08-14T17:31:12Z)
• 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)

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.