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

Laser Physics

A full-quantum algorithm for solving the exact cover problem via quantum gradient descent iteration

Jingyu Huo, Ling Fan, Ru Zhang, Cong Cao

Published Mar 20, 2026• 1 citation
Publisher

Abstract

Abstract Combinatorial optimization problems are pervasive across various real-world industries, yet solving them remains classically intractable due to their nondeterministic polynomial (NP)-hard nature. This paper presents an iterative quantum algorithm based on full quantum gradient descent (QGD) to solve the exact cover problem, a fundamental NP-complete problem serving as a representative scenario of airline tail assignment. We formulate the practical optimization task into a set partitioning framework and subsequently map it onto the ground-state search of an Ising Hamiltonian. By employing a QGD-driven iterative mechanism, the proposed algorithm can evolve the initial state in a quantum register towards a high-fidelity approximation of the Ising ground state within only a few iterations. Numerical simulations validate the algorithm’s effectiveness across various problem scales, encompassing both sparsely and nearly fully connected graph configurations. Results demonstrate that the algorithm achieves high precision with a relatively few number of iterative steps. Compared to existing approaches, this work bypasses complex classical optimization loops and requires significantly less pre-computation overhead, thereby offering a promising and scalable pathway for solving combinatorial optimization problems on future universal quantum computing platforms.

DOI
10.1088/1555-6611/ae5047

Related papers

A Universal Quantum Gradient Descent Framework for Exact Cover Problems

Jingyu Huo, Ru Zhang, Cong Cao

Combinatorial optimization problems are foundational in computational science, yet their NP-complete nature renders them classically intractable as problem scales increase. Many such problems can be successfully mapped onto the ground-state search of an Ising Hamiltonian. In this work, we propose a full-quantum iterative algorithm based on the quantum gradient descent (QGD) framework, implemented via the linear combination of unitaries, to solve the standard exact cover problem. By reformulating discrete logical constraints into a quadratic unconstrained binary optimization model, the algorithm evolves an initial uniform superposition state directly within the Hilbert space toward the ground-state subspace. Numerical simulations on instances ranging from different qubits demonstrate that the algorithm achieves high-fidelity convergence with a logarithmic scaling of iteration depth relative to solution precision. Notably, our results reveal that the QGD framework effectively preserves the symmetry of the solution space, allowing for the simultaneous identification of the entire set of optimal results in the presence of ground-state degeneracy. By bypassing complex classical-quantum optimization loops and the associated barren plateau problem, this work provides a robust and scalable full-quantum pathway for resolving high-dimensional logic constraints on future universal quantum computing platforms.

International Conference on Advanced Electronic Materials, Computers and Software Engineering (AEMCSE)•Mar 20, 2026•0 citations

Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent

Xin Yi, Jingyu Huo, Yong‐Pan Gao +3 more

Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.

Results in Physics•Nov 20, 2023•17 citations

Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem

Pontus Vikstål, Mattias Grönkvist, Marika Svensson +3 more

Airlines today are faced with a number of large-scale scheduling problems. One such problem is the tail-assignment problem, which is the task of assigning individual aircraft to a given set of flights, minimizing the overall cost. Each aircraft is identified by the registration number on its tail fin. In this paper, we simulate the quantum approximate optimization algorithm (QAOA) applied to instances of this problem derived from real-world data. The QAOA is a variational hybrid quantum-classical algorithm recently introduced and likely to run on near-term quantum devices. The instances are reduced to fit on quantum devices with 8, 15, and 25 qubits. The reduction procedure leaves only one feasible solution per instance, which allows us to map the tail-assignment problem onto the exact-cover problem. We find that repeated runs of the QAOA identify the feasible solution with close to unit probability for all instances. Furthermore, we observe patterns in the variational parameters such that an interpolation strategy can be employed, which significantly simplifies the classical optimization part of the QAOA. Finally, we empirically find a relation between the connectivity of the problem graph and the single-shot success probability of the algorithm.

arXiv:1912.10499•Physical Review Applied•Sep 3, 2020•96 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

A universal quantum algorithm for weighted maximum cut and Ising problems

Natacha Kuete Meli, Florian Mannel, Jan Lellmann

