Rigidity of superdense coding

The first result in our paper is to show that superdense coding is rigid: any protocol that accomplishes this task is “locally equivalent” to the Bennett-Wiesner protocol. We model arbitrary protocols for superdense coding in the following manner: Alice and Bob share a density matrix $\tau$ on a bipartite Hilbert space $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, where we assume without loss of generality that $\mathcal{H}_{A}$ factors into $\mathcal{H}_{A^{\prime}}\otimes\mathcal{H}_{A^{\prime\prime}}$ where $\mathcal{H}_{A^{\prime\prime}}$ is isomorphic to ${\mathbb{C}}^{2}$. Given an input $i\in\{1,2,3,4\}$, Alice applies a unitary operator $U_{i}$ (called an encoding operator) to her share of $\tau$ (with support in the space $\mathcal{H}_{A}$), sends the qubit $A^{\prime\prime}$ to Bob, and Bob then performs an optimal distinguishing measurement on the Hilbert space $\mathcal{H}_{A^{\prime\prime}}\otimes\mathcal{H}_{B}$ to determine what the input $i$ was. See Figure 1 for an illustration of a general superdense coding protocol.

A priori it appears daunting to characterize the structure of an arbitrary superdense coding protocol. For one, the dimension of the spaces $\mathcal{H}_{A^{\prime}}$ and $\mathcal{H}_{B}$ are unbounded, and the state $\tau$ is uncharacterized. Furthermore, the encoding unitary operators $U_{i}$ can be extremely complicated, potentially performing complex entangling operations between the space $\mathcal{H}_{A^{\prime}}$ and $\mathcal{H}_{A^{\prime\prime}}$ (the qubit to be sent over to Bob). However, the property of being a superdense coding protocol is extremely constraining. Theorem 1.1 gives a precise characterization of how an arbitrary superdense protocol is locally equivalent to the canonical Bennett-Wiesner protocol. In the statement of the theorem, “$=_{\tau^{\prime}}$” denotes equality of two unitary operators with respect to the state $\tau^{\prime}$; in other words, $C=_{\rho}D$ means that $C\rho C^{*}=D\rho D^{*}$.

Theorem 1.1 can be interpreted as expressing rigidity for superdense coding in the following way: given an arbitrary protocol $(\tau,(U_{i}))$ for superdense coding, there exists local isometries $V,W$ where if Alice applies $V$ and Bob applies $W$ to their share of $\tau$, then an EPR pair is extracted with an auxiliary state $\rho$ remaining. By pre-applying $V^{*}$ to Alice’s unitary operators $U_{i}$, we discover that $U_{i}V^{*}$ has a very regular form: operationally, it can be interpreted as performing some projective measurement $\{P_{r}\}$ on Alice’s part of the auxiliary state $\rho$ to obtain some outcome $r$ in a set $\mathcal{R}$, and then based on $r$, applying a rotated version of the standard Bennett-Wiesner superdense coding protocol to Alice’s part of the EPR pair. Finally, after sending her EPR qubit, Alice then applies some unitary operator $C_{i}$ on her remaining qubits (which does not affect Bob’s measurement in any way). This considerably strengthens and extends the characterization of “tight” superdense coding protocols due to Vollbrecht and Werner [VW00, Lemma 3] (see also Ref. [Wer01]); they studied protocols in which the shared entangled state $\tau$ is a state on ${\mathbb{C}}^{2}\otimes{\mathbb{C}}^{2}$ (or on ${\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d}$ in the case of $d$-dimensional superdense coding protocols; see Section 1.2). This difference would be significant in a cryptographic setting; in the context of quantum key distribution, this is the difference between the device-independent and semi-device-independent settings.

