Universität zu Köln

Eshaghian, Vahideh ORCID: 0009-0002-6021-1486, Wilkening, Sören, Åberg, Johan ORCID: 0000-0002-2573-476X and Gross, David ORCID: 0000-0001-8888-3028 (2025). Runtime–Coherence Tradeoffs for Hybrid Satisfiability Solvers. IEEE Transactions on Quantum Engineering, 6. pp. 1-22. IEEE Transactions on Quantum Engineering. ISSN 2689-1808

PDF RuntimeCoherence_Tradeoffs_for_Hybrid_Satisfiability_Solvers.pdf Bereitstellung unter der CC-Lizenz: Creative Commons Attribution. Download (967kB)

Abstract

[Artikel-Nr. 3101222] 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 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-satisfiability problem (k-SAT). 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 tradeoff 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 tradeoff. Finally, we present numerical simulations, which suggest additional flexibility in implementing hybrid algorithms with the optimal tradeoff.

Item Type:	Article
Creators:	Creators Email ORCID ORCID Put Code Eshaghian, Vahideh UNSPECIFIED https://orcid.org/0009-0002-6021-1486 UNSPECIFIED Wilkening, Sören UNSPECIFIED UNSPECIFIED UNSPECIFIED Åberg, Johan UNSPECIFIED https://orcid.org/0000-0002-2573-476X UNSPECIFIED Gross, David UNSPECIFIED https://orcid.org/0000-0001-8888-3028 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-798343
Identification Number:	10.1109/TQE.2025.3563805
Journal or Publication Title:	IEEE Transactions on Quantum Engineering
Volume:	6
Page Range:	pp. 1-22
Number of Pages:	22
Date:	22 April 2025
Publisher:	IEEE Transactions on Quantum Engineering
ISSN:	2689-1808
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Physics > Institute for Theoretical Physics
Subjects:	Physics
Uncontrolled Keywords:	Keywords Language Coherence time ; quantum algorithm ; quantum search ; runtime ; satisfiability problem English
['eprint_fieldname_oa_funders' not defined]:	Publikationsfonds UzK
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/79834