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.
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.
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.
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.
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.
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.
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.
Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.