Cover Image

Towards a universal gateset for $\mathsf{QMA}_1$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Rudolph, Dorian
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

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)

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)

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

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

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

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

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)

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)

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

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

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
by: Grier, Daniel, et al.
Published: (2026)

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

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

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
by: Zschetzsche, Lilith, et al.
Published: (2026)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

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

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

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
by: Morimae, Tomoyuki, et al.
Published: (2025)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
by: Sakamoto, Kazuki, et al.
Published: (2025)

Classically estimating observables of noiseless quantum circuits
by: Angrisani, Armando, et al.
Published: (2024)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
by: Fortnow, Lance
Published: (2025)

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

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

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

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

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Towards a complexity-theoretic dichotomy for TQFT invariants
by: Bridges, Nicolas, et al.
Published: (2025)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Quantum Algorithms in a Superposition of Spacetimes
by: Shmueli, Omri
Published: (2024)

How to Verify that a Small Device is Quantum, Unconditionally
by: Malavolta, Giulio, et al.
Published: (2025)

Whether a quantum computation employs nonlocal resources is operationally undecidable
by: Fields, Chris, et al.
Published: (2025)

Complexity-theoretic foundations of BosonSampling with a linear number of modes
by: Bouland, Adam, et al.
Published: (2023)

Does there exist a quantum fingerprinting protocol without coherent measurements?
by: Hasegawa, Atsuya, et al.
Published: (2025)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
by: Cardoso, Ricardo Rivera, et al.
Published: (2025)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
by: Daskin, Ammar
Published: (2024)