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:2609.15757

Optimal entanglement-assisted source coding under a balanced-difference promise

Julius A. Zeiss

quant-phmath-phSubmitted Sep 14, 2026• Announced Sep 15, 2026• 0 citations
arXivHTMLPDF

Abstract

Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits. We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it. Alice does not know the pair and must enable Bob to identify her word without error using shared entanglement and one classical message. The candidates satisfy a balanced-difference promise: for words in $\mathbb{Z}_q^n$ with $n=q\ell$, each residue modulo $q$ occurs exactly $\ell$ times in their coordinatewise difference. For all integers $q\geq2$ and $\ell\geq1$, we prove that the task requires exactly $n$ messages when $(q-1)\ell$ is even and two messages when it is odd. These minima allow arbitrary finite-dimensional shared states independent of the inputs and arbitrary local measurements. In even parity, this establishes optimality of an existing entanglement-assisted protocol. In odd parity, an explicit deterministic protocol achieves the optimum of one bit without entanglement. Our proof combines Fourier analysis with a combinatorial counting argument to determine the smallest eigenvalue of the associated graphs. In even parity, this resolves the spectral assertion of Cao et al.'s Conjecture 6.3 for balanced cyclic generalized Hadamard graphs. Together with an explicit odd-parity bipartition, this determines the quantum chromatic number as $n$ in even parity and $2$ in odd parity, where the classical chromatic number is also $2$. All lemmas, theorems, and corollaries are formalized and verified in Lean.

Comments
33 pages, 13 pages appendix, 10 figures

Related papers

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•24 citations

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•54 citations

A Coding Theorem for Bipartite Unitaries in Distributed Quantum Computation

Eyuri Wakakuwa, Akihito Soeda, Mio Murao

We analyze implementations of bipartite unitaries by means of local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in the quantum Shannon theory to study an asymptotic scenario, in which two distant parties perform the same bipartite unitary on infinitely many pairs of inputs. We analyze minimum cost of entanglement and classical communication per copy. For two-round LOCC protocols, we derive a single-letter formula for the minimum cost of entanglement and classical communication, under an additional requirement that the error converges to zero faster than 1/n4, where n is the number of input pairs. The formula is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which can be computed by a finite-step algorithm. We also derive a lower bound on the minimum cost of resources, which applies for protocols with arbitrary number of rounds.

arXiv:1505.04352•IEEE Transactions on Information Theory•May 29, 2017•22 citations

A coding theorem for bipartite unitaries in distributed quantum computation

Eyuri Wakakuwa, Akihito Soeda, Mio Murao

We analyze implementations of bipartite unitaries in a distributed quantum computation setting using local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in quantum Shannon theory to study an asymptotic scenario in which the two distant parties perform the same bipartite unitary on infinitely many pairs of input states generated by a completely random i.i.d. (independent and identically distributed) quantum information source. We analyze the minimum costs of resources of entanglement and classical communication per copy. For protocols consisting of two-round LOCC, we prove that an achievable rate tuple of costs of entanglement and classical communication is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which is conjectured to be optimal as well. The Markovianizing cost can be computed by a finite-step algorithm.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•7 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•9 citations

Classical communication with an exact photon budget: finite-block limits and optimal input ensembles

Zixuan He

