Kavli Affiliate: David Gross
| First 5 Authors: Fabian Henze, Viet Tran, Birte Ostermann, Richard Kueng, Timo de Wolff
| Summary:
Quantum computers can solve semidefinite programs (SDPs) using resources that
scale better than state-of-the-art classical methods as a function of the
problem dimension. At the same time, the known quantum algorithms scale very
unfavorably in the precision, which makes it non-trivial to find applications
for which the quantum methods are well-suited. Arguably, precision is less
crucial for SDP relaxations of combinatorial optimization problems (such as the
Goemans-Williamson algorithm), because these include a final rounding step that
maps SDP solutions to binary variables. With this in mind, Brand~ao,
Franc{c}a, and Kueng have proposed to use quantum SDP solvers in order to
achieve an end-to-end speed-up for obtaining approximate solutions to
combinatorial optimization problems. They did indeed succeed in identifying an
algorithm that realizes a polynomial quantum advantage in terms of its
asymptotic running time. However, asymptotic results say little about the
problem sizes for which advantages manifest. Here, we present an analysis of
the non-asymptotic resource requirements of this algorithm. The work consists
of two parts. First, we optimize the original algorithm with a particular
emphasis on performance for realistic problem instances. In particular, we
formulate a version with adaptive step-sizes, an improved detection criterion
for infeasible instances, and a more efficient rounding procedure. In a second
step, we benchmark both the classical and the quantum version of the algorithm.
The benchmarks did not identify a regime where even the optimized quantum
algorithm would beat standard classical approaches for input sizes that can be
realistically solved at all. In the absence of further significant
improvements, these algorithms therefore fall into a category sometimes called
galactic: Unbeaten in their asymptotic scaling behavior, but not practical for
realistic problems.
| Search Query: ArXiv Query: search_query=au:”David Gross”&id_list=&start=0&max_results=3