Product-state approximations to quantum states

DOI10.1007/S00220-016-2575-1zbMATH Open1333.81447arXiv1310.0017OpenAlexW2285737492WikidataQ59711909 ScholiaQ59711909MaRDI QIDQ5962905FDOQ5962905

Authors: Fernando G. S. L. Brandão, Aram W. Harrow 

Publication date: 25 February 2016

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. First, we show the existence of a good product-state approximation for the ground-state energy of 2-local Hamiltonians with one or more of the following properties: (1) high degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some partition into small pieces. The approximation based on degree is a surprising difference between quantum Hamiltonians and classical CSPs (constraint satisfaction problems), since in the classical setting, higher degree is usually associated with harder CSPs. The approximation based on low entanglement, in turn, was previously known only in the regime where the entanglement was close to zero. Since the existence of a low-energy product state can be checked in NP, the result implies that any Hamiltonian used for a quantum PCP theorem should have: (1) constant degree, (2) constant expansion, (3) a "volume law" for entanglement with respect to any partition into small parts. Second, we show that in several cases, good product-state approximations not only exist, but can be found in polynomial time: (1) 2-local Hamiltonians on any planar graph, solving an open problem of Bansal, Bravyi, and Terhal, (2) dense k-local Hamiltonians for any constant k, solving an open problem of Gharibian and Kempe, and (3) 2-local Hamiltonians on graphs with low threshold rank, via a quantum generalization of a recent result of Barak, Raghavendra and Steurer. Our work introduces two new tools which may be of independent interest. First, we prove a new quantum version of the de Finetti theorem which does not require the usual assumption of symmetry. Second, we describe a way to analyze the application of the Lasserre/Parrilo SDP hierarchy to local quantum Hamiltonians.

Full work available at URL: https://arxiv.org/abs/1310.0017

Recommendations

• Product-state approximations to quantum ground states
• scientific article; zbMATH DE number 7651034
• Approximation algorithms for QMA-complete problems
• Approximation algorithms for quantum many-body problems
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)

Mathematics Subject Classification ID

Quantum coherence, entanglement, quantum correlations (81P40) Many-body theory; quantum Hall effect (81V70) Interacting particle systems in time-dependent statistical mechanics (82C22)

Cites Work

• Finite exchangeable sequences
• Quantum entanglement
• Quantum fluctuations and rate of convergence towards mean field dynamics
• Structure of states which satisfy strong subadditivity of quantum entropy with equality
• Some applications of hypercontractive inequalities in quantum information theory
• Proof verification and the hardness of approximation problems
• Expander graphs and their applications
• Distinguishing multi-partite states by local measurements
• Probabilistic checking of proofs
• Title not available (Why is that?)
• Faithful squashed entanglement
• Robustness of quantum Markov chains
• Area laws in quantum systems: mutual information and correlations
• Finitely correlated states on quantum spin chains
• Unknown quantum states: The quantum de Finetti representation
• Quantum de finetti theorems under local measurements with applications
• Colloquium: area laws for the entanglement entropy
• A Parallel Repetition Theorem
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Title not available (Why is that?)
• The detectability lemma and quantum gap amplification
• Symmetric states of infinite tensor products of \(C^ *\)-algebras
• Locally normal symmetric states and an analogue of de Finetti's theorem
• A de Finetti representation for finite symmetric quantum states
• One-and-a-half quantum de Finetti theorems
• Inapproximability of combinatorial optimization problems
• The PCP theorem by gap amplification
• The complexity of quantum spin systems on a two-dimensional square lattice
• The Complexity of the Local Hamiltonian Problem
• The power of quantum systems on a line
• Commutative version of the local Hamiltonian problem and common eigenspace problem
• Squashed Entanglement for Multipartite States and Entanglement Measures Based on the Mixed Convex Roof
• Entropy scaling and simulability by matrix product states
• An application of Bell's inequalities to a quantum state extension problem
• A simple proof of monogamy of entanglement
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Complexity of commuting Hamiltonians on a square lattice of qubits
• Approximation algorithms for QMA-complete problems
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
• Matrix product operators and central elements: classical description of a quantum state
• Title not available (Why is that?)

Cited In (10)

• Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
• A construction of combinatorial NLTS
• Title not available (Why is that?)
• Title not available (Why is that?)
• A class of stochastic products on the convex set of quantum states
• A fermionic de Finetti theorem
• Semidefinite programming hierarchies for constrained bilinear optimization
• Approximate low-weight check codes and circuit lower bounds for noisy ground states
• Product-state approximations to quantum ground states
• Title not available (Why is that?)

This page was built for publication: Product-state approximations to quantum states

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962905)