An Improved Approximation Algorithm for Quantum Max-Cut
- URL: http://arxiv.org/abs/2209.02589v3
- Date: Tue, 7 Nov 2023 03:28:09 GMT
- Title: An Improved Approximation Algorithm for Quantum Max-Cut
- Authors: Robbie King
- Abstract summary: We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state.
For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio $1 / sqrt2$ on all graphs.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give an approximation algorithm for Quantum Max-Cut which works by
rounding an SDP relaxation to an entangled quantum state. The SDP is used to
choose the parameters of a variational quantum circuit. The entangled state is
then represented as the quantum circuit applied to a product state. It achieves
an approximation ratio of 0.582 on triangle-free graphs. The previous best
algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved
approximation ratios of 0.531 and 0.533 respectively. In addition, we study the
EPR Hamiltonian, which we argue is a natural intermediate problem which
isolates some key quantum features of local Hamiltonian problems. For the EPR
Hamiltonian, we give an approximation algorithm with approximation ratio $1 /
\sqrt{2}$ on all graphs.
Related papers
- An improved Quantum Max Cut approximation via matching [0.10878040851638002]
A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian.
We present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.584 given a generic input.
arXiv Detail & Related papers (2024-01-08T00:36:32Z) - Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions.
We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
arXiv Detail & Related papers (2023-09-19T22:53:17Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems.
We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian.
Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
arXiv Detail & Related papers (2023-06-10T23:28:13Z) - Optimizing quantum circuit parameters via SDP [0.0]
We introduce a new framework for parameterized quantum circuits: round SDP to circuit parameters.
Within this, we propose an algorithm that produces approximate solutions for a quantum optimization problem called Quantum Max Cut.
arXiv Detail & Related papers (2022-09-02T02:34:19Z) - Partition Function Estimation: Quantum and Quantum-Inspired Algorithms [1.7510560590853574]
We present two algorithms, one quantum and one classical, for estimating partition functions of quantum spin Hamiltonians.
The former is a DQC1 (Deterministic quantum computation with one clean qubit) algorithm, and the first such for complex temperatures.
arXiv Detail & Related papers (2022-08-01T15:29:06Z) - 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) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity.
We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
arXiv Detail & Related papers (2022-03-01T19:47:16Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - Locally Private k-Means in One Round [44.00192304748844]
We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of differential privacy (DP)
This algorithm achieves an approximation ratio arbitrarily close to the best non private approximation algorithm.
arXiv Detail & Related papers (2021-04-20T03:07:31Z) - Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems [3.553493344868414]
k-Local Hamiltonian problem is a generalization of classical constraint satisfaction problems (k-CSP)
For strictly quadratic instances, which are maximally entangled instances, we provide a classical 0.764-time 0.764-approximation.
We conjecture these are the hardest instances to approximate.
Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
arXiv Detail & Related papers (2020-12-22T20:41:34Z) - Variational Monte Carlo calculations of $\mathbf{A\leq 4}$ nuclei with
an artificial neural-network correlator ansatz [62.997667081978825]
We introduce a neural-network quantum state ansatz to model the ground-state wave function of light nuclei.
We compute the binding energies and point-nucleon densities of $Aleq 4$ nuclei as emerging from a leading-order pionless effective field theory Hamiltonian.
arXiv Detail & Related papers (2020-07-28T14:52:28Z)
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.