Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

MDPI eBooks

Quantum Computing Algorithms and Computational Complexity

Pelayo, Fernando L., Mezzini, Mauro

Published Oct 10, 2023• 1 citation
Publisher

Abstract

This reprint is mainly concerned with quantum algorithms, their mathematics from behind and the complexity issues arising from them. It comprises seven papers: Two of them are focused on improving the performance by means of quantum algorithms over the best instances of classical ones: A Fast Quantum Image Component Labeling Algorithm [1] by Yan Li, Dapeng Hao, Yang Xu and Kinkeung Lai. Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator [2] by Kamil Khadiev, Artem Ilikaev and Jevgenijs Vihrovs. Another four papers deal with enhanced quantum algorithms: Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation: [3] by Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay and Jacob Biamonte. Quantum Weighted Fractional Fourier Transform [4] by Tieyu Zhao, Tianyu Yang and Yingying Chi. On the Amplitude Amplification of Quantum States Corresponding to the Solutions of the Partition Problem [5] by Mauro Mezzini, Jose J. Paulet, Fernando Cuartero, Hernan I. Cruz and Fernando L. Pelayo. On the Complexity of Finding the Maximum Entropy Compatible Quantum State [6] by Serena Di Giorgio and Paulo Mateus. Last, but not least, one paper researched a classical operational research problem by means of quantum annealing: GPS: A New TSP Formulation for Its Generalizations Type QUBO [7] by Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou. As Guest Editors, we would like to thank the authors and reviewers who made this possible by promoting, spreading research on and supporting quantum computing.

DOI
10.3390/books978-3-0365-7747-0

Related papers

The travelling salesperson problem and the challenges of near-term quantum advantage

Kate Smith‐Miles, Holger H. Hoos, Hao Wang +2 more

Abstract Over the last two decades, the travelling salesperson problem (TSP) has been cited as a benchmark problem to demonstrate the advantage of quantum computers over conventional computers. Its advantage is that it is a well-studied NP-hard optimisation problem that can be easily communicated to highlight the challenges of searching through an exponentially growing number of possible solutions to find the optimal solution. It is therefore a tempting problem to choose to explore quantum advantage. At what point, however, is a call made that quantum advantage is not likely, and efforts should be focused on other problems? This article challenges the continued use of the TSP as a benchmark for quantum optimisation methods—such as quantum annealing and gate-based quantum computing—that require the TSP to be formulated as a quadratic unconstrained binary optimisation (QUBO) problem. We offer explanations for why such quantum approaches are not well suited, nor competitive against state-of-the-art classical methods, for tackling the challenges of the TSP landscape, and we draw parallels with similar observations made almost four decades ago when QUBO-based neural networks proved to be uncompetitive for solving the TSP. After critically reviewing two decades of research effort to solve TSPs using QUBO-based quantum methods, we note a gradual shift in focus: from initial attempts to solve small sized TSPs with general-purpose QUBO-based quantum approaches, to growing evidence that competitiveness is only enhanced where TSP domain knowledge is integrated, via either modified formulations or hybridisation with TSP classical heuristics. We discuss the numerous challenges that must be overcome before QUBO-based quantum optimisers could ever be competitive with classical state-of-the-art TSP solvers. Acknowledging that there may be more promise for non-QUBO-based hybrid approaches, where quantum search accelerates components of conventional algorithms, we offer recommendations for how future studies should be conducted to compare fairly and rigorously any proposed quantum methods against state-of-the-art TSP solvers, or any classical optimisation method, when seeking to establish quantum advantage.

Quantum Science and Technology•May 8, 2025•13 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

Quantum Algorithms: A Survey of Applications and End-to-end Complexities

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.

arXiv:2310.03011•Oct 4, 2023•318 citations

Quantum Optimization for Airline Itinerary and Scheduling: A QUBO and QAOA Approach

Vaibhav V. Khedekar

Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.

•Apr 22, 2025•0 citations

An introduction to quantum annealing and review of QUBO models for Vehicle Routing Problem

Michał Jaroszczuk

Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 18, 2025•2 citations

Introduction to quantum algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.

Proceedings of symposia in applied mathematics•Jan 1, 2002•56 citations
This reprint is mainly concerned with quantum algorithms, their mathematics from behind and the complexity issues arising from them. It comprises seven papers: Two of them are focused on improving the performance by means of quantum algorithms over the best instances of classical ones: A Fast Quantum Image Component Labeling Algorithm [1] by Yan Li, Dapeng Hao, Yang Xu and Kinkeung Lai. Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator [2] by Kamil Khadiev, Artem Ilikaev and Jevgenijs Vihrovs. Another four papers deal with enhanced quantum algorithms: Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation: [3] by Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay and Jacob Biamonte. Quantum Weighted Fractional Fourier Transform [4] by Tieyu Zhao, Tianyu Yang and Yingying Chi. On the Amplitude Amplification of Quantum States Corresponding to the Solutions of the Partition Problem [5] by Mauro Mezzini, Jose J. Paulet, Fernando Cuartero, Hernan I. Cruz and Fernando L. Pelayo. On the Complexity of Finding the Maximum Entropy Compatible Quantum State [6] by Serena Di Giorgio and Paulo Mateus. Last, but not least, one paper researched a classical operational research problem by means of quantum annealing: GPS: A New TSP Formulation for Its Generalizations Type QUBO [7] by Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou. As Guest Editors, we would like to thank the authors and reviewers who made this possible by promoting, spreading research on and supporting quantum computing.
Abstract Over the last two decades, the travelling salesperson problem (TSP) has been cited as a benchmark problem to demonstrate the advantage of quantum computers over conventional computers. Its advantage is that it is a well-studied NP-hard optimisation problem that can be easily communicated to highlight the challenges of searching through an exponentially growing number of possible solutions to find the optimal solution. It is therefore a tempting problem to choose to explore quantum advantage. At what point, however, is a call made that quantum advantage is not likely, and efforts should be focused on other problems? This article challenges the continued use of the TSP as a benchmark for quantum optimisation methods—such as quantum annealing and gate-based quantum computing—that require the TSP to be formulated as a quadratic unconstrained binary optimisation (QUBO) problem. We offer explanations for why such quantum approaches are not well suited, nor competitive against state-of-the-art classical methods, for tackling the challenges of the TSP landscape, and we draw parallels with similar observations made almost four decades ago when QUBO-based neural networks proved to be uncompetitive for solving the TSP. After critically reviewing two decades of research effort to solve TSPs using QUBO-based quantum methods, we note a gradual shift in focus: from initial attempts to solve small sized TSPs with general-purpose QUBO-based quantum approaches, to growing evidence that competitiveness is only enhanced where TSP domain knowledge is integrated, via either modified formulations or hybridisation with TSP classical heuristics. We discuss the numerous challenges that must be overcome before QUBO-based quantum optimisers could ever be competitive with classical state-of-the-art TSP solvers. Acknowledging that there may be more promise for non-QUBO-based hybrid approaches, where quantum search accelerates components of conventional algorithms, we offer recommendations for how future studies should be conducted to compare fairly and rigorously any proposed quantum methods against state-of-the-art TSP solvers, or any classical optimisation method, when seeking to establish quantum advantage.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.
These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.