Cover Image

Quantum Merlin-Arthur with an internally separable proof

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bassirian, Roozbeh, Fefferman, Bill, Leigh, Itai, Marwaha, Kunal, Wu, Pei
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

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

On the Complexity of Decoded Quantum Interferometry
by: Marwaha, Kunal, et al.
Published: (2025)

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

Quantum Merlin-Arthur proof systems for synthesizing quantum states
by: Delavenne, Hugo, et al.
Published: (2023)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
by: Gay, William, et al.
Published: (2026)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
by: Fefferman, Bill, et al.
Published: (2024)

A complexity phase transition at the EPR Hamiltonian
by: Marwaha, Kunal, et al.
Published: (2026)

Classical and quantum Merlin-Arthur automata
by: Yakaryılmaz, Abuzer
Published: (2022)

Exponential improvements to the average-case hardness of BosonSampling
by: Bouland, Adam, et al.
Published: (2024)

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

On Certified Randomness from Fourier Sampling or Random Circuit Sampling
by: Bassirian, Roozbeh, et al.
Published: (2021)

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

Quasi-quantum states and the quasi-quantum PCP theorem
by: Arad, Itai, et al.
Published: (2024)

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

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

On quantum functionals for higher-order tensors
by: Botero, Alonso, et al.
Published: (2026)

Quantum-proof multi-source randomness extractors in the Markov model
by: Arnon, Rotem, et al.
Published: (2015)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
by: Chen, Zeyu, et al.
Published: (2025)

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

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

Dimension Independent Disentanglers from Unentanglement and Applications
by: Jeronimo, Fernando G., et al.
Published: (2024)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

Experimental relativistic zero-knowledge proofs with unconditional security
by: Weng, Chen-Xun, et al.
Published: (2025)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

The Role of piracy in quantum proofs
by: Broadbent, Anne, et al.
Published: (2024)

The Power of Lorentz Quantum Computer
by: Zhang, Qi, et al.
Published: (2024)

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

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

Discreteness of asymptotic tensor ranks
by: Briët, Jop, et al.
Published: (2023)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
by: Grier, Daniel, et al.
Published: (2025)

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
by: Gilani, Amin Shiraz, et al.
Published: (2024)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
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)

New Quantum Algorithms for Computing Quantum Entropies and Distances
by: Wang, Qisheng, et al.
Published: (2022)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
by: Lykov, Danylo, et al.
Published: (2022)

Quantum Threshold is Powerful
by: Grier, Daniel, et al.
Published: (2024)

Basic Quantum Algorithms
by: Portugal, Renato
Published: (2022)