Cover Image

Two bases suffice for QMA1-completeness

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ma, Henry, Natarajan, Anand
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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)

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

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

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

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

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

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

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

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

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

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

The Computational Advantage of MIP* Vanishes in the Presence of Noise
by: Dong, Yangjing, et al.
Published: (2023)

Rounding Almost Commuting Hamiltonians
by: Faisal, Islam, et al.
Published: (2026)

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
by: Ji, Zhengfeng, et al.
Published: (2026)

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

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

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

Two Simple Proofs of Müller's Theorem
by: Epstein, Samuel
Published: (2024)

Two Quantum Paradigms, but Still No Signal
by: Epstein, Samuel
Published: (2024)

Two prover perfect zero knowledge for MIP*
by: Mastel, Kieran, et al.
Published: (2024)

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

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

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

Computational complexity of the homology problem with orientable filtration: MA-completeness
by: Hayakawa, Ryu, et al.
Published: (2025)

Gap-preserving reductions and RE-completeness of independent set games
by: Mančinska, Laura, et al.
Published: (2025)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
by: Zhan, Junpeng
Published: (2023)

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

Verifiable measurement-based quantum random sampling with trapped ions
by: Ringbauer, Martin, et al.
Published: (2023)

Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
by: Barthe, Alice, et al.
Published: (2024)

Finding dense sub-lattices as low-energy states of a Hamiltonian
by: Barberà-Rodríguez, Júlia, et al.
Published: (2023)

DQC1-hardness of estimating correlation functions
by: Moulik, Subhayan Roy, et al.
Published: (2024)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
by: Grillo, Sebastian Alberto, et al.
Published: (2026)

Succinct arguments for QMA from standard assumptions via compiled nonlocal games
by: Metger, Tony, et al.
Published: (2024)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
by: Wu, Mingyou
Published: (2024)

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

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

How to Construct Random Unitaries
by: Ma, Fermi, et al.
Published: (2024)

Quantum Fast Implementation of Functional Bootstrapping and Private Information Retrieval
by: Ma, Guangsheng, et al.
Published: (2024)