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

arXiv:1606.06801 · Electronic Proceedings in Theoretical Computer Science

The Information Content of Systems in General Physical Theories

Ciarán M. Lee, Matty J. Hoban

Published Jun 20, 2016• 10 citations
arXivHTMLPDF

Abstract

What kind of object is a quantum state? Is it an object that encodes an exponentially growing amount of information (in the size of the system) or more akin to a probability distribution? It turns out that these questions are sensitive to what we do with the information. For example, Holevo's bound tells us that n qubits only encode n bits of classical information but for certain communication complexity tasks there is an exponential separation between quantum and classical resources. Instead of just contrasting quantum and classical physics, we can place both within a broad landscape of physical theories and ask how non-quantum (and non-classical) theories are different from, or more powerful than quantum theory. For example, in communication complexity, certain (non-quantum) theories can trivialise all communication complexity tasks. In recent work [C. M. Lee and M. J. Hoban, Proc. Royal Soc. A 472 (2190), 2016], we showed that the immense power of the information content of states in general (non-quantum) physical theories is not limited to communication complexity. We showed that, in general physical theories, states can be taken as "advice" for computers in these theories and this advice allows the computers to easily solve any decision problem. Aaronson has highlighted the close connection between quantum communication complexity and quantum computations that take quantum advice, and our work gives further indications that this is a very general connection. In this work, we review the results in our previous work and discuss the intricate relationship between communication complexity and computers taking advice for general theories.

DOI
10.4204/eptcs.214.5

Related papers

How much classical information is carried by a quantum state? An approach inspired by Kolmogorov complexity

Doriano Brogioli

In quantum mechanics, a state is an element of a Hilbert space whose dimension exponentially grows with the increase of the number of particles (or qubits, in quantum computing). The vague question "is this huge Hilbert space really there?" has been rigorously formalized inside the computational complexity theory; the research suggests a positive answer to the question. Along this line, I give a definition of the (classical) information content of a quantum state, taking inspiration from the Kolmogorov complexity. I show that, for some well-known quantum circuits (having a number of gates polynomial in the number of qubits), the information content of the output state, evaluated according to my definition, is polynomial in the number of qubits. On the other hand, applying known results, it is possible to devise quantum circuits that generate much more complex states, having an exponentially-growing information content. A huge amount of classical information can be really present inside a quantum state, however, I show that this property is not necessarily exploited by quantum computers, not even by quantum algorithms showing an exponential speed-up with respect to classical computation.

arXiv:2204.02370•Apr 5, 2022•0 citations

Foundations of quantum theory and quantum information applications

Ernesto F. Galvão

This thesis establishes a number of connections between foundational issues in quantum theory, and some quantum information applications. It starts with a review of quantum contextuality and non-locality, multipartite entanglement characterisation, and of a few quantum information protocols. Quantum non-locality and contextuality are shown to be essential for different implementations of quantum information protocols known as quantum random access codes and quantum communication complexity protocols. I derive sufficient experimental conditions for tests of these quantum properties. I also discuss how the distribution of quantum information through quantum cloning processes can be useful in quantum computing. Regarding entanglement characterisation, some results are obtained relating two problems, that of additivity of the relative entropy of entanglement, and that of identifying different types of tripartite entanglement in the asymptotic regime of manipulations of many copies of a given state. The thesis ends with a description of an information processing task in which a single qubit substitutes for an arbitrarily large amount of classical communication. This result is interpreted in different ways: as a gap between quantum and classical computation space complexity; as a bound on the amount of classical communication necessary to simulate entanglement; and as a basic result on hidden-variable theories for quantum mechanics. I also show that the advantage of quantum over classical communication can be established in a feasible experiment.

arXiv:quant-ph/0212124•Dec 22, 2002•25 citations

Quantum encodings and applications to locally decodable codes and communication complexity

Iordanis Kerenidis, Umesh V. Vazirani

Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.

•Jan 1, 2004•5 citations

Epistemic View of Quantum States and Communication Complexity of Quantum Channels

A. Montina

The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating a process of state preparation, transmission through the channel and subsequent measurement. It establishes a limit on the power of quantum communication in terms of classical resources. We show that classical simulations employing a finite amount of communication can be derived from a special class of hidden variable theories where quantum states represent statistical knowledge about the classical state and not an element of reality. This special class has attracted strong interest very recently. The communication cost of each derived simulation is given by the mutual information between the quantum state and the classical state of the parent hidden variable theory. Finally, we find that the communication complexity for single qubits is smaller than 1.28 bits. The previous known upper bound was 1.85 bits.

arXiv:1206.2961•Physical Review Letters•Sep 12, 2012•28 citations

Quantum Communication Complexity (A Survey)

Gilles Brassard A

Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits --- unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In extreme cases, the effect of transmitting quantum bits cannot be achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement.

arXiv:quant-ph/0101005•Jan 1, 2001•10 citations

Interaction in Quantum Communication Complexity

Ashwin Nayak, Amnon Ta‐Shma, David Zuckerman

