Quantum Alternation: Prospects and Problems
Costin Bădescu

Prakash Panangaden

McGill University
Montréal, Canada
cbades@cs.mcgill.ca

McGill University
Montréal, Canada
prakash@cs.mcgill.ca

We propose a notion of quantum control in a quantum programming language which permits the superposition of finitely many quantum operations without performing a measurement. This notion takes
the form of a conditional construct similar to the if statement in classical programming languages.
We show that adding such a quantum if statement to the QPL programming language [11] simplifies
the presentation of several quantum algorithms. This motivates the possibility of extending the denotational semantics of QPL to include this form of quantum alternation. We give a denotational semantics
for this extension of QPL based on Kraus decompositions rather than on superoperators. Finally, we
clarify the relation between quantum alternation and recursion, and discuss the possibility of lifting
the semantics defined by Kraus operators to the superoperator semantics defined by Selinger [11].

1

Introduction

The field of quantum programming languages emerged in the early 2000s as a result of researchers’
interest in understanding quantum algorithms structurally. This interest is backed by the belief that a
structural study of quantum algorithms may have the same positive effect on our understanding of quantum
computing as the introduction of structured programming had on classical computation. This endeavor
has two clear objectives: understanding how fundamental quantum resources such as quantum parallelism
and entanglement fit into the theory of computation, and exploiting these resources to aid in designing
new quantum algorithms which can outperform the existing classical ones.
Conforming to this structural approach, the present work casts quantum parallelism as a resource
which can be used to determine the control flow of a program. This flow is usually built up by composing
three primitive operations: sequencing, branching, and recursion. Of these three, branching is the only
operation which depends on data supplied to the program. In quantum computing, this data can be a qubit
whose state is unknown. In this case, a measurement is normally used to extract a Boolean value from the
qubit and the transition to the next state depends on the measurement outcome. This procedure is similar
to sampling a Bernoulli random variable where the distribution is determined by the state of the qubit.
Hence, the form of quantum control implemented by measurements is of a probabilistic nature. A natural
question to ask is whether there is a sensible notion of branching in a quantum programming language
which operates at the quantum level, that is, without interference from the environment. This speculative
type of branching is henceforth referred to as quantum alternation or quantum control. Investigating the
viability of this concept is the main theme of this paper.
The idea of quantum control is not new. Indeed, in a quantum Turing machine [4] – the first formalism
of quantum computation – the flow of execution is described by a constant unitary operator. Thus, both
data and control may be “quantum.” Nevertheless, the passage from the quantum control mechanism
present in a quantum Turing machine to a structural notion of quantum branching in a programming
language is not clear. The first programming language designed to support quantum control was defined
by Altenkirch and Grattage in [1]. The language, called QML, provides a case statement which allows
Chris Heunen, Peter Selinger, and Jamie Vicary (Eds.):
12th International Workshop on Quantum Physics and Logic (QPL 2015).
EPTCS 195, 2015, pp. 33–42, doi:10.4204/EPTCS.195.3

34

Quantum Alternation

