Cover Image

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hasegawa, Atsuya, Gall, François Le, Modanese, Augusto
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

Multi-Prover Interactive Proof Systems with Leakage
by: Asadi, Vahid R., et al.
Published: (2026)

Dequantization and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
by: Chia, Nai-Hui, et al.
Published: (2026)

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

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
by: Delavenne, Hugo, et al.
Published: (2024)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

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

Dequantizing Short-Path Quantum Algorithms
by: Gall, François Le, et al.
Published: (2026)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
by: Gall, François Le
Published: (2024)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
by: Gall, François Le, et al.
Published: (2023)

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

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
by: Mataraarachchi, Ranitha, et al.
Published: (2026)

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

Online Locality Meets Distributed Quantum Computing
by: Akbari, Amirreza, et al.
Published: (2024)

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

A slightly improved upper bound for quantum statistical zero-knowledge
by: Gall, François Le, et al.
Published: (2025)

Group Order is in QCMA
by: Gall, François Le, et al.
Published: (2025)

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

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)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

Trade-offs between Entanglement and Communication
by: Arunachalam, Srinivasan, et al.
Published: (2023)

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

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

Separating Quantum and Classical Advice with Good Codes
by: Bostanci, John, et al.
Published: (2026)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
by: Czégel, András, et al.
Published: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

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

No distributed quantum advantage for approximate graph coloring
by: Coiteux-Roy, Xavier, et al.
Published: (2023)

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

The Communication Complexity of Approximating Matrix Rank
by: Sherstov, Alexander A., et al.
Published: (2024)

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

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

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