Many search-based quantum algorithms that achieve a theoretical speed-up 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 subproblems, 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.
Many search-based quantum algorithms that achieve a theoretical speed-up 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 subproblems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for thek-SAT problem. Our analysis is based on Schöning's algorithm, which solves instances ofk-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.
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.
The Boolean satisfiability problem (SAT) is of central importance in both theory and practice. Yet, most provable guarantees for quantum algorithms rely exclusively on Grover-type methods that cap the possible advantage at only quadratic speed-ups, making the search for approaches that surpass this quadratic barrier a key challenge. In this light, this work presents a rigorous worst-case runtime analysis of a recently introduced measurement-driven quantum SAT solver. Importantly, this quantum algorithm does not exclusively rely on Grover-type methods and shows promising numerical performance. Our analysis establishes that the algorithm's runtime depends on an exponential trade-off between two key properties: the spectral gap of the associated Hamiltonian and the success probability of the driving measurements. We show that this trade-off can be systematically controlled by a tunable rotation angle. Beyond establishing a worst-case runtime expression, this work contributes significant algorithmic improvements. First, we develop a new readout routine that efficiently finds a solution even for instances with multiple satisfying assignments. Second, a measurement parallelization scheme, based on perfect hash families, is introduced. Third, we establish an amplitude-amplified version of the measurement-driven algorithm. Finally, we demonstrate the practical utility of our framework: By suitably scheduling the algorithm's parameters, we show that its runtime collapses from exponential to polynomial on a special class of SAT instances, consistent with their known classical tractability. A problem we leave open is to establish a non-trivial lower bound on the spectral gap as a function of the rotation angle. Resolving this directly translates into an improved worst-case runtime, potentially realizing a super-quadratic quantum advantage.
This thesis presents two main projects focused on hybrid quantum search algorithms. The first, Particle-Guided Grover's Search, applies Bayesian inference to quantum search when the number of solutions is a priori unknown. It begins with a prior distribution that encodes our initial "beliefs" about the true number of solutions in the search space, and recursively updates these beliefs using Bayesian inference. Measurement outcomes of the quantum search that do not yield a solution are interpreted as "evidence", guiding the Bayesian update to determine the optimal number of Grover iterations for subsequent rounds. This approach leverages Particle Filtering -- a Bayesian filtering technique -- to avoid explicitly storing the entire prior distribution at each step. Instead of requiring O(N) memory, the method draws a set of "particles" from the prior and updates their associated weights as quantum search failures accumulate. Particle filtering also offers the advantage of incorporating information from all past failures, rather than only the most recent one. The algorithm's performance is benchmarked against a prior work. The second project, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, is focused on a class of hybrid k-SAT solvers. These solvers are based on a well-known random walk technique called Schoening's algorithm, which uses two sources of randomness to perform a local search over the space of all assignments for a k-SAT problem. In this project, we assume that these sources of randomness are encoded into a long bitstring, allowing the random walk to be interpreted as a deterministic function mapping each bitstring to either 0 or 1, depending on whether the walk successfully finds a satisfying assignment. This functional perspective enables us to pose the question: Given a bound on the coherence time of a quantum computer, which portion of the bitstring should we search coherently, and which portion should be left to classical search? We address this question by introducing a family of hybrid algorithms called "partial Groverizations", which strategically combine quantum and classical resources. We analyze the runtime performance of this family as a function of the available quantum coherence time. The results of this work have been published in IEEE Transactions on Quantum Engineering.
The k-SAT problem is a canonical NP-complete problem for which no efficient algorithm is known. This paper proposes a hybrid quantum–classical algorithm that employs Grover's algorithm as the inner local search of a randomized outer loop. Each outer iteration measures a random assignment, prepares a problem-dependent superposition over the Hamming ball of radius r around it, and applies amplitude amplification to locate a satisfying assignment. Because the ball center is measured, the outer loop remains a classical repetition over independently sampled balls and contributes the inverse success probability rather than its square root; balancing this against the inner quadratic speedup shifts the optimal radius from n/(k+1) to n/(1+k) and yields the running time (2−2/(1+k))n, up to polynomial factors—1.268n for k=3, below the best known classical 1.307n. The contribution is not an asymptotic record—the best known quantum exponents for k-SAT, obtained by amplifying stronger classical solvers as black boxes, remain smaller—but a fully explicit, gate-level construction: the problem-dependent state over the Hamming ball and the k-SAT oracle are decomposed into elementary quantum gates, and the polynomial gate and qubit overheads are accounted for in full.
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.
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.