Cover Image

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agarwal, Avantika, Gharibian, Sevag, Koppula, Venkata, Rudolph, Dorian
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Quantum Physics
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)

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

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

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

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

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

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

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

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

Hardness of approximation for ground state problems
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)

A Cautionary Note on Quantum Oracles
by: Agarwal, Avantika, et al.
Published: (2025)

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

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

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

The Entangled Quantum Polynomial Hierarchy Collapses
by: Grewal, Sabee, et al.
Published: (2024)

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

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

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

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

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

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

StoqMA vs. MA: the power of error reduction
by: Aharonov, Dorit, et al.
Published: (2020)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
by: Khadiev, Kamil, et al.
Published: (2017)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

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

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
by: Miloschewsky, David, et al.
Published: (2024)

Strict Hierarchy for Quantum Channel Certification to Unitary
by: Chen, Kean, et al.
Published: (2026)

Syndrome aware mitigation of logical errors
by: Aharonov, Dorit, et al.
Published: (2025)

Peaked quantum advantage using error correction
by: Deshpande, Abhinav, et al.
Published: (2025)

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

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

Non-signalling parallel repetition using de Finetti reductions
by: Arnon, Rotem, et al.
Published: (2014)

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

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