Fault-Tolerant Quantum Computation with Constant Error Rate

The paper introduces a new class of CSS codes over F_p called polynomial codes.

“We use Calderbank-Shor Steane (CSS) quantum error correcting codes, generalized to qupits, and introduce a new class of CSS codes over F p , called polynomial codes.”

The threshold is calculated to be η_c ≃ 10^-6, in the best case.

“Finally, we calculate the threshold to be η c ≃ 10 -6 , in the best case.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 7 · plain

  “The threshold which is achieved in this case is ≃ 10 -6 .”

If an error correction procedure R corrects and detects any basic error of length d in a quantum code C, then R corrects any general error on any d qubits in C.

“A crucial and basic fact[8] in quantum error corrections is that it suffices to correct two basic errors, called bit flips and phase flips, in a small number of qubits, in order to correct a general error on these qubits.”

• Also stated in: § 2.6. Quantum Circuits with Mixed States. We now define a quantum circuit: · p. 15 · plain

  “Theorem 1. Let C be a quantum code, and let R correct and detect any basic error of length d in C . Then R corrects any general error on any d qubits in C .”

• cites [8] D. Aharonov and D. Gottesman, Accuracy Thresholds: Can We Beat $10^{-4}$? Presentation at ITP Conference of Quantum Information, 2001, available online at http://online.itp.ucsb.edu/online/qinfo_c01/aharonov/.Not checked yet

  Not checked in the free run.

In one case with no geometry imposed, error-free classical operations and measurements allowed, and polynomial codes used, the threshold is ≃10^-6.

“We give here an estimation of the threshold in one case, in which no geometry is imposed on the system, error free classical operations and measurements can be performed during the computation, and the codes which are used are polynomial codes. The threshold which is achieved in this case is ≃ 10 -6 .”

If for any input basis state the ancilla qubits at the end of a procedure are in tensor product with the rest of the qubits and their state does not depend on the input basis state, then for any input superposition the ancilla qubits will be in tensor product with the rest and can be discarded by erasing them.

“It is easy to see that if for any input basis state, the state of the ancilla qubits at the end of the procedure are in a tensor product with the rest of the qubits, and their state does not depend on the input basis state, i.e.”

The length m must be odd.

“Observe also that the length m must be odd due to the above considerations.”

A polynomial code of degree d with length m over Fp corrects min{⌊(m-d-1)/2⌋, ⌊d/2⌋} errors.

“Theorem 3. A polynomial code of degree d with length m over F p is a [ p, m ] quantum code which corrects min {⌊ m -d -1 2 ⌋ , ⌊ d 2 ⌋} errors.”

• cites [9] sourceNot checked yet

  Not checked in the free run.

There are only two cosets of C⊥ in C.

“We now claim that there are only two cosets of C ⊥ in C .”

A polynomial code of degree d with length m over Fp is a [p,m] quantum code.

“Theorem 3. A polynomial code of degree d with length m over F p is a [ p, m ] quantum code which corrects min {⌊ m -d -1 2 ⌋ , ⌊ d 2 ⌋} errors.”

• cites [9] sourceNot checked yet

  Not checked in the free run.

Computing the syndrome independently m times, and from the i'th copy computing e_i and applying a CNOT to the i'th bit, ensures that the error correction procedure is fault tolerant.

“The fact that for each bit we compute the syndrome independently ensures us that the procedure is fault tolerant.”

To construct the encoding procedure fault tolerantly, it is enough to generate a state |S0> fault tolerantly.

“To construct this procedure fault tolerantly, it is enough to generate a state | S 0 〉 fault tolerantly.”

If the length of C is m, then dim(C) - dim(C⊥) = 1.

“Hence, dim ( C ⊥ ) = m -( m +1) / 2 = ( m -1) / 2 and so dim ( C ) -dim ( C ⊥ ) = 1.”

We can verify that the cat state is of the form c0|0> + c1|1>, fault tolerantly.

“Thus, we can verify that the cat state is of the form c 0 | 0 〉 + c 1 | 1 〉 , fault tolerantly.”

There exist such fault tolerant procedures also for encoding, decoding and error correction for these CSS codes.

“There exist such procedures also for encoding, decoding and error correction.”

There exist fault tolerant procedures which simulate the operations of all gates from G1 on states encoded by punctured self dual doubly even CSS codes such that one error in a qubit or a gate affects at most four qubits in each block at the end of the procedure.

“Theorem 4. There exists fault tolerant procedures which simulate the operations of all the gates from G 1 , on states encoded by punctured self dual doubly even CSS codes such that one error in a qubit or a gate effects at most four qubits in each block at the end of the procedure.”

