Space-Efficient Quantum Error Reduction without log Factors

• URL: http://arxiv.org/abs/2502.09249v1
• Date: Thu, 13 Feb 2025 12:04:39 GMT
• Title: Space-Efficient Quantum Error Reduction without log Factors
• Authors: Aleksandrs Belovs, Stacey Jeffery,
• Abstract summary: We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
• Score: 50.10645865330582
• License:
• Abstract: Given an algorithm that outputs the correct answer with bounded error, say $1/3$, it is sometimes desirable to reduce this error to some arbitrarily small $\varepsilon$ -- for example, if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is a procedure called majority voting, which incurs a multiplicative overhead of $O(\log\frac{1}{\varepsilon})$ from calling the algorithm this many times. A recent paper introduced a model of quantum computation called \emph{transducers}, and showed how to reduce the ``error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called \emph{purification}. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors. In this paper, we present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. In addition to providing a new perspective that is easier to contrast with majority voting, our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified. Our new purifier has nearly optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.

Related papers

• Composing Quantum Algorithms [0.59829224684009]
  It has long been known that zero-error quantum algorithms emphdo not compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In this article, aimed at a general computer science audience, we try to give some intuition for these results.
  arXiv  Detail & Related papers  (2025-02-13T11:56:35Z)
• Fault-Tolerant Implementation of the Deutsch-Jozsa Algorithm [0.46040036610482665]
  The Deutsch-Josza algorithm is a natural candidate for small fault-tolerance experiments. We implement the algorithm on a trapped-ion quantum computer with and without fault-tolerant encoding. Averaged across all oracles, the reduction in error rate was nearly $90 %$.
  arXiv  Detail & Related papers  (2024-12-06T05:55:31Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two principled algorithms for the test-time compute of large language models. We prove theoretically that the failure probability of one algorithm decays to zero exponentially as its test-time compute grows.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• A simple quantum algorithm to efficiently prepare sparse states [0.0]
  We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. This is competitive with the best known algorithms for sparse state preparation.
  arXiv  Detail & Related papers  (2023-10-30T07:05:15Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing. Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutsch's algorithm is the first quantum algorithm to show the advantage over the classical algorithm. We propose a new quantum algorithm with indefinite causal order to solve this problem.
  arXiv  Detail & Related papers  (2023-05-09T13:04:28Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$. These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
  arXiv  Detail & Related papers  (2022-05-11T14:29:39Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)

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.