superposing several quantum operations without performing a measurement. However, the case statement
can only be used in certain situations specified by the introduction rules of the type system which use an
“orthogonality” judgement. A more recent work on quantum alternation is [13] where the authors propose
a language called QGCL (after Dijkstra’s Guarded Command Language) to support the paradigm of
“superposition of programs.” QGCL bases the definition of quantum control on the analogy with quantum
random walks and introduces an auxiliary system of “quantum coins” which is used to perform branching.
A more detailed discussion of both of these works and their relation to the work presented in this paper is
deferred to the section on related work. For the moment, we note that there are many similarities and a
few differences between our work and the work reported in [13].
We proceed to outline the basic properties that quantum alternation should possess. The notation
used in the sequel follows the usual mathematical framework for open quantum systems: states are
represented by density operators on some Hilbert space, and quantum operations are given by superoperators, i.e. completely positive (CP) trace-nonincreasing maps. All Hilbert spaces are assumed to be
finite-dimensional, unless otherwise stated. If H is a Hilbert space, we denote by S(H ) the set of states
on H . Thus, a superoperator is a linear map T : S(H ) → S(K ). The dynamics defined by a superoperator T : S(H ) → S(H ) is said to be reversible if T can be represented as a pure unitary operation, viz.
T (ρ) = UρU † for some unitary operator U : H → H . qbit is defined to be the 2-dimensional Hilbert
space C2 with the computational basis |0i and |1i. A qubit is a term q of type qbit, denoted q : qbit. We
define the classical states Π0 = |0ih0| and Π1 = |1ih1| corresponding to the elements of the computational
basis.
We posit the following typing judgement for quantum alternation. Given a qubit q : qbit and two superoperators T0 , T1 : S(H ) → S(K ), the alternation of T0 and T1 with respect to q should be a superoperator
Altq (T0 , T1 ) : S(qbit ⊗ H ) → S(qbit ⊗ K ). Thus,
I. Quantum alternation has the following typing judgement, where Π is a procedure context and Γ
and Γ0 are typing contexts:
Π ` hΓi P hΓ0 i
Π ` hΓi Q hΓ0 i
Π ` hq : qbit, Γi if q then P else Q hq : qbit, Γ0 i
Note that, according to the typing judgement, the branches P and Q cannot access the qubit q. There
are at least two reasons for this particular choice. Firstly, we will require that the alternation of P and Q
with respect to q is a reversible operation if P and Q are reversible, which is not necessarily the case if P
and Q are allowed access to q. Secondly, q is a resource used to superpose different statements and, as
with any type of resource, it should be in some sense consumed. This situation is not unlike the case of
measurement where the state of the qubit collapses to the classical state observed. The difference here is
that quantum branching does not extract any classical information from q, so the qubit does not collapse
to a classical state.
The second fundamental property required of quantum alternation is that it should use the information
encoded in the classical states of q. That is, the alternation should depend on a specific choice of basis for
q and each branch must correspond to a distinct basis vector. The state of q should affect the superposition
of quantum operations:
II. If the qubit q is in a classical state Πi with i ∈ {0, 1}, then Altq (T0 , T1 ) = I ⊗ Ti , i.e. the alternation
reduces to a local operation Ti on S(H ).
The second condition formalizes the intuition of classical alternation in this context. Since Altq (T0 , T1 ) is
a linear map, it follows that if ρ is a state on qbit ⊗ H then

 

A B
T0 A ∗
Altq (T0 , T1 ) :: ρ =
7→
.
C D
∗ T1 D

Costin Bădescu and Prakash Panangaden

35

The off-diagonal asterisks represent entries which are not yet determined by anything other than the blocks
on the diagonal and the condition that the result must be a positive operator. If these entries are null, then
Altq (T0 , T1 ) can be implemented by a measurement followed by merging. Hence, it is necessary to impose
additional constraints to obtain a notion of branching which may be called “quantum.” The final condition
we impose, concerning the reversibility of alternation, addresses this issue:
III. If T0 and T1 are reversible, then Altq (T0 , T1 ) is reversible.
The dynamics of a closed quantum-mechanical system is reversible, so this requirement is natural, if not
compulsory, for any definition of quantum alternation. The reversibility condition also ensures that the
implementation of alternation cannot be based on measurement.
Following the conditions introduced above, we can suggest a definition of quantum alternation in a
closed quantum system:
Let H be a Hilbert space and let U0 ,U1 : H → H be unitary operators. Given a qubit q : qbit, define
the alternation Altq (U0 ,U1 ) with respect to q by
Altq (U0 ,U1 ) = Π0 ⊗U0 + Π1 ⊗U1 .

(1)

This definition of Alt meets all three conditions and generalizes immediately to a definition of quantum
alternation controlled by a system of multiple qubits. Let qbitn be the nfold tensor product of qbit with
itself and set ` = 2n − 1. Let Π0 , . . . , Π` be the classical states of qbitn . Given q̄ : qbitn , the alternation of
unitary operators U0 , . . . ,U` : H → H with respect to q̄ is defined by
`

Altq̄ (U0 , . . . ,U` ) =

∑ Πk ⊗Uk .

(2)

k=0

This form of alternation corresponds to a quantum case statement. As we will see, the Deutsch–Jozsa
algorithm can be obtained from Deutsch’s algorithm essentially by replacing an if statement with a case
statement.
(2) is a special case of a measuring operator [7]. In the definition of a measuring operator, the classical
states Πk can be replaced by projections onto pairwise orthogonal subspaces. Thus, it is possible to
consider a slightly more general notion of quantum alternation where the superposition is controlled by
a set of pairwise orthogonal projections rather than by a system of qubits; this idea is also introduced
in [13].
The problem of defining quantum alternation in QPL amounts to finding an appropriate extension of
the definition given above to open quantum systems which is structural, compositional, and satisfies the
three aforementioned criteria.

