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

arXiv:2512.05205

Constraint-oriented biased quantum search for linear constrained combinatorial optimization problems

Sören Wilkening, Timo Ziegler, Maximilian Hess

quant-phSubmitted Dec 4, 2025• Announced Dec 8, 2025• 0 citations
arXivHTMLPDF

Abstract

In this paper, we extend a previously presented Grover-based heuristic to tackle general combinatorial optimization problems with linear constraints. We further describe the introduced method as a framework that enables performance improvements through circuit optimization and machine learning techniques. Comparisons with state-of-the-art classical solvers further demonstrate the algorithm's potential to achieve a quantum advantage in terms of speed, given appropriate quantum hardware.

Comments
13 pages, 7 figures

Related papers

Constraint-oriented biased quantum search for general constrained combinatorial optimization problems

Sören Wilkening

We present a quantum algorithmic routine that extends the realm of Grover-based heuristics for tackling combinatorial optimization problems with arbitrary efficiently computable objective and constraint functions. Building on previously developed quantum methods that were primarily restricted to linear constraints, we generalize the approach to encompass a broader class of problems in discrete domains. To evaluate the potential of our algorithm, we assume the existence of sufficiently advanced logical quantum hardware. With this assumption, we demonstrate that our method has the potential to outperform state-of-the-art classical solvers and heuristics in terms of both runtime scaling and solution quality. The same may be true for more realistic implementations, as the logical quantum algorithm can achieve runtime savings of up to $10^2-10^3$.

quant-pharXiv:2512.08384•Dec 10, 2025•0 citations

Constraint-Oriented Biased Quantum Search

Sören Wilkening

Quantum computing is a rapidly growing field, promising computational advancements with significant impact on real-world and industrial applications. These areas include cryptography, financial systems, material and drug discovery. They also cover combinatorial optimization, which is the focus of this thesis. For combinatorial optimization problems, researchers have spent several decades extending the capabilities of quantum algorithms for both near-term and far-term quantum hardware. Because current devices comprise too few qubits (quantum bits) and noisy gates (qubit operations prone to errors), potential quantum advantage must be assessed using theoretical and numerical frameworks. Despite the existence of many quantum algorithms, such as Grover’s algorithm and Quantum Branch-and-Bound (QB&B), which provide asymptotic speedups, we lack evidence of a practical quantum speedup on realistic problem instances. Recent benchmarking efforts show that several far-term algorithms with asymptotic advantage still cannot achieve practical quantum advantage under realistic conditions. This thesis comprises three advancements. First, it develops a new type of state preparation tailored to constraint optimization problems. This enables a Grover-based heuristic we call Constraint-oriented biased quantum search (CBQS). Second, it introduces benchmarking methods that compare the quantum search with state-of-the-art classical algorithms on large instances. These methods indicate that the proposed quantum algorithm can achieve a practical quantum advantage. For some cases, logical gate times of just 10−6s with about 19,000 logical qubits are enough to match classical runtime. Third, it presents a quantum circuit backend (software that processes quantum circuits) designed for speed at the cost of suboptimal circuit design. This backend outperforms a wide range of existing software packages in both speed and memory consumption, demonstrated by Quantum Fourier Transformation (QFT) circuits of up to 2000 qubits. Overall, this work points the way toward full-stack quantum advantage while underscoring the need for further research on topics such as quantum error correction.

•Jan 1, 2026•0 citations

Quantum-Inspired Fast Algorithm and Circuit Realization for Constrained Combinatorial Optimization Problem

Haosen Chen, Shailan Deng, Tian Chen +1 more

