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.

1. QUANTUM ESPRESSO: a modular and open-source software project for quantum simulations of materials

   Paolo Giannozzi, Stefano Baroni, Nicola Bonini, et al. · 2009 · Journal of Physics Condensed Matter · 28,958 citations

   QUANTUM ESPRESSO is an integrated suite of computer codes for electronic-structure calculations and materials modeling, based on density-functional theory, plane waves, and pseudopotentials (norm-conserving, ultrasoft, and projector-augmented wave). The acronym ESPRESSO stands for opEn Source Package for Research in Electronic Structure, Simulation, and Optimization. It is freely available to researchers around the world under the terms of the GNU General Public License. QUANTUM ESPRESSO builds upon newly-restructured electronic-structure codes that have been developed and tested by some of the original authors of novel electronic-structure algorithms and applied in the last twenty years by

2. Quantum Computing in the NISQ era and beyond

   John Preskill · 2018 · Quantum · 8,371 citations

   Noisy Intermediate-Scale Quantum (NISQ) technology will be available in the near future. Quantum computers with 50-100 qubits may be able to perform tasks which surpass the capabilities of today's classical digital computers, but noise in quantum gates will limit the size of quantum circuits that can be executed reliably. NISQ devices will be useful tools for exploring many-body quantum physics, and may have other useful applications, but the 100-qubit quantum computer will not change the world right away - we should regard it as a significant step toward the more powerful quantum technologies of the future. Quantum technologists should continue to strive for more accurate quantum gates and,

3. Quantum supremacy using a programmable superconducting processor

   Frank Arute, Kunal Arya, Ryan Babbush, et al. · 2019 · Nature · 7,056 citations

   The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor1. A fundamental challenge is to build a high-fidelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits2–7 to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 253 (about 1016). Measurements from repeated experiments sample the resulting probability distribution, which we verify using classical simulations. Our Sycamore processor takes about 200 seconds to sample one i

4. A variational eigenvalue solver on a photonic quantum processor

   Alberto Peruzzo, Jarrod R. McClean, Peter Shadbolt, et al. · 2014 · Nature Communications · 4,634 citations

   Quantum computers promise to efficiently solve important problems that are intractable on a conventional computer. For quantum systems, where the physical dimension grows exponentially, finding the eigenvalues of certain operators is one such intractable problem and remains a fundamental challenge. The quantum phase estimation algorithm efficiently finds the eigenvalue of a given eigenvector but requires fully coherent evolution. Here we present an alternative approach that greatly reduces the requirements for coherent evolution and combine this method with a new approach to state preparation based on ansätze and classical optimization. We implement the algorithm by combining a highly reconf

5. Quantum Machine Learning: Algorithms and Applications in Quantum Computing

   P. Deshmukh, Benjamin Carter · 2025 · International Journal on Advanced Electrical and Computer Engineering · 4,537 citations

   Quantum Machine Learning (QML) is an emerging interdisciplinary field that integrates quantum computing with classical machine learning techniques to enhance computational efficiency and solve complex problems beyond the capabilities of classical systems. This paper explores fundamental QML algorithms, including quantum-enhanced data processing, quantum neural networks, and quantum support vector machines. We discuss how quantum speedup can be achieved through quantum parallelism and entanglement, leading to improvements in optimization and data classification tasks. Additionally, we highlight applications of QML in areas such as drug discovery, financial modeling, and cryptography. While cu

6. Quantum Algorithm for Linear Systems of Equations

   Aram W. Harrow, Avinatan Hassidim, Seth Lloyd · 2009 · Physical Review Letters · 3,319 citations

   Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix $A$ and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensurema

7. Variational quantum algorithms

   M. Cerezo, Andrew Arrasmith, Ryan Babbush, et al. · 2021 · Nature Reviews Physics · 3,051 citations

8. Noisy intermediate-scale quantum algorithms

   Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, et al. · 2022 · Reviews of Modern Physics · 1,685 citations

   Noisy quantum computers can in principle perform reliable quantum computations, but truly scalable systems require noise levels lower than are presently achieved. Still, moderate-complexity computations can be performed. This review discusses what is possible in this ``noisy intermediate scale'' quantum (NISQ) era. Topic areas include the simulation of many-body physics and chemistry, combinatorial optimization, and machine learning. It is evident that the NISQ era has produced new paradigms for programming that will be built upon as quantum computers are further perfected.

9. Quantum algorithms: an overview

   Ashley Montanaro · 2016 · npj Quantum Information · 1,056 citations

   Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.

10. Exponential algorithmic speedup by a quantum walk

    Andrew M. Childs, Richard Cleve, E. Deotto, et al. · 2003 · 833 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.

11. Demonstration of Blind Quantum Computing

    Stefanie Barz, Elham Kashefi, Anne Broadbent, et al. · 2012 · Science · 475 citations

    Quantum computers, besides offering substantial computational speedups, are also expected to preserve the privacy of a computation. We present an experimental demonstration of blind quantum computing in which the input, computation, and output all remain unknown to the computer. We exploit the conceptual framework of measurement-based quantum computation that enables a client to delegate a computation to a quantum server. Various blind delegated computations, including one- and two-qubit gates and the Deutsch and Grover quantum algorithms, are demonstrated. The client only needs to be able to prepare and transmit individual photonic qubits. Our demonstration is crucial for unconditionally se

12. Quantum speedup of Monte Carlo methods

    Ashley Montanaro · 2015 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 339 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

13. Quantum computing for finance

    Dylan Herman, Cody Googin, Xiaoyuan Liu, et al. · 2023 · Nature Reviews Physics · 264 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

14. Parallel Algorithms with Optimal Speedup for Bounded Treewidth

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

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

    F. Valdez, P. Melin · 2022 · Soft Computing · 45 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

16. Measures of quantum computing speedup

    Anargyros Papageorgiou, Joseph F. Traub · 2013 · Physical Review A · 20 citations

17. Speedup in adiabatic evolution based quantum algorithms

    Jie Sun, SongFeng Lu, Fang Liu · 2012 · Science China Physics, Mechanics and Astronomy · 19 citations

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

    Pau Escofet, Alejandro Gonzalvo, Eduard Alarcón, et al. · 2024 · 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) · 16 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

19. 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, Zimu 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

20. Quantum Speedup Based on Classical Decision Trees

    Salman Beigi, Leila Taghavi · 2020 · Quantum · 14 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

21. 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 · 14 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.

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

    Aurora Maurizio, G. Mazzola · 2025 · 11 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

23. Nanowires: Exponential speedup in quantum computing

    Mariam Akter Mimona, Md. Hosne Mobarak, Emtiuz Ahmed, et al. · 2024 · Heliyon · 10 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

24. No Exponential Quantum Speedup for SIS∞ Anymore

    Robin Kothari, Ryan O'Donnell, Kewen Wu · 2025 · Proceedings of the 58th Annual ACM Symposium on Theory of Computing · 10 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.