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. Quantum computing for finance

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

    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 this paper

  2. 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

  3. 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

  4. A review on quantum computing and deep learning algorithms and their applications

    F. Valdez, P. Melin · 2022 · Soft Computing · 48 citations

    In this paper, we describe a review concerning the Quantum Computing (QC) and Deep Learning (DL) areas and their applications in Computational Intelligence (CI). Quantum algorithms (QAs), engage the rules of quantum mechanics to solve problems using quantum information, where the quantum information is concerning the state of a quantum system, which can be manipulated using quantum information algorithms and other processing techniques. Nowadays, many QAs have been proposed, whose general conclusion is that using the effects of quantum mechanics results in a significant speedup (exponential, polynomial, super polynomial) over the traditional algorithms. This implies that some complex problem

    Save this paper

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

  7. Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures

    Pau Escofet, Alejandro Gonzalvo, E. Alarcón, et al. · 2024 · 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) · 20 citations

    Quantum computers are expected to scale in size to close the gap that currently exists between quantum algorithms and quantum hardware. To this end, quantum compilation techniques must scale along with the hardware constraints, shifting the current paradigm of obtaining an optimal compilation to relying on heuristics that allow for a fast solution, even though the quality of such a solution may not be optimal. Significant concerns arise as the execution time of current mapping techniques experiences a notable increase when applied to quantum computers with a high number of qubits. In this work, we present Route-Forcing, a quantum circuit mapping algorithm that shows a compilation time averag

    Save this paper

  9. Quantum computing for genomics: conceptual challenges and practical perspectives

    Aurora Maurizio, G. Mazzola · 2025 · 17 citations

    We assess the potential of quantum computing to accelerate computation of central tasks in genomics, focusing on often-neglected theoretical limitations. We discuss state-of-the-art challenges of quantum search, optimization, and machine learning algorithms. Examining database search with Grover's algorithm, we show that the expected speedup vanishes under realistic assumptions. For combinatorial optimization prevalent in genomics, we discuss the limitations of theoretical complexity in practice and suggest carefully identifying problems genuinely suited for quantum acceleration. Given the competition from excellent classical approximate solvers, quantum computing could offer a speedup in th

    Save this paper

  10. 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

  11. Toward superpolynomial quantum speedup of equivariant quantum algorithms with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>SU</mml:mi> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi>

    Han Zheng, Zi-Mu Li, Sergii Strelchuk, et al. · 2022 · Physical Review A · 14 citations

    We introduce a framework of the equivariant convolutional quantum algorithms which is tailored for a number of machine-learning tasks on physical systems with arbitrary SU$(d)$ symmetries. It allows us to enhance a natural model of quantum computation -- permutational quantum computing (PQC) -- and define a more powerful model: PQC+. While PQC was shown to be efficiently classically simulatable, we exhibit a problem which can be efficiently solved on PQC+ machine, whereas no classical polynomial time algorithm is known; thus providing evidence against PQC+ being classically simulatable. We further discuss practical quantum machine learning algorithms which can be carried out in the paradigm

    Save this paper

  12. Nanowires: Exponential speedup in quantum computing

    Mariam Akter Mimona, Md. Hosne Mobarak, Emtiuz Ahmed, et al. · 2024 · Heliyon · 13 citations

    This review paper examines the crucial role of nanowires in the field of quantum computing, highlighting their importance as versatile platforms for qubits and vital building blocks for creating fault-tolerant and scalable quantum information processing systems. Researchers are studying many categories of nanowires, including semiconductor, superconducting, and topological nanowires, to explore their distinct quantum features that play a role in creating various qubit designs. The paper explores the interdisciplinary character of quantum computing, combining the fields of quantum physics and materials science. This text highlights the significance of quantum gate operations in manipulating q

    Save this paper

  13. No Exponential Quantum Speedup for SIS∞ Anymore

    Robin Kothari, Ryan O'Donnell, Ke-Wen Wu · 2025 · Proceedings of the 58th Annual ACM Symposium on Theory of Computing · 12 citations

    In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ℓ∞-Short Integer Solution (SIS∞) problem, in a parameter range outside the normal range of cryptographic interest, but still with no known efficient classical algorithm. This was particularly exciting since SIS∞ is a simple problem without structure, and their algorithmic techniques were different from those used in prior exponential quantum speedups. We present efficient classical algorithms for all of the SIS∞ and (more general) Constrained Integer Solution problems studied in their paper, showing there is no exponential quantum speedup anymore.

    Save this paper

  14. (Sub)Exponential Quantum Speedup for Optimization

    Jia-Qi Leng, Ke-Wen Wu, Xiao-Di Wu, et al. · 2025 · ArXiv · 10 citations

    We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization. Our result builds on the Gily\'en--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing. With a sequence of perturbative reductions, we compile their construction into two standalone objective functions, whose oracles can be directly leveraged by the plain adiabatic evolution and Schr\"odinger operator evolution for discrete and continuous optimization, respectively

    Save this paper

  15. 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

  16. Quantum speedup for nonreversible Markov chains

    Baptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché · 2025 · Nature Communications · 8 citations

    Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study constructs Markov chain reversibilizations and develops qua

    Save this paper

  17. A Gentle Introduction to Quantum Computing Algorithms with Applications to Universal Prediction

    Elliot Catt, Marcus Hutter · 2020 · ArXiv · 7 citations

    In this technical report we give an elementary introduction to Quantum Computing for non-physicists. In this introduction we describe in detail some of the foundational Quantum Algorithms including: the Deutsch-Jozsa Algorithm, Shor's Algorithm, Grocer Search, and Quantum Counting Algorithm and briefly the Harrow-Lloyd Algorithm. Additionally we give an introduction to Solomonoff Induction, a theoretically optimal method for prediction. We then attempt to use Quantum computing to find better algorithms for the approximation of Solomonoff Induction. This is done by using techniques from other Quantum computing algorithms to achieve a speedup in computing the speed prior, which is an approxima

    Save this paper

  18. Discovery of Quantum Algorithms Using Genetic Algorithms: Exponential Speedup via Random Sampling

    Tariq Almuqbil, Muhamad Felemban · 2024 · 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) · 5 citations

    The integration of classical machine learning with quantum computing is a promising frontier for solving complex problems more efficiently. This study focuses on discovering oracle-based quantum algorithms, specifically quantum search algorithms like Grover's algorithm, using genetic algorithms (GAs). By leveraging random sampling of oracle combinations, our method reduces the evaluation time complexity from $\mathrm{O}(2^{\mathrm{n}})$ to O(n), enabling the efficient optimization of larger n-qubit circuits. The fitness evaluation of quantum circuits was based on a reduced number of random oracle combinations, significantly speeding up the process while maintaining optimization effectiveness

    Save this paper

  19. QUASIM: Quantum Computing Enhanced Service Ecosystem for Simulation in Manufacturing

    Wolfgang Maass, Ankit Agrawal, Alessandro Ciani, et al. · 2024 · KI - Künstliche Intelligenz · 5 citations

    Quantum computing (QC) and machine learning (ML), taken individually or combined into quantum-assisted ML (QML), are ascending computing paradigms whose calculations come with huge potential for speedup, increase in precision, and resource reductions. Likely improvements for numerical simulations in engineering imply the possibility of a strong economic impact on the manufacturing industry. In this project report, we propose a framework for a quantum computing-enhanced service ecosystem for simulation in manufacturing, consisting of various layers ranging from hardware to algorithms to service and organizational layers. In addition, we give insight into the current state of the art of applic

    Save this paper

  20. Quantum computing applications, challenges, and prospects in financial portfolio optimization

    Omoshola S. Owolabi, Prince C. Uche, Nathaniel T. Adeniken, et al. · 2024 · World Journal of Advanced Research and Reviews · 5 citations

    Quantum computing has the potential to improve financial portfolio optimization by addressing scalability and computational complexity issues. This article explores the application of quantum algorithms to portfolio optimization. It begins by discussing the limitations of classical optimization methods and introduces the basics of quantum computing. Two key quantum algorithms, quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA), are presented in detail. These algorithms are applied to solve the Quadratic Unconstrained Binary Optimization (QUBO) formulation of the portfolio optimization problem. The article provides a high-level quantum algorithm, along with its pseudo

    Save this paper

  24. Quantum Speedup for Hypergraph Sparsification

    Cheng-Hua Liu, Minbo Gao, Zheng-Feng Ji, et al. · 2025 · ArXiv · 3 citations

    Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph sparsification, addressing an open problem proposed by Apers and de Wolf (FOCS'20). For a weighted hypergraph with $n$ vertices, $m$ hyperedges, and rank $r$, our algorithm outputs a near-linear size $\varepsilon$-spectral sparsifier in time $\widetilde O(r\sqrt{mn}/\varepsilon)$. This algorithm matches the quantum lower

    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 →