Beyond product state approximations for a quantum analogue of Max Cut
- URL: http://arxiv.org/abs/2003.14394v1
- Date: Tue, 31 Mar 2020 17:41:13 GMT
- Title: Beyond product state approximations for a quantum analogue of Max Cut
- Authors: Anurag Anshu, David Gosset, Karen Morenz
- Abstract summary: 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.
- Score: 14.567067583556714
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a computational problem where the goal is to approximate the
maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg
interactions between qubits located at the vertices of a graph. Previous work
has shed light on this problem's approximability by product states. For any
instance of this problem the maximum energy attained by a product state is
lower bounded by the Max Cut of the graph and upper bounded by the standard
Goemans-Williamson semidefinite programming relaxation of it. Gharibian and
Parekh described an efficient classical approximation algorithm for this
problem which outputs a product state with energy at least 0.498 times the
maximum eigenvalue in the worst case, and observe that there exist instances
where the best product state has energy 1/2 of optimal. We investigate
approximation algorithms with performance exceeding this limitation which are
based on optimizing over tensor products of few-qubit states and shallow
quantum circuits. We provide an efficient classical algorithm which achieves an
approximation ratio of at least 0.53 in the worst case. We also 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 (larger even than its semidefinite programming
relaxation).
Related papers
- 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) - 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) - 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) - A Quantum Optimal Control Problem with State Constrained Preserving
Coherence [68.8204255655161]
We consider a three-level $Lambda$-type atom subjected to Markovian decoherence characterized by non-unital decoherence channels.
We formulate the quantum optimal control problem with state constraints where the decoherence level remains within a pre-defined bound.
arXiv Detail & Related papers (2022-03-24T21:31:34Z) - 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) - Average-case Speedup for Product Formulas [69.68937033275746]
Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems.
We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states.
Our results open doors to the study of quantum algorithms in the average case.
arXiv Detail & Related papers (2021-11-09T18:49:48Z) - Optimizing Strongly Interacting Fermionic Hamiltonians [2.1756081703276]
Fundamental problem in much of physics and quantum chemistry is to optimize a low-degree in certain anticommuting variables.
One prominent exception is when the optimum is described by a so-called "Gaussian state", also called a free fermion state.
We give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the $q=4$ SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue.
arXiv Detail & Related papers (2021-10-20T18:00:17Z) - Direct Optimal Control Approach to Laser-Driven Quantum Particle
Dynamics [77.34726150561087]
We propose direct optimal control as a robust and flexible alternative to indirect control theory.
The method is illustrated for the case of laser-driven wavepacket dynamics in a bistable potential.
arXiv Detail & Related papers (2020-10-08T07:59:29Z) - 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)
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.