The proof of Theorem 1.1 is given in Section 3. It proceeds via a number of reductions: first, using an information-theoretic argument, we show every superdense coding protocol $(\tau,(U_{i}))$ is locally equivalent to one that uses an EPR pair in the state $\tau$. Given this, we then show that each of the encoding operators $U_{i}$ can be individually block-diagonalized with respect to the EPR pair. Finally, we show that the blocks across the different encoding operators $U_{i}$ can be “matched up” in a way that they correspond to the Pauli matrices. Each of these steps requires carefully deducing the structure imposed on the state and the encoding operators by the correctness of the protocol.

We then consider the generalization of superdense coding to communicating more than $2$ classical bits. Specifically, we consider protocols for communicating one of $d^{2}$ possible messages by sending a $d$-dimensional quantum system over the channel — we call these $d$-dimensional superdense coding protocols. A canonical protocol for $d$-dimensional superdense coding is as follows: the players share a $d$-dimensional maximally entangled state $|\upphi_{d}\rangle\coloneqq\frac{1}{\sqrt{d}}\sum_{e=0}^{d-1}|e\rangle|e\rangle$, and given message $i\in[d^{2}]$, Alice applies a unitary operator $E_{i}$ to her share of $|\upphi_{d}\rangle$, and sends it over to Bob. The family of unitary operators $\{E_{i}\}$ can be any orthogonal unitary basis for the space of $d\times d$ matrices. (The orthogonality property means that $\operatorname{Tr}(E_{i}^{*}E_{j})=0$ if and only if $i\neq j$.) An example of such a basis is the set of Heisenberg-Weyl operators. In dimension $d$, these are a set of $d\times d$ matrices $\{P_{i,j}:0\leq i,j<d\}$ defined as follows. Let $\omega_{d}\coloneqq\exp\left(\frac{2\pi{\mathrm{i}}}{d}\right)$ be a primitive $d$th root of unity. For $i,j\in\{0,1,2,\ldots,d-1\}$, let $P_{i,j}={\mathrm{X}}^{i}_{d}{\mathrm{Z}}^{j}_{d}$ where ${\mathrm{X}}_{d}\coloneqq\sum_{k=0}^{d-1}|k+1\,(\mathrm{mod}\,d)\rangle\!\langle k|$ is the “shift” operator, and ${\mathrm{Z}}_{d}\coloneqq\sum_{k=0}^{d-1}\omega^{k}_{d}\,|k\rangle\!\langle k|$ is the “clock” operator. Does the rigidity phenomenon also extend to dimensions $d$ larger than $2$?

The second result of this paper is that $d$-dimensional superdense coding for $d\geq 3$ is not rigid in the same sense as Theorem 1.1: there are $d$-dimensional superdense coding protocols which are not locally equivalent to each other. This is because in dimensions three and higher there are inequivalent orthogonal unitary bases. (In contrast, all orthogonal unitary bases in dimension two are equivalent to the Pauli matrices.) Here, equivalence between two unitary bases $\{E_{i}\}$ and $\{F_{i}\}$ means there exist unitary operators $U,V$ such that for all $i$, we have $F_{i}=\alpha_{i}UE_{i}V$ for some choice of complex phase $\alpha_{i}$.

The uniqueness of orthogonal unitary bases was first studied by Vollbrecht and Werner [VW00], and the existence of non-equivalent orthogonal unitary bases for all dimensions greater than $2$ was observed in follow-up work by Werner [Wer01]. (We elaborate on prior work on the topic in Section 4.2.) Werner described, without proof, how non-equivalent bases may be constructed. We present explicit constructions of such bases in Section 4. The construction for $d\geq 4$ is based on the observation that the shift operator ${\mathrm{X}}_{d}$ corresponds to a perfect matching in $K_{d,d}$, the complete bipartite graph. Moreover, its powers $\left\{{\mathrm{X}}_{d}^{i}:0\leq i<d\right\}$ correspond to a partition of the edge set of $K_{d,d}$ into $d$ disjoint perfect matchings. By replacing this partition with another carefully chosen such partition, we obtain an orthogonal unitary basis that is not equivalent to the clock and shift construction. The proof of non-equivalence involves comparing the spectra of the operators in the two bases, taking into account the complex phase and unitary operators that witness a potential equivalence map. For $d=3$, we follow a construction described by Werner [Wer01]. We prove non-equivalence to the clock and shift basis by showing that the resulting basis is not a commutative projective group (again accounting for a potential equivalence map).

