20
Probabilistic Quantum Computation and Linear Optical Realizations
Norbert Lütkenhaus
University of Waterloo, Institute for Quantum Computing, 200 University Ave. West, Waterloo, Ontario, N2L 3G1, Canada
20.1 Introduction
Quantum computation is usually thought of as a sequence of quantum gates. This sequence of gates decomposes the desired total unitary operation of our computation. It is followed by a measurement that extracts the result of the computation. In Chapter 11, a different concept was introduced and a specific, highly entangled input state was prepared. The computation was performed by measuring out the individual systems in a specific pattern. Both approaches have one thing in common: in principle they work deterministically. In this chapter, we introduce a concept of computation that allows us to incorporate probabilistic elements into a computation, which in the end becomes deterministic again. The reason for proceeding in this manner is that some specific physical systems do not allow implementing unitary operations that exactly implement basic two‐qubit gates, for example, a controlled‐NOT (CNOT) operation. An example for such a physical system is an optical realization where qubits are represented by single photons with the polarization degree of freedom forming the two‐dimensional Hilbert space. If we restrict the manipulation of such qubits to linear optics, that is, using only combinations of beam splitters and phaseshifters, we find that we cannot realize CNOT gates perfectly even if we add feed‐forward with auxiliary photonic systems and photon counting. Following the ideas outlined by Knill et al. (1), with the concepts introduced in this chapter, we will see that one can use the same resources for universal computation with the help of probabilistic gates. We refer to this scheme as the Knill–Laflamme–Milburn (KLM) scheme.
We will introduce the basic mechanism, which shifts the difficulty of the gate operation from the direct deterministic operation to the problem of probabilistically generating an offline resource of certain auxiliary states. Then, we will introduce more specifically the framework of linear optics and the realization of qubits. In the main section, we introduce the KLM scheme, which shows how one can realize universal computation using linear optics.
20.2 Gottesman/Chuang Trick
In this first section, we show that computation can be performed not only in the paradigm of quantum gates but also by preparing entangled auxiliary states, measurements, and single‐qubit operations. The essential observation comes from an article by Gottesman and Chuang (2): Consider two qubits on which one would like to perform a CNOT operation. One can do so using two teleportation steps (see Chapter 14), as shown in Figure 20.1a, with a subsequent CNOT operation. Next, one can replace a set of single‐qubit Pauli operators followed by a CNOT gate by another arrangement where one first applies the CNOT gate and then applies a different set of Pauli operators. A simple set of translation rules (see Figure 20.2) allows to calculate the required set of new Pauli operators. As a result, we can think of our device as preparing a new state |Ψ〉1,2,3,4, which is then connected with the input qubits via Bell measurements. Then, the application of Pauli operations effects a CNOT operation (see Figure 20.1b).
Figure 20.1 The teleportation procedure in (a) allows to shift the problem of deterministic gate performance to the probabilistic generation in (b) of the offline resource of the state |Ψ〉1,2,3,4.
Figure 20.2 (a) The definition of the basic single‐qubit operations. (b) One can verify these identities directly in the canonical basis of eigenstates of the Z operator. (c) The Hadamard transformation H provides useful identities so that the identities of (b) directly lead to the identities of (d).
With that, we have performed a conceptually important step. The ability to produce the state |Ψ〉1,2,3,4 = CNOT2,3|Φ+〉1,2|Φ+〉3,4, where the subscripts denote the qubits involved, together with the ability to perform the Bell measurements suffice to perform universal quantum computing. Typically, the generation of the required state |Ψ〉1,2,3,4 is difficult, but now we have the opportunity to generate this state probabilistically. In repeated attempts, once we have successfully generated the state, we can use it deterministically in the scheme outlined above. Clearly, though, for this procedure, we require quantum memory to store the qubits on which we want to perform the CNOT, until we succeed in creating the resource state |Ψ〉1,2,3,4.
20.3 Optical Background
In this section, we introduce the basic ideas from optics and show how to realize qubits in optics. Then, we introduce a restricted class of optical operations, called linear optics, which are important in an experimental setting, as these operations can be implemented with basic optical tools, such as beam splitters and phaseshifters.
20.3.1 Optical Qubits
The idea of Gottesman and Chuang is particularly important for the implementation of quantum logic operation with optical qubits. Typically, the qubits are represented by single photons, although other implementations have been proposed. In practice, there are no nonlinear optical interactions available that are strong enough to allow the implementation of unitary CNOT operations. However, as we will see, once we are able to use probabilistic operations, we can perform CNOT operations that succeed asymptotically with probability one, even with linear optics alone. Before we come to this point, let us explain how one can implement qubits in optics.
The first implementation is the occupation‐number qubit. It uses the superposition of Fock states of a single optical mode A. Here we have the logical basis states (where occ stands for occupation number)
On the left‐hand side, the notations 0 and 1 denote logical values corresponding to an orthogonal basis set. On the right‐hand side the ket‐representation denotes the photon number in mode A. The problem with this qubit realization is that the qubit subspace is not formed of energy eigenstates, resulting in problems with decoherence, and that single‐qubit operations are not readily available.
The most widespread implementation of a qubit is the bosonic qubit, also referred to as dual‐rail encoding. Here, one uses two optical modes A and B with one photonic excitation in total. The logical states of this system can be represented by
where the numbers on the right‐hand side, for example, in |0, 1〉 AB refer again to the photonic excitation in modes A and B. An example of this implementation is a single photon with the polarization degree of freedom. The two modes are any two orthogonal polarization modes of the photon. In this case, the qubit is part of an energy eigenspace. Moreover, single‐qubit operations are simply polarization rotations of the photon in the Poincare sphere, which can be achieved easily.
Both representations are related as the dual‐rail encoding corresponds to two complementary photon‐number qubit representation, in its two modes. In that sense we have, for a general state, the relation
20.3.2 Linear Optics Framework
The workhorse of optical experiments is the manipulation via linear optical elements, such as beam splitters and phaseshifters. This class of manipulations can be described using the creation and annihilation operators ai
and 
of the involved optical modes i = 1, …, N. The basic properties of these operators are given by their commutation relation 
and by their operation on the Fock states, 
. Then, a beam splitter can be described by a unitary operation U
BS = 
, where the real number θ determines the transmittivity of the beam splitter. A phaseshifter acts with the unitary operation UP
= exp (iφa
†
a), where the real number φ is the value of the optical phaseshift. Actually, any combination of phaseshifters and beam splitters on N modes can be described by the unitary evolution operator (3)
where Λ is a Hermitian N × N matrix and 
= (a
1, a
2, …, aN
). We can understand the action of this evolution in the Heisenberg picture and find between input and output mode operators in the relation
The action of any linear optical network can be given in the form of Eq. 20.7. Moreover, Reck et al. (4) have also shown that any input–output relation of the form of Eq. 20.7 can be realized by a combination of beam splitters and phaseshifters. The number of required optical elements scales as N 2 with the number of involved optical modes.
Unfortunately, the interaction provided by linear optics does not suffice to implement exact Bell measurements on polarization qubits (5). Nevertheless, as we will see below, it is possible to approximate a Bell measurement with arbitrary precision with rising costs of resources, for example, in the form of highly entangled states. We refer to this as a near‐deterministic process. The production of the entangled states required in the Gottesman–Chuang trick cannot be prepared deterministically, and here we will see later how to do this probabilistically with linear optics.
20.4 Knill–Laflamme–Milburn (KLM) Scheme
So far, we have learned that computation can be performed by a combination of preparation of auxiliary states, measurements, and single‐qubit operations. It turns out that the Bell measurements required in the Gottesman–Chuang trick cannot be implemented perfectly with linear optics. Moreover, the generation of entangled auxiliary states is hard to achieve in general. Knill, Laflamme, and Milburn solved this problem in several steps. In the first step, they extended the Gottesman–Chuang procedure on the qubit level and then showed that the measurements required for this extended scheme can be implemented by linear optics near deterministically. That is, the probability of failure can be made arbitrarily small with increasing resources, for example, the number of qubits in the required auxiliary state. To solve the problem of preparation of these auxiliary states, they made use of the fact that the auxiliary states can be generated probabilistically without affecting the overall computation. We will show how a set of universal gates can be implemented probabilistically with linear optics.
20.4.1 Extension of Gottesman–Chuang Trick
We start by extending the procedure of Gottesman and Chuang on the abstract level of qubits. In the extension, we use not only a maximally entangled state of 2 qubits, but a state 
of 2n qubits, numbered 1, …, 2n. This state is described by the equation
where we use terms like |1〉
j
as a short hand for the state 
.
To see how one can use this state to teleport a general input α|0〉0 + β|1〉0 prepared in qubit 0, let us proceed in two steps. In the first step, we perform a measurement on the input qubit and on the first n qubits of the state 
. It is a quantum nondemolition (QND) measurement of the total number of qubits being in the state |1〉. The QND measurement with outcome k effects a projection of the input state onto a subspace spanned by all qubit states of the input and the first n qubits with exactly k qubits in state |1〉. The range of the result k is [0, …, n + 1]. For the inner values 0 < k < n + 1, that is, for k ≠ 0 and k ≠ n + 1, we find the conditional state
Obviously, only the qubits 0, k, and n + k differ in the terms of the superposition. Omitting the remaining qubits, we have
Now, we perform a measurement to project out the qubits 0 and k to recover the teleported state in qubit k. Any measurement on qubits 0 and k will serve our purpose as long as all of its outcomes project onto states of the form 
. Then, we find the conditional state 
, up to an unimportant global phase. The relative phase between the two terms depends on the measurement outcome of this last step. It is therefore known and can be corrected by applying a single‐qubit operation. Therefore, once we find 0 < k < n, we have successfully teleported the state of qubit 0 to the qubit n + k. This qubit can then be selected to be the output qubit.
In the case where we find for k the value 0 or n + 1, only one term appears in the expression of the conditional state, and the teleportation attempt fails since the input state is effectively measured to be |0〉0 or |1〉0. This happens with the total failure probability 
, which is independent of the input state. If there were a dependence, then the fact that one does not obtain these values would give away information about the input state, which contradicts the assumption of perfect teleportation. For a growing n, the failure probability goes to zero, so that we have a near‐deterministic teleportation.
Let us come back to the implementation with linear optics. The extension of the Gottesman–Chuang trick as described above is important since the measurement outlined above can be performed by linear optics alone. Before discussing this measurement, let us show how these measurements can be used to implement a CNOT operation on two qubits. The total network is shown in Figure 20.3a and uses a generalization of the CNOT operation where not only one, but several qubits are affected by a bit‐flip operator X conditioned on the state of the source qubit. Here, we use it after the generalized Bell measurement. The knowledge of k tells us not only which qubit carries the input signal (up to the operation that corrects the relative phase) but we project also the input modes 1, …, n, without k, into a definite state. Therefore, we can apply correcting bit‐flip operations X for all those generalized CNOT operations that were conditioned on these qubits. More specifically, we have to apply the operation Z k − 1 whenever the input qubit is teleported to output qubit k.
Figure 20.3
(a) The basic trick of Gottesman and Chuang can be extended using the two pairs of input states 
with 2n qubit each, as given in the text. As a result of the extended Bell measurement, one finds the teleported qubit in qubit k, which is then selected. After this teleportation, one has to apply a correction operation on that qubit before applying the CNOT gate. (b) In the replacement picture, one first applies generalized CNOT gates to the input states. Then, after the Bell measurements, one performs correction operations. Here, we explicitly wrote the correction Zk
that becomes necessary because of the influence of the nonselected qubits via the generalized CNOT gates.
It turns out that one can again interchange the multi‐qubit operations with the set of single‐qubit operations as shown in Figure 20.3b, although the exact form of the single‐qubit operations goes beyond the scope of this section.
20.4.2 Implementation with Linear Optics
In the previous section, we found an extension to the procedure of Gottesman and Chuang that performs quantum computation with auxiliary states and measurements. Although this operation is now no longer deterministic, the success probability can be brought arbitrarily close to one so that we refer to this as near deterministic. What we want to show next is that we can implement the measurements introduced in this scheme by linear optics alone.
Looking back at the two steps of the extended Bell measurement, which we introduced above, what we need to do is to perform a projection measurement on the input qubit and the first n qubits of the state 
in such a way that we learn the number of qubits being in the state |1〉, but we cannot trace back which qubits were in this state. In the implementation with dual‐rail bosonic qubits, one needs to perform a complete measurement on the n + 1 first modes of the n + 1 dual‐rail qubits, and also in a second step of the n + 1 second modes of these qubits, so that we have no information from which modes the photons came. The two measurements, on the first and on the second mode of each qubit, are identical, so we first concentrate on a measurement on the first set of modes.
Actually, a linear optical network realizing a discrete Fourier transform on the n + 1 first modes followed by a photon‐number measurement in these modes serves our purpose. It is described by the input–output relations for the annihilation operators of these n + 1 modes, denoted by 
, as
The matrix F
n + 1 has matrix elements {F
n + 1}
pq
= 
. This transformation is a special case of Eq. 20.7. It can therefore be implemented by linear optics with the number of optical elements scaling as n
2. Clearly, this type of measurement gives us the value k via the total number of registered photons. The value k indicates where to find the teleported qubit. One can calculate what happens to the two remaining contributions once we observe a certain pattern of photon detections in the n + 1 output modes. It turns out (1) that the photon‐detection pattern determines the relative phase between the two contributions, which can be compensated by a local optical phaseshift on the first mode of qubit n + k, which influences the phase of the |1〉
n + k
state, while it leaves the state |0〉
n + k
invariant.
The same type of measurement is then performed on the second modes of the dual‐rail qubits of input and the first n qubits, so that we complete the decoupling of the output qubit n + k from the qubits 0 and k in Eq. 20.10. Necessarily, the total photon number after this second Fourier transform will now be n + 1 − k. This allows us to detect whether some loss of photons occurred in the set‐up, either in the linear optical elements or in the photon detectors themselves. Loss will lead to a failure of the teleportation step, although we do not consider it here. Still, the exact pattern of photon detection gives rise again to a relative phase between the two contributions in the teleportation step, and can now be corrected by a single‐qubit operation on the output qubit n + k.
20.4.3 Offline Probabilistic Gates
In the previous sections, we have seen how we can perform universal quantum computation by measurements that can be realized by linear optics. As a prerequisite, we need some entangled auxiliary states. We now demonstrate how to generate these entangled states using only linear optics. For this, we make use of the fact that these states can be generated probabilistically, as they are now an offline resource that is integrated into our computation scheme only once we succeed in generating the state.
Here, we do not demonstrate how to generate the exact auxiliary state that we require in the KLM scheme. Instead, we show that one can realize a universal set of gates probabilistically via linear optics, so that in principle, any quantum state of dual‐rail qubits can be generated.
The single‐photon sources prepare initial states |0〉, for example, via the polarization state of the generated photon. Single‐qubit operations are simple polarization rotations. So, we are left to show that we can probabilistically implement at least one two‐qubit operation that allows us to complete a universal set of gates. We choose here the controlled SIGN (CSIGN) gate that realizes the unitary mapping
In the optical implementation of dual‐rail qubits, this gate can be decomposed as shown in Figure 20.4. This decomposition utilizes an operation that is no longer based on the qubit idea: the nonlinear‐sign‐shift gate (NSS) acts on the Fock space of a single mode with up to two excitations. The unitary operation is defined as
Clearly, this operation cannot be realized by linear optics deterministically. However, it is sufficient to generate this transformation probabilistically within the domain of linear optics. Here, we show how to do this.
Figure 20.4 A CSIGN gate can be implemented using two nonlinear sign shift gates (see text). Both beam splitters have equal transmission and reflection coefficients.
The NSS operation acts as the identity operation on the Fock space with 0 or 1 photons. In the complete set‐up of Figure 20.4, two photons can enter the NSS gate devices only if both qubits are in the state |1〉, since in that case the interference effects assure that there are two photons either in mode 2 or in mode 4. More precisely, the beam splitter BS 1 acting on modes 2 and 4 realizes the transformation
Then the two NSS‐devices assure that both terms acquire a minus sign. The second beam splitter BS 2 then recombines the states in a way that restores the dual‐rail qubit form so that we obtain overall the output state −|1, 1〉2,4. In all, this effects the CSIGN gate on the dual‐rail qubits.
So far, we shifted the problem of generating the CSIGN gate to the implementation of the NSS gate. A probabilistic implementation has been proposed by Knill et al. (1). It uses three beam splitters, one auxiliary photon, and two photodetectors. The scheme is sketched in Figure 20.5. The NSS gate works successfully whenever the detector D
1 detects exactly one photon, and the detector D
2 registers no photon. The calculations are straightforward (6), and one finds that the required beam‐splitting ratios are given by η
2 = (
− 1)2 and η
1 = η
3 = 
. The success probability of such an NSS gate is 1/4, so that the construction of a CSIGN gate based on two NSS gate operations succeeds with probability of 
. One can optimize the linear optical set‐up for a CSIGN operation directly and finds an improved success probability of 
(7). There are different set‐ups to realize gates, using also polarization entangled photon pairs to realize gates (8). For us, however, it is important to see that one can indeed realize probabilistically a set of universal gates, so that with some probability of success we can engineer the states that are required to perform near‐deterministic gate operations of the CNOT gate.
Figure 20.5 A probabilistic nonlinear sign shift gate can be implemented using a single photon source and three beam splitters. For the values of the transmittivities, see text. The gate works successfully if the upper detector detects one photon, while the lower detector does not detect a photon.
References
- 1 Knill, E., Laflamme, R., and Milburn, G. (2001) A scheme for efficient quantum computation with linear optics. Nature, 409, 46.
- 2 Gottesman, D. and Chuang, I.L. (1999) Demonstrating the viability of universal quantum computation using teleportation and single‐qubit operations. Nature, 402, 390–393.
- 3 Vogel, W., Welsch, D.‐G., and Wallentowitz, S. (2001) Quantum Optics: An Introduction, 2nd edn, Wiley‐VCH Verlag GmbH, Berlin.
- 4 Reck, M., Zeilinger, A., Bernstein, H.J., and Bertani, P. (1994) Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73, 58–61.
- 5 Lütkenhaus, N., Calsamiglia, J., and Suominen, K.‐A. (1999) Bell measurements for teleportation. Phys. Rev. A, 59, 3295–3300.
- 6 Ralph, T.C., White, A.G., Munro, W.J., and Milburn, G.J. (2002) Simple scheme for efficient linear optics quantum gates. Phys. Rev. A, 65, 012314.
- 7 Knill, E. (2002) Quantum gates using linear optics and postselection. Phys. Rev. A, 66, 052306.
- 8 Pittman, T.B., Jacobs, B.C., and Franson, J.D. (2002) Demonstration of nondeterministic quantum logic operations using linear optical elements. Phys. Rev. Lett., 88, 257902.