Constrained combinatorial optimization (CCO) problems are prevalent across various fields and represent key challenges in computational science and engineering. Although numerous classical and quantum algorithms have been proposed to tackle these problems, substantial limitations still persist. Classical algorithms exhibit exponential computational complexity growth with scale and persistent vulnerability to local minima traps. Quantum computing, while offering theoretical advantages through global superposition, faces practical barriers such as short decoherence times and current hardware limitations. To address these challenges, we propose a quantum-inspired fast algorithm for solving CCO problems. Our approach enhances global search capability with superposition encoding and avoids constraint-induced local minima​​ via a project-feedback strategy. Particularly, our method aligns with mature electronics manufacturing and demonstrates a proof-of-concept implementation in classical systems, indicating high-efficiency potential for solving constrained optimization problems.

Research•Jan 1, 2026•0 citations

Quantum Optimization Algorithms for Industrial Problems

Maximilian Nikolaus Hess

The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.

•Jan 1, 2026•0 citations

Quantum constraint learning for quantum approximate optimization algorithm

Santosh Kumar Radha

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm that offers the potential to handle combinatorial optimization problems. Introducing constraints in such combinatorial optimization problems poses a significant challenge in the extensions of QAOA to support relevant larger-scale problems. This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. We show that this method can be used for encoding any general form of constraints. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. This procedure gives the flexibility to control the depth of the circuit at the cost of the accuracy of enforcing the constraint, thus having immediate application in the Noisy Intermediate Scale Quantum (NISQ) era. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints. Finally, using this metric, we evaluate the performance of the proposed algorithm.

arXiv:2105.06770•May 14, 2021•4 citations

Quantum-enhanced greedy combinatorial optimization solver

Maxime Dupont, Bram Evert, Mark J. Hodson +13 more

Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster their performance. Here, we introduce an iterative quantum heuristic optimization algorithm to solve combinatorial optimization problems. The quantum algorithm reduces to a classical greedy algorithm in the presence of strong noise. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement. Moreover, we observe an absolute performance comparable with a state-of-the-art semidefinite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics.

