A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices

Published on Oct 7, 2021in arXiv: Quantum Physics
Jakub Marecek13
Estimated H-index: 13
(CTU: Czech Technical University in Prague),
Albert Akhriev5
Estimated H-index: 5
(IBM)
Sources
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.
馃摉 Papers frequently viewed together
References73
Newest
#1Ewin Tang (UW: University of Washington)H-Index: 11
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC'19], we introduce such a model, where we assume we can efficiently perform \ell^2norm samples of input data, a natural analogue to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classica...
Source
#1Kishor BhartiH-Index: 9
#2Tobias HaugH-Index: 11
Last. Leong Chuan KwekH-Index: 52
view all 4 authors...
Semidefinite Programming (SDP) is a class of convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an NP-hard problem that in general requires an exponential time to solve and can contain many far from optim...
#1Alp YurtseverH-Index: 13
#2Joel A. Tropp (Caltech: California Institute of Technology)H-Index: 60
Last. Volkan CevherH-Index: 47
view all 5 authors...
Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorith...
Source
#1Nadiia Chepurko (MIT: Massachusetts Institute of Technology)H-Index: 4
#2Kenneth L. Clarkson (IBM)H-Index: 44
Last. David P. Woodruff (CMU: Carnegie Mellon University)H-Index: 51
view all 4 authors...
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise. With...
Nov 1, 2020 in FOCS (Foundations of Computer Science)
#1Haotian Jiang (UW: University of Washington)H-Index: 6
#2Tarun Kathuria (University of California, Berkeley)H-Index: 3
Last. Zhao Song (Princeton University)H-Index: 24
view all 5 authors...
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents a faster interior point method to solve generic SDPs with variable size n \times nand m constraints in time \begin{equation*} \tilde{O}(\sqrt{n}(mn^{2}+m^{\omega}+n^{\omega})\log(1/\epsilon)), \end{equation*} where \omegais the exponent of ma...
Source
#1Daniel J. Egger (IBM)H-Index: 20
#2Claudio Gambella (IBM)H-Index: 8
Last. Elena Yndurain (IBM)H-Index: 1
view all 9 authors...
This article outlines our point of view regarding the applicability, state-of-the-art, and potential of quantum computing for problems in finance. We provide an introduction to quantum computing as well as a survey on problem classes in finance that are computationally challenging classically and for which quantum computing algorithms are promising. In the main part, we describe in detail quantum algorithms for specific applications arising in financial services, such as those involving simulati...
Source
#1Ankit GargH-Index: 16
#2Robin KothariH-Index: 21
Last. Suhail SherifH-Index: 3
view all 4 authors...
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:\mathbb{R}^n \to \mathbb{R}and its (sub)gradient. Our goal is to find an \epsilonapproximate minimum of fstarting from a point that is distance at most Rfrom the true minimum. If fis GLipschitz, then the classic gradient descent algorithm solves this problem with O((GR/\epsilon)^{2})queries. Importantly, the number of queries is independent of the dim...
#1Iordanis KerenidisH-Index: 27
#2Anupam Prakash (Paris Diderot University)H-Index: 13
We present a quantum interior point method (IPM) for semi-definite programs that has a worst-case running time of O(n2.5 / 2 3 log(1/)). The algorithm outputs a pair of matrices (S,Y) that have obj...
Source
#1Apostolos ChalkisH-Index: 4
#2Ioannis Z. EmirisH-Index: 31
Last. Elias P. Tsigaridas (University of Paris)H-Index: 21
view all 5 authors...
We present algorithmic, complexity, and implementation results on the problem of sampling points from a spectrahedron, that is the feasible region of a semidefinite program. Our main tool is geometric random walks. We analyze the arithmetic and bit complexity of certain primitive geometric operations that are based on the algebraic properties of spectrahedra and the polynomial eigenvalue problem. This study leads to the implementation of a broad collection of random walks for sampling from spect...
#1Jeffrey B. Parker (LLNL: Lawrence Livermore National Laboratory)H-Index: 12
#2Ilon Joseph (LLNL: Lawrence Livermore National Laboratory)H-Index: 20
Quantum phase estimation provides a path to quantum computation of solutions to Hermitian eigenvalue problems Hv = \lambda v such as those occurring in quantum chemistry. It is natural to ask whether the same technique can be applied to generalized eigenvalue problems Av = \lambda B v which arise in many areas of science and engineering. We answer this question affirmatively. A restricted class of generalized eigenvalue could be solved as efficiently as standard eigenvalue problems. A para...
Source
Cited By0
Newest
This website uses cookies.
We use cookies to improve your online experience. By continuing to use our website we assume you agree to the placement of these cookies.
To learn more, you can find in our Privacy Policy.