Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as S parsest C ut and B alanced S eparator in undirected and directed weighted graphs, M in U n C ut and M in 2CNF D eletion , this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. Our ideas have proved useful in quantum computing, especially the recent result of Jain et al. [2011] that QIP = PSPACE.
Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a number of problems, such as S parsest C ut and B alanced S eparator in undirected and directed weighted graphs, M in U n C ut and M in 2CNF D eletion , this yields combinatorial approximation algorithms that are significantly more efficient than interior point methods. The design of our primal-dual algorithms is guided by a robust analysis of rounding algorithms used to obtain integer solutions from fractional ones. Our ideas have proved useful in quantum computing, especially the recent result of Jain et al. [2011] that QIP = PSPACE.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n1/2m1/2s2poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r upper bounds on the size of the optimal primal and dual solutions, respectively. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n1/2+ m2) quantum lower bound for solving semidefinite programs with constant s, R, r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n21m21s2poly(log(n),log(m),R,r,1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R,r a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n21+m21) quantum lower bound for solving semidefinite programs with constant s,R,r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
In recent years, semidefinite programming has played a vital role in shaping complexity theory and quantum computing. There have been numerous applications ranging from estimating quantum values, over approximating combinatorial quantities, to proving various bounds. This work extends the use of semidefinite programs (SDPs) to proving product rules and to characterizing quantum query complexity. In the first application, we provide a general framework to establishing product rules for quantities that can be expressed (or approximated) using SDPs. We use duality theory to give product rules, which bound the value of the ``product'' of two problems in terms of their value. Some previous results have implicitly used the properties of SDPs to give such product rules. Here we give sufficient and necessary conditions under which these approaches work, thereby enabling us to capture these previous results under our unified framework. We also include a discussion about alternate definitions of what a ``product'' means and how they fit into our approach. The second application provides an SDP characterization of quantum query complexity, which is one of the ways in which complexity of a function can be measured. It is known that quantum query complexity can be lower bounded by the so-called ``adversary method'' which is expressible as a semidefinite program. Recently, Ben Reichardt showed that the adversary method leads to a tight lower bound for boolean functions by converting the solution of this SDP (of adversary method) into an algorithm. We show that a related SDP, called ``witness size'' in this thesis, provides a tight bound on the quantum query complexity of non boolean functions (total as well as partial). This witness size SDP is also used to give composition results for quantum query complexity. We also show that the witness size is bounded by a constant multiple of the adversary bound. Finally, we briefly explore whether other convex programming paradigms can be useful in complexity theory. One of them is copositive programming. We show that one of the recent result about parallel repetition of unique games, by Barak et.al., can be interpreted as an application of copositive programming.
We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.
Brandao and Svore recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m is approximately n, which is the same as classical.