For the encoded controlled phase gate, (a+w)·(b+w') = a·b mod 2.

“Now, ( ⃗ a + w ) · ( ⃗ b + w ′ ) = ⃗ a · ⃗ b mod 2.”

In the decoding procedure, one fault in the second stage during the computation of one of the a's can affect only the correctness of that a.

“One fault in the second stage of the procedure, during the computation of one of the a 's, can effect only the correctness of that a .”

In a bitwise procedure of a gate on k qubits, an error can affect only one qubit.

“Obviously, an error in this procedure can effect only one qubit.”

One error in the construction of |A> affects only one qubit in |A>.

“It is left to see that one error in this procedure effects only one qubit in | A 〉 .”

The construction of the state 1/√2(|A>+|B>) is fault tolerant because only the fault tolerant encoding procedure and the fault tolerant encoded Hadamard gate were used.

“The construction of the state 1 √ 2 ( | A 〉 + | B 〉 ) is fault tolerant because we only used the fault tolerant encoding procedure and the fault tolerant encoded Hadamard gate.”

The construction of an encoded cat state is fault tolerant since it is composed of the fault tolerant encoding procedure and bitwise CNOTs.

“The construction of an encodes cat state id fault tolerant since it is composed of the fault tolerant encoding procedure, and bitwise CNOT's.”

The noiseless syndrome computation is not a fault tolerant procedure, since an error in one of the CNOT gates causes an error in the extra qubit, which propagates through the other CNOT gates to other qubits in the block.

“However, this is not a fault tolerant procedure, since an error in one of the CNOT gates causes an error in the extra qubit, which propagates through the other CNOT gates to other qubits in the block.”

C includes the all one vector: 1 ∈ C.

“Observe that C includes the all one vector: ⃗ 1 ∈ C .”

The all one vector is not in C⊥.

“This implies that ⃗ 1 ̸∈ C ⊥ .”

Any eta < eta_c satisfies the threshold condition.

“It is easy to see that any η &lt; η c satisfies the threshold condition.”

If eta < eta_c, there exists delta > 0 such that the probability P(r) for the faults in an r-rectangle to be (r,k)-sparse is larger than 1 - eta(1+delta)^r.

“Lemma 10. If η &lt; η c , ∃ δ &gt; 0 such that the probability P ( r ) , for the faults in an r -rectangle to be ( r, k ) sparse is larger than 1 -η (1+ δ ) r .”

Using T_m(Q,i1,...,ip), a general p^m × p^m unitary matrix U can be constructed.

“The last step is to use T m ( Q,i 1 , ..., i p ) to construct a general p m × p m unitary matrix U .”

Replacing NOT, CNOT and Hadamard by their generalized versions (generalized NOT, generalized CNOT, Fourier transform over F_p) achieves the desired error correction transformation.

“As a general rule, the gates NOT , CNOT and Hadamard are replaced by their generalized version, i.e. generalized NOT, generalized CNOT and Fourier Transform over F p , and this achieves the desired transformation.”

Lemma 3: Let A,B be two non orthogonal subspaces of C^n. Let G_A, G_B be dense subsets of U(A), U(B) respectively. Then the subgroup generated by G_A ∪ G_B is dense in U(A⊕B).

“Lemma 3. Let A,B be two non orthogonal subspaces of C n . Let G A , G B be dense subsets of U ( A ) , U ( B ) respectively. Then the subgroup generated by G A ∪ G B is dense in U ( A ⊕ B ) .”

Applying on the l'th qupit the gate |a> -> w^{c_l a}|a>, where c_l are interpolation coefficients, achieves a rotation by w^{ca}.

“To achieve a rotation by w ca , we apply on the l ′ th qupit the gate | a 〉 ↦- → w c l a | a 〉 . This achieves the desired operation because:”

If the fourth block was not there, the operation on the first three blocks is exactly Toffoli.

“Note that if the fourth block was not there, we are done, because the operation on the first three blocks is exactly Toffoli.”

Lemma 1: Let n≥3, |α>∈C^n, H be the subgroup in U(n) which fixes |α>, and V∈U(n) not in H. Then the subgroup generated by H and V is dense in U(n).

“Lemma 1. Let n ≥ 3 Let | α 〉 ∈ C n . Let H be the subgroup in U ( n ) , which fixes | α 〉 , Let V ∈ U ( n ) be a matrix not in H . Then, the subgroup generated by H and V is dense in U ( n ) .”

Lemma 2: Let U1, U2 be two non-commuting matrices in SU(2), such that their eigenvalues are not integer roots of unity. The subgroup generated by U1, U2 is dense in SU(2).

“Lemma 2. Let U 1 , U 2 be two non-commuting matrices in SU (2) , such that their eigenvalues are not integer roots of unity. The subgroup generated by U 1 , U 2 is dense in SU (2) .”

The fault-tolerant degree reduction procedure achieves the transformation of |S'_a> to |S'_a>|S_a> fault tolerantly.

“This achieves the transformation of | S ′ a 〉 to | S ′ a 〉| S a 〉 fault tolerantly, and completes the description of the degree reduction.”

Applying degree reduction on the third register using the fourth register as target gives |S_a>|S_b>|S'_ab>|S_ab+c>.

“We now apply degree reduction on the third register, using the fourth register as the target of the interpolation as is explained in the next section. This gives | S a 〉| S b 〉| S ′ ab 〉| S ab + c 〉 .”

Theorem 8: G1 together with all phase factors generate a dense subgroup in the group of special unitary matrices operating on five qubits, U(2^5).

“Theorem 8. G 1 together with all phase factors generate a dense subgroup in the group of special unitary matrices operating on five qubits, U (2 5 ) .”

Applying a generalized NOT gate on each qupit in a block gives a generalized NOT on the entire block.

“Applying a generalized NOT gate on each one of the qupits in a block gives an generalized NOT on the entire block, as can be easily checked.”

Together with all phase factors, H1,Y1,Y2,CP give the unitary group on two qubits.

“Together with all phase factors, we get the unitary group on two qubits.”

Applying a generalized CNOT from the i'th qupit in the first block to the i'th qupit of the second block, for all 1 ≤ i ≤ m_s, gives an encoded generalized CNOT from the first block to the second block.

“Applying a generalized CNOT from the i ′ th qupit in the first block to the i ′ th of the second block, for all 1 ≤ i ≤ m s, gives an encoded generalized CNOT from the first block to the second block.”

Using the recursive scheme, a circuit using two-qupit gates can apply T_m(Q) for any m>2 and any one-qupit Q.

“Using the above scheme recursively we can construct a circuit which uses two-qupit gates and applies T m ( Q ) for any m&gt; 2 and any one-qupit Q .”

All gates from G2 can be applied fault tolerantly on states encoded by polynomial codes using the same basic underlying idea: when applying gates bitwise, we always get the desired result, except that sometimes the final state is the correct logical pit encoded with polynomials of degree 2d instead of d; to get back into the code using polynomials of degree d, one applies degree reduction.

“We show how to apply all gates from G 2 fault tolerantly on states encoded by polynomial codes. It turns out that all these procedures can be applied using the same basic underlying idea. This idea is that when applying the gates bitwise, we always get the desired result, except for one problem: Instead of getting the final state as a superposition of polynomials with degree d , we sometimes end”

If no error occurred, the ancillary state does not change when adding h_{i,l} a_l to the l'th coordinate, because the added vector's coordinates sum to 0 mod p.

“If no error occurred, the inner product is supposed to be zero, so the ancillary state does not change, since we have added to the ancilla a vector of which the coordinates sum up to 0 mod p .”

X_i and Y_i generate a dense subgroup in the group of 2x2 unitary matrices U(2) operating on S_i.

“We claim that they generate a dense subgroup in the group of 2 × 2 unitary matrices U (2) operating on S i .”

For strings b with deg(b) ≤ m-d-1, the sum over b in equation 5.8 gives the code word |S'_b> of the polynomial code when degree is at most m-d-1 instead of d.

“Hence, the sum over all b with deg ( b ) ≤ m -d -1 in equation 5.8 gives:”

• Also stated in: § 4.9. A Fault Tolerant Decoding Procedure for CSS codes. A decoding procedure applies · p. 34 · plain

  “Where | S ′ b 〉 is the code word of the polynomial code when the degree of the polynomials is at most m -d -1, instead of d .”

H1,Y1,Y2,CP generate a dense subgroup of SU(L⊕|η>⊕|00>) = SU(4).

“Hence, H 1 , Y 1 , Y 2 , CP , (which are all gates generated by H and CP ), generate a dense subgroup of SU ( L ⊕| η 〉⊕| 00 〉 ) = SU (4).”

For p > 3, the eigenvalues of X_i and Y_i confined to S_i are not integer roots of unity.

“Lemma 7. For p &gt; 3 , the eigenvalues of X i and Y i confined to S i are not integer roots of unity.”

In the encoded error correction, one can omit the degree reduction everywhere.

“It turns out that this does not pose any difficulty since in this case we can omit the degree reduction everywhere.”

The general T_m(Q,i1,...,ip) for any Q can be achieved by first permuting the basis vectors i1,...,ip to the last p vectors, applying T_m(Q), and then permuting back.

“The general T m ( Q,i 1 , ..., i p ) for any Q can clearly be achieved by first permuting the basis vectors i 1 , ..., i p to the last p vectors, applying T m ( Q ), and then permuting back.”

A C'-encoded phase flip transforms by H (the tensor product of generalized Fourier transforms applied pit-wise) to a C''-encoded pit flip.

“The crucial fact is that a C ′ -encoded phase flip transforms by H to a C ′′ -encoded pit flip:”

The sum over the rest of the b's (deg(b) > m-d-1) must vanish.

“Now, we claim that the sum over the rest of the b ′ s must vanish.”

• Also stated in: § 4.9. A Fault Tolerant Decoding Procedure for CSS codes. A decoding procedure applies · p. 34 · plain

  “Thus, the norm of the sum over b ′ s with deg ( b ) &gt; m -d -1 must vanish.”

Applying the general Toffoli gate pit-wise on the m coordinates from |S_a>|S_b> to the extra state |S'_0> gives |S_a>|S_b>|S'_ab>|S_c>.

“Applying the general Toffoli gate pit-wise on the m coordinates, from the first two states | S a 〉| S b 〉 to the extra state gives | S a 〉| S b 〉| S ′ ab 〉| S c 〉 , as is easy to check.”

Let C be a computation code that corrects d errors, with spread l. Let M_r be the r-simulation of M_0 by C. Consider a computation subjected to an (r,k)-sparse fault path with kl <= d. At the end of each r-working period the error is (r,d)-sparse.

“Lemma 8. Let C be a computation code that corrects d errors, with spread l . Let M r be the r -simulation of M 0 by C . Consider a computation subjected to an ( r, k ) -sparse fault path with kl ≤ d . At the end of each r -working period the error is ( r, d ) -sparse.”

Theorem 7: Let G be a universal set of gates on k≥2 qupits, p≥2. Consider the Hilbert space of m>k qupits. Then the gates in G, extended to m qupits, generate a dense subset of U(p^m).

“Theorem 7. Let G be a universal set of gates on k ≥ 2 qupits, for p ≥ 2 . Consider the Hilbert space of m&gt;k qupits. Then the gates in the set G , extended to m qupits, generate a dense subset of U ( p m ) .”

Applying the SWAP gate pit-wise achieves an encoded SWAP.

“In the same way, applying the SWAP gate and the multiplication gate pit-wise, achieves an encoded SWAP and an encoded multiplication gate respectively.”

The set of gates consisting of all one-qupit gates U(C_p) and all classical two-qupit gates generates all unitary matrices on two qupits, U(C_p^2).

“Lemma 4. The set of gates consisting of all one-qupit gates U ( C p ) and all classical two-qupit gates generates all unitary matrices on two qupits, U ( C p 2 ) .”

T_m(Q) with Q any permutation on the basis vectors of one qupit, together with generalized NOT gates, generate all permutation matrices on m qupits.

“We first note that T m ( Q ) with Q being any permutation on the basis vectors of the Hilbert space of one qupit, together with generalized NOT gates, generate all permutation matrices on m qupits.”

G2 together with all phase factors generate a dense subgroup in U(p^3), for p > 3.

“Theorem 9. G 2 together with all phase factors generate a dense subgroup in U ( p 3 ) , for p &gt; 3 .”

There exist fault tolerant procedures which simulate the operations of all gates from G2 on states encoded by polynomial codes, such that one error in a qubit or a gate affects only one qubit in each block at the end of the procedure.

“Theorem 5. There exists fault tolerant procedures which simulate the operations of all the gates from G 2 , on states encoded by polynomial codes, such that one error in a qubit or a gate effects only one qubit in each block at the end of the procedure.”

Let 2d+1 <= m. If the final density matrix of M_r is (r,d)-deviated from the correct one, then the distribution on the strings obtained by taking recursive majority on each r-block of its output is correct.

“Lemma 9. Let 2 d + 1 ≤ m . If the final density matrix of M r is ( r, d ) -deviated from the correct one, then the distribution on the strings which are obtained when taking recursive majority on each r -block of its output is correct.”

X_i and Y_i operate as the identity on S_i^perp.

“Lemma 6. X i and Y i operate as the identity on S ⊥ i .”

The encoded error correction procedure corrects general encoded errors if their number is smaller than that which the code C can correct.

“Hence, the sequence of equalities 3.18 holds also in our case, which shows that the above procedure corrects general encoded errors, if their number is smaller than that which the code C can correct.”

CP can be constructed from the set of gates G1.

“Let us first show how to construct CP from our set of gates:”

• Also stated in: § 4.9. A Fault Tolerant Decoding Procedure for CSS codes. A decoding procedure applies · p. 42 · plain

  “Now, to construct CP we apply P 3 3 T 3 P 3 T 3 which gives | 110 〉 ↦- → i | 110 〉 , | 111 〉 ↦- → -i | 111 〉 and identity on the rest, and applying X 2 we get CP tensor with identity on the third qubit.”

Applying the multiplication gate pit-wise achieves an encoded multiplication gate.

“In the same way, applying the SWAP gate and the multiplication gate pit-wise, achieves an encoded SWAP and an encoded multiplication gate respectively.”

Q_i and Q_i^{-1} are in the subgroup generated by G2 on three qupits.

“Lemma 5. Q i and Q -1 i are in the subgroup generated by G 2 on three qupits.”

The deviation satisfies the triangle inequality because the union of two sets which are (r,l1)-sparse and (r,l2)-sparse respectively is (r,l1+l2)-sparse.

“The deviation satisfies the triangle inequality since the union of two sets which are ( r, l 1 ) , ( r, l 2 )-sparse respectively is ( r, l 1 + l 2 ) sparse, by induction on r .”

Let epsilon > 0. Let C be a computation code with gates G. There exists a threshold eta_c > 0, and constants c1,c2,c3 such that: for any quantum circuit Q with n input qubits, t time steps, s gates from G, and v locations, there exists a quantum circuit Q' operating on n log^{c1}(v/epsilon) qubits, for time t log^{c2}(v/epsilon), and using s log^{c3}(v/epsilon) gates from G, such that in the pres-

“Theorem 10. The Threshold Theorem for Probabilistic Noise: Let ǫ &gt; 0 . Let C be a computation code with gates G . There exists a threshold η c &gt; 0 , and constants c 1 , c 2 , c 3 such that the following holds. Let Q be a quantum circuit, with n input qubits (qupits), which operates t time steps, uses s gates from G , and has v locations. There exists a quantum circuit Q ′ which operates on n”

In our constructions, the threshold is estimated to be approximately 10^-6 in both CSS codes and polynomial codes, using codes of length m=7, which can correct one error.

“In our constructions we estimate the threshold to be ≈ 10 -6 in both cases of CSS codes and polynomial codes, using codes of length m = 7, which can correct one error.”

• AssumptionThe authors state this as an assumption: Measurements can be applied during the computation, and classical operations in the procedures are error free.

Applying a generalized Fourier transform on each coordinate after generating the cat state achieves an equal superposition of all strings j satisfying ∑_k j_k = 0 mod p.

“We now apply a generalized Fourier transform on each of the coordinates, to achieve the state”

• Also stated in: § 4.9. A Fault Tolerant Decoding Procedure for CSS codes. A decoding procedure applies · p. 33 · plain

  “which is simply an equal superposition of all strings j which satisfy ∑ k j k = 0 mod p , as a natural generalization of the corresponding state for qubits which was the superposition of all states with parity zero.”

The scheme requires a polylogarithmic blow-up in the depth of the circuit.

“Our scheme requires a polylogarithmic blow-up in the depth of the circuit.”

For a code of length m = 7 in both CSS and polynomial codes, in a no-geometry circuit with noiseless classical operations and measurements allowed, the threshold is estimated to be approximately 10^-6.

“The threshold then is estimated to be ≈ 10 -6 .”

A minimal bad fault path contains exactly (k+1)r locations.

“A minimal bad fault path contains exactly ( k +1) r locations.”

The trace norm of the bad part is negligible when eta is below the threshold for general noise.

“We show the trace norm of the bad part is negligible, when η is below the threshold for general noise.”

Since the simulated circuit applies gates on nearest neighbors, say on k qubits in a row, the number of SWAP gates required is at most 2(k+1)m, i.e. a constant.

“Since the simulated circuit applies gates on nearest neighbors, say on k qubits in a raw, the number of SWAP gates required is at most 2( k +1) m , i.e. a constant.”

Quantum computation can be made robust against errors and inaccuracies when the error rate η is smaller than a constant threshold η_c.

“This paper improves this result and shows that quantum computation can be made robust against errors and inaccuracies, when the error rate, η , is smaller than a constant threshold, η c .”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 2 · plain

  “In this paper we improve this result and show how to perform fault tolerant quantum computation in the presence of constant error rate, as long as the error rate η , is smaller than some constant threshold, η 0 .”

The result allows exponentially decaying correlations between errors both in space and in time.

“Moreover, we allow exponentially decaying correlations between the errors both in space and in time.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 3 · plain

  “It turns out that for our purposes, we can release these two restrictions slightly, to allow exponentially decaying correlations in both time and space, and all the results of this paper will still hold.”

The cost of the fault-tolerant scheme is polylogarithmic in space and time.

“The cost is polylogarithmic in space and time.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 2 · plain

  “The cost is polylogarithmic in the depth and size of the quantum circuit.”

The result holds for a very general noise model including probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates.

“The result holds for a very general noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 2 · plain

  “The result holds for a very general noise model, which includes, besides probabilistic errors, also decoherence, amplitude and phase damping, depolarization, and systematic inaccuracies in the gates.”

Fault-tolerant computation can be performed with any universal set of gates.

“Fault tolerant computation can be performed with any universal set of gates.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 7 · plain

  “In fact, fault tolerant computation can be performed using any universal set of gates.”

The result also holds for quantum particles with p > 2 states, namely qupits.

“The result also holds for quantum particles with p > 2 states, namely qupits”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 2 · plain

  “The result also holds when working with quantum particles of more than two states, instead of qubits.”

The scheme can be generalized to one-dimensional quantum computers with only nearest-neighbor interactions.

“and is also generalized to one dimensional quantum computers with only nearest neighbor interactions.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 2 · plain

  “Our scheme can be generalized to work also in the case in which the quantum computer is a one dimensional array of qubits or qupits, with only nearest neighbor interactions.”

The effective error rate will be smaller than the actual error rate η if η is smaller than a certain threshold η_c, which depends on the size of the procedures and the number of errors the error-correcting code can correct.

“This effective error rate will be smaller than the actual error rate η , if η is smaller than a certain threshold, η c , which depends on the size of the procedures, and on the number of errors which the error correcting code can correct.”

If the reduced density matrix on any t qubits does not depend on the logical qubit, then there exists a unitary operation which recovers the original state even if the environment interacted with t qubits.

“More precisely, if the reduced density matrix on any t qubits does not depend on the logical qubit, then there exists a unitary operation which recovers the original state even if the environment interacted with t qubits, i.e. t errors occurred.”

• cites [61] sourceNot checked yet

  Not checked in the free run.

Such a small improvement can be achieved when using a code of constant block size.

“Such a small improvement can be achieved when using a code of constant block size.”

Fault-tolerant computation can be achieved using one of the two sets of gates G1 or G2.

“So far, what we have shown is that fault tolerant computation can be achieved using one of the two sets of gates, G 1 , G 2 .”

The fault-tolerant procedures for polynomial codes have a common relatively simple structure using the algebraic properties of the polynomials.

“Unlike the construction of the fault tolerant Toffoli gate for CSS codes, (and other fault tolerant constructions) which is a long and complicated sequence of tricks, the fault tolerant procedures for polynomial codes all have a common relatively simple structure, which uses the algebraic properties of the polynomials.”

For fault tolerance, the effective error rate must be polynomially small to ensure that with constant probability no effective error occurred.

“For fault tolerance, we need the effective error rate to be polynomially small, to ensure that with constant probability no effective error occurred.”

Both sets of gates used in the scheme are universal.

“Thus we have that both sets of gates which are used in our scheme are universal.”

The simulating circuit can tolerate a number of errors, say k, in each procedure, since they are immediately corrected in the following error-correcting stage.

“In contrast, the simulating circuit can tolerate a number of errors, say k , in each procedure, since they are immediately corrected in the following error correcting stage.”

Applying computation on encoded states recursively achieves fault tolerance against constant error rate.

“Our key theorem asserts that applying computation on encoded states recursively achieves fault tolerance against constant error rate.”

It suffices to correct bit and phase flips.

“For example, we give a simple proof that it suffices to correct bit and phase flips”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 3 · boosted

  “We give here a simple proof of the fact, first proven by Bennett at. al. [8], that it suffices to correct only these four basic errors.”

• cites [8] D. Aharonov and D. Gottesman, Accuracy Thresholds: Can We Beat $10^{-4}$? Presentation at ITP Conference of Quantum Information, 2001, available online at http://online.itp.ucsb.edu/online/qinfo_c01/aharonov/.Not checked yet

  Not checked in the free run.

A geometrical lemma asserts that if A and B are non-orthogonal then U(A) ∪ U(B) generate the whole group U(A⊕B).

“To complete the proof, we prove a geometrical lemma which asserts that if A and B are non orthogonal then U ( A ) ∪ U ( B ) generate the whole group U ( A ⊕ B ).”

A phase flip is a bit flip in the Fourier transformed basis.

“A phase flip is actually a bit flip in the Fourier transformed basis”

Two-qubit gates are universal.

“We also give a simple proof of the fact that two-qubit gates are universal.”

As long as the error rate is below the threshold, the effective noise rate of the simulating circuit can be decreased by simulating it again, and so on for several levels r, to get the final circuit M_r.

“The idea is simple: as long as the error rate is below the threshold, the effective noise rate of the simulating circuit can be decreased by simulating it again, and so on for several levels, say r , to get the final circuit M r .”

The proof of the threshold result is done by showing that the probability for bad faults, i.e. the probability for the set of faults not to be sparse, decays exponentially with the number of levels r.

“The proof of the threshold result is done by showing that the probability for 'bad' faults, i.e. the probability for the set of faults not to be sparse decays exponentially with the number of levels, r .”

Kitaev and Solovay showed that universality of a set G guarantees that any quantum computation can be approximated by a circuit using G with only polylogarithmic cost.

“Kitaev[39] and Solovay[66] showed, by a beautiful proof which uses Lie algebra and Lie groups, that universality of a set G guarantees that any quantum computation can be approximated by a circuit which uses G with only polylogarithmic cost.”

• cites [39] D. Coppersmith and E. Grossman, Generators for certain alternating groups with applications to cryptography , SIAM J. Appl. Math., 29 (1975), pp. 624–627. sourceNot checked yet

  Not checked in the free run.

• cites [66] sourceNot checked yet

  Not checked in the free run.

It suffices that each level of simulation improves only slightly the effective noise rate, since the improvement is exponential in the number of levels.

“It will suffice that each level of simulation improves only slightly the effective noise rate, since the improvement is exponential in the number of levels.”

Shor discovered a scheme to reduce the effect of decoherence.

“Despite these pessimistic beliefs, Shor discovered a scheme to reduce the effect of decoherence[63].”

• cites [63] A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation , Grad. Stud. Math. 47, American Mathematical Society, Providence, RI, 2002. sourceNot checked yet

  Not checked in the free run.

Computing on encoded quantum states does not automatically provide protection against faults, even if error corrections are applied after every procedure.

“Unfortunately, computing on encoded quantum states does not automatically provide protection against faults, even if error corrections are applied after every procedure.”

Reliability in the presence of constant error rate is achieved by applying the above scheme recursively.

“Instead, reliability in the presence of constant error rate is achieved by applying the above scheme recursively.”

Improvement from a constant error rate η to a polynomially small effective noise rate is impossible in the above method.

“Such an improvement from a constant error rate η to polynomially small effective noise rate is impossible to achieve in the above method.”

Bad faults are negligible if the error rate is below the threshold.

“Thus, bad faults are negligible, if the error rate is below the threshold.”

The circuit generated by the recursive scheme is robust also against general local noise.

“Actually, the circuit generated by the above recursive scheme is robust also against general local noise.”

The proof that G2 is universal shows certain U(2) subgroups are contained in the subgroup generated by G2, operating on non-orthogonal subspaces that together span the entire space.

“This enables us to show that certain U (2) subgroups are contained in the subgroup generated by G 2 , where these U (2) operate on non orthogonal subspaces, which together span the entire space.”

The bad part of the general noise expansion is negligible, i.e. the norm of the sum of all terms corresponding to non-sparse fault paths is small.

“First, we show that the bad part is negligible i.e. the norm of the sum of all terms which correspond to non-sparse fault paths is small.”

During the computation of a procedure, faults can propagate to correct qubits, potentially damaging all qubits that participate in the gate.

“The problem lies in the fact that during the computation of the procedure, faults can propagate to 'correct' qubits. This can happen if a gate operates on a damaged qubit and some 'correct' qubits- in general, this can cause all the qubits that participate in the gate to be damaged.”

The paper proves the universality of the two sets of gates G1 and G2.

“Next, we prove the universality of the two sets of gates which we use, G 1 for the CSS codes and G 2 for the polynomial codes.”

Shor used noiseless measurements and classical computation extensively in these procedures.

“Shor used noiseless measurements and classical computation extensively in these procedures.”

• cites [64] E. Knill, Non-Binary Unitary Error Bases and Quantum Codes , available online at http://arxiv.org/abs/quant-ph/9608048 (1996).Not checked yet

  Not checked in the free run.

The most general fault on a qubit can be described as a linear combination of four simple operations: identity, bit flip, phase flip, or both a bit flip and a phase flip.

“First, the most general fault, or quantum operation, on a qubit can be described as a linear combination of four simple operations: The identity, i.e. no error at all, a bit flip ( | 0 〉 ↔ | 1 〉 ), a phase flip ( | 0 〉 ↦- → | 0 〉 , | 1 〉 ↦- → -| 1 〉 ) or both a bit flip and a phase flip.”

• cites [8] D. Aharonov and D. Gottesman, Accuracy Thresholds: Can We Beat $10^{-4}$? Presentation at ITP Conference of Quantum Information, 2001, available online at http://online.itp.ucsb.edu/online/qinfo_c01/aharonov/.Not checked yet

  Not checked in the free run.

The threshold result holds also for one-dimensional quantum circuits.

“The threshold result is shown to hold also for one dimensional quantum circuits.”

The paper modifies Shor's procedures so that they can be performed within the paper's model, with all operations being quantum operations subjected to noise.

“Here, we modify Shor's procedures so that they can be performed within the framework of our model, i.e. all operations are quantum operations, subjected to noise.”

If the set of faults is sparse enough, then the set of errors is also kept sparse until the end of the computation.

“The more complicated task is to show that the 'good' faults are indeed good: i.e. if the set of faults is sparse enough, then the set of errors is also kept sparse until the end of the computation.”

The proof that G2 is universal uses field-theoretical arguments to generate matrices with eigenvalues that are not integer roots of unity.

“The idea is first to generate, using gates from G 2 , matrices with eigenvalues which are not integer roots of unity, a fact which is proved using field theoretical arguments.”

Shor uses quantum CSS codes encoding one qubit on polylog(n) to achieve fault tolerance with error rate η being polylogarithmically small.

“In [64] Shor uses quantum CSS codes which encode one qubit on polylog( n ) to achieve fault tolerance with the error rate η being polylogarithmically small.”

• cites [64] E. Knill, Non-Binary Unitary Error Bases and Quantum Codes , available online at http://arxiv.org/abs/quant-ph/9608048 (1996).Not checked yet

  Not checked in the free run.

If η < η_c, M1 will be more reliable than M0.

“If η < η c , M 1 will be more reliable than M 0 .”

No measurements or classical operations are required during the quantum computation.

“No measurements, or classical operations, are required during the quantum computation.”

• Also stated in: § FAULT-TOLERANT QUANTUM COMPUTATION WITH CONSTANT ERROR RATE ∗ · p. 2 · plain

  “No measurements, or classical operations, are required during the quantum computation.”

Calderbank and Shor and Steane showed that good quantum error-correcting codes exist.

“Immediately after that, Calderbank and Shor[13] and Steane[68] showed that good quantum error correcting codes exist”

• cites [13] sourceNot checked yet

  Not checked in the free run.

• cites [68] sourceNot checked yet

  Not checked in the free run.

The existence of quantum error-correcting codes does not imply the existence of noise-resistant quantum computation, because faults propagate during computation.

“The existence of quantum error correcting codes, however, does not imply the existence of noise resistant quantum computation, since due to computation the faults propagate.”

A universal set of gates can be applied fault-tolerantly on states encoded by general CSS codes, based on modifications of Shor's procedures.

“It is shown how to apply a universal set of gates fault tolerantly on states encoded by general CSS codes, based on modifications of Shor's procedures”

Without error corrections, the effect of noise will accumulate and ruin the entire computation.

“Without error corrections, the effect of noise will accumulate and ruin the entire computation[72, 17, 54, 52, 7], and hence the computation must be protected.”

• cites [72] K. Hellwig and K. Kraus, Operations and measurements . II, Comm. Math. Phys. 16 (1970), pp. 142–147. sourceNot checked yet

  Not checked in the free run.

• cites [17] sourceNot checked yet

  Not checked in the free run.

• cites [54] D. Gottesman, Stabilizer Codes and Quantum Error Correction , Ph.D. thesis, Caltech, Pasadena, CA; available online at http://arxiv.org/abs/quant-ph/9705052 (1997).Not checked yet

  Not checked in the free run.

• cites [52] Gottesman D, Class of quantum error-correcting codes saturating the quantum Hamming bound, In Phys. Rev. A 54, pp. 1862–1868, 1996 sourceNot checked yet

  Not checked in the free run.

• cites [7] D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan, Limitations of Noisy Reversible Computation , available online at http://arxiv.org/abs/quant-ph/9611028 (1996).Not checked yet

  Not checked in the free run.

A theorem by Schumacher and Nielsen asserts that a quantum state can be corrected only if no information about the state has leaked to the environment through the noise process.

“The idea is based on a theorem by Schumacher and Nielsen[61] which asserts that a quantum state can be corrected only if no information about the state has leaked to the environment through the noise process.”

• cites [61] sourceNot checked yet

  Not checked in the free run.

The error in the terms corresponding to sparse fault paths is sparse, based on the proof for probabilistic errors and linearity considerations.

“The proof that the good faults are indeed good, i.e. that the error in the terms corresponding to sparse fault paths is sparse, is based on the proof for probabilistic errors, together with some linearity considerations.”

Sequential quantum computation, such as quantum Turing machines, cannot be noise resistant because error corrections cannot be applied fast enough to prevent accumulation of errors.

“First, the choice to work with circuits which allow parallelism is necessary, because sequential quantum computation, such as quantum Turing machines, cannot be noise resistant[3], since error corrections cannot be applied fast enough to prevent accumulation of errors.”

• cites [3] D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), El Paso, TX, 1997, pp. 176–188. sourceNot checked yet

  Not checked in the free run.

