Computer Science Physics Mathematics
ComputerScience,1970-2008-Computer Science-2004.jsonl.gz.gz
Computer Science
670a2411da55a283d4b035eb8d8f376c91431a66
The logic of entanglement

We expose the information flow capabilities of pure bipartite entanglement as a theorem -- which embodies the exact statement on the `seemingly acausal flow of information' in protocols such as teleportation. We use this theorem to re-design and analyze known protocols (e.g. logic gate teleportation and entanglement swapping) and show how to produce some new ones (e.g. parallel composition of logic gates). We also show how our results extend to the multipartite case and how they indicate that entanglement can be measured in terms of `information flow capabilities'. Ultimately, we propose a scheme for automated design of protocols involving measurements, local unitary transformations and classical communication.


Introduction
Entanglement has always been a primal ingredient of fundamental research in quantum theory, and more recently, quantum computing. By studying it we aim at understanding the operational/physical significance of the use of the Hilbert space tensor product for the description of compound quantum systems. Many typical quantum phenomena are indeed due to compound quantum systems being described within the tensor product H 1 ⊗ H 2 and not within a direct sum H 1 ⊕ H 2 .
In this paper we reveal a new structural ingredient of the supposedly well-understood pure bipartite entanglement, that is, we present a new theorem about the tensor product of Hilbert spaces. It identifies a 'virtual flow of information' in so-called entanglement specification networks. For example, it is exactly this flow of information which embodies teleporting [6] an unknown state from one physical carrier to another. Furthermore, our theorem (nontrivially) extends to multipartite entanglement. We also argue that it provides a new way of conceiving entanglement itself and hence of measuring entanglement: entanglement ≡ information flow capabilities Indeed, our result enables reasoning about quantum information flow without explicitly considering classical information flow -this despite the impossibility of transmitting quantum information through entanglement without the use of a classical channel.
Using our theorem we can evidently reconstruct protocols such as logic gate teleportation [10] and entanglement swapping [15]. It moreover allows smooth generation of new protocols, of which we provide an exam-ple, namely the conversion of accumulation of inaccuracies causing 'sequential composition' into fault-tolerant 'parallel composition' [13]. Indeed, when combing our new insights on the flow of information through entanglement with a model for the flow of classical information we obtain a powerful tool for designing protocols involving entanglement.
An extended version of this paper is available as a research report [9]. It contains details of proofs, other/larger pictures, other references, other applications and some indications of connections with logic, proof theory and functional programming.

Classical information flow
By the spectral theorem any non-degenerated measurement on a quantum system described in a ndimensional complex Hilbert space H has the shape M = x 1 · P 1 + . . . + x n · P n .
Since the values x 1 , . . . , x n can be conceived as merely being tokens distinguishing the projectors P 1 , . . . , P n in the above sum we can abstract over them and conceive such a measurement as a set M ≃ {P 1 , . . . , P n } of n mutually orthogonal projectors which each project on a one-dimensional subspace of H. Hence, by von Neumann's projection postulate, a measurement can be conceived as the system being subjected to an action P i and the observer being informed about which action happened (e.g. by receiving the token x i ).
In most quantum information protocols the indeterminism of measurements necessitates a flow of classical information e.g. the 2-bit classical channel required for teleportation [6]. We want to separate this classical information flow from what we aim to identify as the quantum information flow. Consider a protocol involving local unitary operations, (non-local) measurements and classical communication e.g. teleportation: We can decompose such a protocol in 1. a tree with the consecutive operations as nodes, and, in case of a measurement, the emerging branches being labeled by tokens representing the projectors; 2. the configuration of the operations in terms of the time when they are applied and the subsystem to which they apply.
Hence we abstract over spatial dynamics. The nodes in the tree are connected to the boxes in the configuration picture by their temporal coincidence. For teleportation we thus obtain Classical communication is encoded in the tree as the dependency of operations on the labels on the branches below it e.g. the dependency of the operation U xz on the variable xz stands for the 2-bit classical channel required for teleportation. We will also replace any initial state Ψ by the projector P Ψ on it, which can be conceived as its preparation e.g. P EPR is the preparation of an EPR-pair. It should be clear that for each path from the root of the tree to a leaf, by 'filling in the operations on the included nodes in the corresponding boxes of the configuration picture', we obtain a network involving only local unitary operations and (non-local) projectors e.g. one network P EPR

