Cover Image

On the complexity of estimating ground state entanglement and free energy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gharibian, Sevag, Kamminga, Jonas
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

BQP, meet NP: Search-to-decision reductions and approximate counting
by: Gharibian, Sevag, et al.
Published: (2024)

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

The 7 faces of quantum NP
by: Gharibian, Sevag
Published: (2023)

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

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

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)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
by: Aldi, Marco, et al.
Published: (2024)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

On the Complexity of Pure-State Consistency of Local Density Matrices
by: Kamminga, Jonas, et al.
Published: (2024)

The Complexity of Translationally Invariant Problems beyond Ground State Energies
by: Watson, James D., et al.
Published: (2020)

How hard is it to verify a classical shadow?
by: Karaiskos, Georgios, et al.
Published: (2025)

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

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

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

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

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

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

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

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

On estimating the trace of quantum state powers
by: Liu, Yupan, et al.
Published: (2024)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Direct sum theorems beyond query complexity
by: Suruga, Daiki
Published: (2024)

Quantum and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

Separations in query complexity for total search problems
by: Ben-David, Shalev, et al.
Published: (2024)

On the average-case complexity of learning output distributions of quantum circuits
by: Nietner, Alexander, et al.
Published: (2023)

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

On estimating the entropy of shallow circuit outputs
by: Gheorghiu, Alexandru, et al.
Published: (2020)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

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

Computational complexity of Berry phase estimation in topological phases of matter
by: Hayakawa, Ryu, et al.
Published: (2025)

DQC1-hardness of estimating correlation functions
by: Moulik, Subhayan Roy, et al.
Published: (2024)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

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

Distributed inner product estimation with limited quantum communication
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
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)