In one-dimensional circuits, swap gates used to bring far-away qubits together do not cause the error to propagate too much.

“We show that these swap gates do not cause the error to propagate too much.”

Allowing qubits to be input at different times to the circuit is crucial because it provides a way to discard entropy accumulating in the circuit.

“It is also crucial that we allow qubits to be input at different times to the circuit unlike (Yao[75]), because this provides a way to discard entropy which is accumulating in the circuit.”

• cites [75] sourceNot checked yet

  Not checked in the free run.

The paper gives a general simple formula to calculate the threshold in the error rate, given the fault-tolerant procedures.

“We give a general simple formula to calculate the threshold in the error rate, given the fault tolerant procedures.”

Independent and quasi independent probabilistic errors, amplitude and phase damping, decoherence, and systematic inaccuracies in gates are all special cases of the general noise model defined above.

“Independent and quasi independent probabilistic errors, amplitude and phase damping, decoherence, and systematic inaccuracies in gates, are all special cases of the general noise model defined above.”

• cites [17] sourceNot checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: No correlations between environments of different qubits, except through the gates.
• AssumptionThe authors state this as an assumption: The environment is renewed each time step, and hence there are no correlations between the environments at different time steps.

Under the restriction that all qubits are initialized at time 0, it is impossible to compute fault-tolerantly without an exponential blowup in the size of the circuit.