2

Examples

Prior to defining a semantics for quantum control in open quantum systems, we present a few examples of
QPL programs which make use of quantum alternation in a closed system. Thus, all quantum operations
considered in this section are pure operations associated with a specific unitary operator defined within
the program.
We briefly review the fragment of QPL which will be used in this paper. The state of a QPL program
is a density matrix and a statement is interpreted as a superoperator. The primitives we will use are as
follows: skip is the identity superoperator; q̄ ∗= U applies the unitary transformation U to the tuple of
qubits q̄; new qbit q allocates a new qubit register named q initialized to |0i; measure q then P else Q

36

Quantum Alternation

measures the qubit register q and evaluates P or Q accordingly; discard q represents the partial trace over
the component of the state space represented by q.
We will make use of two additional constructs to illustrate quantum alternation: an if q then P else Q
statement interpreted as the superoperator defined by (1), and a case q̄ of Πk → Pk statement interpreted
as the superoperator defined by (2). Note that all branches of an alternation (e.g. P, Q, etc.) are assumed
to be pure unitary operations.
The simplest example using quantum alternation is the construction of controlled unitary operators. If
U is a unitary operator and q0 , q1 : qbit are two qubits, then
if q0 then skip else q1 ∗= U
implements a controlled-U operation. Thus, if N is the NOT gate, two nested if statements can be used
to implement the Toffoli gate:
if q0 then skip else if q1 then skip else q2 ∗= N
Implementing a controlled gate using an if statement allows for a more succint presentation of
quantum circuits in QPL. For instance, given qubits q1 , . . . , qn : qbit, the following program implements
an efficient circuit for the quantum Fourier transform (cf. [9, p. 219]):
for i = 1 to n do
qi ∗= H
for k = 2 to n − i + 1 do
if qk+i−1 then skip else qi ∗= Rk
Here Rk is the phase shift gate defined by Rk = Π0 + eiθ Π1 with θ = 2π/2k .
A more important example, exhibiting the relation between quantum parallelism and quantum alternation, is an implementation of Deutsch’s algorithm [4]. The problem is to determine whether a given
Boolean function f : {0, 1} → {0, 1} is constant.
For each x ∈ {0, 1}, let Ux : qbit → qbit be the permutation operator transposing |0i with | f (x)i and
fixing the rest of the basis. Let x ⊕ y denote the exclusive or of bits x and y. Note that 0 ⊕ x = x and
1 ⊕ x = ¬x for all x ∈ {0, 1}. Thus, Ux |yi = |y ⊕ f (x)i for x, y ∈ {0, 1}. Given qubits q0 , q1 : qbit, consider
the statement:
if q0 then q1 ∗= U0 else q1 ∗= U1
Using definition (1), this statement is interpreted as the pure operation defined by the unitary:
U f :: |0i ⊗ ψ0 + |1i ⊗ ψ1 7→ |0i ⊗U0 ψ0 + |1i ⊗U1 ψ1 .
A simple calculation shows that U f can also be defined by the map |x, yi 7→ |x, y ⊕ f (x)i. Therefore,
Deutsch’s algorithm can be implemented as follows.
new qbit q0 , q1
q0 ∗= H
q1 ∗= H ◦ N
if q0 then q1 ∗= U0 else q1 ∗= U1
q0 ∗= H

Costin Bădescu and Prakash Panangaden

37

The algorithm above can be modified to take as input a general Boolean function f : {0, 1}n → {0, 1}.
A map such as f is said to be balanced if P[ f (x) = 1] = 12 for a uniformly random x ∈ {0, 1}n . The
Deutsch–Jozsa algorithm [5], a generalization of Deutsch’s algorithm, determines whether a given Boolean
function f : {0, 1}n → {0, 1} is constant or not contingent upon the assumption that f either constant or
balanced. An implementation of this algorithm is obtained essentially by replacing the if statement above
with a case statement. Indeed, for each x ∈ {0, 1}n , let Ux be the permutation operator transposing |0i
with | f (x)i and fixing the rest of the basis. Suppose q̄0 : qbitn and q1 : qbit are given. The statement
case q̄0 of |xi → q1 ∗= Ux

(3)

