For many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overlooks significant overheads due to error correction and the fact that real-world instances often contain exploitable structure. In this work, we employ the hybrid benchmarking method to evaluate the potential of quantum Backtracking and Grover's algorithm against the 2023 SAT competition main track winner in solving random k -SAT instances with tunable structure, designed to represent industry-like scenarios, using both T -depth and T -count as cost metrics to estimate quantum run times. Our findings reproduce the results of Campbell, Khurana, and Montanaro (Quantum '19) in the unstructured case using hybrid benchmarking. However, we offer a more sobering perspective in practically relevant regimes: almost all quantum speedups vanish, even asymptotically, when minimal structure is introduced or when T -count is considered instead of T -depth. Moreover, when the requirement is for the algorithm to find a solution within a single day, we find that only Grover's algorithm has the potential to outperform classical algorithms, but only in a very limited regime and only when using T -depth. We also discuss how more sophisticated heuristics could restore the asymptotic scaling advantage for quantum backtracking, but our findings suggest that the potential for practical quantum speedups in more structured k -SAT solving will remain limited.
For many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overlooks significant overheads due to error correction and the fact that real-world instances often contain exploitable structure. In this work, we employ the hybrid benchmarking method to evaluate the potential of quantum Backtracking and Grover's algorithm against the 2023 SAT competition main track winner in solving random k -SAT instances with tunable structure, designed to represent industry-like scenarios, using both T -depth and T -count as cost metrics to estimate quantum run times. Our findings reproduce the results of Campbell, Khurana, and Montanaro (Quantum '19) in the unstructured case using hybrid benchmarking. However, we offer a more sobering perspective in practically relevant regimes: almost all quantum speedups vanish, even asymptotically, when minimal structure is introduced or when T -count is considered instead of T -depth. Moreover, when the requirement is for the algorithm to find a solution within a single day, we find that only Grover's algorithm has the potential to outperform classical algorithms, but only in a very limited regime and only when using T -depth. We also discuss how more sophisticated heuristics could restore the asymptotic scaling advantage for quantum backtracking, but our findings suggest that the potential for practical quantum speedups in more structured k -SAT solving will remain limited.
Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We simulate quantum algorithms by running classical versions of the sub-routines, whilst simultaneously collecting information about what the run-time of the quantum routine would have been if it were run instead. To do this accurately and efficiently for very large input sizes, we describe an estimation procedure and prove that it obtains upper bounds on the true expected complexity of the quantum algorithms.We apply our method to some simple quantum speedups of classical heuristic algorithms for solving the well-studied MAX- k -SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines: Grover search with an unknown number of marked items, and quantum maximum-finding. These improve upon existing results and might be of broader interest.Amongst other results, we found that the classical heuristic algorithms we studied did not offer significant quantum speedups despite the existence of a theoretical per-step speedup. This suggests that an empirical analysis such as the one we implement in this paper already yields insights beyond those that can be seen by an asymptotic analysis alone.
Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this thesis, we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible. We first give a general overview of the quantum (sub)routines that serve as building blocks for more advanced algorithms, as well as of the three hybrid benchmarking techniques used throughout this thesis. Then, we elaborate on each method: we start with the algorithmic descriptions, proceed to the methodology, and conclude with their hybrid evaluation on practically relevant datasets. Within the hybrid benchmarking method 1 (gate count analysis), we analytically derive the minimum number of gates that a quantum version of the classical simplex algorithm would require to solve realistic instances. By executing classical counterparts of the quantum subroutines, we infer the execution speed required per gate for the quantum simplex to outperform its classical counterpart. Within the hybrid benchmarking method 2 (query count analysis), we benchmark functional quantum linear solvers by analytically deriving a precise number of query calls made to the same oracles as a function of problem parameters. This provides insight into which algorithm might be more suitable in a given parameter regime. It allows for a direct comparison only between different quantum algorithms and is independent of classical runtime measurements. Within the hybrid benchmarking method 3 (cycle count analysis), we develop a runtime estimation framework tailored to the quantum tree generator–based search for solving 0-1-knapsack problems. We evaluate its performance on large scale instances beyond the reach of general simulation. We compare it with state-of-the-art classical linear programming solvers in terms of processor cycle counts. Hybrid benchmarking provides a fair, systematic benchmarking methodology, ensuring reproducible and relevant comparisons not only between classical and quantum approaches, but also among different quantum algorithms.
Many search-based quantum algorithms that achieve a theoretical speedup are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts.This raises the question of how to divide computational tasks into a collection of parallelizable sub-problems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the k-SAT problem. Our analysis is based on Schöning's algorithm, which solves instances of k-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for "natural" partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.
Quantum algorithms with super-polynomial or polynomial speedups have been central to the promise of quantum computing, yet their real-world impact remains unclear because most analyses are asymptotic and worst-case. This work develops a systematic framework for characterizing practical quantum advantage that explicitly separates three components of speedup: (i) oracle/algorithmic advantage (Salg), (ii) data/instance structure advantage (Sdata), and (iii) implementability advantage under realistic noise and resource constraints (S impl). We first formalize quantum speedup as a triple (Salg, Sdata, S impl) that jointly captures theoretical complexity, distribution of input instances, and hardware feasibility. We then analyze seven canonical algorithms-Grover search, amplitude estimation, phase estimation, HHL, VQE, QAOA, and Hamiltonian simulationand extract common structural patterns that lead to genuine advantage over classical algorithms for specific problem families. Building on these patterns, we derive sufficient and necessary conditions for average-case quantum advantage in terms of problem symmetries, spectral properties, and data-access models. For NISQ-era devices, we incorporate realistic noise models and compilation overheads to define a practical advantage region in the space of problem size, error rates, and algorithm depth. The framework yields decision procedures and flowcharts that, given a candidate problem and hardware profile, can certify whether a proposed quantum algorithm is likely to achieve practical advantage or not. Case studies in finance (Monte Carlo risk analysis), chemistry (electronic structure estimation), and optimization (QAOA-type problems) illustrate how our method can guide algorithm and hardware co-design, and also show negative results where no advantage is achievable under realistic constraints. This work turns "quantum advantage" from a vague narrative into a quantitatively testable property of algorithmproblem-hardware triples.
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.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024