“Without this assumption, i.e. under the restriction that all qubits are initialized at time 0, it is impossible to compute fault tolerantly without an exponential blowup in the size of the circuit[5].”

• cites [5] D. Aharonov and M. Ben-Or, Polynomial simulations of decohered quantum computers , in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Los Alamitos, CA, 1996, pp. 46–55. sourceNot checked yet

  Not checked in the free run.

The threshold formula depends only on two parameters: the size of the largest procedure used and the number of errors the code corrects.

“This formula depends only on two parameters of these procedures: the size of the largest procedure used in our scheme, and the number of errors which the code corrects.”

Kitaev's set consisting of CP and the Hadamard gate is universal.

“The proof is based on a result by Kitaev[39], which asserts that the following set of gates is universal: CP is a two qubit gate which takes | 11 〉 ↦- → i | 11 〉 and applies identity on the rest, and the Hadamard gate.”

• cites Kitaev[39]Not checked yet

  Not checked in the free run.

The degree reduction techniques used are those introduced by Ben-Or et al [9] for fault tolerant classical distributed computation on a secret shared by several parties.

“We use techniques which were introduced by Ben-Or et al [9] for fault tolerant classical distributed computation, on a secret which is shared by several parties.”

• cites Ben-Or et al [9]Not checked yet

  Not checked in the free run.

