FolioStart free

Computer Science · Literature

Research papers on Quantum computing algorithms

Recent and highly-cited academic work on quantum computing algorithms, gathered from Semantic Scholar, CrossRef and OpenAlex.

Search all 200M+ papers on this topic, free →Or track new quantum computing algorithms papers automatically as they publish

  1. Exponential algorithmic speedup by a quantum walk

    Andrew M. Childs, Richard Cleve, E. Deotto, et al. · 2003 · ACM Symposium on Theory of Computing (STOC) · 825 citations

    We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

    Save this paper

  2. Quantum speedup of Monte Carlo methods

    Ashley Montanaro · 2015 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 337 citations

    Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous

    Save this paper

  4. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms

    Andris Ambainis, Kaspars Balodis, Jānis Iraids, et al. · 2019 · Society for Industrial and Applied Mathematics eBooks · 74 citations

    In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from 0n to 1n in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time O*(1.817n). The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in

    Save this paper

  5. Quantum-Walk Speedup of Backtracking Algorithms

    Ashley Montanaro · 2018 · Theory of Computing · 71 citations

    $ $ We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on $n$ variables, or outputs that none exists, and whose corresponding tree contains $T$ vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using $O(\sqrt{T} n^{3/2} \log n)

    Save this paper

  6. Parallel Algorithms with Optimal Speedup for Bounded Treewidth

    Hans L. Bodlaender, Torben Hagerup · 1998 · SIAM Journal on Computing · 70 citations

    We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n-vertex input graphs, the algorithm works in O((log n) 2 ) time using O(n) operations on the EREW PRAM. We also give faster parallel algorithms with optimal speedup for the problem of deciding whether the treewidth of an input graph is bounded by a given constant and for a variety of problems on graphs of bounded treewidth, including all decision problems expressible in monadic second-order logic. On n-vertex input graphs, the algorithms use O(n) operations together with O(log n log * n) time on the EREW PRAM, or O(log n) time on the CRCW PRAM.

    Save this paper

  7. Quantum speedup of branch-and-bound algorithms

    Ashley Montanaro · 2020 · Physical Review Research · 66 citations

    Quantum computers could significantly outperform their classical counterparts for solving hard optimization problems. One prominent classical technique for such problems is known as branch-and-bound. This work describes a quantum algorithm for accelerating general branch-and-bound methods, and gives an application to spin glasses.

    Save this paper

  8. Anticoncentration theorems for schemes showing a quantum speedup

    Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, et al. · 2018 · Quantum · 59 citations

    One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes "quantum computational supremacy". The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known s

    Save this paper

  9. Demonstration of Algorithmic Quantum Speedup

    Bibek Pokharel, Daniel A. Lidar · 2023 · Physical Review Letters · 55 citations

    Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant devices has remained elusive. Here, we unequivocally demonstrate such a speedup within the oracular model, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, using two different 27-qubit IBM Quantum superconducting processors. The speedup is observed on only one of the two processors when the quantum computation is protected by

    Save this paper

  10. Enhancing the Performance Prediction of Quantum Computing Algorithms using Gradient Boosting and Ada Boost Regression

    Rajendar Dommeti · 2026 · Journal of Quantum Computing and Advanced Algorithms · 25 citations

    Quantum computing is considered to have tremendous potential to help take the emerging field of "Computational Law" to the next level of growth in terms of the expression and implementation of legal principles. With the promise of quantum technology's increasing influence on the legal industry in mind, this essay utilizes the emerging field of Computational Complexity Theory to explore the types of problems that quantum computing is capable of solving more efficiently than classical computing, which is referred to as Quantum Supremacy. From this foundation, three emerging areas within the legal sector have been identified where quantum computing is likely to show transformative superiority.

    Save this paper

  13. Quantum speedups of some general-purpose numerical optimisation algorithms

    Ashley Montanaro, Noah Linden, Cezar-Mihail Alexandru, et al. · 2020 · Explore Bristol Research · 15 citations

    Abstract We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function <?CDATA $f:{\mathbb{R}}^{n}\to \mathbb{R}$?> f : R n → R . First, we show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder–Mead algorithm can be accelerated by up to a multiplicative factor of <?CDATA $O\left(\sqrt{n}\right)$?> O ( n ) . Fourth, we show that a quantum gradient computation algorithm of Gilyén et al can be used to

    Save this paper

  14. Quantum Speedup Based on Classical Decision Trees

    Salman Beigi, Leila Taghavi · 2020 · Quantum · 15 citations

    Lin and Lin \cite{LL16} have recently shown how starting with a classical query algorithm (decision tree) for a function, we may find upper bounds on its quantum query complexity. More precisely, they have shown that given a decision tree for a function f:{0,1}n→[m] whose input can be accessed via queries to its bits, and a guessing algorithm that predicts answers to the queries, there is a quantum query algorithm for f which makes at most O(GT) quantum queries where T is the depth of the decision tree and G is the maximum number of mistakes of the guessing algorithm. In this paper we give a simple proof of and generalize this result for functions f:[ℓ]n→[m] with non-binary input as well as

    Save this paper

  15. Quantum Algorithms: Overviews, Foundations, and Speedups

    Shuangbao Paul Wang, Eric Sakk · 2021 · 12 citations

    This paper discusses quantum computing with a strong focus on quantum software, quantum networks, quantum simulation, and applications. The study on quantum speedups reveals fundamental differences between quantum algorithms and classical algorithms. As a case study, further improvement on Shor's algorithm is presented with experimental results. The study shows that quantum circuits can be generated automatically to further improve the efficiency of quantum algorithms.

    Save this paper

  17. A Reconfigurable Framework for Hybrid Quantum–Classical Computing

    Pratibha, Naveed Mahmud · 2025 · Algorithms · 10 citations

    Hybrid quantum–classical (HQC) computing refers to the approach of executing algorithms coherently on both quantum and classical resources. This approach makes the best use of current or near-term quantum computers by sharing the workload with classical high-performance computing. However, HQC algorithms often require a back-and-forth exchange of data between quantum and classical processors, causing system bottlenecks and leading to high latency in applications. The objective of this study is to investigate novel frameworks that unify quantum and reconfigurable resources for HQC and mitigate system bottleneck and latency issues. In this paper, we propose a reconfigurable framework for hybri

    Save this paper

  21. Quantum Speedups for Treewidth

    Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs · 2022 · arXiv (Cornell University) · 2 citations

    In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms: - O(1.618ⁿ) time and polynomial space; - O(1.554ⁿ) time and O(1.452ⁿ) space; - O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provid

    Save this paper

  23. Quantum Computing for Bayesian Inference: Algorithms, Speedups, Challenges, and Synergies with Scalable Machine Learning (Vol-III)

    Syed Muntasir Mamun · 2026 · Zenodo (CERN European Organization for Nuclear Research)

    The pursuit of massive foundation models is hindered by the limitations of Maximum Likelihood Estimation (MLE), which struggles with uncertainty quantification and out-of-distribution generalization. The Bayesian framework resolves these deficiencies but is crippled by the "marginalisation bottleneck"—the computational intractability of integrating over high-dimensional parameter spaces. Classical approximations like MCMC and Variational Inference (VI) are fundamentally limited by slow mixing times or sub-optimal local minima. Quantum computing offers a paradigm-shifting resolution, leveraging superposition and entanglement to execute high-dimensional integrals with theoretical exponential s

    Save this paper

  24. Quantum Decoding Algorithms: Quantum Speedups in Optimization

    Jan Ljubas, Tim Byrnes · 2026 · arXiv (Cornell University)

    Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection

    Save this paper

Write your paper with these sources

Folio is the integrity-first research workspace: search 200M+ papers, save sources, and write with citations that format themselves. Free for students and researchers.

Start writing free →