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

Entanglement and Interference Resources in Quantum Computation and Communication

Dan Stahlke

Published Jan 1, 2014• 0 citations
Publisher

Abstract

This dissertation contains results on three quite different topics. First, I investigate the entanglement resources required for two parties to jointly implement a unitary operation using local operations and classical communication (LOCC). If this resource is of smallest feasible Schmidt rank then it must be maximally entangled. If the Schmidt rank is higher, less entanglement may suffice. Second, I investigate the source of the “quantum speedup”. I quantify quantum interference and show that in order for a quantum computer to be significantly faster than a classical computer, it must make use of operations capable of producing large amounts of interference (or a large number of operations that can produce small amounts of interference). A quantum computer not making use of such a resource can be efficiently simulated by a classical computer. Third, I investigate zero-error source-channel coding. In this scenario, Alice wishes to convey a message to Bob through a noisy channel, with zero chance of error, in the case where Bob already has some prior knowledge regarding the message that is to be sent. For classical messages and classical channels, it was known that three graph invariants of Lovász, Szegedy, and Schrijver provide necessary conditions for this task. We show that this applies also when Alice and Bob make use of an entangled state, unifying and extending a series of previous results. Finally, I introduce a fully quantum version of source-channel coding where the message to be sent, the channel, and the side information are all quantum. Whereas the classical case makes use of graphs, the quantum case makes use of non-commutative graphs. I generalize the concept of graph homomorphism, as well as the Szegedy and Schrijver numbers, to non-commutative graphs and show that the necessary conditions for the classical case generalize to the quantum case. Using this theory, I construct a quantum channel whose one-shot zero-error entanglement assisted capacity can only be unlocked using a non-maximally entangled state, showing that in this case less is more when it comes to entanglement resources.

DOI
10.1184/r1/6716282

Related papers

Quantum Zero-Error Source-Channel Coding and Non-Commutative Graph Theory

Dan Stahlke

Alice and Bob receive a bipartite state (possibly entangled) from some finite collection or from some subspace. Alice sends a message to Bob through a noisy quantum channel such that Bob may determine the initial state, with zero chance of error. This framework encompasses, for example, teleportation, dense coding, entanglement assisted quantum channel capacity, and one-way communication complexity of function evaluation. With classical sources and channels, this problem can be analyzed using graph homomorphisms. We show this quantum version can be analyzed using homomorphisms on non-commutative graphs (an operator space generalization of graphs). Previously the Lovász ϑ number has been generalized to non-commutative graphs; we show this to be a homomorphism monotone, thus providing bounds on quantum source-channel coding. We generalize the Schrijver and Szegedy numbers, and show these to be monotones as well. As an application, we construct a quantum channel whose entanglement assisted zero-error one-shot capacity can only be unlocked using a non-maximally entangled state. These homomorphisms allow definition of a chromatic number for non-commutative graphs. Many open questions are presented regarding the possibility of a more fully developed theory.

arXiv:1405.5254•IEEE Transactions on Information Theory•Nov 2, 2015•42 citations

Zero-error source-channel coding with entanglement

Jop Briët, Harry Buhrman, Monique Laurent +2 more

We study a problem from zero-error information theory—a topic well-known for its rich connections to combinatorics [1,8,10–12,14]—in a setting where a sender and receiver may use quantum entanglement, one of the most striking features of quantum mechanics. The problem that we consider is the classical source-channel coding problem , where Alice and Bob are each given an input from a random source and get access to a noisy channel through which Alice can send messages to Bob. Their goal is to minimize the average number of channel uses per source input while allowing Bob to learn Alice’s inputs. Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. We also consider the source problem , the case where Alice can send messages to Bob without noise. We prove a lower bound on the rate of source codes with entanglement in terms of a variant of the Lovász theta number [10,13], a graph parameter given by a semidefinite program.

Scuola Normale Superiore eBooks•Jan 1, 2013•8 citations

Entanglement-Assisted Zero-Error Source-Channel Coding

Jop Briet, Harry Buhrman, Monique Laurent +2 more

We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as little as possible. In the zero-error regime, the optimal rates of source codes and channel codes are given by graph parameters known as the Witsenhausen rate and Shannon capacity, respectively. The Lovász theta number, a graph parameter defined by a semidefinite program, gives the best efficiently computable upper bound on the Shannon capacity and it also upper bounds its entanglement-assisted counterpart. At the same time, it was recently shown that the Shannon capacity can be increased if Alice and Bob may use entanglement. Here, we partially extend these results to the source-coding problem and to the more general source-channel coding problem. We prove a lower bound on the rate of entanglement-assisted source-codes in terms of Szegedy's number (a strengthening of the theta number). This result implies that the theta number lower bounds the entangled variant of the Witsenhausen rate. We also show that entanglement can allow for an unbounded improvement of the asymptotic rate of both classical source codes and classical source-channel codes. Our separation results use low-degree polynomials due to Barrington, Beigel and Rudich, Hadamard matrices due to Xia and Liu, and a new application of remote state preparation.