In recursive simulations, error corrections to the current level are added at each level, preventing accumulation of errors in all levels.

“The advantage of using recursive simulations, instead of one step of simulation, as in Shor's scheme[63], is that in each level error corrections to the current level are added. This means that error corrections of all scales are applied frequently during the computation procedures, preventing accumulation of errors in all levels.”

The general-noise threshold η′c is smaller than the threshold for probabilistic noise ηc.

“η ′ c will be smaller than the threshold for probabilistic noise, η c .”

For any computation code C with gates G, there exists a threshold η′c > 0 and constants c1, c2, c3 such that any quantum circuit Q with n input qubits, t time steps, s gates from G, and v locations can be simulated by a circuit Q′ using n log^{c1}(v/ǫ) qubits, time t log^{c2}(v/ǫ), and s log^{c3}(v/ǫ) gates from G, and in the presence of general noise with error rate η < η′c, Q′ computes a result

“There exists a threshold η ′ c &gt; 0 , and constants c 1 , c 2 , c 3 such that the following holds.”

• Also stated in: § Theorem 11. The Threshold Theorem for General Noise: · p. 56 · plain

  “There exists a quantum circuit Q ′ which operates on n log c 1 ( v ǫ ) qubits, for time t log c 2 ( v ǫ ) , and uses s log c 3 ( v ǫ ) gates from G such that in the presence of general noise with error rate η &lt; η ′ c , Q ′ computes a function which is ǫ -close to that computed by Q .”

