Details
| Original language | English |
|---|---|
| Number of pages | 39 |
| Publication status | E-pub ahead of print - 16 Nov 2023 |
Abstract
Keywords
- quant-ph, cs.DS, math.OC
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
2023.
Research output: Working paper/Preprint › Preprint
}
TY - UNPB
T1 - Realistic Runtime Analysis for Quantum Simplex Computation
AU - Ammann, Sabrina
AU - Fekete, Sándor P.
AU - Goedicke, Paulina L. A.
AU - Gross, David
AU - Hess, Maximilian
AU - Lefterovici, Andreea
AU - Osborne, Tobias J.
AU - Perk, Michael
AU - Ramacciotti, Debora
AU - Rotundo, Antonio
AU - Skelton, S. E.
AU - Stiller, Sebastian
AU - Wolff, Timo de
PY - 2023/11/16
Y1 - 2023/11/16
N2 - 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.
AB - 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.
KW - quant-ph
KW - cs.DS
KW - math.OC
U2 - http://arxiv.org/abs/2311.09995v1
DO - http://arxiv.org/abs/2311.09995v1
M3 - Preprint
BT - Realistic Runtime Analysis for Quantum Simplex Computation
ER -