Cover Image

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nelson, Jon, Gottesman, Daniel
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
by: Rudolph, Dorian, et al.
Published: (2024)

QMA vs. QCMA and Pseudorandomness
by: Liu, Jiahui, et al.
Published: (2024)

Superposition detection and QMA with non-collapsing measurements
by: Bassirian, Roozbeh, et al.
Published: (2024)

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

Towards a universal gateset for $\mathsf{QMA}_1$
by: Rudolph, Dorian
Published: (2024)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

Toward Separating QMA from QCMA with a Classical Oracle
by: Zhandry, Mark
Published: (2024)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
by: Miloschewsky, David, et al.
Published: (2026)

Bounds on Eventually Universal Quantum Gate Sets
by: Karamchedu, Chaitanya, et al.
Published: (2025)

A Criterion for Post-Selected Quantum Advantage
by: Karamchedu, Chaitanya, et al.
Published: (2024)

Hamiltonians whose low-energy states require $Ω(n)$ T gates
by: Coble, Nolan J., et al.
Published: (2023)

Separating QMA from QCMA with a classical oracle
by: Bostanci, John, et al.
Published: (2025)

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

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

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

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

Computational complexity of the homology problem with orientable filtration: MA-completeness
by: Hayakawa, Ryu, et al.
Published: (2025)

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

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

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

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

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

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

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)

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)

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

Efficient approximate unitary designs from random Pauli rotations
by: Haah, Jeongwan, et al.
Published: (2024)

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 advantage from random geometrically-two-local Hamiltonian dynamics
by: Quek, Yihui
Published: (2025)

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

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)

Hamiltonian Locality Testing via Trotterized Postselection
by: Kallaugher, John, et al.
Published: (2025)

The dihedral hidden subgroup problem
by: Chen, Imin, et al.
Published: (2021)

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