Thresholds for Linear Optics Quantum Computation
Abstract
We previously established that in principle, it is possible to quantum compute using passive linear optics with photodetectors knill:qc2000b . Here we describe techniques based on error detection and correction that greatly improve the resource and device reliability requirements needed for scalability. The resource requirements are analyzed for ideal linear optics quantum computation (LOQC). The coding methods can be integrated both with loss detection and phase errorcorrection to deal with the primary relaxation processes in nonideal optics, including detector inefficiencies. The main conclusion of our work is that the resource requirements for implementing quantum communication or computation with LOQC are reasonable. Furthermore, this work clearly demonstrates how special knowledge of the error behavior can be exploited for greatly improving the fault tolerance and overheads of a physical quantum computer.
]http://www.c3.lanl.gov: knill
I Introduction
In knill:qc2000b we proposed that linear optics quantum computation (LOQC) is a viable option for physically realizing quantum computers. The proposal depends on a series of optical protocols that require single photon state preparation and measurement whose outcome can be used to control other optical elements. The basic idea is to kick back the hidden nonlinearities in photodetectors to qubits encoded in pairs of optical modes (photonic qubits). The protocols were shown to implement the necessary quantum gates with arbitrarily high probability of success. In their simplest form, the resources required for implementing the protocols grow rapidly as the desired success probability is increased. We noted that due to the general accuracy threshold theorem aharonov:qc1996a ; kitaev:qc1997a ; knill:qc1998a ; preskill:qc1998a , the model scales efficiently asymptotically, with constant overhead for implementing the standard fault tolerant model of quantum computation. We also suggested that with the use of erasure codes grassl:1996a , this overhead could be significantly reduced.
Here we apply the techniques of of quantum errordetection and correction to greatly increase the efficieny of implementing quantum information processing by LOQC. We first show that for ideal LOQC (where errors in devices are ignored), it is possible to use a two qubit errordetecting code to rapidly eliminate the probability of failed implementations of the two qubit gates. This follows from a threshold analysis demonstrating a threshold of for an error model where the errors are measurements at known locations. One consequence of this result is that the nondeterministic gates of knill:qc2000b need only be implemented using the  or photon prepared states. The next task is to demonstrate that the main sources of device errors can be efficiently eliminated. We accomplish this by adding phase errorcorrection, and more importantly erasure coding methods. The latter serves the purpose of removing errors caused by particle loss and detector inefficiency, exploiting the builtin loss detection capabilities of basic LOQC. In the process we give a conservative bound on the threshold for the erasure error model.
On the basis of this paper and knill:qc2000b we can propose a roadmap for experimental and theoretical work toward implementing LOQC. It is based on viewing basic LOQC as a fundamental model of computation that can be used to implement standard quantum computation by using a set of layered techniques. For benchmarking purposes, the relevant resources of LOQC can be taken to be the number of particles independently generated, the probability of (detected) failure of the implemented computation (without postselection), and the measured error in the output conditional on success (i.e. with postselection). The roadmap for LOQC based quantum computation can be outlined as follows:

Basic LOQC.

Nondeterministic nonlinear sign changes.

Preparation of the state for teleportation (see knill:qc2000b for the definition of ).

Teleportation using for increasing with probability of success close to .

Controlled sign changes with good probability of success.


QC based on LOQC.

Boosting the success probability by the use of encoding.

Decrease phase errors by applying error correction.

Decrease loss errors by encoding with erasure codes.

Concatenation (or larger codes) for achieving high accuracy.