arXiv:1308.4283•IEEE Transactions on Information Theory•Dec 22, 2014•14 citations

Entanglement and Causal Relation in distributed quantum computation

Seiseki Akibue

In this thesis, we investigate two different aspects of entanglement and classical communication in distributed quantum computation (DQC). In the first part, we analyze implementable computation over a given quantum network resource by introducing a new concept, quantum network coding for quantum computation. We consider a setting of networks where quantum communication for each edge of a network is restricted to sending one-qubit, but classical communication is unrestricted. Specifically, we analyze implementable $k$-qubit unitary operations over a certain class of networks, called cluster networks. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for network coding. We also obtain necessary and sufficient conditions for the probabilistic implementability of unitary operations over cluster networks. In the second part, we investigate resource tradeoffs in DQC. First, we show that entanglement required for local state discrimination can be substituted by less entanglement by increasing the rounds of classical communication. Second, we develop a new framework of deterministic joint quantum operations by using a causal relation between the outputs and inputs of the local operations without predefined causal order, called "classical communication" without predefined causal order (CC*). We show that local operations and CC* (LOCC*) is equivalent to the separable operation (SEP). This result indicates that entanglement-assisted LOCC implementing SEP can be simulated by LOCC* without entanglement. We also investigate the relationship between LOCC* and another formalism for deterministic joint quantum operations without assuming predefined causal order based on the quantum process formalism. As a result, we construct an example of non-LOCC SEP by using LOCC*.

arXiv:2202.06518•Feb 14, 2022•1 citation

Multiparty Zero-Error Classical Channel Coding With Entanglement

Teresa Piovesan, Giannicola Scarpa, Christian Schaffner

We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.

arXiv:1403.5003•IEEE Transactions on Information Theory•Dec 10, 2014•4 citations

Quantum entanglement in non-local games, graph parameters and zero-error information theory

Scarpa, Giannicola

We study quantum entanglement and some of its applications in graph theory and zero-error information theory. In Chapter 1 we introduce entanglement and other fundamental concepts of quantum theory. In Chapter 2 we address the question of how much quantum correlations generated by entanglement can deviate from classical predictions. We focus on non-local games: experiments in which two players are separated and forbidden to communicate, and have to collaborate to accomplish a task. We give two games exhibiting quantum-classical separations close to optimal. Remarkably, our results in theoretical physics are inspired by theoretical computer science. Chapter 3 is dedicated to the study of quantum graph parameters. Well-known quantities such as the chromatic number and the independence number of a graph can be interpreted as parameters for non-local games. A definition of quantum graph parameters follows from this fact. We contribute to the field in a number of ways. Among other results, we find a surprising characterization of the quantum chromatic number that relates to the Kochen-Specker theorem, a result in the foundations of quantum mechanics. In Chapter 4, we move to zero-error information theory. We study the zero error capacity of a classical noisy channel when the sender and the receiver can use quantum entanglement. We initiate the study of the source problem and source-channel problem with entanglement and we find channels and sources that exhibit a strong divergence in quantum and classical behaviours. To do that, we use results in combinatorics, linear algebra, optimization and number theory.

