Introduction

Any two state quantum system can be used as a qubit. A quantum state evolves according Schroedinger's equation. For time independent conditions on the evolution, the equation is a first order linear differential equation,

    i d φ / dt = H φ.

    φ(t) = e-i H t φ(to).

The matrix exponential is defined by the series,

   e-M = Σi≥0 Mi/i!

Operations on qubits is, therefore, any unitary linear transform with the additional requirement that the matrix must act only on a small number of qubits, leaving the rest unchanged. This is a "finite fan-in" requirement. It exists to give the theory some relavance to how people believe quantum computers will be constructed. A quantum circuit is a collection of quantum gates wired together so that outputs from one gate are inputs to another.

Reversibility

In comparing quantum and classical gates, there is an obvious difference. A quantum gate acts by an invertible matrix. So any gate has an inverse gate. Classical gates are typically non-reversible. Example: the AND gate cannot be reversed: given 0=AND(x,y), we know only that at least one of x and y differed from 1.

All quantum computing is reversible (except for collapse of quantum state on measurement.) We need to fixup classical computing so as to be reversible as well. The trick is to include the inputs in the output and encode the output on a spare input variable. Here is how it is done for AND:

   AND(x,y,z) = (x,y,z+xy)

Exercise: write down the description of the inverse AND gate

Tensor products

To describe the matrices acting on multiple qubits we need to identify the space of multiple qubits. Do not think that we simply concatenate the sets of basis vectors! That is, if we have 4 qubits, with 2 basis vectors for each qubit, that the total system has 8 basis vectors. In fact, the system has 16 dimensions, one for each combination of basis vectors.

We must take the tensor product of the subspaces to form the complete space. Given vector spaces U and V of dimesions m and n, their vector product is a vector space and a bilinear map,

      ⊗: U × V → U ⊗ V
         (u,v) → u ⊗ v

      w: U × V → W
         (u,v) → w(u,v)

   w(u,v) = f(u⊗v).

The gist of the definition is that the tensor product is the universal way of combining two vector spaces into one so that any linear transformation possible on the individual spaces, or bilinear transformation combining the two spaces, can be expressed in the combined space.

Consider the basis vectors of spaces U and V, denoted u_i and v_j, where i=1,...,m and j=1,...,n. Each pair of basis vectors maps to some vector in the tensor space and the collection of mn such vectors must span the space.

   ⊗(ui,vj) = ui⊗vj

Now consider arbitrary vectors u∈U and v∈V. Express each of these as a linear combination of basis vectors. The bilinearity of the tensor map then gives the image of (u,v) in the tensor space,

    ⊗( Σ aiui, Σ bjvj) = Σ (aibj) ui⊗vj.

Exercise: Show that the map ⊗ defined concretely as above is bilinear. Show also that it is universal - for any bilinear map w:U×V → W there is a linear map f so that f(⊗(v,w))=w(v,w).

Exercise: Show that the tensor is unique up to isomorphism. That is, if ⊗' is another universal bilinear map, then there is an isomorphism between ⊗' and ⊗.

Suppose F and G are linear maps on U and V. For the sake of simplicity, think of them as matrices. Consider the composite map ⊗( Fu, Gv ). It is a bilinear map so by universality there is a matrix H so that,

   H ⊗(u,v)  = ⊗( Fu, Gv ).

Given matrices F and G, the Kronecker product of F and G is formed by replacing each entry f_i,j in F with the matrix f_i,jG. Index the entries of a vector in w∈U⊗V so that basis vector u_i⊗v_j, has index n(i-1)+(j-1), where n is the dimension of V. With this indexing, the Kronecker product calculates the tensor product F⊗G.

Exercise: Prove that the Kronecker product calculates the tensor product, with appropriate indexing of entries.

Quantum Gates

A system of n qubits is the space formed by the n-fold tensor product of the space of each qubit. Rather than write, say, |a⟩⊗|b⟩, where a and b are 0 or 1, we write |ab⟩. To return to our example of four qubits, the basis vectors for this 16 dimensional space are,

   |0000⟩, |0001⟩, |0010⟩, |0011⟩, ...

Let us return to the AND operator,

    AND(x,y,z) = (x,y,z+xy)

    |000⟩ → |000⟩
    |001⟩ → |001⟩
    |010⟩ → |010⟩
    |011⟩ → |011⟩

    |100⟩ → |100⟩
    |101⟩ → |101⟩
    |110⟩ → |111⟩
    |111⟩ → |110⟩

         | 1 0 0 0   0 0 0 0 |
         | 0 1 0 0   0 0 0 0 |
         | 0 0 1 0   0 0 0 0 |
         | 0 0 0 1   0 0 0 0 |
   AND = |                   |
         | 0 0 0 0   1 0 0 0 |
         | 0 0 0 0   0 1 0 0 |
         | 0 0 0 0   0 0 0 1 |
         | 0 0 0 0   0 0 1 0 |

In a system of n qubits, where we wish to apply AND to the last three, use the tensor product of AND and identity matrices. The result matrix U represents the operator I on the first n-3 spaces, and AND on the space of the last 3 qubits, hence,

   U = I ⊗ I ⊗ ... ⊗ I ⊗ AND

Exercise: Demonstrate this with a small example. Either a 4 or 5 qubit system with AND applied to the last 3 qubits.

To operate on an arbitary three qubits out of the n, mentally we can consider swapping qubits until the three are in the last positions, applying U and then swapping them back. The details we leave to a good symbolic algebra package. To swap qubits, take the reverse identity,

     | 0 1 |
     | 1 0 |

     | 0 0 1 0 |
     | 0 0 0 1 |
     | 1 0 0 0 |
     | 0 1 0 0 |