Hamiltonians whose low-energy states require $Ω(n)$ T gates

• URL: http://arxiv.org/abs/2310.01347v2
• Date: Mon, 10 Jun 2024 19:37:16 GMT
• Title: Hamiltonians whose low-energy states require $Ω(n)$ T gates
• Authors: Nolan J. Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi,
• Abstract summary: We prove a relationship between the number of T gates preparing a state and the number of terms at which the state is pseudo-stabilizer. This result represents a significant improvement over [CCNN23] where we used a different technique to give an energy bound.
• Score: 0.22499166814992438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Even with NLTS now solved, there remain many independent and unresolved prerequisites to the QPCP Conjecture, such as the NLSS Conjecture of [GL22]. In this work we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose low-energy states all require $\omega(\log n)$ T gates to prepare. In fact, we prove a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require $\Omega(n)$ T gates. We further show that our procedure can be applied to the NLTS Hamiltonians of [ABN22] to yield local Hamiltonians whose low-energy states require both $\Omega(\log n)$-depth and $\Omega(n)$ T gates to prepare. In order to accomplish this we define a "pseudo-stabilizer" property of a state with respect to each local Hamiltonian term, and prove an additive local energy lower bound for each term at which the state is pseudo-stabilizer. By proving a relationship between the number of T gates preparing a state and the number of terms at which the state is pseudo-stabilizer, we are able to give a constant energy lower bound which applies to any state with T-count less than $c \cdot n$ for some fixed positive constant $c$. This result represents a significant improvement over [CCNN23] where we used a different technique to give an energy bound which only distinguishes between stabilizer states and states which require a non-zero number of T gates.

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• LDPC stabilizer codes as gapped quantum phases: stability under graph-local perturbations [0.025206105035672277]
  We generalize the proof of stability of topological order, due to Bravyi, Hastings and Michalakis, to Hamiltonians corresponding to low-density parity check codes. We show that LDPC codes very generally define stable gapped quantum phases, even in the non-Euclidean setting.
  arXiv  Detail & Related papers  (2024-11-04T18:52:44Z)
• 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)
• Fermionic Hamiltonians without trivial low-energy states [12.961180148172197]
  We construct local fermionic Hamiltonians with no low-energy trivial states (NLTS) Distinctly from the qubit case, we define trivial states via finite-depth $textitfermionic$ quantum circuits. We define a fermionic analogue of the class quantum PCP and discuss its relation with the qubit version.
  arXiv  Detail & Related papers  (2023-07-25T18:00:02Z)
• A hybrid quantum algorithm to detect conical intersections [39.58317527488534]
  We show that for real molecular Hamiltonians, the Berry phase can be obtained by tracing a local optimum of a variational ansatz along the chosen path. We demonstrate numerically the application of our algorithm on small toy models of the formaldimine molecule.
  arXiv  Detail & Related papers  (2023-04-12T18:00:01Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Local Hamiltonians with no low-energy stabilizer states [0.4588028371034407]
  A family of local Hamiltonians with low-enough constant energy do not have succinct representations allowing perfect sampling access. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states.
  arXiv  Detail & Related papers  (2023-02-28T16:55:05Z)
• 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)
• 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)
• Circuit lower bounds for low-energy states of quantum code Hamiltonians [17.209060627291315]
  We prove circuit lower bounds for all low-energy states of local Hamiltonians arising from quantum error-correcting codes. We show that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
  arXiv  Detail & Related papers  (2020-11-03T22:36:22Z)

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.