The experimental challenges include the ability to use multiple independently generated single photons and to control the photonic qubits using feedback from detectors. The first demonstrations are likely not to involve feedback, but rather to use postselection and high repetition rates to demonstrate success. Although feedback can be delayed in our schemes, this comes at the cost of high failure rates in the state preparation protocols, particularly for those states that depend on previously prepared states. The ultimate goal is to build the state preparation protocols into state factories with the ability to attempt failureprone state preparations at high rates (perhaps in parallel), exploiting the ease with which photons can be generated.
Here is the outline of this paper. We begin by recalling the needed properties of the LOQC protocols given in knill:qc2000b . We briefly describe the concatenation method for establishing thresholds, give a code suitable for increasing the success probability in ideal LOQC, and show how to implement encoded operations. The gain in success probability is estimated so as to determine a threshold. The resources that determine the general error propagation behavior are bounded for the goal of approaching the quantum communication threshold. As a result we conservatively estimate that a gate with the necessary reliability depends on at most a few hundred LOQC controlled sign flips implemented nondeterminstically with a pair of states each involving three photons. More are used up in unsuccessful state preparations, but at least in principle, this overhead is not much larger. The quantum coding methods are then enhanced for the purpose of dealing with phase and detectedloss errors, including particle detector inefficiencies, and finally for dealing with any residual general errors.
We assume familiarity with quantum computation aharonov:qc1998a ; divincenzo:qc2000a and quantum errorcorrection via stabilizer codes gottesman:qc1996a ; gottesman:qc1997a . For the basic ideas of LOQC see knill:qc2000b . Most of this paper is written in the language of qubits using products of Pauli operators.
Ii Features of LOQC
LOQC is a model of quantum computation where some of the gates are nondeterministic, with detectable failures. The probability of failure of the gates depends on the resources used. Specifically, the model is characterized by enabling the following operations on standard qubits (which are encoded in the physical system as photonic qubits):

Preparation of : .

Measurement in the basis : .

Every one qubit rotation.

Controlled sign flip: c, with a probability of failure, which is detected.
In practice errors other than detected failures occur. For the moment, we assume that such errors are significantly less likely than detected failures, so that initially, they can be ignored. Specifically, this leads to designing implementations by dealing with errors in order of their importance. We call LOQC with only the errors due to detected failure of the conditional sign flip “ideal LOQC” (iLOQC). In iLOQC, single photon state preparation, particle number detection and passive linear optical elements are all perfect. As explained in our previous paper knill:qc2000b , when applying , with probability , qubit is measured in the basis. If this event does not occur then with probability , qubit is measured in the basis. Thus the prior probability of the second event is . The measurement outcome is known in either case and the qubit not measured is preserved. We take that to be the error model of iLOQC. Note that the failure behavior is asymmetric, so that the ordering of the labels is significant. We call the first qubit in this operation the “source”, and the second the “target”. The resource overhead for implementing this gate depends on . If the methods of knill:qc2000b are used for implementing the c operation, a state with approximately photons needs to be adjoined. The preparation of the state needs to be tried several times, using ancillary photons. With the naive method, the total number of photons used in the preparation attempts grows exponentially in , so it is desirable to show that we can scale with as high a probability of failure as possible.
For the present purposes, it is convenient to use a gate set based on the product operator formalism sorensen:qc1983a . Thus, gates are exponentials of products of Pauli operators. To simplify the notation, define . For a product operator , write and note that since , . For example, is a bit flip up to a global phase. When there is no possibility for confusion, we abbreviate , where the parenthesized superscripts are system labels.
One reason for why product operators are convenient is because it is straightforward to follow their evolution under rotations by using appropriate triples of axes. For example, a rotation takes the axis to the axis, so that . This implies that if in a quantum network, a measurement or a rotation precedes a rotation, then this is equivalent to an measurement or rotation (by the same angle) after the . A complete set of gates that generates the determinant unitary matrices is given by

rotations: for any angle .

rotations: .

rotations: .
(With the use of ancillas, may be eliminated from the set without loss of completeness.) The third gate is related to c by
(1) 
As a result, the rotation is readily implemented in LOQC up to global phases. Furthermore, we can modify the implementation to achieve the following failure behavior for : With probability , qubit is measured in and qubit is untouched. With probability , qubit is measured in . If the outcome is , qubit experienced a and if it is , a . Note that due to the availability of rotations, we can also use rotations for and either or with similar error behavior, where the measurements commute with the rotation. Similarly, it is straightforward to implement the rotations, measurement and eigenstate preparation. We will find that the encoded rotation also has a probability of failure, where a measurement occurs if it fails. In this case, eigenstate preparation (using preparation and an followed by a ) may fail. However, since the preparation is successful if failure has not been detected, it is possible to retry it until success is achieved. This makes it possible to get a perfect eigenstate preparation.
Iii Establishing accuracy thresholds
For the very special error model introduced in the previous section, accuracy threshold analyses are much simpler. The basic principle is to use a quantum code that permits implementing the basic operations on the encoded information in such a way that the new error model is consistent with the original one, and so that the new error rate is substantially less. The encoded qubits then behave just like the more fundamental ones used to encode them, so that the same coding method can be used with these new types of qubits. This recursive coding method is known as concatenation and has the property that the errorrates decrease superexponentially with the number of levels of concatenation. The basic components of an accuracy threshold result by concatenation are the following:

A quantum code.

Means of implementing each of the basic operations on the encoded qubit.

Means of recovering from error, which may be part of 2.

Establishing the error model that applies to the encoded qubits and calculating a bound on the new error rate.
The plan is to show that a two qubit code suffices for establishing a threshold of for iLOQC. After dealing with the errors of iLOQC, it is necessary to consider the contributions of other sources of noise, particularly photon loss and phase error. It turns out that the same family of codes can be used with phase error correction. We recall that LOQC comes with an effective leakage detection scheme and observe that the basic teleportation protocol used in LOQC can be enhanced to allow detection of loss from particle detector inefficiency. As a result, it possible to use erasure code to eliminate errors from photon loss. We point out that due to the special nature of the erasure error model, good accuracy thresholds apply and error rates can be readily improved with relatively simple codes and few levels of encoding.
Iv A two qubit quantum code
Let and be the eigenstates of . Up to overall scale factors, the associated projection operators are . We continue to omit these scale factors in identities. To improve the failure probabilities, we use a two qubit quantum code with the encoding
(2)  
(3)  
and show how to implement the necessary operations on the encoded states. The encoded states define the state space of the “logical qubit”. In the language of stabilizer codes, the code is defined by the stabilizer , and accordingly, the projection onto the code space is given by . We use as the label for logical (encoded) operators and states. With this encoding, logical operators are given by
(4)  
(5)  
(6) 
where we introduced the notation to denote identity when restricted to the code.
For the purposes of establishing a threshold, we use the following set of basic operations and assumptions:

, and eigenstate (eigenvalue ) preparation: .

and measurements: and . means that the result of the measurement was eigenvalue .

, and rotations.

rotations.

rotation, with failure probability after the first encoding.

