Q2L6b.txt

#
# File:   content-mit-8371x-subtitles/Q2L6b.txt
#
# Captions for 8.421x module
#
# This file has 104 caption lines.
#
# Do not add or delete any lines.  If there is text missing at the end, please add it to the last line.
#
#----------------------------------------

How does one design a fault-tolerant circuit
which operates reliably despite having faulty components?
We have seen that the threshold for fault tolerance
is given by 1 over the number of fault paths in a given circuit.
This circuit should be the fault-tolerant procedure
for a universal gate.
That is a which allows an arbitrary computation
to be constructed.
We define a procedure as being fault-tolerant
if a single component failure leads to at most one error
in each encoded block of outputs from the circuit.
Here are some examples to illustrate the principles.
Some good constructions for a NOT gate, for example,
utilize three NOT gates followed by an error correction circuit.
This error correction circuit should output three bits
encoded in the same code as the input
here, the triple redundancy code.
A non fault-tolerant procedure would replace a single inverter
with three inverters just as before.
But instead of using an error correction circuit
would use, for example, a single majority voting gate
as we have done in one of our examples,
where the output is generated by fan out of a single output.
This is bad because there's a single point of failure which
may propagate to more than one error.
In the quantum case we may consider a logic gate
between two encoded blocks, say A and B.
And a good construction would use three controlled NOT
gates between, for example, the three qubit code.
In contrast, a non fault-tolerant procedure
for a logical controlled NOT gate
might employ a single qubit for the control
line of the logical controlled NOT gate.
A key idea is that error propagation must be controlled,
and this must be true also in the error correction step.
One approach for controlling error propagation
is to employ a concept known as transversal gates.
In the quantum case, this means that for n-qubit blocks
a logical qubit operation u, would be transversal
if it were the tensor product of n individual qubit operations.
Such operations are also known as being bitwise operators.
Clearly this increases a number of gates needed.
What is the cost of fault-tolerance therefore,
in terms of the overhead of the number of gates required?
If the circuit size is originally
d for the size of the fault-tolerant procedure,
we ask then, what is the circuit size
of the fault tolerant circuit?
Suppose we have k recursion levels, also
known as concatenation levels.
This means that the overall circuit
grows as d to the k, which seems to be a rather
expensive exponential cost.
To accurately evaluate this cost,
we must recall that our goal is to simulate an n-qubits circuit
with a particular probability of error that is epsilon.
Therefore, each fault-tolerant gate procedure
should have an error of at most, something
like epsilon divided by n.
We can use this to bound the number of recursion levels
necessary.
Recall that c is the number of fault
paths in each fault-tolerant procedure.
The fault tolerance recursion equation
tells us that cp fail is equal to cp to the 2 to the k.
Substitute in that p threshold is 1
over the number of fault paths.
This recursion equation can thus be
rewritten in this rather convenient and insightful form,
that the ratio of p fail to p threshold is given by p
over pth to the 2 to the k.
This is the fault tolerance recursion equation
and it governs each individual fault-tolerant procedure.
Let us compute the circuit size required by solving
this equation to find k.
We obtain k by substituting in for the acceptable probability
of failure of each fault-tolerant procedure, that
is epsilon over n.
We get this new inequality which allows
us to take a logarithm of both sides
to find two to the k times log p over pth
is bounded by a logarithm of epsilon over n times pth.
Solving for 2 to the k, we find that it
is the ratio of two logarithms.
And this thus gives us the overall circuit size,
namely n times d to the k where we now
substitute in our expression for 2
to the k as the ratio of two logarithms.
Here for convenience we invert the fractions
in each of the logarithms to make the logarithms positive.
The overall result is that the circuit size
is polynomial in log n over epsilon times n.
This is exactly what we desired for
the fault-tolerance theorem.
To summarize, the main principles
we have learned for fault tolerance
are first, that we compute on encoded data
and never unencode.
And second, we control error propagation
by employing fault-tolerant procedures, which limit errors
from spreading and becoming uncorrectable.
These principles apply to both classical and quantum circuits
and provide the foundation for a threshold for fault-tolerant quantum computation.