implements the unitary Ũ f :: |x, yi 7→ |x, y ⊕ f (x)i with x ∈ {0, 1}n . Hence, the Deutsch–Jozsa algorithm
can be written as:
new qbitn q̄0
new qbit q1
q̄0 ∗= H ⊗ n
q1 ∗= H ◦ N
case q̄0 of |xi → q1 ∗= Ux
q̄0 ∗= H ⊗ n
The map which assigns the unitary operator Ũ f to a Boolean function f appears in a number of
quantum algorithms. For instance, if f (x0 ) = 1 for some x0 ∈ {0, 1}n and f (x) = 0 otherwise, then Ũ f is
the “black box oracle” O used to implement Grover’s search algorithm (see e.g. [9, p. 254]). Similarly, Ũ f
is used in the period-finding algorithm if f is a periodic function.
The ability of quantum computation to superpose multiple evaluations of a function f in a single
application of a unitary operator is often referred to as quantum parallelism. Considering the permutation
matrix Ux as an evaluation of f at x, the definition of Ũ f as the case statement in (3) shows that quantum
alternation embodies a form of quantum parallelism. Furthermore, the fact that an application of Ũ f is
considered a O(1) operation is reflected in the syntactic representation of alternation as a conditional
construct.
Finally, an elementary but important observation is that the conditional statement
if q0 then skip else q1 ∗= eiθ
implements a controlled phase. Since skip and q1 ∗= eiθ are physically indistinguishable as quantum
operations, it follows that quantum alternation is not directly physically realizable. Rather, it represents a
conceptual semantic construct in a quantum programming language. Furthermore, this example shows that
there is no structural semantics for quantum alternation which is based on superoperators with extensional
equality.

3

Semantics

In this section, we give a definition of quantum alternation for open quantum systems and present a formal
semantics for QPL with quantum control. We only define alternation with respect to a single qubit q : qbit
and two branches. A formula for the general case can be easily obtained using the same techniques.

38

Quantum Alternation

Let H , K , and L be Hilbert spaces. A finite set S of nonzero bounded operators from H to K
defines a superoperator T : S(H ) → S(K ) by
T (ρ) =

∑

EρE †

E∈S

if

∑

E † E 6 I.

(4)

E∈S