For any two universal sets of quantum gates G′ and G′′, there exists a threshold η′′c > 0 and constants c1, c2, c3, c4 such that any quantum circuit Q′ with n input qubits, t time steps, s gates from G′, and v locations can be simulated by a circuit Q′′ using c1 n log^{c2}(v/ǫ) qubits, time c3 t log^{c2}(v/ǫ), and c4 s log^{c2}(v/ǫ) gates from G′′, and in the presence of general noise with error

“There exists a threshold η ′′ c &gt; 0 , and constants c 1 , c 2 , c 3 , c 4 such that the following holds.”

• Also stated in: § Theorem 12. The Threshold Result in Full Generality: · p. 57 · plain

  “There exists a quantum circuit Q ′′ which operates on c 1 n log c 2 ( v ǫ ) qubits, for time c 3 t log c 2 ( v ǫ ) , and uses c 4 s log c 2 ( v ǫ ) gates from G ′′ such that in the presence of general noise with error rate η &lt; η ′′ c , Q ′′ computes a function which is ǫ -close to that computed by Q ′ .”

• AssumptionThe authors state this as an assumption: The universal set of gates G contains a gate which discards a qubit, and a gate which adds a blank qubit to the circuit.

An error in a SWAP gate causes contamination of all qubits on which g operates, so it is equivalent to an error in all original sites of the qubits participating in the gate and the final site of the other qubit participating in the SWAP gate.

