An improved Quantum Max Cut approximation via matching
- URL: http://arxiv.org/abs/2401.03616v2
- Date: Mon, 26 Feb 2024 12:10:09 GMT
- Title: An improved Quantum Max Cut approximation via matching
- Authors: Eunou Lee, Ojas Parekh
- Abstract summary: 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.
- Score: 0.10878040851638002
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding a high (or low) energy state of a given quantum Hamiltonian is a
potential area to gain a provable and practical quantum advantage. 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. In this work,
we present a classical approximation algorithm for Quantum Max Cut that
achieves an approximation ratio of 0.584 given a generic input, and a ratio of
0.595 given a triangle-free input, outperforming the previous best algorithms
of Lee \cite{Lee22} (0.562, generic input) and King \cite{King22} (0.582,
triangle-free input). The algorithm is based on finding the maximum weighted
matching of an input graph and outputs a product of at most 2-qubit states,
which is simpler than the fully entangled output states of the previous best
algorithms. --v2 update: Ojas Parekh added as an author, triangle free
condition removed.
Related papers
- A quantum advantage over classical for local max cut [48.02822142773719]
Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs.
Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
arXiv Detail & Related papers (2023-04-17T16:42:05Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems.
This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state.
Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
arXiv Detail & Related papers (2023-02-07T10:57:36Z) - An Improved Approximation Algorithm for Quantum Max-Cut [0.0]
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.
arXiv Detail & Related papers (2022-09-06T15:45:04Z) - 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 Optimal Product-State Approximation for 2-Local Quantum Hamiltonians
with Positive Terms [3.553493344868414]
We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states.
A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC.
We give a classical 1/2-approximation for QMC that is unconditionally optimal.
arXiv Detail & Related papers (2022-06-16T17:44:52Z) - Quantum mean states are nicer than you think: fast algorithms to compute
states maximizing average fidelity [1.9336815376402714]
We resolve the open problem of maximizing average fidelity over arbitrary finite ensembles of quantum states.
We first construct a semidefinite program whose optimal value is the maximum average fidelity and then derive fixed-point algorithms that converge to the optimal state.
We also derive expressions for near-optimal states that are easier to compute and upper and lower bounds for maximum average fidelity that are exact when all the states in the ensemble commute.
arXiv Detail & Related papers (2022-06-16T13:52:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Quantum Assisted Eigensolver [0.0]
We propose a hybrid quantum-classical algorithm for approxing the ground state and ground state energy of a Hamiltonian.
The output from the quantum part of the algorithm is utilized as input for the classical computer.
arXiv Detail & Related papers (2020-09-23T08:33:18Z) - 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) - Beyond product state approximations for a quantum analogue of Max Cut [14.567067583556714]
We consider a problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian.
Previous work has shed light on this problem's approximability by product states.
We show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state.
arXiv Detail & Related papers (2020-03-31T17:41:13Z)
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.