rotation, with failure probability in our error model.
Operations 1. to 4. are errorfree in iLOQC. The rotation is error free in iLOQC, but as we will see, it may fail with probability with a measurement after the first level of encoding. Note that , and rotations can be implemented by conjugation with errorfree rotations.
iv.1 State preparation
To encode an arbitrary state to , one can use the sequence of operations given by
(7) 
To see that this works, follow the effect of the unitary gates on the initial operators , (basic operators associated with the state to be encoded) and (the projection onto the prepared state). It can be seen that , and (the projection onto the code).
The sequence can be used to prepare encoded eigenstates of , or by preparing the eigenstate on qubit first. The process fails with probability , and can be repeated an expected times to successfully prepare it. Later, it will be the case that the rotation in the sequence can fail, which changes the failure probability to . The resource usage can be improved by reusing qubits not affected by the measurement in the failure.
iv.2 Measurement
To measure the logical qubit in the logical basis, measure both of the supporting qubits. A measurement on both yields a logical measurement via the total parity of the two outcomes. Similarly, a measurement on the first qubit and a measurement on the second gives a logical measurement. A logical measurement is accomplished by measuring on the first qubit. All of these measurements are without error.
iv.3 Logical qubit rotations
The logical rotations are implemented by applying basic ones to each qubit. Thus
(8)  
(9)  
(10) 
These are errorfree. The ability of implementing ’s in this way is generic for stabilizer codes gottesman:qc1997a . The rotations are obtained by applying and are errorfree. To implement , apply . This is not errorfree, and we show later how to use recovery from measurement to get a smaller probability of failure.
iv.4 rotation
If the logical qubits are encoded in qubits , and ,, respectively, the logical rotation can be obtained by applying . This can be done by the sequence
(11) 
where we use the convention that the order of application is right to left within a line and top to bottom for multiple lines. Unfortunately, this does not readily yield a logical gate with significantly less error. To do that requires using the teleportation techniques of gottesman:qc1997a ; gottesman:qc1999a .
V Robust teleportation
v.1 Basic teleportation
The basic teleportation protocol transfers an arbitrary state from qubit to qubit by first preparing a state on qubits and , then making a measurement on qubits and , and finally correcting qubit by applying one of the rotations. Here is a sequence for a variant of the usual protocol that has better error behavior for our purposes.
(12) 
The source in the second coupling evolution is chosen to be qubit . The necessary correction can be derived by determining the effect of the process on an input operator. Using the projection operators and for the prepared states and for the effects of the measurement the transformation for an initial operator is
(13)  
Using the rules
(14)  
(15) 
and their variations (continuing to omit constants in the identities), this evaluates to . Similarly,
(16)  
which evaluates to to . This implies that
(17) 
For a nice group theoretic treatment of teleportation, see braunstein:qc2000a .
The state obtained on qubits and before the last rotation and measurements is a prepared entanglement denoted by . The idea is to use the built in errordetection and multiple tries to obtain the state without error.
In order to analyze the propagation of errors, we need to understand the effect of an unintended or measurement before the protocol’s end. Both of these commute with the two rotations in the protocol. A measurement implies that the net effect of the applied rotations on the third qubit is a (the sign depends on the measurement outcome). Nothing happens to the first qubit. If a measurement happens, this directly applies to the first qubit. The second qubit experiences a rotation. To simplify matters we intentionally perform the measurement on this qubit to return to the first case as far as qubit is concerned.
v.2 Logical rotations by teleportation
One method for implementing the logical rotation on qubits encoded in qubits and respectively is to first teleport the four qubits, then apply the rotation . Since the final step of the teleportation protocol involves a number of rotations, and is in the normalizer of the Pauli group, we can instead apply to the destination qubits in the four copies of and apply appropriately modified rotations after the teleportation measurement. Actually, it is better to apply first, use the original corrections and note that the overall effect is equivalent to or after teleportation. Which one actually occurred can be determined from the measurement outcomes. To go from to it is sufficient to apply ’s to each qubit. Because of the ability to retry the state preparation until it succeeds, this reduces the problem of reliably implementing to the problem of reliable teleportation.
v.3 Error recovery by teleportation
Our methods are designed so that the only error from which it is necessary to recover is a measurement with known outcome on one of the qubits. It is desirable to implement the recovery so that at worst, a measurement occurs on the logical qubit. By symmetry, it is sufficient to consider a measurement on qubit . The effect of the measurement is to apply , where the sign is known. One way of restoring the encoded qubit is to notice that
(18) 
Since the first operator is a rotation around , it can be undone by applying its inverse.
A method more easily made reliable is based on the syndrome measurement technique of error correction. From this perspective, the unintended measurement creates a superposition of states with two syndromes, that is eigenvalues of . The encoded qubit can be recovered by measuring and if the eigenvalue is , applying . To measure we again use teleportation, reducing the measurement problem to a state preparation and teleportation problem (see steane:qc1999a for similar ideas used to solve the more difficult problem of correcting unknown errors). The idea is to measure on the destination qubits of two copies of before completing the protocol, and then infer the eigenvalue from the combination of all measurement outcomes. The correction operations of the protocol are unchanged. To see how this works, implement the protocol by teleporting qubit with and qubit with , so that the teleported state ends up in qubits and . The measurement on qubits and can be implemented by the sequence
(19) 
Note that the two operators on qubit occurring in the twoqubit rotations can be obtained by conjugating operators by a rotation. If the measurement of results in , we correct the state by applying . (To see that this correction works, examine the quantum network, moving the correction operator back to the beginning by appropriately changing orientations of rotations by anticommuting operators, and then absorbing it at the commuting state preparation steps.) Again, we can retry this state preparation until it succeeds. The prepared state is now given by
Vi Error analysis
We begin by considering errors that occur in the encoded operations and how one should respond to such errors.
vi.1 Errors in recovery
The recovery procedure is applied when an unintended measurement occurs. Suppose this occurs at qubit . Since the state of qubit is now known, we can take advantage of this to prepare a state with the first teleportation step (that is the one involving qubit ) already completed. This can be done errorfree, given a number of attempts. Specifically, the first teleportation protocol can be replaced by preparing the destination qubit in the appropriate eigenstate of , and then applying the measurement to this and the target of the second teleportation before completing the latter. As before, one can use either outcome of the measurement, in this case by applying only a correction, if necessary.
If the teleportation of the second qubit fails at the source of the relevant rotation, the second qubit is untouched, and we try again. If it fails at the target, then the second qubit is measured in , which implies that the logical qubit is measured in . Let be the probability of failure. By following the different possible outcomes in the attempts, we get
(20)  
(21) 
vi.2 Errors in the implementation of
When applying to the qubits, the following can happen: 1. The first qubit is measured in the basis. In this case, apply the recovery procedure and if it succeeds, attempt the operation again. If it fails, the logical qubit is measured in . 2. The second qubit is measured in the basis with outcome and the first qubit experiences a . The effect is the same as if a had been applied before the measurement, so if the subsequent recovery procedure succeeds, then the desired operation has been applied. Otherwise, the logical qubit has been measured in . The probability of failing once case 2 is entered is . The probability of entering case 1 is . By following the reattempts going through case 1, we obtain the equation for the probability of failure
(22)  
(23) 
vi.3 Errors in the implementation of
To avoid having to retry the operation we modify the protocol for implementing the logical rotation slightly. Instead of preparing copies of with the rotation already applied, prepare such copies. In the end, the destination qubits of the unused copies are measured in , so that the effective applied rotation becomes , where the sign depends on the measurement outcomes. Compensate for a minus sign by applying ’s to each qubit. Let the qubits be encoded in qubits and respectively. Perform the teleportation protocols for the qubits in this order. When a protocol fails at the source of the critical rotation, try again with the next available pair of qubits in the prepared state. When the protocol fails at the target, the procedure depends on whether it is the first or second member of a pair of encoding qubits. If it is the first, attempt recovery using the second qubit as usual. If it is the second, do the same, but using the already teleported qubit as the first member. In this case, we do not need to reattempt teleportation for implementing the rotation, as in the case of the logical rotation. Computing the probability of failure that the procedure fails by the first logical qubit being measured gives
(24)  
(25) 
The probabilities for the second logical qubit being measured given successful completion of the first two steps is the same, as required by the assumptions of the model.
vi.4 The threshold
The threshold for obtaining an improvement in the failure parameter can be determined by solving , which gives
(26) 
Vii Resource analysis
Resource analysis can be used to estimate the effect of residual errors (not fitting the error model) in the basic operations and to determine the total overhead of implementing an accurate quantum gate for standard quantum computation or communication. The total overhead includes the expected number of attempts required to prepare the requisite states. In an actual system, the state preparation attempts can be arbitrarily parallelized and implemented in independent highthroughput state factories. In the system as proposed here, the states are relatively simple in terms of the lower level implementation, and success probabilities are reasonable. An explicit total resource analysis is left as a problem for future work. For now, our primary concern is how general errors can propagate from the physical implementation to the encoded qubits. This depends only on the operations that directly contribute toward the state used in the final gate via their errors conditional on success. This property can be exploited to largely eliminate the problem of inefficient detectors, see Sect. VIII.2.
The analysis that follows is intended as an example for how this can be done and is completed with an explicit example. We begin by counting resources in terms of the operations of iLOQC, counting separately first the errorfree one qubit rotations, state preparations and measurements in the or basis (), second the and rotations (), and third the two qubit rotations with or operators (). This separation helps with the resource estimate due to the fact that they differ in resource requirements at the first and later levels. For our purposes two or three levels are expected to suffice. Note that we are not counting steps that are required to temporarily store a qubit. This is necessary in principle, as imperfect memories without parallelism imply that truly scalable quantum or classical computing is impossible aharonov:qc1996b . In particular, it is beneficial to parallelize implementations as much as possible.
As we proceed, we will comment on the expected number of tries for state preparations. For this purpose, define as the probability of failure of the one qubit rotations contributing to and let be the total failure probability of the two qubit rotations contributing to . In a total resource analysis, one can exploit the fact that at the first level.
vii.1 Resources for teleportation
The preparation of requires
(27)  
(28)  
(29) 
Since the probability of success is , the expected number of attempts to assure success is .
To prepare copies of with the rotation applied to the targets using the method given in Sect. IV.4 requires
(30)  
(31)  
(32) 
The probability of successful preparation is only , so the preparation method needs to be improved. An efficient (in ) scheme is based on the idea of using a parity containing ancilla to kick back the desired rotation, and to generate this ancilla in a tree like fashion cmoore:qc1998a . The sequence is defined recursively by: consists of preparing and , then applying c from the target of to . The qubit is the “parity” qubit. applies to the outputs of and , then measures parity qubit in the basis by applying and then measuring . If the outcome is , apply a to each of the target qubits of the that make up . The new parity qubit is . The controllednot operation is applied with
(33) 
To kick back the desired rotation to copies of after has been successfully completed, apply to the parity qubit and measure it in the basis, applying a correction as before, if necessary. The last step can be deferred until after the teleportation when using this for implementing the logical operation. The failure response of the algorithm can be optimized by recovering states as much as possible. For simplicity, we assume that the state associated with a failed is discarded.
The resources required for implementing can be determined recursively.
(34)  
(35)  
(36)  
(37)  
(38)  
(39) 
which one can solve to obtain
(40)  
(41)  
(42) 
The probability of success of using two independent outputs of is , which can be shown to imply polynomial total resource use. We now obtain new expressions for the preparation resources (assuming that the last correcting series of ’s is deferred):
(43)  
(44)  
(45) 
The success probability given the output of is .
To prepare the state needed for recovery after one of the qubits has been measured, follow the part of the protocol that does not involve the remaining qubit. There are two measurements that need to be made, and we note that the state can be used for completing the protocol regardless of the outcome. As explained in Sect. VI.1, the preparation can be decomposed into making a copy of and of an eigenstate of and then measuring , correcting the outcome with a if ncessary. Using the implementation of the measurement above and counting the two rotations needed to obtain the operators from ’s in the couplings, we get
(46)  
(47)  
(48) 
The success probability is .
vii.2 Resources for operations
To follow the resource usage through several levels of concatenation, it is necessary to determine the maximum resource usage for each category of operations. First are the one qubit rotations, state preparations and measurements in the or basis. Of these, state preparation has the highest resource requirements for and . is highest for the rotations. This gives the following estimates:
(49)  
(50)  
(51) 
The next category consists of the or rotations. For the rotation, we conjugate a rotation by logical ’s. The resource analysis is complicated by the need for using recovery operations on partial failures. The expected number of rotations that need to be retried after failure and successful recovery of the first qubit is , as is the probability of failing and then successfully recovering. To get a better bound on the number of directly contributing operations, note that the couplings are implemented in such a way that if the source fails, the target is not touched. Thus teleportation steps that fail at the source of the coupling that precedes the measurements need not be counted except when estimating total resources. Thus, the expected number of contributing recovery operations can be bounded by for failures at the first qubit and for failures at the second qubit. Thus
(52)  
(53)  
(54)  
The final category has the couplings. Except for at most rotations needed to get operators, it suffices to determine the requirements for the logical operation. Let be the number of copies of used in the prepared state. The calculation is similar to that for . Noting that the probability of a teleportation failing at the target and the subsequent recovery succeeding is , one can bound the expected number of recovery attempts by . Some of the teleportations are attempted multiple times (just like the rotation is attempted multiple times in the previous case) and we need to account for the correction steps of the teleportation.
(55)  
(56)  
vii.3 An explicit example
Suppose the goal is to have a failure probability per qubit, which is not far from the current best estimates for the communication threshold briegel:qc1998a . If we use pairs of threephoton entanglements to generate the controlled sign flip at the first level in LOQC, the initial failure probability per qubit is . Using the expression for in Eq. 23 gives after one level and after two. For simplicity, we choose in both levels (hopefully a safe choice, though in principle this effects the probabilities a bit). Other useful values at the first and second levels are , and . We evaluate the values for the coupling evolution at the second level. Using parenthesized superscripts to denote the levels gives, for example,
(58)  
Similarly,
(59)  
(60) 
Much of the inefficiency comes from the lack of optimization for implementing the logical rotation.
The expected total resource usage including those needed for the failed state preparation attempts can be determined from the probabilities of successful preparation and requires recalculating the expressions for the various resources. For example, at the first level, and and at the second, and . Thus the expected number of attempts required to make the state needed for error recovery is approximately at the first level and at the second.
The resource values imply that a controlled sign flip at the top level depends on less than controlled sign flips implemented with pairs of three photon entanglements in iLOQC. This can be used to bound the effect of errors that cannot otherwise be controlled. The resource bounds improve if four or five photon states can be reliably generated, thus giving better initial values of and substantial gains in efficiency at the higher levels.
Viii Compensating for other errors
So far we have shown how to use a simple code with careful implementation of the basic operation to rapidly boost the probability of successful completion of gates. The next step is to consider the contribution of other errors and how to correct for them. Two important types of errors are phase errors and loss of particles.
viii.1 Phase errors
The occurrence of a phase error can be detected for the code used above by following the teleported measurement procedure in the absence of a failure. A eigenvalue indicates an error. At this point, it is necessary to return the state to the code space by applying an appropriate rotation. Although it is not possible to correct for the error (we don’t know which qubit is faulty), its detection can be used as information for correction in a higher level erasure code. An alternative is to use the generalization of the code to three qubits, which does have the capability of correcting for phase errors. In fact, the fold concatenation of the two qubit code with itself is actually a qubit code that corrects for up to phase errors. That property can be exploited by introducing an appropriate error detection/correction procedure periodically after the first few levels, without changing the overall concatenation scheme or the basic methods for implementing operations.
viii.2 Loss of particles and detector inefficiency
The methods of LOQC include one that can, with some probability of failure, detect loss of a photon used to define a photonic qubit. The failure mode is again one involving a measurement, so the scheme can be used with the two qubit code. This will have an effect on the overall error behavior. We leave the calculations as an open problem.
One observation not made in knill:qc2000b is that if after any of the teleportation steps used for basic LOQC, we measure the modes not containing the teleported qubits, and the total number of photons detected is not equal to the number initially prepared in the entanglement, then a photon was lost, possibly due to detector inefficiency. Such an event can be declared as a qubit loss. Doing so turns the problem of detector inefficiency into one of having to handle detected qubit loss at some rate. It is a useful task to determine the relationship between detector inefficiency and the probability of detected loss.
If total loss is detected, the two qubit code is insufficient for restoring the encoded information. Instead, it is necessary (perhaps after a few levels of two qubit encodings) to use erasure codes. These are codes with the property that one (or a few) lost qubits can be restored without loss of information. The accuracy threshold for the error model where each operation satisfies that the target qubits are lost with independent probability appears to be very good also, perhaps below . A brief explanation based on conservative calculations giving a value close to is below. The erasure model is one of few for which it is possible to establish exact quantum communication quantities, such as the quantum channel capacity bennett:qc1997b . We therefore suggest that calculating the threshold for the erasure errormodel is an excellent open problem to solve.
viii.3 An erasure code
A useful erasure code encoding one qubit into four is defined by the stabilizer group generated by
(61) 
One can define encoded operators by
(62)  
(63) 
We chose the erasure code and the logical operators for their small support (number of nonidentity Pauli operators in the products). If it is desirable to encode two qubits into four, the erasure code with stabilizer generated by and can be used.
It turns out that it is easier to analyze thresholds for erasure errors than for measurements. Implementations of operations can be based on teleportation the same way we did before, again relying on the ability to guarantee prepared states by retrying after failure. For the present discussion, we implement the teleportations required for an operation all in one step, and then follow up with error recovery if necessary. Of the operations required for quantum computing, state preparation can be implemented errorfree at all levels by retrying the process until success. To measure , first measure , and if this fails, restore the logical qubit. After successfully measuring , measure , and if that fails, and . The value of the measurement can be inferred by using the parity constraint associated with the third generator of . The other logical Pauli operators can be measured similarly. The probability that the measurement fails is bounded by , where is the probability that the error recovery procedure fails.
Suppose that qubit is lost. The error recovery procedure requires measuring the first and third operators of , which, by reintroducing a fixed state for qubit , can be done with two full teleportation steps each. We ignore the fact that some failures in these steps can be recovered and estimate that each teleportation step fails with probability at most (due to the coupling rotation and two measurements, not including the correction for now). The recovery step concludes with a correcting operation on qubit , so that we can estimate (ignoring the possibility of retrying the recovery step if one of the last corrections fail). The probability of a failed measurement is therefore bounded by .
Since we are unable to implement arbitrary rotations directly, it is necessary to implement (say) a rotation by teleportation. (The compensation step is now a coupling rotation, which can be implemented either by teleportation or directly, exploiting the independence assumption on loss of qubits.) Since the most complex operation involves coupling two logical qubits with a rotation, we finish by giving a rough estimate of this failure probability. The Hamiltonians to be evolved have weight four (two on each pair of encoding qubits), so it suffices to teleport four qubits after a suitable state preparation. If one of the teleportations fail, the recovery procedure is followed. We may need to compensate for a negative rotation induced by the teleportations’ last correction step, but that can be absorbed into the procedure. Thus the error probability for the first logical qubit is bounded by , whence an accuracy threshold better than about .
viii.4 General errors
The techniques discussed so far compensate for all of the primary errors that are expected to occur in an LOQC system. Additional errors can be attributed to improper settings of beam splitters, undetected loss, stray photons, etc. The first of these depends on accurate calibration of classical control parameters. Happily, this type of error affects the probabilities quadratically, so that it can be minimized well by engineering. To deal with other errors eventually requires more powerful quantum error correction, and the goal of any implementation is to minimize the need for these techniques.
Ix Conclusion
This work is a first attempt at reducing the overhead and need for efficient devices for implementing LOQC. It shows that even without much optimization of the operations or tight estimates of errors and resources, there are techniques that can be used to obtain useful quantum operations in LOQC with overheads within two orders of magnitude of those required for other reliable implementations of quantum computers. The advantages of LOQC include the ability to compensate readily for the primary errors in optics while preparing large numbers of the basic quantum systems, which are photons in a superposition of two modes. It is necessary to further optimize the methods and to better analyze the error behavior, particularly the effects of detector inefficiencies, single photon state preparation errors and timing or overlap problems for photons. A fruitful area of further investigation is to determine whether larger codes and the method of encoding multiple qubits at once can be used to improve efficiency and error behavior.
Our proposal consists of a multilevel system with various types of errorcontrol gradually introduced and supported by highoutput state preparation factories that exploit the ease with which many photons can be produced. Although in the very long term, solid state or molecular computing methods are the preferred implementation for large scale quantum computing, LOQC is now a viable alternative to achieving the capability of nontrivial quantum information processing. One area where LOQC has a long term future is in communication. Photon based systems are currently the only reasonable proposals for long distance quantum communication. Since the necessary accuracies for successfully exchanging entanglement over arbitrary distances are well below , this may also be the first application of LOQC to quantum information processing to be experimentally implemented.
Acknowledgments: We thank the Aspen Center for Physics for its hospitality. E.K. and R.L. received support from the NSA and from the DOE (contract W7405ENG36).
References
 (1) E. Knill, R. Laflamme, and G. Milburn, Efficient Linear Optics Quantum Computation (2000), quantph/0006088.
 (2) D. Aharonov and M. BenOr, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computation (STOC) (ACM Press, New York, New York, 1996), pp. 176–188.
 (3) A. Y. Kitaev, Uspekhi Mat. Nauk. 52, 53 (1997).
 (4) E. Knill, R. Laflamme, and W. H. Zurek, Science 279, 342 (1998).
 (5) J. Preskill, Proc. R. Soc. Lond. A 454, 385 (1998).
 (6) M. Grassl, T. Beth, and T. Pellizari, Phys. Rev. A 56, 33 (1997).
 (7) Y. Aharonov and J. Anandan, Meaning of the Density Matrix (1998), quantph/9803018.
 (8) D. DiVincenzo, The Physical Implementation of Quantum Computation (2000), to appear in Fort. Phys., special issue on “Experimental Proposals for Quantum Computation”. quantph/0002077.
 (9) D. Gottesman, Phys. Rev. A 54, 1862 (1996).
 (10) D. Gottesman, Phys. Rev. A 57, 127 (1998).
 (11) O. W. Sörensen, G. W. Eich, M. H. Levitt, G. Bodenhausen, and R. R. Ernst, Prog. Nucl. Mag. Res. Spect. 16, 163 (1983).
 (12) D. Gottesman and I. L. Chuang, Nature 402, 390 (1999).
 (13) S. L. Braunstein, G. M. D’Ariano, G. J. Milburn, and M. F. Sacchi, Phys. Rev. Lett. 84, 3486 (2000).
 (14) A. Steane, Nature 399, 124 (1999).
 (15) D. Aharonov and M. BenOr, in Proceedings. 37th Annual Symposium on the Foundations of Computer Science, edited by ? (IEEE Comput. Soc. Press, Los Alamitos, CA, 1996), pp. 46–55.
 (16) C. Moore and M. Nilsson, Parallel Quantum Computation and Quantum Codes (1998), quantph/9808027.
 (17) H.J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, Quantum Repeaters for Communication (1998), quantph/9803056.
 (18) C. H. Bennett, D. P. DiVincenzo, and J. A. Smolin, Phys. Rev. Lett. 78, 3217 (1997).