Variational Quantum Algorithms for Semidefinite Programming
- URL: http://arxiv.org/abs/2112.08859v3
- Date: Wed, 12 Jun 2024 02:26:50 GMT
- Title: Variational Quantum Algorithms for Semidefinite Programming
- Authors: Dhrumil Patel, Patrick J. Coles, Mark M. Wilde,
- Abstract summary: A semidefinite program (SDP) is a convex optimization problem with applications in operations research, optimization, quantum information science, and beyond.
We propose variational quantum algorithms for approximately solving SDPs.
- Score: 3.481985817302898
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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\gg 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.
Related papers
- Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
We show that a quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms.
We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states.
arXiv Detail & Related papers (2023-10-11T18:00:53Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - The Quantum Approximate Optimization Algorithm performance with low
entanglement and high circuit depth [0.0]
Variational quantum algorithms constitute one of the most widespread methods for using current noisy quantum computers.
We investigate entanglement's role in these methods for solving optimization problems.
We conclude that entanglement plays a minor role in the MaxCut and Exact Cover 3 problems studied here.
arXiv Detail & Related papers (2022-07-07T16:21:36Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - An entanglement perspective on the quantum approximate optimization
algorithm [0.0]
We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits.
We also investigate the entanglement spectrum in connection with random matrix theory.
arXiv Detail & Related papers (2022-06-14T17:37:44Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
We present an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree $d$.
This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs, and the Sherrington-Kirkpatrick model.
arXiv Detail & Related papers (2021-10-20T17:58:53Z) - NISQ Algorithm for Semidefinite Programming [0.0]
We present a current term NISQ algorithm for Semidefinite Programming (SDP)
We harness the SDP based formulation of the Hamiltonian ground state problem to design a NISQ eigensolver.
Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
arXiv Detail & Related papers (2021-06-07T18:08:53Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope.
Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
arXiv Detail & Related papers (2020-06-11T17:43:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.