Cover Image

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aldi, Marco, Gharibian, Sevag, Rudolph, Dorian
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

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

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)

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

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

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

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

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

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

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

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

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

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

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

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

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

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

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

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

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

On Pigeonhole Principles and Ramsey in TFNP
by: Jain, Siddhartha, et al.
Published: (2024)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

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

Classically estimating observables of noiseless quantum circuits
by: Angrisani, Armando, et al.
Published: (2024)

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

Learning quantum states prepared by shallow circuits in polynomial time
by: Landau, Zeph, et al.
Published: (2024)

Grothendieck inequalities characterize converses to the polynomial method
by: Briët, Jop, et al.
Published: (2022)

Hierarchies within TFNP: building blocks and collapses
by: Ghentiyala, Surendra, et al.
Published: (2025)

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

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

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

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

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

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Second order cone relaxations for quantum Max Cut
by: Huber, Felix, et al.
Published: (2024)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

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

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