Cover Image

Separating QMA from QCMA with a classical oracle

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bostanci, John, Haferkamp, Jonas, Nirkhe, Chinmay, Zhandry, Mark
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

QMA vs. QCMA and Pseudorandomness
by: Liu, Jiahui, et al.
Published: (2024)

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

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

Tight bounds on depth-2 QAC-circuits computing parity
by: Fenner, Stephen, et al.
Published: (2025)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

On the hardness of cloning and connections to representation theory
by: Havlíček, Vojtěch, et al.
Published: (2024)

The status of the quantum PCP conjecture (games version)
by: Natarajan, Anand, et al.
Published: (2024)

Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)

L is different from NP
by: Montoya, J. Andres
Published: (2024)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Quantum algorithms through graph composition
by: Cornelissen, Arjan
Published: (2025)

Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)

Disjunctive Complexity
by: Ivanov, Nikita, et al.
Published: (2025)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
by: Kühn, Kolja, et al.
Published: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
by: Hemaspaandra, Lane A., et al.
Published: (2021)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

Understanding Robust Catalytic Computing
by: Koucký, Michal, et al.
Published: (2026)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

A point to set principle for finite-state dimension
by: Mayordomo, Elvira
Published: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
by: Bajaj, Divya, et al.
Published: (2026)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
by: Chakraborty, Sourav, et al.
Published: (2024)

The Space-Time Cost of Purifying Quantum Computations
by: Zhandry, Mark
Published: (2024)

NLTS Hamiltonians from good quantum codes
by: Anshu, Anurag, et al.
Published: (2022)

Explicit Commutative ROABPs from Partial Derivatives
by: Bhargava, Vishwas, et al.
Published: (2024)

A Computational Separation Between Quantum No-cloning and No-telegraphing
by: Nehoran, Barak, et al.
Published: (2023)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

Correspondences in computational and dynamical complexity II: forcing complex reductions
by: Everett, Samuel
Published: (2026)

Arithmetic Complexity of Solutions of the Dirichlet Problem
by: Boche, Holger, et al.
Published: (2026)

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)