“This will cause contamination of all the qubits on which g operates on, (in the worst case), so an error in a SWAP gate is equivalent to an error in all the original sites of the qubits participating in the gate, and the final site of the other qubit participating in the SWAP gate.”

If quantum behavior cannot be simulated efficiently by classical systems (BPP = BQP), then increasing the noise causes a transition from quantum computational behavior to classical computational behavior.

“Suppose that indeed quantum behavior cannot be simulated efficiently by classical systems, an idea suggested by Feynmann[27] which originated quantum computation. In other words, suppose BPP = BQP . Then, increasing the noise, a transition from the quantum computational behavior to classical computational behavior occurs.”

• cites [27] sourceNot checked yet

  Not checked in the free run.

For a very small noise rate, quantum systems can maintain their quantum nature.

“In this paper we show that for very small noise rate, quantum systems can maintain their quantum nature.”

The same threshold used for probabilistic noise guarantees that bad fault paths are negligible also in the presence of exponentially decaying correlations, for probabilistic noise.

“In this section we show that the same threshold as is used for probabilistic noise, (definition 7.4) guarantees that the bad fault paths are negligible also is the presence of exponentially decaying correlations, for probabilistic noise.”

• AssumptionThe authors state this as an assumption: Noise correlations decay exponentially in space and time.

