Runtime–Coherence Tradeoffs for Hybrid Satisfiability Solvers
Open Access
- 22 April 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-22
Abstract
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Computational Speedups Using Small Quantum DevicesPhysical Review Letters, 2018
- Quantum search algorithmsACM SIGACT News, 2004
- A probabilistic algorithm for k-SAT and constraint satisfaction problems2003
- Elements of Information Theory2001
- A fast quantum mechanical algorithm for database search1996