Image de couverture de livre

The 7 faces of quantum NP

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Gharibian, Sevag
Format:	Preprint
Publié:	2023
Sujets:	Quantum Physics Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

BQP, meet NP: Search-to-decision reductions and approximate counting
par: Gharibian, Sevag, et autres
Publié: (2024)

On the complexity of estimating ground state entanglement and free energy
par: Gharibian, Sevag, et autres
Publié: (2025)

Hardness of approximation for ground state problems
par: Gharibian, Sevag, et autres
Publié: (2024)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
par: Aldi, Marco, et autres
Publié: (2024)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
par: Gharibian, Sevag, et autres
Publié: (2021)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
par: Rudolph, Dorian, et autres
Publié: (2024)

Quantum k-SAT Related Hypergraph Problems
par: Kremer, Simon-Luca, et autres
Publié: (2025)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
par: Agarwal, Avantika, et autres
Publié: (2024)

The Complexity of Translationally Invariant Problems beyond Ground State Energies
par: Watson, James D., et autres
Publié: (2020)

How hard is it to verify a classical shadow?
par: Karaiskos, Georgios, et autres
Publié: (2025)

Beating the natural Grover bound for low-energy estimation and state preparation
par: Buhrman, Harry, et autres
Publié: (2024)

Improved Hardness Results for the Guided Local Hamiltonian Problem
par: Cade, Chris, et autres
Publié: (2022)

Quantum Max-Cut is NP hard to approximate
par: Piddock, Stephen
Publié: (2025)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
par: Gu, Shouzhen, et autres
Publié: (2026)

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

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
par: Zhan, Junpeng
Publié: (2023)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
par: Morimae, Tomoyuki, et autres
Publié: (2025)

Quasi-quantum states and the quasi-quantum PCP theorem
par: Arad, Itai, et autres
Publié: (2024)

On the complexity of unique quantum witnesses and quantum approximate counting
par: Anshu, Anurag, et autres
Publié: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
par: Buhrman, Harry, et autres
Publié: (2024)

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
par: He, Entong
Publié: (2024)

Second order cone relaxations for quantum Max Cut
par: Huber, Felix, et autres
Publié: (2024)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
par: Liu, Zhenning, et autres
Publié: (2024)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
par: Anand, Kartik, et autres
Publié: (2025)

Symmetric quantum computation
par: Castro-Silva, Davi, et autres
Publié: (2025)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
par: Iyer, Vishnu, et autres
Publié: (2026)

The power of quantum circuits in sampling
par: Blanc, Guy, et autres
Publié: (2025)

Improved quantum data analysis
par: Bădescu, Costin, et autres
Publié: (2020)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
par: Gall, François Le, et autres
Publié: (2023)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
par: Buhrman, Harry, et autres
Publié: (2025)

Optimising quantum circuits is generally hard
par: van de Wetering, John, et autres
Publié: (2023)

Peaked quantum advantage using error correction
par: Deshpande, Abhinav, et autres
Publié: (2025)

The status of the quantum PCP conjecture (games version)
par: Natarajan, Anand, et autres
Publié: (2024)

Space-bounded quantum interactive proof systems
par: Gall, François Le, et autres
Publié: (2024)

Even quantum advice is unlikely to solve PP
par: Yirka, Justin
Publié: (2024)

Physical complexity and black hole quantum computers
par: Reilly, Michele, et autres
Publié: (2025)

The membership problem for constant-sized quantum correlations is undecidable
par: Fu, Honghao, et autres
Publié: (2021)

Finding quantum partial assignments by search-to-decision reductions
par: Weggemans, Jordi
Publié: (2024)

Derandomised tensor product gap amplification for quantum Hamiltonians
par: Bergamaschi, Thiago, et autres
Publié: (2025)

A simplified version of the quantum OTOC$^{(2)}$ problem
par: King, Robbie, et autres
Publié: (2025)