The threshold result implies that quantum computation might be practical if the noise in the system can be made very small.

“The result implies that quantum computation might be practical if the noise in the system can be made very small.”

Any error rate η below the general-noise threshold η′c satisfies the threshold condition.

“It is easy to see that any η &lt; η ′ c satisfies the threshold condition.”

The threshold result holds in full generality for d-dimensional quantum computers, for any d ≥ 1.

“We show that the threshold result holds in full generality for d -dimensional quantum computers, for any d ≥ 1.”

For any d ≥ 1 and any two universal sets of quantum gates G′ and G′′, there exists a threshold η′′c > 0 and constants c1, c2, c3, c4 such that any d-dimensional quantum circuit Q′ with n input qubits, t time steps, s gates from G′, and v locations can be simulated by a d-dimensional circuit Q′′ using c1 n log^{c2}(v/ǫ) qubits, time c3 t log^{c2}(v/ǫ), and c4 s log^{c2}(v/ǫ) gates from G′′ ∪ {SWAP

“There exists a threshold η ′′ c &gt; 0 , and constants c 1 , c 2 , c 3 , c 4 such that the following holds.”

• Also stated in: § Theorem 13. Threshold theorem for d -dimensional circuits:: · p. 58 · plain

  “There exists a d-dimensional quantum circuit Q ′′ which operates on c 1 n log c 2 ( v ǫ ) qubits, for time c 3 t log c 2 ( v ǫ ) , and uses c 4 s log c 2 ( v ǫ ) gates from G ′′ ∪{ SWAP } such that in the presence of general noise with error rate η &lt; η ′′ c , Q ′′ computes a function which is ǫ -close to that computed by Q ′ .”

• AssumptionThe authors state this as an assumption: The universal set of gates G′′ used in the final circuit contains the SWAP and the RESTART gates.

An error in a SWAP gate adds a factor of 2 to the original spread of the procedure.

“This adds a factor of 2 to the original spread of the procedure.”

If a fault path is bad, then there must be at least one r-rectangle in which it is bad.

“If a fault path is bad, there must be at least one r -rectangle in which it is bad.”

The proof for the exponentially decaying correlation model is complete because the bad-fault-path probability expression decays exponentially to zero with r when η is below the probabilistic-noise threshold.

“This completes the proof for this model of noise, since the expression above decays exponentially fast to zero with r , if η is below the threshold for probabilistic noise from definition 7.4”

• AssumptionThe authors state this as an assumption: Noise correlations decay exponentially in space and time.

The d-dimensional fault-tolerant procedure is still fault tolerant.

“The claim is that the procedure is still fault tolerant.”

If an error occurs in a SWAP gate, then the two qubits participating in it are contaminated.

“If an error occurred in a SWAP gate, then the two qubits participating in it are contaminated.”

A SWAP gate that is not faulty does not cause propagation of error.

“a SWAP gate which is not faulty does not cause propagation of error.”