Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 3101222 |
| Seitenumfang | 22 |
| Fachzeitschrift | IEEE Transactions on Quantum Engineering |
| Jahrgang | 6 |
| Publikationsstatus | Veröffentlicht - 22 Apr. 2025 |
Abstract
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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
- Informatik (insg.)
- Informatik (sonstige)
- Physik und Astronomie (insg.)
- Physik der kondensierten Materie
- Ingenieurwesen (insg.)
- Ingenieurwesen (sonstige)
- Ingenieurwesen (insg.)
- Maschinenbau
- Informatik (insg.)
- Angewandte Informatik
- Ingenieurwesen (insg.)
- Elektrotechnik und Elektronik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: IEEE Transactions on Quantum Engineering, Jahrgang 6, 3101222, 22.04.2025.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review
}
TY - JOUR
T1 - Runtime–Coherence Tradeoffs for Hybrid Satisfiability Solvers
AU - Eshaghian, Vahideh
AU - Wilkening, Sören
AU - Åberg, Johan
AU - Gross, David
N1 - Publisher Copyright: © 2020 IEEE.
PY - 2025/4/22
Y1 - 2025/4/22
N2 - 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.
AB - 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.
KW - Coherence time
KW - quantum algorithm
KW - quantum search
KW - runtime
KW - satisfiability problem
UR - http://www.scopus.com/inward/record.url?scp=105003692013&partnerID=8YFLogxK
U2 - 10.1109/TQE.2025.3563805
DO - 10.1109/TQE.2025.3563805
M3 - Article
AN - SCOPUS:105003692013
VL - 6
JO - IEEE Transactions on Quantum Engineering
JF - IEEE Transactions on Quantum Engineering
M1 - 3101222
ER -