In a previous version of this paper, we conjectured that rigidity for higher dimensional superdense coding holds up to choosing orthogonal unitary bases [NY20, Conjecture 1.3]. That is, every $d$-dimensional superdense coding protocol is locally equivalent (in the sense of Theorem 1.1) to one where Alice and Bob share an entangled state $\rho^{A^{\prime}B^{\prime}}\otimes|\upphi_{d}\rangle\!\langle\upphi_{d}|^{A^{\prime\prime}B^{\prime\prime}}$ for some density matrix $\rho^{A^{\prime}B^{\prime}}$, and Alice’s encoding operators are of the form

where $\{P_{r}\}$ is a set of pairwise orthogonal projectors that sum to the identity on $\mathcal{H}_{A^{\prime}}$ and for every $r$, the set $\{E_{r,i}\}_{i\in[d^{2}]}$ is an orthogonal unitary basis for the space of $d\times d$ complex matrices. This would be a natural extension of the statement of Theorem 1.1 to the case of general $d\geq 2$ where the registers $A^{\prime}B^{\prime}$ are treated as a source of “shared randomness” to help Alice and Bob synchronize their choice of orthogonal unitary basis.

We can show that when the shared entangled state between Alice and Bob is a pure state in $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$, then this conjecture holds (see Section 4.1): up to local unitary operators, the shared state is necessarily the maximally entangled state $|\upphi_{d}\rangle$ of local dimension $d$, and the encoding operators $\{U_{i}\}$ necessarily form an orthogonal unitary basis. However, this conjecture is false for protocols where Alice sends only a part of her entangled state. In work subsequent to ours, Farkas, Kaniewski, and Nayak [FKN22] show that there exist infinitely many superdense coding protocols that are not locally equivalent to a protocol of the form described in the conjecture. In particular, in these counterexample protocols Alice may perform a complicated entangling operation between her message and the rest of her state, rather than just treating the ancilla system as a source of shared randomness.

Finally, we consider probabilistic protocols for $d$-dimensional superdense coding, where Bob’s decoding only needs to succeed with high probability. In particular, we say that $(\tau,(U_{i}))$ is a $(d,\varepsilon)$-superdense coding protocol if Bob is able to decode Alice’s message $i$ with probability at least $1-\varepsilon$, for all $i$. We focus on the case where Alice and Bob share an entangled state in $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ (i.e., have local dimension $d$). As mentioned previously, in the exact case $\varepsilon=0$, their shared state is necessarily the maximally entangled state and Alice’s encoding unitary operators form an orthogonal unitary basis. We conjecture that even in the probabilistic setting, this characterization of $d$-dimensional superdense coding protocols is robust, in the following sense.

We note that the choice of the normalized Hilbert-Schmidt norm in the statement of 1.3 is somewhat arbitrary; one can also consider other formulations of the conjecture with other norms (such as the spectral norm, etc.).

The last part of our paper analyzes a possible challenge to 1.3 proposed by Aram Harrow. Consider the following probabilistic construction for a potential $(d,\varepsilon)$-superdense coding protocol: independently sample $d^{2}$ matrices ${\bm{U}}_{1},\ldots,{\bm{U}}_{d^{2}}$ from the Haar measure on ${\mathsf{U}}({\mathbb{C}}^{d})$, the group of $d\times d$ complex unitary matrices. Let $\tau\coloneqq|\upphi_{d}\rangle\!\langle\upphi_{d}|$ denote the $d$-dimensional maximally entangled state. How well does the protocol $(\tau,({\bm{U}}_{i}))$ accomplish superdense coding?