•Jan 1, 2013•3 citations
This dissertation contains results on three quite different topics. First, I investigate the entanglement resources required for two parties to jointly implement a unitary operation using local operations and classical communication (LOCC). If this resource is of smallest feasible Schmidt rank then it must be maximally entangled. If the Schmidt rank is higher, less entanglement may suffice. Second, I investigate the source of the “quantum speedup”. I quantify quantum interference and show that in order for a quantum computer to be significantly faster than a classical computer, it must make use of operations capable of producing large amounts of interference (or a large number of operations that can produce small amounts of interference). A quantum computer not making use of such a resource can be efficiently simulated by a classical computer. Third, I investigate zero-error source-channel coding. In this scenario, Alice wishes to convey a message to Bob through a noisy channel, with zero chance of error, in the case where Bob already has some prior knowledge regarding the message that is to be sent. For classical messages and classical channels, it was known that three graph invariants of Lovász, Szegedy, and Schrijver provide necessary conditions for this task. We show that this applies also when Alice and Bob make use of an entangled state, unifying and extending a series of previous results. Finally, I introduce a fully quantum version of source-channel coding where the message to be sent, the channel, and the side information are all quantum. Whereas the classical case makes use of graphs, the quantum case makes use of non-commutative graphs. I generalize the concept of graph homomorphism, as well as the Szegedy and Schrijver numbers, to non-commutative graphs and show that the necessary conditions for the classical case generalize to the quantum case. Using this theory, I construct a quantum channel whose one-shot zero-error entanglement assisted capacity can only be unlocked using a non-maximally entangled state, showing that in this case less is more when it comes to entanglement resources.
Alice and Bob receive a bipartite state (possibly entangled) from some finite collection or from some subspace. Alice sends a message to Bob through a noisy quantum channel such that Bob may determine the initial state, with zero chance of error. This framework encompasses, for example, teleportation, dense coding, entanglement assisted quantum channel capacity, and one-way communication complexity of function evaluation. With classical sources and channels, this problem can be analyzed using graph homomorphisms. We show this quantum version can be analyzed using homomorphisms on non-commutative graphs (an operator space generalization of graphs). Previously the Lovász ϑ number has been generalized to non-commutative graphs; we show this to be a homomorphism monotone, thus providing bounds on quantum source-channel coding. We generalize the Schrijver and Szegedy numbers, and show these to be monotones as well. As an application, we construct a quantum channel whose entanglement assisted zero-error one-shot capacity can only be unlocked using a non-maximally entangled state. These homomorphisms allow definition of a chromatic number for non-commutative graphs. Many open questions are presented regarding the possibility of a more fully developed theory.
We study a problem from zero-error information theory—a topic well-known for its rich connections to combinatorics [1,8,10–12,14]—in a setting where a sender and receiver may use quantum entanglement, one of the most striking features of quantum mechanics. The problem that we consider is the classical source-channel coding problem , where Alice and Bob are each given an input from a random source and get access to a noisy channel through which Alice can send messages to Bob. Their goal is to minimize the average number of channel uses per source input while allowing Bob to learn Alice’s inputs. Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. We also consider the source problem , the case where Alice can send messages to Bob without noise. We prove a lower bound on the rate of source codes with entanglement in terms of a variant of the Lovász theta number [10,13], a graph parameter given by a semidefinite program.
We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as little as possible. In the zero-error regime, the optimal rates of source codes and channel codes are given by graph parameters known as the Witsenhausen rate and Shannon capacity, respectively. The Lovász theta number, a graph parameter defined by a semidefinite program, gives the best efficiently computable upper bound on the Shannon capacity and it also upper bounds its entanglement-assisted counterpart. At the same time, it was recently shown that the Shannon capacity can be increased if Alice and Bob may use entanglement. Here, we partially extend these results to the source-coding problem and to the more general source-channel coding problem. We prove a lower bound on the rate of entanglement-assisted source-codes in terms of Szegedy's number (a strengthening of the theta number). This result implies that the theta number lower bounds the entangled variant of the Witsenhausen rate. We also show that entanglement can allow for an unbounded improvement of the asymptotic rate of both classical source codes and classical source-channel codes. Our separation results use low-degree polynomials due to Barrington, Beigel and Rudich, Hadamard matrices due to Xia and Liu, and a new application of remote state preparation.
In this thesis, we investigate two different aspects of entanglement and classical communication in distributed quantum computation (DQC). In the first part, we analyze implementable computation over a given quantum network resource by introducing a new concept, quantum network coding for quantum computation. We consider a setting of networks where quantum communication for each edge of a network is restricted to sending one-qubit, but classical communication is unrestricted. Specifically, we analyze implementable kkk-qubit unitary operations over a certain class of networks, called cluster networks. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for network coding. We also obtain necessary and sufficient conditions for the probabilistic implementability of unitary operations over cluster networks. In the second part, we investigate resource tradeoffs in DQC. First, we show that entanglement required for local state discrimination can be substituted by less entanglement by increasing the rounds of classical communication. Second, we develop a new framework of deterministic joint quantum operations by using a causal relation between the outputs and inputs of the local operations without predefined causal order, called "classical communication" without predefined causal order (CC*). We show that local operations and CC* (LOCC*) is equivalent to the separable operation (SEP). This result indicates that entanglement-assisted LOCC implementing SEP can be simulated by LOCC* without entanglement. We also investigate the relationship between LOCC* and another formalism for deterministic joint quantum operations without assuming predefined causal order based on the quantum process formalism. As a result, we construct an example of non-LOCC SEP by using LOCC*.
We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.
We study quantum entanglement and some of its applications in graph theory and zero-error information theory. In Chapter 1 we introduce entanglement and other fundamental concepts of quantum theory. In Chapter 2 we address the question of how much quantum correlations generated by entanglement can deviate from classical predictions. We focus on non-local games: experiments in which two players are separated and forbidden to communicate, and have to collaborate to accomplish a task. We give two games exhibiting quantum-classical separations close to optimal. Remarkably, our results in theoretical physics are inspired by theoretical computer science. Chapter 3 is dedicated to the study of quantum graph parameters. Well-known quantities such as the chromatic number and the independence number of a graph can be interpreted as parameters for non-local games. A definition of quantum graph parameters follows from this fact. We contribute to the field in a number of ways. Among other results, we find a surprising characterization of the quantum chromatic number that relates to the Kochen-Specker theorem, a result in the foundations of quantum mechanics. In Chapter 4, we move to zero-error information theory. We study the zero error capacity of a classical noisy channel when the sender and the receiver can use quantum entanglement. We initiate the study of the source problem and source-channel problem with entanglement and we find channels and sources that exhibit a strong divergence in quantum and classical behaviours. To do that, we use results in combinatorics, linear algebra, optimization and number theory.