We provide a new way to bound the security of quantum key distribution using only two high-level, diagrammatic features of quantum processes: the compositional behavior of complementary measurements and the essential uniqueness of purification. We begin by demonstrating a proof in the simplest case, where the eavesdropper doesn't noticeably disturb the channel at all and has no quantum memory. We then show how this approach extends straightforwardly to account for an eavesdropper with quantum memory and the presence of noise.

§ INTRODUCTION

Traditionally in cryptography, parties use pre-shared keys to communicate securely. In 1976 Diffie and Hellman introduced the first key agreement protocol that allows two parties, say Alice and Bob, to securely establish a key over an insecure channel [Diffie and Hellman, 1976]. There are two caveats to its security. First, it's an unauthenticated key agreement protocol,[
An attacker Eve that can intercept and modify all communication
between Alice and Bob, can simply impersonate Bob and perform all
the steps Bob would.  Now Alice thinks she established a shared key
with Bob, where in reality she established a shared key with Eve.]

and second, its security hinges on the difficulty of computing discrete logarithms. Famously, Shor showed in 1994 [Shor, 1994] that a (large-scale stable) quantum computer is able to calculate discrete logarithms with ease, breaking Diffie and Hellman's original scheme.

There are other key agreement protocols whose
security is based on mathematical problems
which are believed to  be difficult,
even for quantum computers.
An example is NewHope [Alkim et al., 2015, Braithwaite, 2016].
Such schemes form part of the program of post-quantum cryptography [Bernstein et al., 2009].

On the other hand Bennett and Brassard
proposed a completely different unauthenticated key agreement
protocol, now called BB84 [Bennett and Brassard, 1984],
whose security is not based on a mathematical problem, but on physical assumptions on quantum mechanical systems. In this protocol Alice needs to be able to send Bob qubits. In most implementations, like [Stucki et al., 2002], this is done by sending photons over a fiber optic cable, where the qubits are encoded in the polarization of the photons. After BB84 other variations have been proposed, notably E91 [Ekert, 1991], and they are all indiscriminately referred to as Quantum Key Distribution (QKD).

In their original paper, Bennett and Brassard give a short argument for the security of BB84. Feeling this proof was not satisfactory, subsequent authors have proposed more meticulous proofs, for instance [Mayers, 2001]. However, this added rigor came at the cost of complexity, prompting Shor and Preskill to publish a `simple proof' [Shor and Preskill, 2000].
This did not settle the matter: many subsequent publications have appeared on the security of BB84 and its variants, differing not only in levels of rigor vs. simplicity, but also in the physical assumptions and the efficiency of the protocol itself (e.g. qubits required per bit of shared key) [Renner, 2008, Lo and Chau, 1999, Acín et al., 2007, Ben-Or et al., 2005, Lütkenhaus, 2000, Scarani et al., 2009, Scarani and Renner, 2008, Marøy et al., 2010, Moroder et al., 2006, Kraus et al., 2005].

The present paper contributes another proof to the mix, whose primary aim is simplicity. It is quite different from those that came before, in that we adopt a purely graphical notation and rely on techniques which arose in categorical quantum mechanics [Abramsky and Coecke, 2004] and the diagrammatic approach to quantum theory [Coecke and Kissinger, 2014]. We will show that two high-level features of quantum processes–namely the behavior of complementary measurements under composition [Coecke and Duncan, 2011] and the essential uniqueness of purification of quantum channels [Chiribella et al., 2016]–suffice to show that there exists no quantum process with which an eavesdropper can undetectably extract information about Alice and Bob's shared key.

We begin by briefly reviewing the graphical notation for quantum processes, including depictions of purification and complementary measurements. In Section <ref>, we describe a version of BB84 in this notation and give a one-line version of a proof of correctness which already appears in the literature [Coecke et al., 2011, Coecke and Kissinger, 2014], but makes the (unreasonably) strong assumption that Eve is only allowed to measure and re-prepare in the $Z$ and $X$ bases. Our first main result removes this assumption, allowing Eve to perform any quantum process to (attempt to) extract information from Alice and Bob's channel:
We then formulate the condition that Eve's channel remains undetected by means of two equations, corresponding to the cases where Alice and Bob's measurement choices agree:

\[
\tikzfig{exact-req1}\qquad \qquad
\tikzfig{exact-req2}
\]

Using the behavior of complementary measurements, we show that this implies that Eve's channel separates:

While already much more general than previous graphical proofs, this still makes two very strong assumptions. First, it assumes that Eve performs the same process each time Alice and Bob use their channel. Second, it assumes all equalities are exact, so it offers no guarantees in the presence of noise.

We remove the first limitation in Section <ref> by allowing Eve to maintain an arbitrarily large quantum memory between usages of the channel, and show that the separation argument still holds. We remove the second limitation in Section <ref> by showing the same graphical proof from Section <ref> goes through, thanks to the continuity properties of purification and diagram rewriting, if we replace equality by $\epsilon$-closeness in the completely bounded norm (written `$\,\cdots \underset{\mathrm{cb}}{\overset{\varepsilon}{=}} \cdots\,$'). This enables us to give a security bound for the QKD protocol comparable to the one suggested in [Kretschmann et al., 2008]. In particular, the fact that Eve's process disturbs the channel very little can be formulated as:

\[
\tikzfig{approx-req1}\qquad\qquad
\tikzfig{approx-req2}
\]

This implies that Eve's process is within $N\sqrt{\epsilon}$ of a separable one:

\[
\tikzfig{separates-approx}
\]

for some constant $N$ depending only on the dimension of Alice and Bob's system.

§ PRELIMINARIES

Throughout the paper, we will use string diagram notation
for linear maps and channels. [Coecke and Kissinger, 2014] Systems are depicted as wires and maps as boxes. To make it clear whether we are working with linear maps between Hilbert spaces or completely positive maps (CP-maps),
we will depict finite-dimensional Hilbert spaces $H, K, \ldots$ as thin wires and the associated spaces of operators $\mathcal B(H), \mathcal B(K), \ldots$ as thick wires.

A linear map $V \colon H \to K$ and CP-map $\Phi \colon \mathcal B(H) \to \mathcal B(K)$ (for Hilbert spaces $H,K$) are depicted respectively as:

\[
\tikzfig{lin-map}
\qquad\qquad
\tikzfig{cp-map}
\]

We omit wire labels if they are irrelevant or clear from context.
Compositions of maps is depicted by plugging boxes together vertically:

\[
V \circ U \ =:\ \tikzfig{lin-map-comp}
\qquad\qquad
\Psi \circ \Phi \ =:\ \tikzfig{cp-map-comp}
\]

and tensor products by putting boxes side-by-side:

\[
U \otimes V \ =:\ \tikzfig{lin-map-tensor}
\qquad
\Phi \otimes \Psi \ =:\ \tikzfig{cp-map-tensor}
\]

Similarly, maps between tensor products such as $U \colon H \to K \otimes L$ or $\Phi \colon \mathcal B(H ) \to \mathcal B(K) \otimes \mathcal B (L)$ are depicted as boxes with multiple input/output wires:

\[
\tikzfig{lin-map-multi}
\qquad\qquad
\tikzfig{cp-map-multi}
\]

where we identify $\mathcal B(H) \otimes \mathcal B(K) \cong \mathcal B(H \otimes K)$. Identity linear maps/CP-maps are represented as `plain wires':

\[
1_H\ =:\ \tikzfig{wire}
\qquad\qquad
1_{\mathcal B(H)} \ =:\ \tikzfig{dwire}
\]

since $U \circ 1_H = 1_K \circ U = U$ and similarly for CP-maps.
The trivial system $\mathbb C$ is depicted as `no wire', since $H \otimes \mathbb C \cong H$ and $\mathcal B(H) \otimes \mathbb C \cong \mathcal B(H)$. Regarding vectors as linear maps $v \colon \mathbb C \to H$ and positive operators as CP-maps $\rho : \mathbb C \to \mathcal B(H)$, we can depict vectors $\ket{\psi} \in H$ and quantum states in $\rho \in \mathcal B(H)$ respectively as maps from 0 to 1 wire:

\[
\tikzfig{lin-map-state}
\qquad\qquad
\tikzfig{cp-map-state}
\]

Similarly, we can depict linear functionals $\bra{\psi} \colon H \to \mathbb C$ and CP-maps of the form $\bm e \colon \mathcal B(H) \to \mathbb C$ as maps from 1 to 0 wires:

\[
\tikzfig{lin-map-effect}
\qquad\qquad
\tikzfig{cp-map-effect}
\]

§.§ Purification

