Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXPONENTIAL SEPARATION:
Reports tagged with exponential separation:
TR07-058 | 9th June 2007
Dmytro Gavinsky

Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model.

more >>>

TR20-101 | 7th July 2020
Uma Girish, Ran Raz, Wei Zhan

Lower Bounds for XOR of Forrelations

The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between ... more >>>


TR23-083 | 2nd June 2023
Srinivasan A, Uma Girish

Trade-offs between Entanglement and Communication

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. ... more >>>




ISSN 1433-8092 | Imprint