This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from the existing robust SDP-based interior point method analysis due to [Huang, Jiang, Song, Tao and Zhang, FOCS 2022]. While, the previous work only provides an efficient implementation in the classical setting. This work provides a novel quantum implementation. We give a quantum second-order algorithm with high-accuracy in both the optimality and the feasibility of its output, and its running time depending on $\log(1/ε)$ on well-conditioned instances. Due to the limitation of quantum itself or first-order method, all the existing quantum SDP solvers either have polynomial error dependence or low-accuracy in the feasibility.
This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from the existing robust SDP-based interior point method analysis due to [Huang, Jiang, Song, Tao and Zhang, FOCS 2022]. While, the previous work only provides an efficient implementation in the classical setting. This work provides a novel quantum implementation. We give a quantum second-order algorithm with high-accuracy in both the optimality and the feasibility of its output, and its running time depending on log(1/ε) on well-conditioned instances. Due to the limitation of quantum itself or first-order method, all the existing quantum SDP solvers either have polynomial error dependence or low-accuracy in the feasibility.
We present a quantum interior point method (IPM) for semi-definite programs that has a worst-case running time of Õ( n 2.5 / ξ 2 μ κ 3 log(1/ϵ)). The algorithm outputs a pair of matrices ( S,Y ) that have objective value within ϵ of the optimal and satisfy the constraints approximately to error xi. The parameter mu is at most √2 n while kappa is an upper bound on the condition number of the intermediate solution matrices arising in the classical IPM. For the case where κ ≪ n 5/6 , our method provides a significant polynomial speedup over the best-known classical semi-definite program solvers that have a worst-case running time of Õ( n 6 ). For linear programs, our algorithm has a running time of Õ( n 1.5 / ξ 2 μ κ 3 log (1/ϵ)) with the same guarantees and with parameter μ < √2 n . Our technical contributions include an efficient quantum procedure for solving the Newton linear systems arising in the classical IPMs, an efficient pure state tomography algorithm, and an analysis of the IPM where the linear systems are solved approximately. Our results pave the way for the development of quantum algorithms with significant polynomial speedups for applications in optimization and machine learning.
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.
Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an ϵ -optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.
The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as artificial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often suffer from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, offer promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain significant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative refinement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worst-case scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.
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 optimal local minima. Here, we present a current term NISQ algorithm for SDP. The classical optimization program of our NISQ solver is another SDP over a smaller dimensional ansatz space. We harness the SDP based formulation of the Hamiltonian ground state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex, can be solved in polynomial time with the number of ansatz parameters and every local minimum is a global minimum. Further, we demonstrate the potential of our NISQ SDP solver by finding the largest eigenvalue of up to 21000 dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.