Kavli Affiliate: David Gross
| First 5 Authors: Sabrina Ammann, Maximilian Hess, Debora Ramacciotti, Sándor P. Fekete, Paulina L. A. Goedicke
| Summary:
In recent years, strong expectations have been raised for the possible power
of quantum computing for solving difficult optimization problems, based on
theoretical, asymptotic worst-case bounds. Can we expect this to have
consequences for Linear and Integer Programming when solving instances of
practically relevant size, a fundamental goal of Mathematical Programming,
Operations Research and Algorithm Engineering? Answering this question faces a
crucial impediment: The lack of sufficiently large quantum platforms prevents
performing real-world tests for comparison with classical methods.
In this paper, we present a quantum analog for classical runtime analysis
when solving real-world instances of important optimization problems. To this
end, we measure the expected practical performance of quantum computers by
analyzing the expected gate complexity of a quantum algorithm. The lack of
practical quantum platforms for experimental comparison is addressed by hybrid
benchmarking, in which the algorithm is performed on a classical system,
logging the expected cost of the various subroutines that are employed by the
quantum versions. In particular, we provide an analysis of quantum methods for
Linear Programming, for which recent work has provided asymptotic speedup
through quantum subroutines for the Simplex method. We show that a practical
quantum advantage for realistic problem sizes would require quantum gate
operation times that are considerably below current physical limitations.
| Search Query: ArXiv Query: search_query=au:”David Gross”&id_list=&start=0&max_results=3