What can be transmitted with a fixed photon supply? An optical source that supplies exactly K photons across n modes poses a concrete communication problem: how many messages can it transmit at a chosen error probability, and which input states make the best use of those photons? This paper gives directly evaluable coding bounds for pure loss and identifies the exact optimal input ensembles for identical noisy Gaussian channels. The results allow researchers to assess finite optical blocks, quantify the information cost of fixing the photon supply, and determine when entanglement between separately constrained blocks can be dispensed with. Every message is supported on the same exact K-photon sector. Within that sector, encoding may use arbitrary mixed states and entanglement among modes, and the receiver may perform a joint measurement. Communication is unassisted. All logarithms below are natural; information is measured in nats. Finite-message bounds and the optimal third-order rate For n ≥ 2 identical pure-loss channels of transmissivity 0 < η < 1 and K ≥ 1, the number L of surviving photons has the same binomial distribution for every encoded state. Define \[p_\ell=\binom K\ell\eta^\ell(1-\eta)^{K-\ell},\qquad d_{n,\ell}=\binom{n+\ell-1}{\ell}.\] If ps*(M;n,K) is the best average success probability for M equiprobable messages, then \[\sum_{\ell=0}^{K}p_\ell\left[1-\frac{M-1}{d_{n,\ell}}\right]_+\le p_{\mathrm s}^{*}(M;n,K)\le\sum_{\ell=0}^{K}p_\ell\min\!\left\{1,\frac{d_{n,\ell}}{M}\right\}.\] Here [x]+ = max{x,0}. The lower bound provides an achievable guarantee; the upper bound limits every admissible code. Evaluating both sums brackets the performance at a specified photon supply and block length. Their proof has a simple physical interpretation: surviving photons determine the available output dimension, while one collective-mode codebook works across all possible survivor counts. For fixed E > 0, fixed error tolerance 0 < ε < 1, Kn = ⌊nE⌋ and en = Kn/n, the bounds determine the largest message count through third order: \[\log M^*(n,K_n,\varepsilon)=ng(\eta e_n)+\sqrt{n\eta(1-\eta)e_n}\,h(\eta e_n)\Phi_{\mathrm N}^{-1}(\varepsilon)-\tfrac12\log n+O(1).\] Here g(x) = (x+1)log(x+1) − x log x, h(x) = log(1+1/x), and ΦN is the standard normal distribution function. This fixes both the fluctuation scale and the optimal −½ log n correction. The finite bounds also yield the exact decay exponent of success above capacity and a matching error exponent on a specified interval below capacity. Which inputs are optimal under Gaussian noise? For n identical nonidentity gauge-covariant Gaussian channels, with thermal photon means transformed as r ↦ ar+b, a > 0 and b ≥ max{0,a−1}, the paper determines the exact fixed-photon Holevo optimum and every ensemble attaining it. Each optimal letter places all K photons in one collective mode: \[|K,u\rangle=\frac{\left(\sum_{j=1}^{n}u_j a_j^\dagger\right)^K}{\sqrt{K!}}|0\rangle,\qquad \sum_j|u_j|^2=1.\] An ensemble is optimal precisely when almost all its letters have this form and its average is uniform on the K-photon sector. A finite weighted optimal ensemble exists. These collective modes may themselves extend across, and be entangled among, physical optical modes. Thus the characterization identifies the structure to optimize without imposing a Gaussian-input restriction. The central proof step combines different loss histories that end in the same output photon sector. A common ordering of the comparison eigenstates allows the separate majorization bounds to be combined. For pure loss, a quantitative rigidity estimate further converts a small Holevo deficit into closeness to collective-mode number states. Resource cost and communication across blocks At fixed positive photon density and fixed nonidentity Gaussian noise, requiring an exact photon supply incurs a Holevo penalty of ½ log n plus an explicitly determined constant, relative to the usual mean-energy value. The paper separates this cost into photon-count uncertainty and the mismatch from a thermal output distribution. For separately constrained blocks of quantum-limited loss, quantum-limited amplification or entanglement-breaking Gaussian noise, the one-block Holevo values add exactly. Every optimal letter is a product of blockwise collective-mode number states, and the repeated-block unassisted classical capacity equals the one-block Holevo value. The low-rate reliability interval outside the matching range and repeated-block additivity for intermediate Gaussian noise remain open.