In classical and quantum communication, many tasks can be performed near-optimally via probabilistically constructed protocols. See, e.g., the text by Wilde [Wil13] for examples from Shannon theory. A simple example from communication complexity is the task of quantum fingerprinting [BCWdW01], which enables checking whether two $n$-bit strings $x$ and $y$ are equal by only comparing two $\mathrm{O}(\log n)$-qubit fingerprints of the strings. It can be shown that picking random $\mathrm{O}(\log n)$-qubit states for each $n$-bit string $x$ yields a good quantum fingerprinting protocol.

Let ${\bm{\Pi}}_{d}$ denote the random superdense protocol specified by $(\upphi_{d},({\bm{U}}_{i}))$. Note that the error ${\bm{\varepsilon}}$ of ${\bm{\Pi}}_{d}$, when averaged over the choice of random unitaries $({\bm{U}}_{i})$, is some function of $d$. We first argue that the conjecture implies that the error of a random superdense coding protocol, when averaged over the choice of $({\bm{U}}_{i})$, cannot be too small:

Put another way, it cannot be that both 1.3 is true and also the random superdense protocol has error vanishing so quickly such that $\delta_{2}({\bm{\varepsilon}})$ is smaller than $(2d)^{-2}$, on average. Due to the concentration of measure phenomenon for Haar-random states and unitary operators (as expressed by, e.g., the Lévy-like property in Theorem 5.5), it is plausible a priori that the average error ${\bm{\varepsilon}}$, and therefore also $\delta_{2}({\bm{\varepsilon}})$, scale as $\mathrm{o}(d^{-2})$. Thus, the random superdense protocol is potentially a counterexample to 1.3.

We show that this probabilistic construction does not yield a good superdense coding protocol: with overwhelmingly high probability over the choice of random unitary operators $(U_{i})$, the protocol has a nonzero probability of error that is independent of $d$. Thus, 1.3 is not ruled out by the random protocol construction.

We prove Theorem 1.5 by showing that the distinguishability of the ensemble of random states $\{({\bm{U}}_{i}\otimes\mathds{1})|\upphi_{d}\rangle\}_{i\in[d^{2}]}$ is bounded away from $1$ (with high probability). The generalized Holevo-Curlander bounds [Kho79, Cur79, ON99, Tys09b] relate the distinguishability of an ensemble $\{(p_{i},\rho_{i})\}$ to the quantity

Our analysis of this quantity is largely inspired by work due to Montanaro [Mon07] on the distinguishability of random pure quantum states. However, extending his approach to the ensemble of interest to us—one consisting of random maximally entangled states—involves significant technical difficulties. The approach involves relating the distinguishability of an ensemble of states to the spectrum of the ensemble average. In the case of Haar-random pure states, the ensemble average is well approximated by the ensemble average of unnormalized complex gaussian vectors with suitably chosen variance. The spectrum of such matrices in the asymptotic limit is given by the Marčenko-Pastur Theorem from random matrix theory. In our case, the entries of the random vectors in the ensemble are not independent. We instead bound the generalized Holevo-Curlander quantity in Equation 1.1 by employing a recent generalization of the Marčenko-Pastur Theorem due to Yaskov [Yas16]. (The theorem was proven for ensembles of random real vectors. We verify that its proof also extends to complex random vectors with analogous properties.) In the process, we show that random maximally entangled states satisfy a pseudo-isotropy condition that suffices for the theorem to hold.

A subtlety in the use of the Marčenko-Pastur law is that we would like to deduce the convergence of a sequence of means to the mean of the limiting distribution from the convergence of a sequence of distributions. This does not necessarily hold in general. In order to prove such a relation between the two forms of convergence, we show that random maximally entangled states are sub-gaussian. This allows us to draw on a generalization of the Bai-Yin Theorem, which bounds the norm of matrices whose columns are given by i.i.d. sub-gaussian vectors. We thus show that the norm of the ensemble average has an exponentially decaying tail, which in turn guarantees the form of convergence we seek.

