Image de couverture de livre

The Computational Advantage of MIP* Vanishes in the Presence of Noise

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dong, Yangjing, Fu, Honghao, Natarajan, Anand, Qin, Minglong, Xu, Haochen, Yao, Penghui
Format:	Preprint
Publié:	2023
Sujets:	Quantum Physics Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
par: Fu, Honghao, et autres
Publié: (2025)

A Relativizing MIP for BQP
par: Aaronson, Scott, et autres
Publié: (2026)

Succinct Perfect Zero-knowledge for MIP*
par: Fu, Honghao, et autres
Publié: (2025)

Quantum Pseudorandom Scramblers
par: Lu, Chuhan, et autres
Publié: (2023)

Parallel Kac's Walk Generates PRU
par: Lu, Chuhan, et autres
Publié: (2025)

The status of the quantum PCP conjecture (games version)
par: Natarajan, Anand, et autres
Publié: (2024)

Two bases suffice for QMA1-completeness
par: Ma, Henry, et autres
Publié: (2025)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
par: Yao, Penghui, et autres
Publié: (2023)

Two prover perfect zero knowledge for MIP*
par: Mastel, Kieran, et autres
Publié: (2024)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
par: Wu, Xudong, et autres
Publié: (2025)

The membership problem for constant-sized quantum correlations is undecidable
par: Fu, Honghao, et autres
Publié: (2021)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
par: Guan, Ziyi, et autres
Publié: (2023)

Rounding Almost Commuting Hamiltonians
par: Faisal, Islam, et autres
Publié: (2026)

Quantum Communication Advantage in TFNP
par: Göös, Mika, et autres
Publié: (2024)

Formal Framework for Quantum Advantage
par: Buhrman, Harry, et autres
Publié: (2025)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
par: Watts, Adam Bene, et autres
Publié: (2023)

A Criterion for Post-Selected Quantum Advantage
par: Karamchedu, Chaitanya, et autres
Publié: (2024)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
par: Grier, Daniel, et autres
Publié: (2025)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
par: Lykov, Danylo, et autres
Publié: (2022)

On the Computational Complexity of Geometrically Local QAC0 circuits
par: Dong, Yangjing, et autres
Publié: (2026)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
par: Grillo, Sebastian Alberto, et autres
Publié: (2026)

Verifiable Quantum Advantage without Structure
par: Yamakawa, Takashi, et autres
Publié: (2022)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
par: Anand, Kartik, et autres
Publié: (2025)

Quantum Advantage from One-Way Functions
par: Morimae, Tomoyuki, et autres
Publié: (2023)

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
par: Gao, Xun, et autres
Publié: (2021)

Quantum Advantages in (n,d)->1 Random Access Codes
par: Ambainis, Andris, et autres
Publié: (2015)

Distributed Quantum Advantage for Local Problems
par: Balliu, Alkida, et autres
Publié: (2024)

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
par: Zhang, Zhihan, et autres
Publié: (2024)

The Power of Lorentz Quantum Computer
par: Zhang, Qi, et autres
Publié: (2024)

Bosonic Quantum Computational Complexity
par: Chabaud, Ulysse, et autres
Publié: (2024)

On the Computational Power of QAC0 with Barely Superlinear Ancillae
par: Anshu, Anurag, et autres
Publié: (2024)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
par: Balliu, Alkida, et autres
Publié: (2025)

Computational complexity of isometric tensor network states
par: Malz, Daniel, et autres
Publié: (2024)

Computational aspects of the trace norm contraction coefficient
par: Delsol, Idris, et autres
Publié: (2025)

The Space-Time Cost of Purifying Quantum Computations
par: Zhandry, Mark
Publié: (2024)

Modifications of Quantum Computation and Adaptive Queries to PP
par: Miloschewsky, David, et autres
Publié: (2025)

Why Philosophers Should Care About Computational Complexity
par: Aaronson, Scott
Publié: (2011)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
par: Barch, Brian, et autres
Publié: (2025)

New Quantum Algorithms for Computing Quantum Entropies and Distances
par: Wang, Qisheng, et autres
Publié: (2022)

Linear-Size QAC0 Channels: Learning, Testing and Hardness
par: Dong, Yangjing, et autres
Publié: (2025)