One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of conveying information with exponentially fewer qubits than possible classically. Moreover, these methods have a very simple structure---they involve little interaction between the communicating parties. We look more closely at the ways in which information encoded in quantum states may be manipulated, and consider the question as to whether every classical protocol may be transformed to a ``simpler'' quantum protocol of similar efficiency. By a simpler protocol, we mean a protocol that uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other applications as well.

arXiv:quant-ph/0005106•May 25, 2000•4 citations
What kind of object is a quantum state? Is it an object that encodes an exponentially growing amount of information (in the size of the system) or more akin to a probability distribution? It turns out that these questions are sensitive to what we do with the information. For example, Holevo's bound tells us that n qubits only encode n bits of classical information but for certain communication complexity tasks there is an exponential separation between quantum and classical resources. Instead of just contrasting quantum and classical physics, we can place both within a broad landscape of physical theories and ask how non-quantum (and non-classical) theories are different from, or more powerful than quantum theory. For example, in communication complexity, certain (non-quantum) theories can trivialise all communication complexity tasks. In recent work [C. M. Lee and M. J. Hoban, Proc. Royal Soc. A 472 (2190), 2016], we showed that the immense power of the information content of states in general (non-quantum) physical theories is not limited to communication complexity. We showed that, in general physical theories, states can be taken as "advice" for computers in these theories and this advice allows the computers to easily solve any decision problem. Aaronson has highlighted the close connection between quantum communication complexity and quantum computations that take quantum advice, and our work gives further indications that this is a very general connection. In this work, we review the results in our previous work and discuss the intricate relationship between communication complexity and computers taking advice for general theories.
In quantum mechanics, a state is an element of a Hilbert space whose dimension exponentially grows with the increase of the number of particles (or qubits, in quantum computing). The vague question "is this huge Hilbert space really there?" has been rigorously formalized inside the computational complexity theory; the research suggests a positive answer to the question. Along this line, I give a definition of the (classical) information content of a quantum state, taking inspiration from the Kolmogorov complexity. I show that, for some well-known quantum circuits (having a number of gates polynomial in the number of qubits), the information content of the output state, evaluated according to my definition, is polynomial in the number of qubits. On the other hand, applying known results, it is possible to devise quantum circuits that generate much more complex states, having an exponentially-growing information content. A huge amount of classical information can be really present inside a quantum state, however, I show that this property is not necessarily exploited by quantum computers, not even by quantum algorithms showing an exponential speed-up with respect to classical computation.
This thesis establishes a number of connections between foundational issues in quantum theory, and some quantum information applications. It starts with a review of quantum contextuality and non-locality, multipartite entanglement characterisation, and of a few quantum information protocols. Quantum non-locality and contextuality are shown to be essential for different implementations of quantum information protocols known as quantum random access codes and quantum communication complexity protocols. I derive sufficient experimental conditions for tests of these quantum properties. I also discuss how the distribution of quantum information through quantum cloning processes can be useful in quantum computing. Regarding entanglement characterisation, some results are obtained relating two problems, that of additivity of the relative entropy of entanglement, and that of identifying different types of tripartite entanglement in the asymptotic regime of manipulations of many copies of a given state. The thesis ends with a description of an information processing task in which a single qubit substitutes for an arbitrarily large amount of classical communication. This result is interpreted in different ways: as a gap between quantum and classical computation space complexity; as a bound on the amount of classical communication necessary to simulate entanglement; and as a basic result on hidden-variable theories for quantum mechanics. I also show that the advantage of quantum over classical communication can be established in a feasible experiment.
Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. On one hand, the ability of a quantum system to be in a superposition of states provides a way to encode an exponential amount of information in a quantum state. However, this information is accessible only indirectly via measurements. The goal of this thesis is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. (1) We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long standing open question in the area of quantum communication complexity. (2) We show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity. We resolve a main open question about the efficiency of Locally Decodable Codes by reducing the problem to one about quantum codes and solving the latter using tools from quantum information theory. This is the first example where quantum techniques are essential in resolving a purely classical question. (3) We investigate the power of quantum encodings in the area of cryptography. We study certain cryptographic primitives, such as Private Information Retrieval, Symmetrically-Private Information Retrieval and Coin Flipping.
The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating a process of state preparation, transmission through the channel and subsequent measurement. It establishes a limit on the power of quantum communication in terms of classical resources. We show that classical simulations employing a finite amount of communication can be derived from a special class of hidden variable theories where quantum states represent statistical knowledge about the classical state and not an element of reality. This special class has attracted strong interest very recently. The communication cost of each derived simulation is given by the mutual information between the quantum state and the classical state of the parent hidden variable theory. Finally, we find that the communication complexity for single qubits is smaller than 1.28 bits. The previous known upper bound was 1.85 bits.
Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits --- unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In extreme cases, the effect of transmitting quantum bits cannot be achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement.
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of conveying information with exponentially fewer qubits than possible classically. Moreover, these methods have a very simple structure---they involve little interaction between the communicating parties. We look more closely at the ways in which information encoded in quantum states may be manipulated, and consider the question as to whether every classical protocol may be transformed to a ``simpler'' quantum protocol of similar efficiency. By a simpler protocol, we mean a protocol that uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other applications as well.