•Oct 13, 2026•0 citations
Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits. We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it. Alice does not know the pair and must enable Bob to identify her word without error using shared entanglement and one classical message. The candidates satisfy a balanced-difference promise: for words in Zqn\mathbb{Z}_q^nZqn​ with n=qℓn=q\elln=qℓ, each residue modulo qqq occurs exactly ℓ\ellℓ times in their coordinatewise difference. For all integers q≥2q\geq2q≥2 and ℓ≥1\ell\geq1ℓ≥1, we prove that the task requires exactly nnn messages when (q−1)ℓ(q-1)\ell(q−1)ℓ is even and two messages when it is odd. These minima allow arbitrary finite-dimensional shared states independent of the inputs and arbitrary local measurements. In even parity, this establishes optimality of an existing entanglement-assisted protocol. In odd parity, an explicit deterministic protocol achieves the optimum of one bit without entanglement. Our proof combines Fourier analysis with a combinatorial counting argument to determine the smallest eigenvalue of the associated graphs. In even parity, this resolves the spectral assertion of Cao et al.'s Conjecture 6.3 for balanced cyclic generalized Hadamard graphs. Together with an explicit odd-parity bipartition, this determines the quantum chromatic number as nnn in even parity and 222 in odd parity, where the classical chromatic number is also 222. All lemmas, theorems, and corollaries are formalized and verified in Lean.
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.
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 analyze implementations of bipartite unitaries by means of local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in the quantum Shannon theory to study an asymptotic scenario, in which two distant parties perform the same bipartite unitary on infinitely many pairs of inputs. We analyze minimum cost of entanglement and classical communication per copy. For two-round LOCC protocols, we derive a single-letter formula for the minimum cost of entanglement and classical communication, under an additional requirement that the error converges to zero faster than 1/n4, where n is the number of input pairs. The formula is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which can be computed by a finite-step algorithm. We also derive a lower bound on the minimum cost of resources, which applies for protocols with arbitrary number of rounds.
We analyze implementations of bipartite unitaries in a distributed quantum computation setting using local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in quantum Shannon theory to study an asymptotic scenario in which the two distant parties perform the same bipartite unitary on infinitely many pairs of input states generated by a completely random i.i.d. (independent and identically distributed) quantum information source. We analyze the minimum costs of resources of entanglement and classical communication per copy. For protocols consisting of two-round LOCC, we prove that an achievable rate tuple of costs of entanglement and classical communication is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which is conjectured to be optimal as well. The Markovianizing cost can be computed by a finite-step algorithm.
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.
What can be transmitted with a fixed photon supply? An optical source that supplies exactly K photons across n modes poses a concrete communication problem: how many messages can it transmit at a chosen error probability, and which input states make the best use of those photons? This paper gives directly evaluable coding bounds for pure loss and identifies the exact optimal input ensembles for identical noisy Gaussian channels. The results allow researchers to assess finite optical blocks, quantify the information cost of fixing the photon supply, and determine when entanglement between separately constrained blocks can be dispensed with. Every message is supported on the same exact K-photon sector. Within that sector, encoding may use arbitrary mixed states and entanglement among modes, and the receiver may perform a joint measurement. Communication is unassisted. All logarithms below are natural; information is measured in nats. Finite-message bounds and the optimal third-order rate For n ≥ 2 identical pure-loss channels of transmissivity 0 < η < 1 and K ≥ 1, the number L of surviving photons has the same binomial distribution for every encoded state. Define pℓ=(Kℓ)ηℓ(1−η)K−ℓ,dn,ℓ=(n+ℓ−1ℓ).p_\ell=\binom K\ell\eta^\ell(1-\eta)^{K-\ell},\qquad d_{n,\ell}=\binom{n+\ell-1}{\ell}.pℓ​=(ℓK​)ηℓ(1−η)K−ℓ,dn,ℓ​=(ℓn+ℓ−1​). If ps*(M;n,K) is the best average success probability for M equiprobable messages, then ∑ℓ=0Kpℓ[1−M−1dn,ℓ]+≤ps∗(M;n,K)≤∑ℓ=0Kpℓmin⁡ ⁣{1,dn,ℓM}.\sum_{\ell=0}^{K}p_\ell\left[1-\frac{M-1}{d_{n,\ell}}\right]_+\le p_{\mathrm s}^{*}(M;n,K)\le\sum_{\ell=0}^{K}p_\ell\min\!\left\{1,\frac{d_{n,\ell}}{M}\right\}.∑ℓ=0K​pℓ​[1−dn,ℓ​M−1​]+​≤ps∗​(M;n,K)≤∑ℓ=0K​pℓ​min{1,Mdn,ℓ​​}. Here [x]+ = max{x,0}. The lower bound provides an achievable guarantee; the upper bound limits every admissible code. Evaluating both sums brackets the performance at a specified photon supply and block length. Their proof has a simple physical interpretation: surviving photons determine the available output dimension, while one collective-mode codebook works across all possible survivor counts. For fixed E > 0, fixed error tolerance 0 < ε < 1, Kn = ⌊nE⌋ and en = Kn/n, the bounds determine the largest message count through third order: log⁡M∗(n,Kn,ε)=ng(ηen)+nη(1−η)en h(ηen)ΦN−1(ε)−12log⁡n+O(1).\log M^*(n,K_n,\varepsilon)=ng(\eta e_n)+\sqrt{n\eta(1-\eta)e_n}\,h(\eta e_n)\Phi_{\mathrm N}^{-1}(\varepsilon)-\tfrac12\log n+O(1).logM∗(n,Kn​,ε)=ng(ηen​)+nη(1−η)en​​h(ηen​)ΦN−1​(ε)−21​logn+O(1). Here g(x) = (x+1)log(x+1) − x log x, h(x) = log(1+1/x), and ΦN is the standard normal distribution function. This fixes both the fluctuation scale and the optimal −½ log n correction. The finite bounds also yield the exact decay exponent of success above capacity and a matching error exponent on a specified interval below capacity. Which inputs are optimal under Gaussian noise? For n identical nonidentity gauge-covariant Gaussian channels, with thermal photon means transformed as r ↦ ar+b, a > 0 and b ≥ max{0,a−1}, the paper determines the exact fixed-photon Holevo optimum and every ensemble attaining it. Each optimal letter places all K photons in one collective mode: ∣K,u⟩=(∑j=1nujaj†)KK!∣0⟩,∑j∣uj∣2=1.|K,u\rangle=\frac{\left(\sum_{j=1}^{n}u_j a_j^\dagger\right)^K}{\sqrt{K!}}|0\rangle,\qquad \sum_j|u_j|^2=1.∣K,u⟩=K!​(∑j=1n​uj​aj†​)K​∣0⟩,∑j​∣uj​∣2=1. An ensemble is optimal precisely when almost all its letters have this form and its average is uniform on the K-photon sector. A finite weighted optimal ensemble exists. These collective modes may themselves extend across, and be entangled among, physical optical modes. Thus the characterization identifies the structure to optimize without imposing a Gaussian-input restriction. The central proof step combines different loss histories that end in the same output photon sector. A common ordering of the comparison eigenstates allows the separate majorization bounds to be combined. For pure loss, a quantitative rigidity estimate further converts a small Holevo deficit into closeness to collective-mode number states. Resource cost and communication across blocks At fixed positive photon density and fixed nonidentity Gaussian noise, requiring an exact photon supply incurs a Holevo penalty of ½ log n plus an explicitly determined constant, relative to the usual mean-energy value. The paper separates this cost into photon-count uncertainty and the mismatch from a thermal output distribution. For separately constrained blocks of quantum-limited loss, quantum-limited amplification or entanglement-breaking Gaussian noise, the one-block Holevo values add exactly. Every optimal letter is a product of blockwise collective-mode number states, and the repeated-block unassisted classical capacity equals the one-block Holevo value. The low-rate reliability interval outside the matching range and repeated-block additivity for intermediate Gaussian noise remain open.