Pxz
Uxz for each of the four values xz takes. It will be these networks (from which we extracted the classical information flow) for which we will reveal the quantum information flow. Hence each projector in it which is not a preparation is to be conceived conditionally.

Bipartite entanglement
where (m αβ ) αβ is the matrix of the corresponding function in bases {e (1) α } α and {e We can now represent the states of H 1 ⊗ H 2 by functions in H 1 → H 2 or in H 1 H 2 , and vice versa, these functions represent states of H 1 ⊗ H 2 . Omitting normalization constants, an attitude we will abide by throughout this paper, examples of linear maps encoding states are: These four functions which encode the Bell-base states are almost the Pauli matrices plus the identity which itself encodes the EPR-state. We can also encode each projector Hence we can use these (linear or antilinear) functional labels both to denotate the states of H 1 ⊗H 2 and the projectors on elements of H 1 ⊗H 2 . We introduce a graphical notation which incarnates this. Hence the projector f acts on the multipartite state represented by and produces a pure tensor consisting of (up to a normalization constant) f and some remainder. Hence this picture portrays 'preparation of the f -labeled state'.
By an entanglement specification network we mean a collection of bipartite projectors f 'configured in space and time' e.g.
The arrows indicate which of the two Hilbert spaces in H 1 ⊗ H j is the domain and which is the codomain of the labeling function. Such a network can also contain local unitary operations -which we will represent by a grey square box U . We will refer to the lines labeled by some Hilbert space H i (≃ time-lines) as tracks. The notion of a path allows us to make certain predictions about the output Ψ out of a network, that is, the state of the whole system after all projectors have been effectuated. Before stating the theorem we illustrate it on our example. Let be its input state. This input state factors into the pure factor φ in , which we call the input of the path, and a remainder.
It should be clear that after effectuating all projectors we end up with an output which factors in the bipartite state labeled by f 1 , the bipartite state labeled by f 2 and a remaining pure factor φ out -which we call the output of the path. Our theorem (below) predicts that Be aware of the fact that the functions f 1 , . . . , f 8 are not physical operations but labels obtained via a purely mathematical isomorphism. Moreover, the order in which they appear in the composite (1) has no obvious relation to the temporal order of the corresponding projectors. Their order in the composite (1) is: the order in which the path passes through them -this despite the fact that the path goes both forward and backward in physical time. Here's the theorem.
Proof: Straightforward verification or see [9] §5.1. 2 Theorem 3.3 (i) Given are an entanglement specification network and a path. Assume that : 1. The order in which the path passes through the projectors is 2. The input of the path is a pure factor φ in .
3. Ψ out has a non-zero amplitude.
Then the output of the path is (indeed) a pure factor φ out which is explicitly given by (ii) If the path passes forwardly through U then U will be part of the composite (2) and if it passes backwardly through U then U † will be part of the composite (2).
Proof: Lemma 3.2 is the crucial lemma for the proof. For a full proof see [9] §5. 2 It might surprise the reader that in the formulation of Theorem 3.3 we didn't specify whether f 1 , . . . , f k are either linear or anti-linear, and indeed, we slightly cheated. The theorem is only valid for f 1 , . . . , f k antilinear. However, in the case that f 1 , . . . , f k are linear, in order to make the theorem hold it suffices to conjugate the matrix elements of those functional labels for which the path enters (and leaves) the corresponding projector 'from below' (see [9] §4.1): In most practical examples these matrix elements are real (see below) and hence the above theorem also holds for linear functional labels. One also verifies that if a path passes though a projector in the opposite direction of the direction of an anti-linear functional label f , then we have to use the adjoint f † of the anti-linear map f in the composite (2) -the matrix of the adjoint of an anti-linear map f † is the transposed of the matrix of f (see [9] §4.2). Finally note that we did not specify that at its input a path should be directed forwardly in physical time, and indeed, the theorem also holds for paths such as We discuss this in Section 5.
due to (id • id)(φ) = φ. When conceiving the first projector as the preparation of an EPR-pair while tilting the tracks we indeed obtain 'a' teleportation protocol. However, the other projector has to 'belong to a measurement' e.g. M Bell := {P id , P π , P id * , P π * }. Hence the above introduced protocol is a conditional one. We want to make it unconditional.
Definition 4.1 Paths are equivalent iff for each input φ in they produce the same output φ out . Proof: Intuitively, one can move the box U † along the path and permute it with projectors whose functional labels commute with U (= commute with U † ) until it gets annihilated by the U -factor of U • f . Applying Corollary 4.2 to f, g := id and U ∈ {id, π, id * , π * } , since π † = π, (id * ) † = id * and (π * ) † = −π * , we obtain four conditional teleportation protocols of which the one with U := id coincides with (3). These four together constitute an unconditional teleportation protocol since they correspond to the four paths 'from root to leaf' of the tree discussed in Section 2, from which then also the 2-bit classical channel emerges. In order to obtain the teleportation protocol as it is found in the literature, observe that π * = π •id * , hence • id id * id id id * π π π * and thus we can factor -with respect to composition of functional labels -the 2-bit Bell-base measurement in two 1-bit 'virtual' measurements (∨ stands for 'or'): id∨id * id∨π id∨π∨id * ∨π * ≃ 2 bits 1 bit 1 bit Note that such a decomposition of M Bell does not exist with respect to ⊗ nor does it exist with respect to composition of projector actions. All this results in id id∨id * id∨π id∨π id∨id * which is the standard teleportation protocol [6].
The aim of logic gate teleportation [10] is to teleport a state and at the same time subject it to the action of a gate f . By Theorem 3.3 we evidently have We make this protocol unconditional analogously as we did it for ordinary teleportation. Proof: Analogous to that of Corollary 4.3. 2 We apply the above to the case f := id ⊗ id and g := CNOT that is, the first projector is now to be conceived as the preparation of the state Proof: The first claim is verified straightforwardly.
Hence we can factor the 4-qubit measurement to which the second projector belongs in two Bell-base measurements, that is, we set The resulting protocol is the one to be found in [10] -recall that U † factors as a tensor since CNOT is a member of the Clifford group.
Our last example in this section involves the passage from sequential to parallel composition of logic gates. Due to the accumulation of inaccuracies in sequential composition [13] it would be desirable to have a fault-tolerant parallel alternative. This would for example be useful if we have a limited set of available gates from which we want to generate more general ones e.g. generating all Clifford group gates from CNOT gates, Hadamard gates and phase gates via tensor and composition. By Theorem 3.3 the network

Entanglement swapping
However, Theorem 3.3 assumes φ in to be a pure factor while it is part of the output Ψ out of the network. This fact constraints the network by requiring that for some φ in and φ out i.e. the state labeled by h • g • f has to be disentangled -which is equivalent to the range of h • g • f being one-dimensional [9] §5.3.
Using Lemma 3.2 this pathology can be overcome by conceiving the output state of the bipartite subsystem described in H 1 ⊗ H 4 not as a pair (φ in , φ out ) but as a function ϕ : H 1 H 4 which relates any input φ in ∈ H 1 to an output φ out := ϕ(φ in ) ∈ H 4 . Hence we conceive the above network as producing a function To such a function produced by a network we can provide an input via a unipartite projector. The generic example (which can be easily verified) is One can then conceive f as a λ-term λφ.f φ [5] and the process of providing it with an input via a unipartite projector embodies the β-reduction [5] (λφ.f φ)φ in β = f (φ in ) .
As we will see below we can 'feed' such a function at its turn as an input of function type in another network. This view carries over to the interpretation of multipartite entanglement where it becomes crucial.
The entanglement swapping protocol [15] can now be derived analogously as the teleportation protocol by setting f = g = h := id in the above. For this particular case Lemma 3.2 becomes Details can be found in [9] §6.2.

Multipartite entanglement
The passage from states to functions as inputs and outputs enables to extend our functional interpretation of bipartite entanglement to one for multipartite entanglement. In general this involves higher order functions and hence the use of denotational tools from modern logic and proof theory such as λ-calculus [1,5]. Whereas (due to commutativity of − ⊗ −) a bipartite tensor H 1 ⊗ H 2 admits interpretation as a function either of type H 1 H 2 or of type H 1 H 2 , a tripartite tensor (due to associativity of − ⊗ −) admits interpretation as a function of a type within the union of two (qualitatively different) families of types namely Explicitly, given we respectively obtain :: We illustrate this in an example -we will not provide an analogue to Theorem 3.3 for the multipartite case since even its formulation requires advanced denotational tools. Consider the following configuration. For 'good' types we can draw a 'compound' path.
To verify this we explicitly calculate φ out α8 . Set where Ψ 0 is the (essentially arbitrary) input of the network and Ψ τ for τ ∈ {1, 2, 3, 4} is the state at time τ + ǫ. For I ⊆ {1, . . . , 8} and I c := {1, . . . , 8} \ I let P I Φ stipulate that this projector projects on the subspace where i 1 . . . i 8 [j α /i α | α ∈ I] denotes that for α ∈ I we substitute the index i α by the index j α which ranges over the same values as i α .
Proof: Straightforward verification or see [9] §6.4. 2 Using Lemma 6.1 one verifies that the resulting state Ψ 4 i1...i8 factors into five components, one in which no index in {i 1 , . . . , i 8 } appears, three with indices in {i 1 , . . . , i 7 } and one which contains the index i 8 namely l4l5l6l7 m1m2m3 Substituting the indices m 1 , m 2 , m 3 , l 4 , l 5 , l 6 , l 7 , i 8 by α 1 , . . . , α 8 we exactly obtain our prediction for φ out α8 . It should be clear from our discussion of multipartite entanglement that, provided we have an appropriate entangled state involving a sufficient number of qubits, we can implement arbitrary (linear) λ-terms [1,5].

Discussion
For a unitary operation U : H → H there is a flow of information from the input to the output of U in the sense that for an input state φ the output U (φ) fully depends on φ.

U(φ)
How does a projector P ψ act on states? After renormalization and provided that φ | ψ = 0 the input state φ is not present anymore in the output ψ = P ψ (φ). At first sight this seems to indicate that through projectors on one-dimensional subspaces there cannot be a flow of information cfr. the 'wall' in the picture below. While there cannot be a flow from the input to the output, there is a 'virtual flow' between the two inputs and the two outputs of a bipartite projector whenever it is configured within an appropriate context. And such a bipartite projector on a state in H 1 ⊗ H 2 can act on this flow as any (anti-)linear function f with domain in H 1 and codomain in H 2 -which is definitely more general than unitary operations and also more general than actions by (completely) positive maps. This behavioral interpretation extends to multipartite entanglement, and, as is shown in [9] §6.6, it also enables interpretation of non-local unitary operations.
The wall within a projector incarnates the fact that Indeed, one verifies that disentangled states ψ⊗φ are in bijective correspondence with those linear maps which have a one-dimensional range [9] §5.3, that is, since states correspond to one-dimensional subspaces, disentangled states correspond to (partial) constant maps on states. Since constant maps incarnate the absence of information flow (cfr. 'the wall' mentioned above): Pursuing this line of thought of conceiving entanglement in terms of its information flow capabilities yields a proposal for measuring pure multipartite entanglement [9] §7.5 -given a measure for pure bipartite entanglement e.g. majorization [11].
The use of Theorem 3.3 in Sections 4 and 5 hints towards automated design of general protocols involving entanglement. We started with a simple configuration which conditionally incarnates the protocol we want to implement. Conceiving this conditional protocol as a pair consisting of (i) a single path 'from root to leaf' in a tree, and, (ii) a configuration picture, we can extend the tree and the configuration picture with unitary corrections in order to obtain an unconditional protocol. It constitutes an interesting challenge to produce an explicit algorithm which realizes this given an appropriate front-end design language.
Elaborating on the results in [2] S. Abramsky and the author have produced an axiomatic characterization of the in this paper exposed behavioral properties of quantum entanglement with respect to information flow. Remarkably, the additive feature of a vector space which gives rise to the notion of superposition and hence to that of entanglement itself seems not to be crucial with respect to the quantum-flow! In particular, we obtain a similar information-flow as the one enabled by quantum entanglement when replacing 'vector space' by 'set', 'linear map' by 'relation' and 'tensor product' by 'cartesian product' [3]. Replacing 'linear map' by 'function' in stead of 'relation' would not enable such an information flow. This is due to a different categorical status [4,12] of the cartesian product in the category of sets and relations as compared to its status in the category of sets and functions. The category of relations does fail to have a full teleportation protocol because it has no four-vector Bell-base [3].
Recent proposals for fault-tolerant quantum computers of which the architecture is manifestly different from the circuit model require a different mathematical setting for programming them and reasoning about them [8]. We are convinced that the insights obtained in this paper provide the appropriate tool for doing so.