We will refer to S as a decomposition of T or, when the superoperator is implicit, as a Kraus decomposition. A well-known theorem of Kraus [8] states that every superoperator has a decomposition, but this
decomposition is never unique. Thus, two Kraus decompositions S and T are said to be extensionally
equal, denoted S ' T , if the corresponding superoperators are equal. The empty set ∅ corresponds to
the 0 superoperator.
If S ⊆ B(K , L ) and T ⊆ B(H , K ) are Kraus decompositions, their composition S ◦ T is defined
to be the set obtained
√ from the multiset {E ◦ F | E ∈ S , F ∈ T } by replacing ` occurences of a bounded
operator K with `K and removing any occurrence of the zero operator. Each Hilbert space H with
identity operator I : H → H determines a unique Kraus decomposition idH = {I} which acts as the
identity for composition. Thus, we can define a category C with Hilbert spaces H , K as objects
and Kraus decompositions S ⊆ B(H , K ) as morphisms S : H → K . A statement in QPL will be
interpreted as a morphism in C.
We define the quantum alternation of two morphisms1 S , T : H → K to be the morphism S • T :
qbit ⊗ H → qbit ⊗ K defined by
)
(
F
E
+ Π1 ⊗ p
| E ∈ S ,F ∈ T .
S • T = Π0 ⊗ p
|T |
|S |
Here the projections Π0 and Π1 are determined by the qubit q : qbit which is used in the alternation. It is
easy to see that S • T satisfies condition (4). Moreover, if S = {U0 } and T = {U1 } where U0 and U1
are unitary operators, then S • T defines the same superoperator as Altq (U0 ,U1 ). Indeed, the elements
of S • T are of the form Altq (Ê, F̂) where
E
,
Ê = p
|T |

F
F̂ = p
,
|S |

for E ∈ S and F ∈ T .

Thus, S • T can be understood operationally as randomly replacing a state ρ with KρK † / tr(KρK † )
with probability tr(KρK † ) where K is the “pure” quantum alternation Altq (Ê, F̂).
We briefly recall the definition of the category Q associated to the superoperator semantics of QPL. A
signature σ is defined to be a tuple of positive integers σ = (n1 , . . . , ns ). If σ and τ are signatures, then
their concatenation σ ⊕ τ and tensor product σ ⊗ τ are also signatures. To each such σ , we associate a
complex vector space
Vσ = M(C, n1 ) × . . . × M(C, ns ),
where M(C, k) denotes the vector space of k × k complex matrices. Clearly, M(C, k) = B(Ck ), so the
elements of Vσ are tuples of bounded operators. We define the trace of an element in Vσ to be the sum of
the traces of its components and say that an element of Vσ is positive if all of its components are positive
operators. Thus, a density operator in Vσ is a positive element with trace at most 1. The semantics of QPL,
as defined in [11], is given by the category Q whose objects are signatures σ , τ and whose morphisms are
superoperators T : Vσ → Vτ .
1 This

equation also appears in [13].

Costin Bădescu and Prakash Panangaden

39

A semantics for QPL with quantum control is obtained by replacing the morphisms of Q with Kraus
decompositions. The resulting category is the category C defined above. We assign to each QPL primitive
a Kraus decomposition and define the semantics of an arbitrary program by structural induction. Although
the choice of Kraus decomposition for a primitive may be arbitrary, we will rely on the fact that the
computational basis for qbit is the “preferred” basis and give Kraus decompositions which are particularly
simple to express using |0i and |1i. For instance, let in0 , in1 : σ → σ ⊕ σ be the injections in0 (ρ) = (ρ, 0)
and in1 (ρ) = (0, ρ). We can then define the semantics as follows.
:σ →τ

JP; QK

= JQK ◦ JPK

:σ →σ

JskipK

= {id}

: σ → σ ⊕σ

= {in0 }

: σ → qbit ⊗ σ

= {|0i ⊗ −}

: qbit ⊗ σ → σ

= {h0| ⊗ id, h1| ⊗ id}

: σ ⊕σ → σ

= {in†0 , in†1 }

Jmeasure qK

: σ → σ ⊕σ

= {in0 ◦Π0 , in1 ◦Π1 }

:σ →σ

= {U}

Jif q then P else QK

: qbit ⊗ σ → qbit ⊗ τ

= JPK • JQK

Jnew bit b := 0K
Jnew qbit q := 0K

Jdiscard qK
JmergeK

Jq ∗= UK

The semantics defined above cannot be lifted to a semantics of superoperators, because quantum alternation
does not preserve extensional equality. Indeed, the Kraus decompositions {U0 } • {V0 } and {U1 } • {V1 }
are extensionally equal if and only if there exists a phase θ such that U0 = eiθ U1 and V0 = eiθ V1 , so
{U0 } • {V0 } ' {U1 } • {V1 } may not hold even if {U0 } ' {U1 } and {V0 } ' {V1 }. The failure of quantum
alternation to preserve extensional equality shows that there is no compositional superoperator semantics
which satisfies the definition of alternation given in the introduction. However, as the examples above and
previous work [1] [13] show, that particular definition of quantum alternation for closed quantum systems
is the most intuitive and practical.
An important part of the superoperator semantics for QPL is the ability to define recursion. The
category Q is CPO-enriched [11], a fact which together with the ⊕ operation makes Q a traced monoidal
category. Since each Kraus decomposition determines a unique superoperator, we can define an order
on the Hom-sets of C using the order on the Hom-sets of Q, viz. S v T if the relation holds for the
corresponding superoperators. We can then try to adapt the situation to quantum alternation. But we have
the following proposition.
Proposition. Quantum alternation is not monotone with respect to the v order.
Proof. Let H be the Hilbert space associated to a signature σ . Let U and V be two unitary operators on
H defining Kraus decompositions S = {U} and T = {V }. Let ρ be a state on qbit ⊗ H defined by


A B
ρ=
C D
where B 6= 0. Then S v S and ∅ v T , but

0
UBV †
(S • T − S • ∅)(ρ) =
.
VCU † V DV †


Recall that if a diagonal entry of a positive matrix is zero, then the corresponding row and column must be
all zero. Since UBV † 6= 0, it follows that (S • T − S • ∅)(ρ) is not positive. Therefore, S • ∅ 6v S • T ,
but S v S and ∅ v T .


40

Quantum Alternation

This counter-example shows that quantum alternation is not compatible with the semantics for
recursion defined in [11]. Since a CP map T is a pure operation ρ 7→ EρE † if and only if all operations
completely dominated by it are its nonnegative multiples [10], it appears that the reversibility condition
(III) makes quantum alternation fundamentally incompatible with the standard order on CP maps.
Quantum operations admit several equivalent representations based on the structure theory of CP
maps [10]. Each representation illustrates a different aspect of the quantum operation. The rest of this
section defines quantum alternation in terms of Stinespring representations. This alternative perspective
will clarify the relation between our definition of alternation and that of [1].
Let T : S(H ) → S(K ) be a superoperator. By Stinespring’s theorem, T can be written as T (ρ) =
V † (ρ ⊗ IA )V , where A is a Hilbert space called the ancilla and V : K → H ⊗ A is a bounded operator.
The ancilla models the environment of the operation T . The pair (A ,V ) is called a Stinespring representation of T . Stinespring’s theorem can be interpreted as saying that any quantum operation T can be
implemented as a pure operation on a larger Hilbert space. Given a Kraus decomposition S defining a
superoperator T : S(H ) → S(K ), a Stinespring representation of T can be obtained from S as follows.
Let A be a Hilbert space with basis {|Ei}E∈S and define V : K → H ⊗ A by
Vψ =

∑

E † ψ ⊗|Ei.

E∈S

Then (A ,V ) is a Stinespring representation of T . Conversely, a representation (A ,V ) of T with a fixed
basis for A determines a Kraus decomposition of T .
If S and T are Kraus decompositions, then there is a natural Stinespring representation for the
superoperator determined by S • T , viz. the pair (E ,W ) defined by E = A 0 ⊗ A and
Wψ =

∑

Altq (Ê, F̂)† ψ ⊗|Fi ⊗|Ei,

E∈S ,F∈T

where A and A 0 are the ancillas of the Stinespring representations determined by S and T , respectively.
Thus, the environment of the quantum alternation is the tensor product of the environments of the quantum
operations involved.

4

Related Work

Altenkirch and Grattage [1] defined QML, a quantum programming language with quantum control based
on a new type of judgement called “orthogonality.” The denotational semantics for QML is based on
expressing superoperators T : S(A ) → S(B) in the form T (ρ) = TrG U(ρ ⊗|ξ ihξ |)U † , where H and G
are Hilbert spaces, ξ ∈ H is a fixed unit vector, and U : A ⊗ H → B ⊗ G is an isometry. Defining the
bounded operator V : B → A ⊗ G by V ψ = U(ψ ⊗ ξ ), we obtain an equivalent Stinespring representation
(G ,V ) of T . In QML, a strict morphism corresponds to a superoperator with dim G = 1. Thus, strict
morphisms correspond to singleton Kraus decompositions in our semantics, i.e. pure operations ρ 7→ EρE †
with E † E 6 I. Only strict morphisms may be alternated in QML. The alternation is further restricted by
the orthogonality judgement, which is implemented by an incomplete set of introduction rules.
The work of Mingsheng Ying et al. [13] is very recent and closely related to ours, though their attitude
is quite different. They also note that the superoperator semantics is not compositional, but they are
content with this. They do not define a Kraus semantics as we do. However, our construction is essentially
embedded inside their definition of their superoperator semantics. Perhaps, the right way to look at it is
that we have both defined a Kraus semantics but they have gone on to give a superoperator semantics

Costin Bădescu and Prakash Panangaden

41

as an abstract interpretation of the Kraus semantics. In such a case it often happens that the resulting
semantics is not compositional. The fact that quantum alternation is not monotone using the Löwer order
is not noted by them. Ying has a different approach to recursion based on second quantization [12] which
seems to avoid the difficulties noted here but we do not understand it well enough to comment on it here.
Certainly, combining recursion with quantum alternation will require some radically new idea.

5

Conclusion

Superficially this may strike the reader as a very negative, or perhaps schizophrenic, paper. Certainly, we
feel that quantum alternation as often casually discussed, is quite problematic and some fix based on type
theory or syntactic control will not serve to make it meaningful. On the other hand we see this as the start
of some new directions.
Quantum alternation is not really physically meaningful. Even if it is, it seems incompatible with
recursion. Is there some crisp no-go theorem here? If so, what is meaningful? Ideally one should
start from physical systems and develop a structural understanding from which linguistic entities should
emerge. It seems to us that quantum alternation is a fantasy arising from programming language semantics
rather than from physics. What we propose is that one should look closely at, say, quantum optics where
devices like Mach-Zehnder interferometers [6] provide physical situations that are reasonably viewed
as alternation. Note that in MZ interferometers the system being split is the system on which the two
alternate operations are applied; there is not a distinct control qubit.
On a more mathematical note one can question the arbitrariness of the Kraus semantics; different
Kraus semantics correspond to the same operator so doesn’t that mean that the semantics is making
unobservable distinctions? However, this is not the case. Different Kraus decompostions correspond to
different choices of measurement that an experimenter may choose to make. In the standard paradigm,
with classical control, the contexts provided by the language do not make these differences visible but in
the enriched language they do.
One can still ask whether there is a canonical decomposition one can associate to a superoperator
which can be used to define alternation. Indeed there is and it involves more sophisticated mathematics;
we choose not to include it in this note. There is an operator-algebra analogue of the Radon-Nikodym
theorem due to Belavkin [3] and, independently, Arverson [2]. Given two CP maps S and T with S v T , it
gives a representation of S in terms of a chosen minimal Stinespring representation of T and a positive
operator DT (S), the Radon-Nykodim derivative of S with respect to T . Now there is a map, the tracial
map, which can be proven to dominate any CP map from B(H ) to B(K ). This gives a canonical
decomposition of an arbitrary CP map; we have worked out a denotational semantics of the language with
quantum alternation based on this approach. The trouble, and the reason we have not included it here, is
that the physical significance of this semantics is unclear to us.

Acknowledgements
Panangaden would like to thank Mingsheng Ying for discussions allowing us to understand the relationship
between our semantics for quantum alternation. He would also like to thank Vincent Danos who was
present at the discussion and made several insightful remarks sprinkled with some interesting non sequiturs.
We thank the referees for their comments. We have both been supported by NSERC. Bădescu has also
been supported by a scholarship by FQRNT. Panangaden acknowledges the generous support of the
Chinese Academy of Sciences, Institute of Mathematics, during his stay in Beijing.

42

Quantum Alternation

References
[1] Thorsten Altenkirch & Jonathan Grattage (2005): A functional quantum programming language. In: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, 2005., IEEE, pp. 249–258,
doi:10.1109/LICS.2005.1.
[2] W. Arveson (1969): Subalgebras of C∗ -algebras. Acta Math 123, pp. 141–224, doi:10.1007/BF02392388.
[3] V. P. Belavkin & P. Staszewski (1986): Radon-Nikodym theorem for completely positive maps. Reports on
Mathematical Physics 24(1), pp. 49–55, doi:10.1016/0034-4877(86)90039-X.
[4] D. Deutsch (1985): Quantum theory, the Church-Turing Principle and the universal quantum computer. Proc.
Roy. Soc. Lond. A 400, p. 97, doi:10.1098/rspa.1985.0070.
[5] D. Deutsch & R. Jozsa (1992): Rapid solution of problems by quantum computation. Proc. Roy. Soc. Lond. A
439, p. 553, doi:10.1098/rspa.1992.0167.
[6] J. C. Garrison & R. Y. Chiao (2008):
doi:10.1093/acprof:oso/9780198508861.001.0001.

Quantum Optics.

Oxford University Press,

[7] A. Yu. Kitaev, A. H. Shen & M. N. Vyalyi. (2002): Classical and quantum computation. Graduate Studies in
Mathematics, American Mathematical Society, Providence, RI.
[8] K. Kraus (1983): States, Effects and Operations.
doi:10.1007/3540127321 22.

Lecture Notes in Physics 190, Springer-Verlag,

[9] M. Nielsen & I. Chuang (2000): Quantum Computation and Quantum Information. Cambridge University
Press.
[10] Maxim Raginsky (2003): Radon-Nikodym derivatives of quantum operations. Journal of Mathematical Physics
44(11), pp. 5003–5020, doi:10.1063/1.1615697.
[11] Peter Selinger (2004): Towards a Quantum Programming Language. Mathematical Structures in Computer
Science 14(4), pp. 527–586, doi:10.1017/S0960129504004256.
[12] Mingsheng Ying (2014): Quantum Recursion and Second Quantisation. Available on the arXiv 1405.4443.
[13] Mingsheng Ying, Nengkun Yu & Yuan Feng (2014): Alternation on quantum programming: from superposition
of data to superposition of programs. Available in arXiv as 1402.5172.

