Cover Image

Quantum Communication Advantage in TFNP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Göös, Mika, Gur, Tom, Jain, Siddhartha, Li, Jiawei
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

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

On Pigeonhole Principles and Ramsey in TFNP
by: Jain, Siddhartha, et al.
Published: (2024)

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

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

Consumable Data via Quantum Communication
by: Gilboa, Dar, et al.
Published: (2024)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

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

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Efficient Quantum Hermite Transform
by: Jain, Siddhartha, et al.
Published: (2025)

Formal Framework for Quantum Advantage
by: Buhrman, Harry, et al.
Published: (2025)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

A Criterion for Post-Selected Quantum Advantage
by: Karamchedu, Chaitanya, et al.
Published: (2024)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
by: Watts, Adam Bene, et al.
Published: (2023)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

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

Equality is Far Weaker than Constant-Cost Communication
by: Göös, Mika, et al.
Published: (2025)

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

Verifiable Quantum Advantage without Structure
by: Yamakawa, Takashi, et al.
Published: (2022)

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

Quantum Advantage from One-Way Functions
by: Morimae, Tomoyuki, et al.
Published: (2023)

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

Distributed Quantum Advantage for Local Problems
by: Balliu, Alkida, et al.
Published: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
by: Fang, Yuting, et al.
Published: (2024)

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
by: Gao, Xun, et al.
Published: (2021)

Quantum Advantages in (n,d)->1 Random Access Codes
by: Ambainis, Andris, et al.
Published: (2015)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Distributed Quantum Advantage in Locally Checkable Labeling Problems
by: Balliu, Alkida, et al.
Published: (2025)

Hierarchies within TFNP: building blocks and collapses
by: Ghentiyala, Surendra, et al.
Published: (2025)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
by: Hasegawa, Atsuya, et al.
Published: (2025)

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

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2026)

Information-theoretic generalization bounds for learning from quantum data
by: Caro, Matthias, et al.
Published: (2023)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

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)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)