An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians
with Positive Terms
- URL: http://arxiv.org/abs/2206.08342v1
- Date: Thu, 16 Jun 2022 17:44:52 GMT
- Title: An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians
with Positive Terms
- Authors: Ojas Parekh and Kevin Thompson
- Abstract summary: 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.
- Score: 3.553493344868414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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, paralleling the
celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving
the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect
that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give
a classical 1/2-approximation for QMC that is unconditionally optimal, since
simple examples exhibit a gap of 1/2 between the energies of an optimal product
state and general quantum state. Our result relies on a new nonlinear monogamy
of entanglement inequality on a triangle that is derived from the second level
of the quantum Lasserre hierarchy. This inequality also applies to the quantum
Heisenberg model, and our results generalize to instances of Max 2-Local
Hamiltonian where each term is positive and has no 1-local parts. Finally, we
give further evidence that product states are essential for approximations of
2-Local Hamiltonian.
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) - Analysis of sum-of-squares relaxations for the quantum rotor model [0.0]
The noncommutative sum-of-squares hierarchy was introduced by Navascu'es-Pironio-Ac'i as a sequence of semidefinite programming relaxations for approximating quantum values of nonlocal games.
Recent work has started to analyze the hierarchy for approximating ground energies of local Hamiltonians.
arXiv Detail & Related papers (2023-11-15T14:53:22Z) - 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) - Canonically consistent quantum master equation [68.8204255655161]
We put forth a new class of quantum master equations that correctly reproduce the state of an open quantum system beyond the infinitesimally weak system-bath coupling limit.
Our method is based on incorporating the knowledge of the reduced steady state into its dynamics.
arXiv Detail & Related papers (2022-05-25T15:22: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) - 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) - 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) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form.
Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries.
This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
arXiv Detail & Related papers (2020-08-03T18:00:05Z) - 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.