Quantum Circuit Proof Notes
I'm going through some lecture notes on quantum computing by Childs. The lecture notes are dense, so I'm rewriting the formulas and adding personal notes to help me understand. On a quantum computer, any unitary operation can be applied to qubits, in theory. This section deals with approximating arbitrary unitary gates.
Preliminaries
A unitary gate corresponds to a unitary matrix: any matrix that meets the following condition.
1
The adjoint of a unitary gate is its own inverse.
A list of equivalent conditions is availiable on Wikipedia.
Conveniently, the determinent of a unitary matrix is always 
.
2
In the context of quantum computing, this is easy to remember. The application of any quantum circuit starts and ends with a normalized ket, 
. The ket must be normalized, a unit vector, for the sum of all outcome probablities to equal , unity. Knowing this, it's easy to remember that any quantum circuit must take a normalized input ket to a normalized output ket. A matrix with a determenent of is guranteed to preserve the magnitude of its input vector. This is a bit confusing; I've mixed around cause and effect, but it does make it easy to remember that unitary gates have a determenent of .
Subadditivity of Errors
On an actual quantum computer, actual gate operations are only approximations of ideal gate operations. Unitarity is guranteed, but there will be some error. We can define the error as the determinent of the difference between some desired gate matrix 
and an actual gate matrix 
: that is 
. If we have a threshold 
, then our approximation is fine so long as 
.
It is of great interest how the error rate of multiple operations grow. We will prove that the error rate of a sequence of gates within the error threshold is at most the sum of each gate's error rate:
3
The proof is by induction.
In the base case, 
. This is trivial.
4
The recursive case:
5
We can add in these terms because they add to zero.
6
By the triangle inequality, we know that the sum of the magnitudes is less than or equal to the magnitude of the sum; the sum of a triangles two shortest sides can only be as long as the longest side.
7
We can factor some terms.
8
Now remember that A and B are both guranteed to be unitary. They both have a deteriment of 1. Fortunately, the determinent of products is the product of determinents: || AB || = || A || || B ||.
9
So we have our recursive case:
10
This shows a linear error growth.
Examples
To drive this home, here's a concrete example with a three gate system.
Suppose we have an ideal program:
11
And an actual program:
12
We assume each gate is within some known error bound.
13
14
15
Now lets expand our program's error rate and see what we get:
16
Let's expand the 2 gate program:
17
If we combine the two equations, we see that the error rate of our entire program is less than or equal to the sum of the individual gate error rates.
18
This is what was expected. Awesome!
Constructing Qubits
This is under construction.