arXiv:2303.05509•Science Advances•Nov 10, 2023•41 citations
In this paper, we extend a previously presented Grover-based heuristic to tackle general combinatorial optimization problems with linear constraints. We further describe the introduced method as a framework that enables performance improvements through circuit optimization and machine learning techniques. Comparisons with state-of-the-art classical solvers further demonstrate the algorithm's potential to achieve a quantum advantage in terms of speed, given appropriate quantum hardware.
We present a quantum algorithmic routine that extends the realm of Grover-based heuristics for tackling combinatorial optimization problems with arbitrary efficiently computable objective and constraint functions. Building on previously developed quantum methods that were primarily restricted to linear constraints, we generalize the approach to encompass a broader class of problems in discrete domains. To evaluate the potential of our algorithm, we assume the existence of sufficiently advanced logical quantum hardware. With this assumption, we demonstrate that our method has the potential to outperform state-of-the-art classical solvers and heuristics in terms of both runtime scaling and solution quality. The same may be true for more realistic implementations, as the logical quantum algorithm can achieve runtime savings of up to 102−10310^2-10^3102−103.
Quantum computing is a rapidly growing field, promising computational advancements with significant impact on real-world and industrial applications. These areas include cryptography, financial systems, material and drug discovery. They also cover combinatorial optimization, which is the focus of this thesis. For combinatorial optimization problems, researchers have spent several decades extending the capabilities of quantum algorithms for both near-term and far-term quantum hardware. Because current devices comprise too few qubits (quantum bits) and noisy gates (qubit operations prone to errors), potential quantum advantage must be assessed using theoretical and numerical frameworks. Despite the existence of many quantum algorithms, such as Grover’s algorithm and Quantum Branch-and-Bound (QB&B), which provide asymptotic speedups, we lack evidence of a practical quantum speedup on realistic problem instances. Recent benchmarking efforts show that several far-term algorithms with asymptotic advantage still cannot achieve practical quantum advantage under realistic conditions. This thesis comprises three advancements. First, it develops a new type of state preparation tailored to constraint optimization problems. This enables a Grover-based heuristic we call Constraint-oriented biased quantum search (CBQS). Second, it introduces benchmarking methods that compare the quantum search with state-of-the-art classical algorithms on large instances. These methods indicate that the proposed quantum algorithm can achieve a practical quantum advantage. For some cases, logical gate times of just 10−6s with about 19,000 logical qubits are enough to match classical runtime. Third, it presents a quantum circuit backend (software that processes quantum circuits) designed for speed at the cost of suboptimal circuit design. This backend outperforms a wide range of existing software packages in both speed and memory consumption, demonstrated by Quantum Fourier Transformation (QFT) circuits of up to 2000 qubits. Overall, this work points the way toward full-stack quantum advantage while underscoring the need for further research on topics such as quantum error correction.
Constrained combinatorial optimization (CCO) problems are prevalent across various fields and represent key challenges in computational science and engineering. Although numerous classical and quantum algorithms have been proposed to tackle these problems, substantial limitations still persist. Classical algorithms exhibit exponential computational complexity growth with scale and persistent vulnerability to local minima traps. Quantum computing, while offering theoretical advantages through global superposition, faces practical barriers such as short decoherence times and current hardware limitations. To address these challenges, we propose a quantum-inspired fast algorithm for solving CCO problems. Our approach enhances global search capability with superposition encoding and avoids constraint-induced local minima​​ via a project-feedback strategy. Particularly, our method aligns with mature electronics manufacturing and demonstrates a proof-of-concept implementation in classical systems, indicating high-efficiency potential for solving constrained optimization problems.
The semiconductor supply chain gives rise to many complex, large and heavily constrained combinatorial optimization problems. We derive simpler problems from these complex formulations and analyze quantum algorithms for their solution. We study two main regimes: variational algorithms derived from the Quantum Approximate Optimization Algorithm (QAOA) and quantum search algorithms based on Grover’s search algorithm and Amplitude Amplification. In the first case, the main challenge lies in integrating problem constraints into the QAOA framework, which was originally devised for unconstrained problems such as MaxCut. The canonical method of adding penalty terms to the objective leads to an undesirable inflation of the energy spectrum. Instead, we examine alternative problem encodings as well as constraint-preserving mixing operators, which are designed to limit the quantum algorithm to the subspace of feasible states. We make explicit suggestions for a wide selection of problems. In the second case, we operate under the premise that any quantum search protocol for combinatorial optimization must use tailored initial states– otherwise the square root speedup of quantum search is not enough to offset the exponential size of the search space in a combinatorial optimization problem. Consequently, we examine state preparation routines for a wide range or problems. The main devices lie in preparing superpositions of only feasible states and superpositions which are centered around a reference solution. We present a benchmarking technique, in an exact and an approximate version, which allows us to generate performance metrics for our algorithms based on quantum search. We use the benchmarking tools to carry out numerical studies for a selection of problems. We conclude that our variational methods tailored to constrained problems while technically sound– lead to deep quantum circuits which are not suitable for the NISQ machines which QAOA was originally developed for. Our conclusion for optimization algorithms based on quantum search is more optimisitic. Their compatability with classical optimization principles, such as neighborhood search, gives rise to promising further research directions. Advanced benchmarking techniques allow us to test these algorithms independently of quantum hardware developments.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm that offers the potential to handle combinatorial optimization problems. Introducing constraints in such combinatorial optimization problems poses a significant challenge in the extensions of QAOA to support relevant larger-scale problems. This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. We show that this method can be used for encoding any general form of constraints. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. This procedure gives the flexibility to control the depth of the circuit at the cost of the accuracy of enforcing the constraint, thus having immediate application in the Noisy Intermediate Scale Quantum (NISQ) era. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints. Finally, using this metric, we evaluate the performance of the proposed algorithm.
Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster their performance. Here, we introduce an iterative quantum heuristic optimization algorithm to solve combinatorial optimization problems. The quantum algorithm reduces to a classical greedy algorithm in the presence of strong noise. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement. Moreover, we observe an absolute performance comparable with a state-of-the-art semidefinite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics.