Cover Image

QMA vs. QCMA and Pseudorandomness

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liu, Jiahui, Mutreja, Saachi, Yuen, Henry
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

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

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

Toward Separating QMA from QCMA with a Classical Oracle
by: Zhandry, Mark
Published: (2024)

Separating QMA from QCMA with a classical oracle
by: Bostanci, John, et al.
Published: (2025)

Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)

Group Order is in QCMA
by: Gall, François Le, et al.
Published: (2025)

CountCrypt: Quantum Cryptography between QCMA and PP
by: Goldin, Eli, et al.
Published: (2024)

Superposition detection and QMA with non-collapsing measurements
by: Bassirian, Roozbeh, et al.
Published: (2024)

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

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

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

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

Unconditional Pseudorandomness against Shallow Quantum Circuits
by: Ghosh, Soumik, et al.
Published: (2025)

Pseudorandom density matrices
by: Bansal, Nikhil, et al.
Published: (2024)

Quantum Pseudorandom Scramblers
by: Lu, Chuhan, et al.
Published: (2023)

Pseudorandom quantum authentication
by: Haug, Tobias, et al.
Published: (2025)

Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
by: Hutton, Kiera, et al.
Published: (2025)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
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)

Pseudorandomness in the (Inverseless) Haar Random Oracle Model
by: Ananth, Prabhanjan, et al.
Published: (2024)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

Pseudorandom and Pseudoentangled States from Subset States
by: Jeronimo, Fernando Granha, et al.
Published: (2023)

On the Pauli Spectrum of QAC0
by: Nadimpalli, Shivam, et al.
Published: (2023)

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

Random Unitaries in Constant (Quantum) Time
by: Foxman, Ben, et al.
Published: (2025)

Quantum State Group Actions
by: Mutreja, Saachi, et al.
Published: (2024)

Pseudorandom unitaries are neither real nor sparse nor noise-robust
by: Haug, Tobias, et al.
Published: (2023)

On black-box separations of quantum digital signatures from pseudorandom states
by: Coladangelo, Andrea, et al.
Published: (2024)

An efficient quantum parallel repetition theorem and applications
by: Bostanci, John, et al.
Published: (2023)

A distribution testing oracle separation between QMA and QCMA
by: Natarajan, Anand, et al.
Published: (2022)

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

Unitary Complexity and the Uhlmann Transformation Problem
by: Bostanci, John, et al.
Published: (2023)

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

Revocable Encryption, Programs, and More: The Case of Multi-Copy Security
by: Ananth, Prabhanjan, et al.
Published: (2024)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
by: Li, Xingjian, et al.
Published: (2023)

Proper vs Improper Quantum PAC learning
by: Nayak, Ashwin, et al.
Published: (2024)

Satisfiability of commutative vs. non-commutative CSPs
by: Bulatov, Andrei A., et al.
Published: (2024)

Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE
by: Bartusek, James, et al.
Published: (2025)

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

Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
by: Liu, Yupan, et al.
Published: (2026)