The Complexity of Translationally Invariant Problems beyond Ground State Energies

• URL: http://arxiv.org/abs/2012.12717v1
• Date: Wed, 23 Dec 2020 14:44:57 GMT
• Title: The Complexity of Translationally Invariant Problems beyond Ground State Energies
• Authors: James D. Watson, Johannes Bausch, Sevag Gharibian
• Abstract summary: Three fundamental questions regarding local Hamiltonians are $mathsfQMA$-hard, $mathsfPmathsfQMA[log]$-hard and $mathsfQCMA$-hard. We show that translationally invariant versions of both APX-SIM and GSCON remain intractable.
• Score: 6.445605125467574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is known that three fundamental questions regarding local Hamiltonians -- approximating the ground state energy (the Local Hamiltonian problem), simulating local measurements on the ground space (APX-SIM), and deciding if the low energy space has an energy barrier (GSCON) -- are $\mathsf{QMA}$-hard, $\mathsf{P}^{\mathsf{QMA}[log]}$-hard and $\mathsf{QCMA}$-hard, respectively, meaning they are likely intractable even on a quantum computer. Yet while hardness for the Local Hamiltonian problem is known to hold even for translationally-invariant systems, it is not yet known whether APX-SIM and GSCON remain hard in such "simple" systems. In this work, we show that the translationally invariant versions of both APX-SIM and GSCON remain intractable, namely are $\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}$- and $\mathsf{QCMA}_{\mathsf{EXP}}$-complete, respectively. Each of these results is attained by giving a respective generic "lifting theorem" for producing hardness results. For APX-SIM, for example, we give a framework for "lifting" any abstract local circuit-to-Hamiltonian mapping $H$ (satisfying mild assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by $H$, while preserving the structural and geometric properties of $H$ (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we "compress" the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we give a hardness construction robust against highly non-local unitaries, i.e. even if the adversary acts on all but one qudit in the system in each step.

Related papers

• On the Computational Complexity of Schrödinger Operators [6.1436827446807705]
  We study computational problems related to the Schr"odinger operator $H = -Delta + V$ in the real space. We prove that (i) simulating the dynamics generated by the Schr"odinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schr"odinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians) This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known
  arXiv  Detail & Related papers  (2024-11-07T19:39:52Z)
• Preparing angular momentum eigenstates using engineered quantum walks [1.0232954388448414]
  We develop a quantum-walk scheme that does not require inputting $O(j)$ nonzero Clebsch-Gordan (CG) coefficients classically. Our scheme prepares angular momentum eigenstates using a sequence of Hamiltonians to move an initial state deterministically to desired final states. We test our state preparation scheme on classical computers, reproducing CG coefficients, and implement small test problems on current quantum hardware.
  arXiv  Detail & Related papers  (2024-08-26T23:20:00Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Geometry of degenerate quantum states, configurations of $m$-planes and invariants on complex Grassmannians [55.2480439325792]
  We show how to reduce the geometry of degenerate states to the non-abelian connection $A$. We find independent invariants associated with each triple of subspaces. Some of them generalize the Berry-Pancharatnam phase, and some do not have analogues for 1-dimensional subspaces.
  arXiv  Detail & Related papers  (2024-04-04T06:39:28Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
  arXiv  Detail & Related papers  (2023-03-03T16:53:30Z)
• Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States [0.0]
  We show that the so-called guided local Hamiltonian problem remains BQP-complete when the Hamiltonian is 2-local. We improve upon this result by showing that it remains BQP-complete when i) the Hamiltonian is 2-local, ii) the overlap between the guiding state and target eigenstate is as large as $1.
  arXiv  Detail & Related papers  (2022-07-20T18:00:02Z)
• 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)
• Computational Complexity of the Ground State Energy Density Problem [0.0]
  We study the complexity of finding the ground state energy density of a local Hamiltonian on a lattice in the thermodynamic limit of infinite lattice size. We show that for classical, translationally invariant, nearest neighbour Hamiltonians on a 2D square lattice, $mathsfPmathsfNEEXPsubseteqmathsfEXPmathsfGSEDsubseteq mathsfEXPmathsfNEXP$, and for quantum Hamiltonians $mathsfPmathsfNEEXPsubseteqmathsfEXPmath
  arXiv  Detail & Related papers  (2021-07-11T14:52:43Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
  arXiv  Detail & Related papers  (2021-06-30T18:00:01Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)

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.