Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints
- URL: http://arxiv.org/abs/2206.14999v3
- Date: Sun, 9 Jul 2023 03:51:59 GMT
- Title: Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints
- Authors: Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin
- Abstract summary: 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.
- Score: 62.72309460291971
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Semidefinite programs are optimization methods with a wide array of
applications, such as approximating difficult combinatorial problems. One such
semidefinite program is the Goemans-Williamson algorithm, a popular integer
relaxation technique. We introduce a variational quantum algorithm for the
Goemans-Williamson algorithm that uses only $n{+}1$ qubits, a constant number
of circuit preparations, and $\text{poly}(n)$ expectation values in order to
approximately solve semidefinite programs with up to $N=2^n$ variables and $M
\sim O(N)$ constraints. Efficient optimization is achieved by encoding the
objective matrix as a properly parameterized unitary conditioned on an auxilary
qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to
optimize the objective function by estimating only a single expectation value
of the ancilla qubit, rather than separately estimating exponentially many
expectation values. Similarly, we illustrate that the semidefinite programming
constraints can be effectively enforced by implementing a second Hadamard Test,
as well as imposing a polynomial number of Pauli string amplitude constraints.
We demonstrate the effectiveness of our protocol by devising an efficient
quantum implementation of the Goemans-Williamson algorithm for various NP-hard
problems, including MaxCut. Our method exceeds the performance of analogous
classical methods on a diverse subset of well-studied MaxCut problems from the
GSet library.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding.
We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
arXiv Detail & Related papers (2023-05-23T16:17:57Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
In this work, we integrate the potentials of quantum and classical techniques for optimization.
We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size.
We present numerous computational results from real quantum hardware.
arXiv Detail & Related papers (2023-02-10T20:12:53Z) - 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) - 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) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - 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.