Kavli Affiliate: David Gross
| First 5 Authors: Vahideh Eshaghian, Sören Wilkening, Johan Åberg, David Gross,
| Summary:
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"oning’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.
| Search Query: ArXiv Query: search_query=au:”David Gross”&id_list=&start=0&max_results=3