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

WORLD SCIENTIFIC eBooks

Quantum computing and communication complexity

Harry Buhrman

Published Jan 1, 2000• 18 citations
OpenAlex

Abstract

Quantum computing combines the framework of quantum mechanics with that of computer science.In this paper we give a short introduction to quantum computing and survey the results in the area of quantum communiC4tion compluity.

Related papers

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

An Introduction to Quantum Communication

Vinod K. Mishra

Quantum mechanics is the most successful theory for describing the microworld of photons, atoms, and their aggregates. It is behind much of the successes of modern technology. It has deep philosophical implications to the fundamental nature of material reality. A few decades ago, it was also realized that it is connected to the computer science and information theory. With this understanding were born the new disciplines of quantum computing and quantum communication. The current book introduces the very exciting area of quantum communication, which lies at the intersection of quantum mechanics, information theory, and atomic physics. The relevant concepts of these disciplines are explained, and their implication for the task of unbreakably secure communication is elucidated. The mathematical formulation of various approaches has been explained. An attempt has been made to keep the exposition self-contained. A senior undergraduate with good mathematics and physics background should be able to follow the current thinking about these issues after understanding the material presented in this book.

•Jul 25, 2016•10 citations

A Short Introduction to Quantum Computing for Physicists

Oswaldo Zapata

These notes provide an introduction to standard topics on quantum computation and communication for those who already have a basic knowledge of quantum mechanics. The main target audience are professional physicists as well as advanced students of physics; however, engineers and computer scientists may also benefit from them.

arXiv:2306.09388•Jun 15, 2023•0 citations

A Survey of Quantum Machine Learning: Foundations, Algorithms, Frameworks, Data and Applications

Francesc Rodríguez-Díaz, David Gutiérrez‐Avilés, Alicia Troncoso +1 more

Quantum machine learning combines quantum computing with machine learning to solve complex computational problems more efficiently than classical approaches. This survey provides an introduction to the foundations, algorithms, frameworks, data and applications of quantum machine learning, serving as a resource for researchers and practitioners. We begin by reviewing existing surveys to identify gaps that this work addresses, followed by a detailed discussion of the foundational principles of quantum mechanics and machine learning essential for quantum machine learning. Key algorithms are examined, highlighting their mechanisms, advantages, and applications across various domains. Current frameworks and platforms for implementing quantum machine learning algorithms are explored, emphasizing their unique features and suitability for different contexts. Existing quantum datasets for practical usage are also reported and commented on. This survey also reviews over 135 articles, categorized into theoretical and practical contributions, to identify key advances, limitations, and application areas within quantum machine learning. Critical challenges such as hardware limitations, error rates, and scalability are analyzed to detect the obstacles that must be addressed for practical deployment. By synthesizing these elements into a structured overview, this survey aims at serving as both an introduction and a guide for advancing research and development in this disruptive field.

ACM Computing Surveys•Sep 11, 2025•28 citations

A State-of-the-art Review on Quantum Information Computing

R. Ku. Jena, Prabhat Mahanti

The subject of quantum computing brings ideas from classical information theory, computer science, and quantum physics. Quantum mechanics provide new computational paradigms that had not been imagined prior to the 1980's and whose power was not fully appreciated until the mid 1990's.This review aims to succinctly summarize not just quantum computing, but the whole subject of quantum information theory.

International Journal of Engineering•May 31, 2017•2 citations

Quantum Hamiltonian Complexity

Sevag Gharibian, Yichen Huang, Zeph A. Landau +1 more

Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem” to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.

arXiv:1401.3916•Foundations and Trends® in Theoretical Computer Science•Oct 13, 2015•144 citations
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum mechanics is the most successful theory for describing the microworld of photons, atoms, and their aggregates. It is behind much of the successes of modern technology. It has deep philosophical implications to the fundamental nature of material reality. A few decades ago, it was also realized that it is connected to the computer science and information theory. With this understanding were born the new disciplines of quantum computing and quantum communication. The current book introduces the very exciting area of quantum communication, which lies at the intersection of quantum mechanics, information theory, and atomic physics. The relevant concepts of these disciplines are explained, and their implication for the task of unbreakably secure communication is elucidated. The mathematical formulation of various approaches has been explained. An attempt has been made to keep the exposition self-contained. A senior undergraduate with good mathematics and physics background should be able to follow the current thinking about these issues after understanding the material presented in this book.
Quantum machine learning combines quantum computing with machine learning to solve complex computational problems more efficiently than classical approaches. This survey provides an introduction to the foundations, algorithms, frameworks, data and applications of quantum machine learning, serving as a resource for researchers and practitioners. We begin by reviewing existing surveys to identify gaps that this work addresses, followed by a detailed discussion of the foundational principles of quantum mechanics and machine learning essential for quantum machine learning. Key algorithms are examined, highlighting their mechanisms, advantages, and applications across various domains. Current frameworks and platforms for implementing quantum machine learning algorithms are explored, emphasizing their unique features and suitability for different contexts. Existing quantum datasets for practical usage are also reported and commented on. This survey also reviews over 135 articles, categorized into theoretical and practical contributions, to identify key advances, limitations, and application areas within quantum machine learning. Critical challenges such as hardware limitations, error rates, and scalability are analyzed to detect the obstacles that must be addressed for practical deployment. By synthesizing these elements into a structured overview, this survey aims at serving as both an introduction and a guide for advancing research and development in this disruptive field.
Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem” to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.