The linear map that sends $\rho \in \mathcal B(H)$ to its trace is a CP-map $\Tr \colon \mathcal B(H) \to \mathbb C$, which we draw as a `ground' symbol:

\[
%1_H\ =\ \maxmix \qquad\qquad
\Tr\ =\ \discard
\]

Using this notation, we can express the property of a CP-map being trace-preserving as follows:

Furthermore, any linear map $U \colon H \to K$ induces a CP-map $\widehat U \colon \mathcal B(H) \to \mathcal B(K)$ via:

\begin{equation}\label{eq:pure}
\widehat U(\rho) = U \,\rho \,U^{\dagger}
\end{equation}

We call a CP-map pure if it is of the form of (<ref>). We call this method of turning a linear map into a pure CP-map doubling.

An important theorem about CP-maps is that any CP-map can be represented in an essentially unique manner, by means of a pure CP-map and the trace.

For any completely positive map $\Phi \colon \mathcal B (H)\to \mathcal B (K)$ there is a Hilbert space $L$ and linear map $V \colon H \to K \otimes L$ with

\begin{equation}\label{eq:purification}
\tikzfig{purification}
\end{equation}

Moreover, for any (other) linear map $V' \colon H \to K \otimes L$ satisfying (<ref>), there is a unitary $U \colon L \to L$ such that:

§.§ Spiders and decoherence

To each orthonormal basis (ONB) $\{ \ket i \} $ of  a (finite-dimensional) Hilbert space $H$, we associate a family of linear maps called spiders as follows:

\[ \whitedot_m^n :=\ \tikzfig{spider-mn}\ =\ \sum_i \underbrace{\ket{i\ldots i}}_n\underbrace{\bra{i\ldots i}}_m \]

where a spider with zero legs is a complex number $D$, the dimension of the Hilbert space.

Different ONBs induce different spiders, and furthermore an ONB is uniquely fixed by its family of spiders [Coecke et al., 2011].

Adjacent spiders associated with the same ONB fuse together. That is, for $k \geq 1$, we have:

\begin{equation}
\label{eq:spider1}
\tikzfig{spidercompcount}\ =\
\tikzfig{spidernnmm}
\end{equation}

We write the doubled spiders as follows:

\[
\whitedot_m^n := \tikzfig{spider} \quad\mapsto\quad
\widehat{\whitedot_m^n} := \tikzfig{qspider}
\]

These CP-maps, which satisfy the same fusion law, are called quantum spiders. Examining the concrete expression:

\begin{align*}
\widehat{\whitedot_m^n}(\rho) \  :=\ & (\whitedot_m^n) \, \rho\,  (\whitedot_m^n)^\dagger \\
\ =\ &\
\sum_{ij}  \underbrace{\ket{i\ldots i}}_n\underbrace{\bra{i\ldots i}}_m\, \rho\, \underbrace{\ket{j\ldots j}}_m\underbrace{\bra{j\ldots j}}_n
\end{align*}

we see that:

\[ \Tr(\widehat{\whitedot_m^n}(\rho)) \ =\
\sum_{i} \underbrace{\bra{i\ldots i}}_m\, \rho\, \underbrace{\ket{i\ldots i}}_m
\]

Hence, such a map is trace-preserving whenever it has exactly one input:

\begin{equation}\label{eq:tp-one-input}
\tikzfig{tp-one-input}
\end{equation}

One derived map which will be particularly important in the sequel is the decoherence map, which arises from tracing out one output of $\widehat{\whitedot_1^2}$:

\[
\bm d_{\whitedot} \ =\ \tikzfig{decoh-def}
\]

\[
\bm d_{\whitedot}(\rho) =
\sum_i \ketbra{i}{i}\, \rho\, \ketbra{i}{i}
\]

That is, it projects a positive matrix written with respect to the ONB $\{ \ket i \} \subset H$ to its diagonal entries:

\[ \rho_{ij} \mapsto \delta_{ij} \rho_{ii} \]

The fact that this CP-map is trace-preserving follows from (<ref>):
and idempotence from spider-fusion and (<ref>):

If $\dim(H) = n$, decoherence gives a rank-$n$ projector in the $n^2$-dimensional space $\mathcal B(H)$, hence we can split this projector using the following linear maps:

\[
\bm m_{\whitedot} \ =\  \tikzfig{meas-types} \qquad\qquad
\bm e_{\whitedot} \ =\  \tikzfig{enc-types}
\]

\[
\bm m_{\whitedot}(\ketbra{i}{j}) := \delta_{ij} \ket{i}
\qquad\qquad
\bm e_{\whitedot}(\ket{i}) := \ketbra{i}{i}
\]

Then we have:

\begin{equation}\label{eq:decoh-split}
\tikzfig{decoh-split} \qquad\textrm{and}\qquad
\tikzfig{decoh-split2}
\end{equation}

Treating $\mathcal B(H)$ itself as a Hilbert space using the Hilbert-Schmidt inner product $\braket{U}{V} := \Tr(U^\dagger V)$, one can easily verify that $\bm m_{\whitedot} = (\bm e_{\whitedot})^\dagger$.

These maps have a straightforward operational interpretation which will play a role in the following sections. The first, $\bm m_{\whitedot}$, sends a quantum state to a classical probability distribution, whose entries are the Born rule probabilities associated with an ONB measurement of $\{\ket{i}\}$:

\[
\bm m_{\whitedot}(\rho) = \left(
\begin{matrix}
\bra{1}\rho\ket{1} \\
\vdots \\
\bra{n}\rho\ket{n}
\end{matrix}
\right)
\]

Hence, we can think of it as a map from a quantum space $\mathcal B(H)$ to a classical space of probability distributions in $H$ (treated simply as a vector space), representing the act measuring in the given basis.

Conversely, $\bm e_{\whitedot}$ sends a classical value (or distribution over classical values) to an encoding of that value as a quantum state:
Hence, it represents the act of encoding a classical value with respect to an ONB of quantum states.

With these interpretations in mind, the left equation in (<ref>) gives an operational reading for decoherence. Namely, it arises from measuring a quantum system, followed by re-preparing it in the same basis.

Furthermore, certain spiders take on a special meaning as operations on classical systems. Namely,

\begin{equation}\label{eq:copy}
\tikzfig{copy}\ =\ \sum_i \ketbra{ii}{i}
\end{equation}

is the process which copies a classical value,

\begin{equation}\label{eq:delete}
\tikzfig{delete}\ =\ \sum_i \bra{i}
\end{equation}

is deleting (a.k.a. marginalisation), and

\begin{equation}\label{eq:uniform}
\oneoverD\ \tikzfig{uniform}\ =\ \oneoverD\ \sum_i \ket{i}
\end{equation}

is the uniform probability distribution. Note that (<ref>) and (<ref>) are the classical analogue to the trace and the maximally mixed state, respectively. Since (<ref>) is a cloning (i.e. broadcasting) operation, it has no quantum analogue.

The final spider-derived map we will use is a non-demolition measurement:
This map captures the process where we perform an ONB measurement (which produces classical data) but also leave the quantum system intact. Alternatively, we can read the RHS above literally as performing a (demolition) measurement, copying the measurement outcome, and using one of the copies to re-prepare the quantum system.

§.§ Complementary spiders

We can study the interaction of distinct ONBs on the same Hilbert space by introducing distinct families of spiders. From hence forth, we will fix two ONBs $\{ \ket{z_i} \}$, $\{ \ket{x_i} \}$ of a Hilbert space $H$ of dimension $D$, and let:

\begin{align*}
\whitedot_m^n & :=\ \tikzfig{spider-mn}\ =\ \sum_i \underbrace{\ket{z_i\ldots z_i}}_n\underbrace{\bra{z_i\ldots z_i}}_m \\[4mm]
\graydot_m^n & :=\ \tikzfig{gray-spider-mn}\ =\ \sum_i \underbrace{\ket{x_i\ldots x_i}}_n\underbrace{\bra{x_i\ldots x_i}}_m
\end{align*}

Consequently, we let:

\begin{align*}
\bm m_{\whitedot}(\ketbra{z_i}{z_j}) & := \delta_{ij} \ket{z_i}
\bm e_{\whitedot}(\ket{z_i}) & := \ketbra{z_i}{z_i} \\
\bm m_{\graydot}(\ketbra{x_i}{x_j}) & := \delta_{ij} \ket{x_i}
\bm e_{\graydot}(\ket{x_i}) & := \ketbra{x_i}{x_i}
\end{align*}

Two ONBs are said to be mutually unbiased or complementary whenever any member of one basis gives equal probabilities to all outcomes of a measurement with respect to the other, i.e. we have $|\braket{z_i}{x_j}|^2 = \frac{1}{D}$, for all $i, j$. We can also express this property succinctly in terms of the measurement/encoding maps associated with a pair of spiders.

Two ONBs are mutually unbiased if and only if their measurement/encoding maps satisfy the following equation:

\begin{equation}\label{eq:complementaritythick}
\tikzfig{complementaritythick}
\end{equation}

Precomposing the LHS of (<ref>) with $\ket{z_i}$ and post-composing with $\bra{x_j}$ yields:

\[
\bra{x_j} \bm m_{\graydot} \bm e_{\whitedot} \ket{z_i} =
(\bm e_{\graydot} \ket{x_j})^\dagger (\bm e_{\whitedot} \ket{z_i}) \]

\[
= \Tr(\ketbra{x_j}{x_j}\ketbra{z_i}{z_i}) = |\braket{z_i}{x_j}|^2
\]

By definition of spiders, performing the same pre- and post-composition on the RHS yields , which completes the proof.

Rather than resorting to measurement and encoding maps, we can also express mutual unbiasedness directly in terms of spiders with the help of an additional linear map, called the antipode associated with a pair of spiders:

\[
\tikzfig{dualiser-def} \ = \ \sum_{ij} \braket{z_i}{x_j} \ketbra{x_j}{z_i}
\]

Two ONBs are mutually unbiased if and only if their associated spiders satisfy the following equation:

\begin{equation} \label{eq:complementarity}
\tikzfig{complementarity}
\end{equation}

Follows similarly to the proof of Theorem <ref>. Pre-composing the LHS of (<ref>) with $\ket{z_i}$ and post-composing with $\bra{x_j}$ yields:

\[ \bra{x_j}s\ket{z_i} \braket{x_j}{z_i} = \braket{z_i}{x_j} \braket{x_j}{z_i} = |\braket{x_j}{z_i}|^2 \]

Whereas pre- and post-composing on the RHS again yields $\oneoverD$.

The two conditions for unbiasedness given by Theorems <ref> and <ref> are related to each other via the (basis-dependent) isomorphism $\mathcal B(H) \cong H \otimes H$:

\[ \sum_{ij} \rho_{ij} \ketbra{z_j}{z_i}
\ \ \overset{\sim}{\longleftrightarrow} \ \
\sum_{ij} \rho_{ij} \ket{z_i} \otimes \ket{z_j} \]

Since the above isomorphism is defined with respect to the -basis, the map $s$ corrects the -spider to account for this basis-dependence:

\[
\tikzfig{white-enc}
\ \overset{\sim}{\longleftrightarrow}\
\tikzfig{copy}
\qquad\qquad
\tikzfig{gray-meas}
\ \overset{\sim}{\longleftrightarrow}\
\tikzfig{graymult-correct}
\]

The map $s$ is called an antipode because equation (<ref>) is the antipode law for a Hopf algebra. If the spiders associated with a pair of mutually unbiased bases satisfy the other three Hopf algebra laws, they are called strongly complementary bases, which are special mutually unbiased bases which always arise from finite abelian groups via Fourier transform [Coecke and Kissinger, 2014].

§ KEY DISTRIBUTION PROTOCOL

Alice chooses a random bit and encodes this bit as a qubit using either the Z $\whitedot$ or X $\graydot$ basis with equal probability. She sends the qubit to Bob. Independently, Bob chooses to perform either a Z or X basis measurement on the qubit he received, again with equal probability.
With probability 1/2 their choices agree and the bit is perfectly transmitted:

\[
\tikzfig{encode1}
\qquad \qquad \qquad
\tikzfig{encode1a}
\]

Otherwise, Bob receives a random bit, with no information conveyed:

\[
\tikzfig{encode2}
\qquad \qquad \qquad
\tikzfig{encode3}
\]

To agree on a shared key with average size $n$, Alice and Bob go through the previous routine $4n$ times.
Then Alice and Bob announce the bases they used for encoding and measuring respectively and discard those bits where the bases disagree.  On average $2n$ bits remain. To check for trouble, Alice randomly picks $n$ of the remaining bits and announces their value to Bob. If there is any mismatch on these check-bits, Alice and Bob abort. If not, Alice and Bob are left with (on average) $n$ bits.

Suppose that an eavesdropper Eve intercepts a transmitted qubit in attempt to extract information. Eve does not know which basis Alice used to encode her bit, so let us first assume Eve adopts a naive strategy whereby she randomly decides to perform a non-demolition measurement with respect to Z or X.

Alice and Bob will ignore any bits for which their basis choices differ, so we need only consider the case where they match. If Alice and Bob both choose Z, and Eve chooses (correctly) to also measure in Z:

\begin{equation*}% \label{eq:Eve_requirements_exact}
\tikzfig{outcomes1}
\end{equation*}

she indeed receives a perfect copy of Alice's bit. On the other hand, if she guesses wrong, and measures X:

\begin{equation*}% \label{eq:Eve_requirements_exact}
\tikzfig{outcomes2}
\end{equation*}

Eve and Bob both receive a random bit, completely uncorrelated to Alice's original bit. Alice and Bob's communication will be similarly disrupted when they both measure X but Eve measures Z. In a longer run, these disruptions will be detected by Alice and Bob using the check-bits, giving away Eve's presence.

Now let us consider the case where Eve can apply any operation to attempt to extract some information about Alice's bit. That is, show applies some quantum channel $\Phi \colon \mathcal{B}(\ahilb) \to \mathcal{B}(\ahilb \otimes \ehilb)$, where $\ahilb$ is the Hilbert space of the qubit and $\ehilb$ is that of some other system possessed by Eve:

In order for Eve's intervention to remain undetected in either case where Alice and Bob's measurements agree, Eve's channel must satisfy the following equations:

\begin{equation}\label{eq:eve-secret}
\tikzfig{exact-req1-enc}\qquad \qquad
\tikzfig{exact-req2-enc}
\end{equation}

We now prove that, in this scenario, Eve cannot possibly extract any information. That is, her channel separates.

For any $\Phi$ satisfying (<ref>) for complementary ONBs /we have:

\[
\tikzfig{separateslabels}
\]

for some state $\rho$ of $\mathcal{B}(\ehilb)$.

By precomposing measurement maps and postcomposing encoding maps, we find

\begin{equation} \label{eq:Eve_requirements_exact}
\tikzfig{exact-req1}\qquad \qquad
\tikzfig{exact-req2}
\end{equation}

By purifying $\Phi$, we can without loss of generality assume that Eve's map $\Phi$ is pure, say with $\Phi = \widehat \evepure$. The left-hand side of (<ref>) states that:

\begin{equation} \label{eq:addpurestate}
\tikzfig{proof1}
\end{equation}

for any normalized pure state $\psi$ of $\ehilb \otimes \ahilb$. By essential uniqueness of purification, we conclude that:

\begin{equation} \label{eq:unitaryappearsinproof}
\tikzfig{proof3}
\end{equation}

for some unitary $U$ on $\ahilb \otimes \ehilb \otimes \ahilb$. Hence:

\begin{equation} \label{eq:counitsontopinproof}
\tikzfig{proof4}
\end{equation}

Using the spider laws (<ref>), it follows that:

\begin{equation} \label{eq:phaseproofstep}
\tikzfig{proof5}
\end{equation}

The same equations also hold for the gray spiders
with the same reasoning
starting with the right-hand side of (<ref>).
But together these imply that $\evepure$ separates, since:

\[
\tikzfig{proof8p}
\]

\[
\tikzfig{proof9p}
\]

(where for a qubit we have $D = 2$). Hence $\Phi$ separates as well.

The simple nature of the graphical proof makes clear several immediate generalizations. Firstly, the same protocol and proof may be applied apply whether Alice and Bob are sharing a qubit or a qudit for arbitrary (finite) Hilbert space dimension $D$, on which Alice and Bob must simply choose any pair of complementary orthonormal bases.

§ EAVESDROPPERS WITH MEMORY

A very strong assumption in the previous derivation was that Eve performs the same channel every time in attempts to extra information from Alice's string of bits. Suppose now that Eve may now vary her behavior depending on the qubits she has received previously. That is, she may now make use of a quantum memory that persists between individual steps of the protocol. Her channel is now of the form $\Phi \colon \mathcal{B}(\ahilb \otimes \ehilb) \to \mathcal{B}(\ahilb \otimes \ehilb)$, with an extra input into which is passed the output from the previous intercepted qubit. She initially prepares her auxiliary system in some state $\rho$. Then Eve's procedure, during $n$ transmissions between Alice and Bob, amounts to the channel $\Phi' \colon \mathcal{B}(\ahilb^{\otimes n}) \to \mathcal{B}(\ahilb^{\otimes n} \otimes \ehilb)$ given by:

\begin{equation}% \label{eq:quantummemory}
\tikzfig{memory1labels}
\end{equation}

(As Eve can keep a counter in $E$,
this setting is as general as if we would allow Eve
a different $\Phi_n\colon \mathcal B(H \otimes E) \to \mathcal B (H \otimes E)$
for each transmitted qubit.)

As before, for Eve's interference to remain completely undetected,
we must have that:

\begin{equation} \label{eq:quantummemoryreq}
\tikzfig{memory2half}
\end{equation}

along with analogous equations for all of the remaining $2n-1$ variations of basis and position. In particular the one for the first bit becomes:

\begin{equation*} %\label{eq:Eve_requirements_exact}
\tikzfig{memory3}
\end{equation*}

The same equation holds for the gray spiders also. From cancellativity of the tensor product, we conclude that $\Phi \circ (\id{} \otimes \rho)$ satisfies the requirements of Theorem <ref>, and so separates as:

\begin{equation*} %\label{eq:Eve_requirements_exact}
\tikzfig{memory4}
\end{equation*}

for some state $\rho'$ of $\mathcal{B}(\ehilb)$.

Returning to the requirement (<ref>), the same argument again with ${n-1}$ instances of $\Phi$ and $\rho'$ replacing $\rho$ shows that $\Phi \circ (\id{} \otimes \rho')$ itself separates. Repeating this argument inductively reveals that $\Phi$ itself separates, and thus Eve again receives no information.

§ NOISE-TOLERANCE

The proofs we have just seen might be pleasing, but they do not give us a priori confidence in the security of QKD: it might be the case that with only a minute disturbance, Eve might extract a lot of information. We will see in this section that this is not the case: the equational proof also leads to a polynomial bound on the distance of Eve's channel from a separable one by the amount of disturbance. The key is an approximate version of essential uniqueness of purifications due to Kretschmann, Schlingemann and Werner [Kretschmann et al., 2008, Kretschmann et al., 2008]:
Let $V_1, V_2 \colon A \to B \otimes E$ be linear maps. Then:

\begin{align*} \label{eq:continuitystinespring}
&\inf_U \,\Biggl\|\  \tikzfig{v1-minus-v2}\   \Biggr\|^2_\infty \  \\
&\qquad\leq\ \Biggl\| \ \tikzfig{v1-minus-v2-dbl} \  \Biggr\|_{\mathrm{cb}} \\ \
&\qquad\leq \  2\inf_U \,\Biggl\|\  \tikzfig{v1-minus-v2}\  \Biggr\|_\infty
\end{align*}

where the infima are taken over all unitaries $U \colon E \to E$.

Here $\|\,\cdot\,\|_\infty$ denotes the usual operator norm
and ${\|\,\cdot\,\|_\cb}$ the completely bounded norm
of super operators which is defined via the sup-norm on super-operators:

\begin{equation*}
\|V \|_\infty := \sup_{\|\psi\|\leq 1} \|V \psi\|
\qquad \|\Phi\|_\infty := \sup_{\| T \| \leq 1}  \| \Phi(T) \|_\infty
\end{equation*}

\begin{equation*}
\|\Phi\|_\cb := \sup_{n \in \N} \| \id_{M_n}\otimes \Phi\|_\infty
\end{equation*}

The operator norm (on operators) and cb-norm (on super operators)
satisfy the following rules.

\begin{equation*} %\label{eq:opnormrules}
\| f \circ g \| \leq \| f \| \, \|g \|
\quad \| f \otimes  g \| = \| f \| \, \|g \|
\quad \| \id \| = 1
\end{equation*}

The regular sup-norm on super operators does not satisfy the middle rule. For brevity, we will write

\begin{align*}
V \mathrel{\overset{\varepsilon}{=}} V'
&\ \Leftrightarrow\
\| V - V' \|_{\infty}\  \leq \ \varepsilon \\
T \mathrel{\underset{\cb}{\overset{\varepsilon}{=}}} T' &\ \Leftrightarrow \
\|T - T'\|_{\cb} \ \leq \ \varepsilon.
\end{align*}

The compositional rules for the operator norm allow us to lift approximate equations between sub-diagrams to those between full diagrams, using the rule:

\begin{equation} \label{eq:diagreasoning}
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=small box] (0) at (0, 0) {$V$};
\node [style=none] (1) at (0, -1.25) {};
\node [style=none] (2) at (0, 1.25) {};
\node [style=right label] (3) at (0.25, -1) {};
\node [style=right label] (4) at (0.25, 1) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw (1.center) to (0);
\draw (0) to (2.center);
\end{pgfonlayer}
\end{tikzpicture}
\overset{\varepsilon}{=}
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [style=small box] (0) at (0, 0) {$W$};
\node [style=none] (1) at (0, -1.25) {};
\node [style=none] (2) at (0, 1.25) {};
\node [style=right label] (3) at (0.25, -1) {};
\node [style=right label] (4) at (0.25, 1) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw (1.center) to (0);
\draw (0) to (2.center);
\end{pgfonlayer}
\end{tikzpicture}
\implies
\tikzfig{diag-reason}
\end{equation}

There is a constant ${\noiseconst}$, depending only on the dimension of Alice and Bob's system, such that whenever

\begin{equation} \label{eq:Evenoise}
\tikzfig{approx-req1}\qquad\qquad
\tikzfig{approx-req2}
\end{equation}

we have that

\begin{equation}
\label{eq:conclusionnoise}
\tikzfig{separates-approx}
\end{equation}

for some state $\rho$ of $\mathcal{B}(\ehilb)$.

From the upper bound of Theorem <ref>, it suffices to prove that there is such a constant $\noiseconst$ for which any purification $\widehat \evepure$ of Eve's channel satisfies:

\begin{equation} \label{eq:sep_noise}
\tikzfig{separates-approx-pure}
\end{equation}

This follows from the proof of Theorem <ref>, by repeatedly applying the rule (<ref>) to replace each strict equation in the proof by an approximate one. At each step one only picks up linear factors from the norms of other maps featuring in each diagram. Inspecting the proof, one can see that these are independent of Eve's system or channel.

In more detail, let $\widehat \evepure$ be a purification of Eve's channel. Then the left hand side of (<ref>) says precisely that the two sides of (<ref>) are within $\varepsilon$ in the completely bounded norm, for any such pure state $\psi$. By Theorem <ref>, there is then a unitary $U$ such that the two sides of (<ref>) are within $2 \sqrt{\varepsilon}$. Applying two copies of $\whitedot^1_0$ as in (<ref>), we obtain equation (<ref>) up to $2 \sqrt{\varepsilon}||\whitedot^1_0||^2$.
This ensures that (<ref>) holds up to a constant factor in $\sqrt{\varepsilon}$ dependent only on the norms of the $\whitedot^n_m$ maps. Similarly so does the same equation for the gray spider.

The final steps of the proof now follow just as before. Again at each step we simply replace a strict equation by one up to a constant factor in $\sqrt\varepsilon$, dependent only on the white and gray spiders, using the rule (<ref>).

Taking the distance of Eve's channel from a separable channel as a measure of how much information she can extra from Alice's bit, we see that, as expected, the amount of information is bounded by how much Eve disturbs the communication between Alice and Bob.

We conclude this section with a few caveats:

* The bound applies if the systems of Alice, Bob and Eve can be modeled by finite-dimensional Hilbert spaces and their interaction as a completely positive map between their tensor products.  For other applications these assumptions are untenable, see e.g. [Yngvason, 2005] and [Shaji and Sudarshan, 2005]. There is, however, no clear indication that for quantum information arguments these assumptions are invalid.
Nonetheless it's of interest how far these arguments generalize. Interactions between arbitrary (possibly infinite-dimensional) von Neumann algebras admit a Stinespring-like dilation [Westerbaan and Westerbaan, 2017], but no continuity result is known.

* Like the proof in Section <ref>, the proof above assumes Eve performs the same operation every time. This should be extended to incorporate memory as in Section <ref>.

* The random sampling (check-bits) on its own does not guarantee the bound (<ref>). Renner solves the analogous problem with some effort by showing the resulting combined state of Alice, Bob and Eve may be assumed to be approximately symmetric under permutations of the bits in the run [Renner, 2008]. A similar method may apply here.

§ OUTLOOK

We saw how to derive a bound on the security of QKD using the diagrammatic behavior of complementary observables and continuity of Stinespring.  Whether the protocol ensures the assumed bound (<ref>) and
how the conclusion (<ref>) is related to the more common quantities like mutual information and the secret-key rate, we leave open to future research.

In closing we note that, in the current literature, diagrammatic arguments have typically only been used for exact reasoning about quantum processes. Our proof of Theorem <ref> suggests a  general strategy of using the rule (<ref>) to extend such exact diagrammatic arguments to approximate ones. We call this technique $\varepsilon$-bounded diagrammatic reasoning. It should be applicable to many further quantum protocols, allowing the intuitive diagrammatic approach to quantum information theory developed in [Coecke and Kissinger, 2014] to be used to make physically reasonable and robust arguments, such as required for security protocols.

We thank Hans Maassen, Sam Staton, Bram Westerbaan and John van de Wetering for insightful discussion. We would also like to thank the anonymous QPL referees for their useful feedback on a short abstract summarising this work.

This work is supported by the ERC under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC grant no 320571 and an EPSRC Studentship OUCL/2014/SET.

[Abramsky and Coecke, 2004]
S. Abramsky and B. Coecke.
A categorical semantics of quantum protocols.
In Proceedings of the 19th Annual IEEE Symposium on Logic in
Computer Science (LICS), pages 415–425. IEEE Computer Society, 2004.

[Acín et al., 2007]
A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani.
Device-independent security of quantum cryptography against
collective attacks.
Physical Review Letters, 980 (23):0 230501,

[Alkim et al., 2015]
E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe.
Post-quantum key exchange — a new hope.
IACR Cryptology ePrint Archive, 2015:0 1092, 2015.

[Ben-Or et al., 2005]
M. Ben-Or, M. Horodecki, D. W. Leung, D. Mayers, and J. Oppenheim.
The universal composable security of quantum key distribution.
In Theory of Cryptography Conference, pages 386–406.
Springer, 2005.

[Bennett and Brassard, 1984]
C. H. Bennett and G. Brassard.
Quantum cryptography: Public key distribution and coin tossing.
In Proceedings of IEEE International Conference on Computers,
Systems and Signal Processing, pages 175–179. IEEE, 1984.

[Bernstein et al., 2009]
D. J. Bernstein, J. Buchmann, and E. Dahmen.
Post-quantum cryptography.
Springer Science & Business Media, 2009.

[Braithwaite, 2016]
M. Braithwaite.
Experimenting with Post-Quantum Cryptography, 2016 (accessed
April 7, 2017).

[Chiribella et al., 2010]
G. Chiribella, G. M. D'Ariano, and P. Perinotti.
Probabilistic theories with purification.
Physical Review A, 810 (6):0 062348, 2010.

[Chiribella et al., 2016]
G. Chiribella, G. M. D'Ariano, and P. Perinotti.
Quantum from Principles, pages 171–221.
Springer, Dordrecht, 2016.
ISBN 978-94-017-7303-4.

[Coecke and Duncan, 2011]
B. Coecke and R. Duncan.
Interacting quantum observables: categorical algebra and
New Journal of Physics, 13:0 043016, 2011.

[Coecke and Kissinger, 2014]
B. Coecke and A. Kissinger.
Picturing Quantum Processes.
Cambridge University Press, 2014.

[Coecke et al., 2011]
B. Coecke, D. Pavlović, and J. Vicary.
A new description of orthogonal bases.
Mathematical Structures in Computer Science,

[Coecke et al., 2011]
B. Coecke, Q. Wang, B. Wang, Y. Wang, and Q. Zhang.
Graphical calculus for quantum key distribution (extended abstract).
Electronic Notes in Theoretical Computer Science, 2700
(2):0 231–249, 2011b.

[Diffie and Hellman, 1976]
W. Diffie and M. Hellman.
New directions in cryptography.
IEEE transactions on Information Theory, 220
(6):0 644–654, 1976.

[Ekert, 1991]
A. K. Ekert.
Quantum cryptography based on Bell's theorem.
Physical Review Letters, 670 (6):0 661–663,
ISSN 1079-7114.

[Kraus et al., 2005]
B. Kraus, N. Gisin, and R. Renner.
Lower and upper bounds on the secret-key rate for quantum key
distribution protocols using one-way classical communication.
Physical review letters, 950 (8):0 080501,

[Kretschmann et al., 2008]
D. Kretschmann, D. Schlingemann, and R. F. Werner.
The information-disturbance tradeoff and the continuity of
stinespring's representation.
IEEE transactions on information theory, 540
(4):0 1708–1717, 2008a.

[Kretschmann et al., 2008]
D. Kretschmann, D. Schlingemann, and R. F. Werner.
A continuity theorem for stinespring's dilation.
Journal of Functional Analysis, 2550 (8):0
1889–1904, 2008b.

[Lo and Chau, 1999]
H.-K. Lo and H. F. Chau.
Unconditional security of quantum key distribution over arbitrarily
long distances.
science, 2830 (5410):0 2050–2056, 1999.

[Lütkenhaus, 2000]
N. Lütkenhaus.
Security against individual attacks for realistic quantum key
Physical Review A, 610 (5):0 052304, 2000.

[Marøy et al., 2010]
Ø. Marøy, L. Lydersen, and J. Skaar.
Security of quantum key distribution with arbitrary individual
Physical Review A, 820 (3):0 032337, 2010.

[Mayers, 2001]
D. Mayers.
Unconditional security in quantum cryptography.
Journal of the ACM (JACM), 480 (3):0 351–406,

[Moroder et al., 2006]
T. Moroder, M. Curty, and N. Lütkenhaus.
One-way quantum key distribution: Simple upper bound on the secret
key rate.
Physical Review A, 740 (5):0 052301, 2006.

[Renner, 2008]
R. Renner.
Security of quantum key distribution.
International Journal of Quantum Information, 60
(01):0 1–127, 2008.

[Scarani and Renner, 2008]
V. Scarani and R. Renner.
Quantum cryptography with finite resources: Unconditional security
bound for discrete-variable protocols with one-way postprocessing.
Physical review letters, 1000 (20):0 200501,

[Scarani et al., 2009]
V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek,
N. Lütkenhaus, and M. Peev.
The security of practical quantum key distribution.
Reviews of modern physics, 810 (3):0 1301,

[Shaji and Sudarshan, 2005]
A. Shaji and E. C. G. Sudarshan.
Who's afraid of not completely positive maps?
Physics Letters A, 3410 (1):0 48–54, 2005.

[Shor, 1994]
P. W. Shor.
Algorithms for quantum computation: discrete logarithms and
In Foundations of Computer Science, 1994 Proceedings., 35th
Annual Symposium on, pages 124–134. IEEE, 1994.

[Shor and Preskill, 2000]
P. W. Shor and J. Preskill.
Simple proof of security of the bb84 quantum key distribution
Physical review letters, 850 (2):0 441, 2000.

[Stinespring, 1955]
W. F. Stinespring.
Positive functions on c*-algebras.
Proceedings of the American Mathematical Society, 60
(2):0 211–216, 1955.

[Stucki et al., 2002]
D. Stucki, N. Gisin, O. Guinnard, G. Ribordy, and H. Zbinden.
Quantum key distribution over 67 km with a plug&play system.
New Journal of Physics, 40 (1):0 41, 2002.

[Westerbaan and Westerbaan, 2017]
A. Westerbaan and B. Westerbaan.
Paschke dilations.
In Proceedings of the 13th International Conference in Quantum
Physics and Logic (QPL), volume 236 of Electronic Proceedings in
Theoretical Computer Science, pages 229–244, 2017.

[Yngvason, 2005]
J. Yngvason.
The role of type iii factors in quantum field theory.
Reports on Mathematical Physics, 550 (1):0
135–147, 2005.