Copertina

Hardness of approximation for ground state problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gharibian, Sevag, Hecht, Carsten
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Quantum Physics Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

The 7 faces of quantum NP
di: Gharibian, Sevag
Pubblicazione: (2023)

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

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

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

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

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

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

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

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

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

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

Forrelation is Extremally Hard
di: Girish, Uma, et al.
Pubblicazione: (2025)

Free Fermion Distributions Are Hard to Learn
di: Nietner, Alexander
Pubblicazione: (2023)

Hardness results for decoding the surface code with Pauli noise
di: Fischer, Alex, et al.
Pubblicazione: (2023)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
di: Grier, Daniel, et al.
Pubblicazione: (2025)

Low-degree approximation of QAC$^0$ circuits
di: Montanaro, Ashley, et al.
Pubblicazione: (2024)

Quantum Max-Cut is NP hard to approximate
di: Piddock, Stephen
Pubblicazione: (2025)

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

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

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

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

The dihedral hidden subgroup problem
di: Chen, Imin, et al.
Pubblicazione: (2021)

On the Computational Hardness of Quantum One-Wayness
di: Cavalar, Bruno, et al.
Pubblicazione: (2023)

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

Quantum algorithms for path and cycle containment problems
di: Cornelissen, Arjan, et al.
Pubblicazione: (2026)

Further Statistical Study of NISQ Experiments
di: Kalai, Gil, et al.
Pubblicazione: (2025)

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

The membership problem for constant-sized quantum correlations is undecidable
di: Fu, Honghao, et al.
Pubblicazione: (2021)

A simplified version of the quantum OTOC$^{(2)}$ problem
di: King, Robbie, et al.
Pubblicazione: (2025)

Quantum Cryptography and Hardness of Non-Collapsing Measurements
di: Morimae, Tomoyuki, et al.
Pubblicazione: (2025)

Hardness of Quantum Distribution Learning and Quantum Cryptography
di: Hiroka, Taiga, et al.
Pubblicazione: (2025)

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

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

Quasi-quantum states and the quasi-quantum PCP theorem
di: Arad, Itai, et al.
Pubblicazione: (2024)

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
di: Pirnay, Niklas, et al.
Pubblicazione: (2022)

Quantum Merlin-Arthur proof systems for synthesizing quantum states
di: Delavenne, Hugo, et al.
Pubblicazione: (2023)

Learning junta distributions, quantum junta states, and QAC$^0$ circuits
di: Bao, Jinge, et al.
Pubblicazione: (2024)