Abstract We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary combinatorial problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system. The system is enforced to evolve toward the ground state of the problem Hamiltonian by optimizing a set of angles using normalized gradient descent. Experimentally, our algorithm outperforms the state-of-the-art quantum approximate optimization algorithm on random fully connected graphs and challenges D-Wave quantum annealers by producing good approximate solutions. Source code and data files are publicly available ( https://github.com/nkuetemeli/UQMaxCutAndIsing ).

arXiv:2306.06539•Quantum Information Processing•Jul 11, 2023•4 citations

Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms

Young-Hyun Oh, Hamed Mohammadbagherpoor, Patrick Dreher +3 more

The design of a good algorithm to solve NP-hard combinatorial approximation problems requires specific domain knowledge about the problems and often needs a trial-and-error problem solving approach. Graph coloring is one of the essential fields to provide an efficient solution for combinatorial applications such as flight scheduling, frequency allocation in networking, and register allocation. In particular, some optimization algorithms have been proposed to solve the multi-coloring graph problems but most of the cases a simple searching method would be the best approach to find an optimal solution for graph coloring problems. However, this naive approach can increase the computation cost exponentially as the graph size and the number of colors increase. To mitigate such intolerable overhead, we investigate the methods to take the advantages of quantum computing properties to find a solution for multi-coloring graph problems in polynomial time. We utilize the variational quantum eigensolver (VQE) technique and quantum approximate optimization algorithm (QAOA) to find solutions for three combinatorial applications by both transferring each problem model to the corresponding Ising model and by using the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA algorithms can find one of the best solutions for each application. Therefore, our modeling approach with hybrid quantum algorithms can be applicable for combinatorial problems in various fields to find an optimal solution in polynomial time.

arXiv:1911.00595•Nov 1, 2019•12 citations
Abstract Combinatorial optimization problems are pervasive across various real-world industries, yet solving them remains classically intractable due to their nondeterministic polynomial (NP)-hard nature. This paper presents an iterative quantum algorithm based on full quantum gradient descent (QGD) to solve the exact cover problem, a fundamental NP-complete problem serving as a representative scenario of airline tail assignment. We formulate the practical optimization task into a set partitioning framework and subsequently map it onto the ground-state search of an Ising Hamiltonian. By employing a QGD-driven iterative mechanism, the proposed algorithm can evolve the initial state in a quantum register towards a high-fidelity approximation of the Ising ground state within only a few iterations. Numerical simulations validate the algorithm’s effectiveness across various problem scales, encompassing both sparsely and nearly fully connected graph configurations. Results demonstrate that the algorithm achieves high precision with a relatively few number of iterative steps. Compared to existing approaches, this work bypasses complex classical optimization loops and requires significantly less pre-computation overhead, thereby offering a promising and scalable pathway for solving combinatorial optimization problems on future universal quantum computing platforms.
Combinatorial optimization problems are foundational in computational science, yet their NP-complete nature renders them classically intractable as problem scales increase. Many such problems can be successfully mapped onto the ground-state search of an Ising Hamiltonian. In this work, we propose a full-quantum iterative algorithm based on the quantum gradient descent (QGD) framework, implemented via the linear combination of unitaries, to solve the standard exact cover problem. By reformulating discrete logical constraints into a quadratic unconstrained binary optimization model, the algorithm evolves an initial uniform superposition state directly within the Hilbert space toward the ground-state subspace. Numerical simulations on instances ranging from different qubits demonstrate that the algorithm achieves high-fidelity convergence with a logarithmic scaling of iteration depth relative to solution precision. Notably, our results reveal that the QGD framework effectively preserves the symmetry of the solution space, allowing for the simultaneous identification of the entire set of optimal results in the presence of ground-state degeneracy. By bypassing complex classical-quantum optimization loops and the associated barren plateau problem, this work provides a robust and scalable full-quantum pathway for resolving high-dimensional logic constraints on future universal quantum computing platforms.
Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.
Airlines today are faced with a number of large-scale scheduling problems. One such problem is the tail-assignment problem, which is the task of assigning individual aircraft to a given set of flights, minimizing the overall cost. Each aircraft is identified by the registration number on its tail fin. In this paper, we simulate the quantum approximate optimization algorithm (QAOA) applied to instances of this problem derived from real-world data. The QAOA is a variational hybrid quantum-classical algorithm recently introduced and likely to run on near-term quantum devices. The instances are reduced to fit on quantum devices with 8, 15, and 25 qubits. The reduction procedure leaves only one feasible solution per instance, which allows us to map the tail-assignment problem onto the exact-cover problem. We find that repeated runs of the QAOA identify the feasible solution with close to unit probability for all instances. Furthermore, we observe patterns in the variational parameters such that an interpolation strategy can be employed, which significantly simplifies the classical optimization part of the QAOA. Finally, we empirically find a relation between the connectivity of the problem graph and the single-shot success probability of the algorithm.
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.
Abstract We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary combinatorial problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system. The system is enforced to evolve toward the ground state of the problem Hamiltonian by optimizing a set of angles using normalized gradient descent. Experimentally, our algorithm outperforms the state-of-the-art quantum approximate optimization algorithm on random fully connected graphs and challenges D-Wave quantum annealers by producing good approximate solutions. Source code and data files are publicly available ( https://github.com/nkuetemeli/UQMaxCutAndIsing ).
The design of a good algorithm to solve NP-hard combinatorial approximation problems requires specific domain knowledge about the problems and often needs a trial-and-error problem solving approach. Graph coloring is one of the essential fields to provide an efficient solution for combinatorial applications such as flight scheduling, frequency allocation in networking, and register allocation. In particular, some optimization algorithms have been proposed to solve the multi-coloring graph problems but most of the cases a simple searching method would be the best approach to find an optimal solution for graph coloring problems. However, this naive approach can increase the computation cost exponentially as the graph size and the number of colors increase. To mitigate such intolerable overhead, we investigate the methods to take the advantages of quantum computing properties to find a solution for multi-coloring graph problems in polynomial time. We utilize the variational quantum eigensolver (VQE) technique and quantum approximate optimization algorithm (QAOA) to find solutions for three combinatorial applications by both transferring each problem model to the corresponding Ising model and by using the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA algorithms can find one of the best solutions for each application. Therefore, our modeling approach with hybrid quantum algorithms can be applicable for combinatorial problems in various fields to find an optimal solution in polynomial time.