Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Multiple-Valued Logic (ISMVL)

Quantum communication complexity: a survey

Gilles Brassard A

Published Sep 28, 2004• 24 citations
Publisher

Abstract

Summary form only given. This is a survey talk on the topic of quantum communication complexity. A full survey paper by the author is available in Foundations of Physics (G. Brassard, vol.33(11), p.1593-1616, 2003).
DOI
10.1109/ismvl.2004.1319920

Related papers

Quantum Communication Complexity

Hartmut Klauck

This paper surveys the field of quantum communication complexity. Some interesting recent results are collected concerning relations to classical communication, lower bound methods, one-way communication, and applications of quantum communication complexity.

arXiv:quant-ph/0005032•May 8, 2000•18 citations

A survey on device-independent quantum communications

Jingzheng Huang, Zhen−Qiang Yin, Wei Chen +4 more

Quantum communications helps us to enhance the security and efficiency of communications and to deepen our understanding of quantum physics. Its rapid development in recent years has attracted the interest of researchers from diverse fields such as physics, mathematics, and computer science. We review the background and current state of quantum communications technology, with an emphasis on quantum key distribution, quantum random number generation, and a relatively hot topic: device independent protocols.

China Communications•Feb 1, 2013•7 citations

Feynman and computation: From Los Alamos to quantum computers

Tony Hey

The last lecture course that Nobel Prize winner Richard Feynman gave to students at Caltech was not on physics but on computer science. The course in 1983 was an overview of standard and not-so-standard topics in computer science, all given in Feynman’s inimitable style. This talk will begin by giving an overview of Feynman’s long-time interest in computing - starting with his time at Los Alamos during the war through to his suggestion of simulating physics on a quantum computer at a ‘Physics of Computation Conference at MIT in 1981 and his acting as a consultant for the parallel computer company, Thinking Machines. The talk will conclude with a summary of Feynman’s long-term interest in the physical limits to computation and the exemplary way he could communicate complex ideas to all types of audience.

The International Journal of High Performance Computing Applications•May 12, 2025•0 citations

Quantum complexity theory tools, goals and challenges

Jozef Gruska

Analysis of methods and results of quantum complexity theory and their contribution for better understanding of main theoretical and practical problems in quantum information processing.

•Jan 1, 2005•0 citations

Approximate Degree in Classical and Quantum Computing

Mark Bun, Justin Thaler

The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.

•Jan 1, 2022•0 citations

Project Qu-Gov: Exploration of Quantum Technologies for and Inside Governmental Administration

Oliver Muth

In 2022 Bundesdruckerei started the Project Qu-Gov which includes an overall advising approach of the German Federal ministry of Finance concerning the topics Quantum-Information, Quantum-Communication, Post-Quantum-Security, Quantum-Analytics and the souvereign use of Quantum devices and services. In this lecture we talk about our approach and first results. Full-text article not available; see video presentation

Quantum 2.0 Conference and Exhibition•Jan 1, 2024•0 citations
Quantum communications helps us to enhance the security and efficiency of communications and to deepen our understanding of quantum physics. Its rapid development in recent years has attracted the interest of researchers from diverse fields such as physics, mathematics, and computer science. We review the background and current state of quantum communications technology, with an emphasis on quantum key distribution, quantum random number generation, and a relatively hot topic: device independent protocols.
The last lecture course that Nobel Prize winner Richard Feynman gave to students at Caltech was not on physics but on computer science. The course in 1983 was an overview of standard and not-so-standard topics in computer science, all given in Feynman’s inimitable style. This talk will begin by giving an overview of Feynman’s long-time interest in computing - starting with his time at Los Alamos during the war through to his suggestion of simulating physics on a quantum computer at a ‘Physics of Computation Conference at MIT in 1981 and his acting as a consultant for the parallel computer company, Thinking Machines. The talk will conclude with a summary of Feynman’s long-term interest in the physical limits to computation and the exemplary way he could communicate complex ideas to all types of audience.
The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.