Related papers: Composing Quantum Algorithms

Composing Quantum Algorithms

URL: http://arxiv.org/abs/2502.09240v1
Date: Thu, 13 Feb 2025 11:56:35 GMT
Title: Composing Quantum Algorithms
Authors: Stacey Jeffery,
Abstract summary: 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.
Score: 0.59829224684009
License:
Abstract: Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing ``efficient'' algorithms should result in an ``efficient'' algorithm -- even using this intuition to justify our definition of ``efficient.'' Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms \emph{do not} compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. In this article, aimed at a general computer science audience, we try to give some intuition for these results: why composing quantum algorithms is tricky, particularly in the zero-error setting, but why it nonetheless works \emph{better} than classical composition in the bounded-error setting.

Related papers

Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
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.
arXiv Detail & Related papers (2025-02-13T12:04:39Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z)
Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
We propose a quantum algorithm for integer multiplication with time complexity $O(sqrtnlog2 n)$. Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.
arXiv Detail & Related papers (2023-06-14T12:40:54Z)
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)
Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
This work revisits quantum algorithms for the well-known welded tree problem. It proposes a very succinct quantum algorithm based on the simplest coined quantum walks.
arXiv Detail & Related papers (2023-04-17T16:03:50Z)
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)
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)
Quantum Inspired Adaptive Boosting [0.0]
We show that the quantum ensemble method does not have advantage over classical algorithms. We propose methods inspired by combining the quantum ensemble method with adaptive boosting. The algorithms were tested and found to be comparable to the AdaBoost algorithm on publicly available data sets.
arXiv Detail & Related papers (2021-02-01T16:33:14Z)

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