A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM
Framework
- URL: http://arxiv.org/abs/2207.11154v1
- Date: Fri, 22 Jul 2022 15:51:02 GMT
- Title: A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM
Framework
- Authors: Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang
- Abstract summary: This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy.
We give a quantum second-order algorithm with high-accuracy in both the optimality and the feasibility of its output.
- Score: 14.531920189937495
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies a fundamental problem in convex optimization, which is to
solve semidefinite programming (SDP) with high accuracy. This paper follows
from 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/\epsilon)$ 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.
Related papers
- Optimal Coherent Quantum Phase Estimation via Tapering [0.0]
We study the coherent version of the phase estimation problem.
The goal is to estimate the phases of $U$ in superposition.
We propose an improved version of the well-known standard quantum phase estimation algorithm.
arXiv Detail & Related papers (2024-03-27T18:17:23Z) - QSlack: A slack-variable approach for variational quantum semi-definite
programming [5.0579795245991495]
Quantum computers could provide a speedup over the best known classical algorithms.
We show how to solve optimization problems involving semi-definite and linear programs.
We show that our implementations of both the primal and dual for these problems approach the ground truth.
arXiv Detail & Related papers (2023-12-06T19:00:01Z) - On adaptive low-depth quantum algorithms for robust multiple-phase
estimation [11.678822620192438]
We present robust multiple-phase estimation (RMPE) algorithms with Heisenberg-limited scaling.
These algorithms are particularly suitable for early fault-tolerant quantum computers.
arXiv Detail & Related papers (2023-03-14T17:38:01Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - 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) - Quantum Sparse Coding [5.130440339897477]
We develop a quantum-inspired algorithm for sparse coding.
The emergence of quantum computers and Ising machines can potentially lead to more accurate estimations.
We conduct numerical experiments with simulated data on Lightr's quantum-inspired digital platform.
arXiv Detail & Related papers (2022-09-08T13:00:30Z) - 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) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
We propose a hybrid quantum-classical algorithm for robust fitting.
Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs.
We present results obtained using an actual quantum computer.
arXiv Detail & Related papers (2022-01-25T05:59:24Z) - Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
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.
arXiv Detail & Related papers (2021-12-16T13:10:48Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.