Folio Search · free preview

Papers on “quantum computing algorithms speedup”

Live results from Semantic Scholar, CrossRef and OpenAlex. No account needed to look.

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 cites

   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 to my library →

2. Quantum speedup of Monte Carlo methods

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

   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 to my library →

3. Quantum computing for finance

   Dylan Herman, Cody Googin, Xiao-Yuan Liu, et al. · 2023 · Nature Reviews Physics · 300 cites

   Quantum computers are expected to surpass classical computers and transform industries. This Review focuses on quantum computing for financial applications and provides a summary for physicists on potential advantages and limitations of quantum techniques, as well as challenges that physicists could help tackle. Quantum algorithms for stochastic modelling, optimization and machine learning are applicable to various financial problems. Quantum Monte Carlo integration and gradient estimation can provide quadratic speedup over classical methods, but more work is required to reduce the amount of quantum resources for early fault-tolerant feasibility and achieving an actual speedup. Financial opt

   Save to my library →

4. Quantum Computing

   Péter Wittek · 2014 · Elsevier eBooks · 97 cites

   Save to my library →

5. 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 cites

   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 to my library →

6. Quantum-Walk Speedup of Backtracking Algorithms

   Ashley Montanaro · 2018 · Theory of Computing · 71 cites

   $ $ 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 to my library →

7. Parallel Algorithms with Optimal Speedup for Bounded Treewidth

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

   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 to my library →

8. Quantum speedup of branch-and-bound algorithms

   Ashley Montanaro · 2020 · Physical Review Research · 66 cites

   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 to my library →