Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Coble, Nolan J., Coudron, Matthew, Nelson, Jon, Nezhadi, Seyed Sajjad
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Provably Overwhelming Transformer Models with Designed Inputs
by: Stambler, Lev, et al.
Published: (2025)

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
by: Nelson, Jon, et al.
Published: (2025)

Finding dense sub-lattices as low-energy states of a Hamiltonian
by: Barberà-Rodríguez, Júlia, et al.
Published: (2023)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
by: Wu, Mingyou
Published: (2024)

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

Unitary synthesis with fewer T gates
by: Tan, Xinyu
Published: (2025)

Learning quantum states and unitaries of bounded gate complexity
by: Zhao, Haimeng, et al.
Published: (2023)

On the complexity of estimating ground state entanglement and free energy
by: Gharibian, Sevag, et al.
Published: (2025)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
by: Waite, Gabriel
Published: (2025)

Physically-Motivated Guiding States for Local Hamiltonians
by: Waite, Gabriel, et al.
Published: (2025)

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
by: Waite, Gabriel, et al.
Published: (2025)

The Complexity of Stoquastic Sparse Hamiltonians
by: Grilo, Alex B., et al.
Published: (2026)

Commuting Local Hamiltonians Beyond 2D
by: Bostanci, John, et al.
Published: (2024)

On the Complexity of the Succinct State Local Hamiltonian Problem
by: Waite, Gabriel, et al.
Published: (2025)

Entanglement-Dependent Error Bounds for Hamiltonian Simulation
by: Kulkarni, Prateek P.
Published: (2026)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
by: Daskin, Ammar
Published: (2024)

Circuit-to-Hamiltonian from tensor networks and fault tolerance
by: Anshu, Anurag, et al.
Published: (2023)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

Complexity Classification of Product State Problems for Local Hamiltonians
by: Kallaugher, John, et al.
Published: (2024)

Derandomised tensor product gap amplification for quantum Hamiltonians
by: Bergamaschi, Thiago, et al.
Published: (2025)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
by: Grewal, Sabee, et al.
Published: (2025)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
by: Krovi, Hari
Published: (2024)

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

Quantum advantage from random geometrically-two-local Hamiltonian dynamics
by: Quek, Yihui
Published: (2025)

On the hardness of learning ground state entanglement of geometrically local Hamiltonians
by: Bouland, Adam, et al.
Published: (2024)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
by: Cade, Chris, et al.
Published: (2022)

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
by: Ji, Zhengfeng, et al.
Published: (2026)

Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
by: Zhang, Bingzhi, et al.
Published: (2025)

Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
by: Hwang, Yeongwoo, et al.
Published: (2024)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
by: Zschetzsche, Lilith, et al.
Published: (2026)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

Transversal non-Clifford gates for quantum LDPC codes on sheaves
by: Lin, Ting-Chun
Published: (2024)

Quantum state isomorphism problems for groups
by: Gheorghiu, Alexandru, et al.
Published: (2026)

Quantum state testing with restricted measurements
by: Liu, Yuhan, et al.
Published: (2024)

Hardness of approximation for ground state problems
by: Gharibian, Sevag, et al.
Published: (2024)

Amplitude amplification and estimation require inverses
by: Tang, Ewin, et al.
Published: (2025)

Computational complexity of isometric tensor network states
by: Malz, Daniel, et al.
Published: (2024)