We believe the techniques used in our analysis are of independent interest. In fact, the subtlety mentioned above was overlooked by Montanaro; the ideas we develop may also be used to close a gap in his analysis (see Section 5.4 for the details).

In this paper we have initiated the study of rigidity phenomena in superdense coding protocols. Given its importance in quantum Shannon theory, our study may shed new light on protocols based on superdense coding. The power of entanglement as a resource in distributed quantum computation, in particular in two-party communication complexity, remains a mystery. The rigidity theorem we establish (Theorem 1.1) gives a complete picture for a simple but fundamental task. The property shown in the analysis of random superdense coding protocols (Theorem 1.5) may also be interpreted as placing a limit on how closely a sequence of random unitary operators approximate an orthogonal basis. This may be of relevance to the theory of error-correction, where unitary error bases play a central role.

We list several open questions that arise from this work:

1. 1.

   Is 1.3 true? Does a robust version of Theorem 1.1 hold?

2. 2.

   Do $d$-dimensional superdense coding protocols, in which the shared state between Alice and Bob may have local dimension larger than $d$, also exhibit some non-trivial form of rigidity?

3. 3.

   Does rigidity also hold for quantum teleportation, a task that is “dual” to superdense coding? Can this be derived in a black-box way from the rigidity of superdense coding?

4. 4.

   Are there any connections between the QRAC rigidity results of [TKV⁺18, FK19] and our results on the rigidity of superdense coding?

5. 5.

   What other quantum information processing tasks have the rigidity property?

We believe the investigation of these questions will lead to significant new insights into the nature of quantum information, with wide ranging ramifications.

We refer the reader to texts such as [NC11, Wat18, Wil13] for the basics of quantum information, and mention some notational conventions here.

We write $\mathds{1}$ to denote the identity operator on a Hilbert space. We use superscripts on quantum states, e.g., $|\psi\rangle^{AB}$ or $\rho^{AB}$, to denote the registers in which they are stored. Similarly, we use subscripts on operators to indicate the registers on which they act, unless this is clear from the context. Given a bipartite density matrix $\rho^{AB}$, we write $\rho^{A}$ to denote its reduction to register $A$ (i.e., the partial trace over $B$).

Given operators $A,B$ and a density matrix $\rho$ acting on a Hilbert space $\mathcal{H}$, we write $A=_{\rho}B$ to denote $A\rho A^{*}=B\rho B^{*}$. In other words, the operators $A$ and $B$ have the same action on the state $\rho$.

We write $|\mathrm{EPR}\rangle$ to denote the maximally entangled state $\frac{1}{\sqrt{2}}\Big{(}|00\rangle+|11\rangle\Big{)}$ on two qubits. We write $|\upphi_{d}\rangle=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}|i\rangle|i\rangle$ to denote the $d$-dimensional maximally entangled state, or simply $|\upphi\rangle$ if the dimension $d$ is clear from context. We recall the single qubit Pauli matrices:

Here we give a formal definition of a general superdense coding protocol, and prove some basic properties about them.

Next we define what it means for superdense protocols to be locally equivalent.

In this section, we define nice form protocols and then show that every superdense coding protocol is locally equivalent to one that has a nice form.

Item 2 says that up to a local unitary operation, the two parties share a maximally entangled state (in addition to other entanglement), and Item 3 turns out to be a consequence of this. Item 4 is equivalent to saying that the encoding of distinct messages $i\neq j$ are orthogonal to each other. The proof of Lemma 2.7 below may give the reader further intuition into these properties.

In the proof of Lemma 2.7, we make use of an information-theoretic argument that involves quantities such as von Neumann entropy $\operatorname{H}(A)$, conditional entropy $\operatorname{H}(A|B)$, and mutual information $\operatorname{I}(A:B)$. For a comprehensive reference on these quantities and their basic properties, we recommend Wilde’s textbook [Wil13]. It is an interesting question whether Lemma 2.7 can be proved without making use of these information-theoretic quantities.