Constraint-Oriented Biased Quantum Search
Sören Wilkening · Institutional Repository of Leibniz Universität Hannover (Leibniz Universität Hannover) · 2026
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.