A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
arXiv:2110.03400
Abstract
There is an increasing interest in quantum algorithms for optimization problems. Within convex optimization, interior-point methods and other recently proposed quantum algorithms are non-trivial to implement on noisy quantum devices. Here, we discuss how to utilize an alternative approach to convex optimization, in general, and semidefinite programming (SDP), in particular. This approach is based on a randomized variant of the cutting-plane method. We show how to leverage quantum speed-up of an eigensolver in speeding up an SDP solver utilizing the cutting-plane method. For the first time, we demonstrate a practical implementation of a randomized variant of the cutting-plane method for semidefinite programming on instances from SDPLIB, a well-known benchmark. Furthermore, we show that the RCP method is very robust to noise in the boundary oracle, which may make RCP suitable for use even on noisy quantum devices.
References in corpus (11)
- Quantum algorithm for solving linear systems of equations
- Supervised learning with quantum enhanced feature spaces
- Quantum principal component analysis
- Warm-starting quantum optimization
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Quantum phase estimation for a class of generalized eigenvalue problems
- Quantum algorithms and lower bounds for convex optimization
- Several natural BQP-Complete problems
- Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
- Efficient Sampling from Feasible Sets of SDPs and Volume Approximation