Local Hamiltonians with topological quantum order exhibit highly entangled
ground states that cannot be prepared by shallow quantum circuits. Here, we
show that this property may extend to all low-energy states in the presence of
an on-site $Z_2$ symmetry. This proves a version of the No Low-Energy
Trivial States (NLTS) conjecture for a family of local Hamiltonians with
symmetry protected topological order. A surprising consequence of this result
is that the Goemans-Williamson algorithm outperforms the Quantum Approximate
Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant
level. We argue that the locality and symmetry of QAOA severely limits its
performance. To overcome these limitations, we propose a non-local version of
QAOA, and give numerical evidence that it significantly outperforms standard
QAOA for frustrated Ising models on random 3-regular graphs.
Description
Obstacles to State Preparation and Variational Optimization from Symmetry Protection
%0 Generic
%1 bravyi2019obstacles
%A Bravyi, Sergey
%A Kliesch, Alexander
%A Koenig, Robert
%A Tang, Eugene
%D 2019
%K quantumcomputing
%T Obstacles to State Preparation and Variational Optimization from
Symmetry Protection
%U http://arxiv.org/abs/1910.08980
%X Local Hamiltonians with topological quantum order exhibit highly entangled
ground states that cannot be prepared by shallow quantum circuits. Here, we
show that this property may extend to all low-energy states in the presence of
an on-site $Z_2$ symmetry. This proves a version of the No Low-Energy
Trivial States (NLTS) conjecture for a family of local Hamiltonians with
symmetry protected topological order. A surprising consequence of this result
is that the Goemans-Williamson algorithm outperforms the Quantum Approximate
Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant
level. We argue that the locality and symmetry of QAOA severely limits its
performance. To overcome these limitations, we propose a non-local version of
QAOA, and give numerical evidence that it significantly outperforms standard
QAOA for frustrated Ising models on random 3-regular graphs.
@misc{bravyi2019obstacles,
abstract = {Local Hamiltonians with topological quantum order exhibit highly entangled
ground states that cannot be prepared by shallow quantum circuits. Here, we
show that this property may extend to all low-energy states in the presence of
an on-site $\mathbb{Z}_2$ symmetry. This proves a version of the No Low-Energy
Trivial States (NLTS) conjecture for a family of local Hamiltonians with
symmetry protected topological order. A surprising consequence of this result
is that the Goemans-Williamson algorithm outperforms the Quantum Approximate
Optimization Algorithm (QAOA) for certain instances of MaxCut, at any constant
level. We argue that the locality and symmetry of QAOA severely limits its
performance. To overcome these limitations, we propose a non-local version of
QAOA, and give numerical evidence that it significantly outperforms standard
QAOA for frustrated Ising models on random 3-regular graphs.},
added-at = {2020-09-06T21:39:44.000+0200},
author = {Bravyi, Sergey and Kliesch, Alexander and Koenig, Robert and Tang, Eugene},
biburl = {https://www.bibsonomy.org/bibtex/24b2c755868065534fdc84453b1c3b107/cmcneile},
description = {Obstacles to State Preparation and Variational Optimization from Symmetry Protection},
interhash = {5313e73af30eff050b893c635a2b6aac},
intrahash = {4b2c755868065534fdc84453b1c3b107},
keywords = {quantumcomputing},
note = {cite arxiv:1910.08980Comment: 16 pages},
timestamp = {2020-09-06T21:39:44.000+0200},
title = {Obstacles to State Preparation and Variational Optimization from
Symmetry Protection},
url = {http://arxiv.org/abs/1910.08980},
year = 2019
}