Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication

V. N. Vapnik and A. Y. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” Theory of Probability and its Applications

1971

Earlier work this paper cites.

A. C.-C. Yao, “Some complexity questions related to distributive computing,” in Proceedings of the 11th Annual ACM Symposium on Theory of Computing

1979

Earlier work this paper cites.

A. C. Yao, “Protocols for secure computations,” FOCS 23rd Annual Symposium on Foundations of Computer Science

1982

Earlier work this paper cites.

C. H. Bennett and S. J. Wiesner, “Communication via One- and Two-Particle Operators on Einstein-Podolsky-Rosen States,” Phys. Rev. Lett

1992

Earlier work this paper cites.

A. C.-C. Yao, “Quantum circuit complexity,” Proceedings of the 34th Annual Symposium on the Foundations of Computer Science

1993

Earlier work this paper cites.

P. Hausladen, R. Jozsa, B. Schumacher, M. Westmoreland, and W. K. Wootters, “Classical information capacity of a quantum channel,” Phys. Rev. A

1996

Earlier work this paper cites.

(Cambridge University Press, New York, NY, USA, 1997)

E. Kushilevitz and N. Nisan, Communication Complexity · 1997

Earlier work this paper cites.

H.-K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A

1997

Earlier work this paper cites.

R. Cleve, W. van Dam, M. Nielsen, and A. Tapp, “Quantum entanglement and the communication complexity of the inner product function,” Lect.Notes Comput.Sci

1998

Earlier work this paper cites.

A. Nayak, “Optimal lower bounds for quantum automata and random access codes,” 40th Annual Symposium on Foundations of Computer Science

1998

Earlier work this paper cites.

(ACM, New York, NY, USA, 1999), pp. 63-68

H. R. Buhrman, R. Cleve, and A. Wigderson, “Quantum vs. Classical Communication and Computation,” in Proceedings of the 30th Annual ACM Symposium on Theory of Computing · 1999

Cited alongside, same era.

ACM, New York, NY, USA, 1999

R. Raz, “Exponential Separation of Quantum and Classical Communication Complexity,” in Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing · 1999

Cited alongside, same era.

arXiv:quant-ph/9804043

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, “Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata,” in Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing · 1999

Cited alongside, same era.

H. Klauck, “On quantum and probabilistic communication: Las Vegas and one-way protocols,” Proceedings of the 32nd annual ACM symposium on Theory of computing

2000

Cited alongside, same era.

A. Nayak and J. Salzman, “On communication over an entanglement-assisted quantum channel,” in Proceedings of 34th ACM STOC

2002

Cited alongside, same era.

O. Oreshkov, F. Costa, and Č. Brukner, “Quantum correlations with no causal order,” Nat. Commun

Original

2012

Later among the works it cites.

G. Chiribella, “Perfect discrimination of no-signalling channels via quantum superposition of causal structures,” Phys. Rev. A

Original

2012

Later among the works it cites.

H. Buhrman, M. Christandl, and C. Schaffner, “Complete Insecurity of Quantum Protocols for Classical Two-Party Computation,” Phys. Rev. Lett

Original

2012

Later among the works it cites.

G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, “Quantum computations without definite causal structure,” Phys. Rev. A

Original

2013

Later among the works it cites.

W. Liu, C. Liu, H. Wang, and T. Jia, “Quantum private comparison : A Review,” IETE Tech Rev 30