M:=RandomChoice[{2/10,3/10,2/10,3/10}->{"00","01","10","11"}]

Qbits 1I

With the classical cbits |0 ⟩, |1⟩ we where able to construct, via the Kronecker or direct product, two cbit and higher 
words, e .g.  |00 ⟩, |10⟩, |01⟩, |11⟩ that comprise the basis |x⟩_2.  We can also construct direct products of Qbits
so if

|(Subscript[ψ, α])⟩ = (Subscript[α, 0])|0⟩ +  (Subscript[α, 1])|1⟩   and |(Subscript[ψ, β])⟩ = (Subscript[β, 0])|0⟩ +  (Subscript[β, 1])|1⟩   then

|(Subscript[ψ, α])⟩ ⊗ |(Subscript[ψ, β])⟩ =  ((Subscript[α, 0])|0⟩ +  (Subscript[α, 1])|1⟩ )  ⊗  (Subscript[β, 0])|0⟩ +  (Subscript[β, 1])|1⟩= (Subscript[α, 0])(Subscript[β, 0]) |00⟩ +  (Subscript[α, 0])(Subscript[β, 1]) |01⟩ +  (Subscript[α, 1])(Subscript[β, 0]) |10⟩ + (Subscript[α, 1])(Subscript[β, 1]) |11⟩

that is a 2-Qbit is a linear combination of the computational basis states. Four complex numbers are required
to fully specify this 2-Qbit.

Question: Suppose we have a 3-Qbit word how many complex numbers are required to uniquely specify it?,
for 100-Qubit word?

2^100
ScientificForm[N[%]]

In general

| ψ⟩ =   (∑_( 0 < x < (2^n)))  (Subscript[(Subscript[α, x]) |x ⟩, n])

The coefficients    | (Subscript[α, x])((|)^2)  give the probability to find the system in state | x ⟩  (The Born rule).

Class Project:   We are given a 2-Qbit,  |ψ⟩,  that is the output of a quantum computer. You have a measuring device
M  that tells you the value x =0,1,2,3  (00,01,10,11) that is output. (i) Repeat your measurements several times. How come every time  you make a measurement you get different results?, how could this possible be useful?  A classical deterministic  computer gives us the correct answer with just one measurement!   (ii) Take statistics of your measurements, for example  count the number of "hits" for every value of x.  You could do this by hand, or automate it. (iii) From the results obtained in (iii) try to reconstruct |ψ⟩.

M

(* Some Mathematica Hints *)

(* Make a table of all your experiments, and sort your results *)

measurenum=1000;
table=Sort[Table[M,{i,1,measurenum}]];

(* count and collate your measurements using the Tally command *)

tally=Tally[table]
numberof00=tally[[1,2]]
numberof01=tally[[2,2]]
numberof10=tally[[3,2]]
numberof11=tally[[4,2]]

(* now estimate probability of occurances *)

p00=N[numberof00/measurenum]
p01=N[numberof01/measurenum]
p10=N[numberof10/measurenum]
p11=N[numberof11/measurenum]

Entangled States

In the example given above the 2-Qubit can be factored as a product of two Qubits (after all that is how we constructed it). Question: can all 2-Qubits be factored in this way. The answer is No!  For example consider

| ψ ⟩ = (1/(Sqrt[2]))| 01 ⟩ + (1/(Sqrt[2]))| 10 ⟩ + 0 |00⟩+ 0 |11⟩

is this a valid 2-Qubit? Why?  Can you factor it into a direct product of single Qbits?

This is an example of what is called an entangled state. Much of the "magic" in QI&C is enabled by the existence of these states.

Generalized Born rule  (Section 1.8 in Mermin)

The measurement M  described above gives us the value of x =(({1,0})^(⊗^n)) in an n-dimensional Qbit word, but often we
only measure a single bit in that word. Consider again the computational basis of n=3 word, whose basis are
|000⟩,|001⟩,|010⟩,|011⟩,|100⟩,|101⟩,|110⟩,|111⟩. If we measured just the first single bit (on the left) we would get, in a classical measurement, the values 0,0,0,0,1,1,1,1 respectively. What would happen for a Qbit ? for such a measurement?
Lets first look at a simple example. For n=2, let

| ψ ⟩ = (1/(Sqrt[4]))| 01 ⟩ + (1/(Sqrt[4]))| 10 ⟩ - (1/(Sqrt[4]))|00⟩ - (1/(Sqrt[4])) |11⟩

which we can rewrite

(Subscript[α, 0])|0⟩|(Subscript[Φ, 0]) ⟩ +  (Subscript[α, 1])|1⟩|(Subscript[Φ, 1]) ⟩       where  |(Subscript[Φ, 0]) ⟩=(1/(Sqrt[2]))| 1 ⟩ - (1/(Sqrt[2]))|0⟩    |(Subscript[Φ, 1]) ⟩=(1/(Sqrt[2]))| 0 ⟩ - (1/(Sqrt[2]))|1⟩   and (Subscript[α, 0])=(1/(Sqrt[2]));  (Subscript[α, 1])=(1/(Sqrt[2]))

Note that     ⟨(Subscript[Φ, 0]) |(Subscript[Φ, 0]) ⟩ = ⟨(Subscript[Φ, 1]) |(Subscript[Φ, 1]) ⟩ =1;  but   ⟨(Subscript[Φ, 0]) |(Subscript[Φ, 1]) ⟩ ≠ 0

Then  P(that bit1=0)=|(Subscript[α, 0])((|)^2) = (1/2)
          P(that bit1=1)=|(Subscript[α, 1])((|)^2) = (1/2)
          
          If result 0 is obtained state "collapses" into |(Subscript[Φ, 0]) ⟩
          If result 1 is obtained state "collapses" into |(Subscript[Φ, 1]) ⟩

For a general n+1 Qubit we can write, as above

(Subscript[| ψ ⟩, n+1]) = (Subscript[α, 0])|0⟩|(Subscript[Φ, 0]) (Subscript[⟩ , n])+  (Subscript[α, 1])|1⟩ |(Subscript[Φ, 1]) (Subscript[⟩ , n])

so that if (Subscript[   | ψ ⟩, n+1])= (∑_(x=0)^(x=(2^(n+1))-1)) γ(x) |x⟩_(n+1)   

then   |(Subscript[Φ, 0]) (Subscript[⟩ , n])=1/(Subscript[α, 0]) (∑_(x=0)^(x=(2^n)-1)) γ(x) |x⟩_n     |(Subscript[Φ, 1]) (Subscript[⟩ , n])=1/(Subscript[α, 1]) (∑_(x=0)^(x=(2^n)-1)) γ((2^n)+x) |x⟩_n  

((Subscript[α, 0])^2)= (∑_(x=0)^(x=(2^n)-1)) |γ(x)((|)^2)      ((Subscript[α, 1])^2)= (∑_(x=0)^(x=(2^n)-1)) |γ(x+(2^n))((|)^2)

Quantum processing

Section 2.1 of Mermin

In  a previous notebook we illustrated the circuit model of computation by building a four bit adder. 
We took two 4 bit words as input, and output a four bit word which was a sum of the two inputs. We could
treat the inputs as single 8-bit word that is mapped to  a  8 bit register,

Sometimes written in shorthand as  {0,1}^(⊗8)   (the alphabet is 0,1 and we take a direct product of those Cbits 8 times)
and the output is {0,1}^(⊗4)  and so the addition function (SubPlus[f])   can be written as a rule

(SubPlus[f]): {0,1}^(⊗8) ⟶{0,1}^(⊗4)

for example if we want to add 3 + 4 taking the first four bits to represent 3, and the second set of four bits to represent 4
we have

(SubPlus[f]): 00110100  ⟶ 0111

The function (SubPlus[f]) has a similar type of mapping for possible values of the pair of input registers.  We notice that
the above mapping can be decomposed into four separate ones i.e.

 (Subscript[f, +]^a): 00110100  ⟶ 0
 (Subscript[f, +]^b): 00110100  ⟶ 1
 (Subscript[f, +]^c): 00110100  ⟶ 1
 (Subscript[f, +]^d): 00110100  ⟶ 1
 
 so without loss of generality we can define a computation as the assignment

 f: {0,1}^(⊗n) ⟶{0,1}

Examples

Consider all functions

f:{0,1}  ⟶ {0,1}

Only four functions arise;

(Subscript[f, 0]):0 ⟶0         (Subscript[f, 1]):0 ⟶0        (Subscript[f, 2]):0 ⟶1       (Subscript[f, 3]):0 ⟶1
(Subscript[f, 0]):1 ⟶0         (Subscript[f, 1]):1 ⟶1        (Subscript[f, 2]):1 ⟶0       (Subscript[f, 3]):1 ⟶1

Consider now

f:{0,1}^(⊗2)  ⟶ {0,1}

How many functions exist for this mapping?

({{    00, 01, 10, 11}, {(Subscript[f, 0])  0, 0, 0, 0}, {(Subscript[f, 1]) 0, 0, 0, 1}, {(Subscript[f, 2]) 0, 0, 1, 0}, {      0, 1, 0, 0}, {      1, 0, 0, 0}, {      0, 0, 1, 1}, {      0, 1, 0, 1}, {      1, 0, 0, 1}, {      1, 0, 1, 0}, {      0, 1, 1, 0}, {      1, 1, 0, 0}, {      0, 1, 1, 1}, {      1, 0, 1, 1}, {      1, 1, 0, 1}, {      1, 1, 1, 0}, {(Subscript[f, 15])1, 1, 1, 1}})

Convince yourself that for an input register {0,1}^(⊗n)  we can define (2^(2^n))  functions!
so as n gets larger the number of possible functions grows as a double exponential.

Given a function f we wish to evaluate f(x) for some input x. This is a statement of our computational problem.
We can do this by defining and input and output register of size n, m respectively 

(Subscript[|x ⟩, n]) (Subscript[|y ⟩, m])

after the computation we want the output to look something like this

(Subscript[|x ⟩, n]) (Subscript[|f(x)⟩, m]) 

so that the output register contains the desired result. 

For the quantum protocol we define an operator  (Subscript[U, f])  so that  (see Eq. 2.1 in Mermin)

(Subscript[U, f])(Subscript[|x ⟩, n]) (Subscript[|y ⟩, m]) ⟶ (Subscript[|x ⟩, n]) |y ⊕ f(x) ⟩

Here ⊕ is the generalization of the modular sum for two Cbits, e.g. 1101  ⊕ 0011 =   1110 note that
when  z ⊕ z =0  e.g.  1001 ⊕ 1001 =   0000 etc.

Why are we defining (Subscript[U, f]) in this way?   

Note: (Subscript[U, f])  is reversible

(Subscript[U, f]) (Subscript[U, f])(Subscript[|x ⟩, n]) (Subscript[|y ⟩, m]) = (Subscript[U, f]) (Subscript[|x ⟩, n]) |y ⊕ f(x) ⟩_m=(Subscript[|x ⟩, n]) |y ⊕ f(x) ⊕ f(x) ⟩_m

but  f(x) ⊕ f(x) =0  and so |y ⊕ f(x) ⊕ f(x) ⟩ = |y ⊕ 0 ⟩ =   |y ⟩ 

or

(Subscript[U, f]) (Subscript[U, f])(Subscript[|x ⟩, n]) (Subscript[|y ⟩, m]) ⟶ (Subscript[|x ⟩, n]) (Subscript[|y ⟩, m]) 

QED

Thus (Subscript[U, f]) has the desired property of being reversible, but how about evaluating our function f(x)?
Suppose the input is  (Subscript[|x ⟩, n]) (Subscript[|0 ⟩, m])  (we set all bits in the second register to zero) then according to the above definition

(Subscript[U, f])(Subscript[|x ⟩, n]) (Subscript[|0⟩, m]) ⟶ (Subscript[|x ⟩, n]) |0 ⊕ f(x) ⟩= (Subscript[|x ⟩, n]) | f(x) ⟩

and we get the desired result.

Quantum Parallelism

Given the Hadamard gate for a single Qbit we found that

H |0⟩ = (1/(Sqrt[2]))|0⟩ + (1/(Sqrt[2]))|1⟩

H |1⟩ = (1/(Sqrt[2]))|0⟩ - (1/(Sqrt[2]))|1⟩

therefore 

H ⊗ H |0⟩|0⟩ = (1/2)(|0⟩ + |1⟩)⊗ (|0⟩ + |1⟩) = (1/2)( |00⟩+|01⟩+|10⟩+|11⟩ )

The direct product gate (H ⊗ H) ≡ (H^(⊗2))  maps |0⟩|0⟩ into a linear superposition state.

How about (H^(⊗3))|0⟩|0⟩|0⟩ = (1/(2^(3/2)))(|0⟩ + |1⟩)⊗ (|0⟩ + |1⟩) ⊗ (|0⟩ + |1⟩) =
 (1/(2^(3/2)))(|000⟩ + |001⟩+ |010⟩+ |100⟩+ |101⟩+ |110⟩+|011⟩+ |111⟩)

or

 (H^(⊗n))(Subscript[|0⟩, n]) = (1/(2^(n/2))) (Underoverscript[ ∑, (x=0), (x=(2^n)-1)])  |x⟩_n
 
 Now let us take two registers
 
 (Subscript[|0⟩, n])(Subscript[|0⟩, m])
 
 and operate on it with  (H^(⊗n)) ⊗ 1. Here  the Hadamard operators act on register n only, while the unity operator
 acts on the space of the second register, or
 
 (H^(⊗n)) ⊗ 1(Subscript[|0⟩, n])(Subscript[|0⟩, m])  Now suppose we have the operator (Subscript[U, f]) defined above and lets evaluate 
 
 (Subscript[U, f]) (H^(⊗n)) ⊗ 1(Subscript[|0⟩, n])(Subscript[|0⟩, m]) =  (Subscript[U, f])  (1/(2^(n/2))) (Underoverscript[ ∑, (x=0), (x=(2^n)-1)])  |x⟩_n|0⟩_m = (1/(2^(n/2))) (Underoverscript[ ∑, (x=0), (x=(2^n)-1)]) |x⟩_n|f(x)⟩_m
 
 where we have used the relation (Eq. (2.1)) above.
 
 What is the implication of the above result ?
 
 For a classical gate (Subscript[U, f]) calculates f(x) for a given value of x. So lets suppose we have a four bit gate, which means
 since x={0,1,..(2^4)}  i.e. 16 different input value we need to run our computer 16 times to evaluate all possible 
 values of x.  However by inserting the Hadamard gates (H^(⊗4)), as above, the quantum computer will evaluate
 all possible values since 
 
 (Underoverscript[ ∑, (x=0), (x=(2^n)-1)]) |x⟩_n|f(x)⟩_m = |0000⟩ |f(0000)⟩+ |0001⟩ |f(0001)⟩ + |0010⟩ |f(0010)⟩ +  |0011⟩ |f(0011)⟩ +...
 
 or more succinctly
 
 (Subscript[|0⟩, 4]) |f(0)⟩_4  +  (Subscript[|1⟩, 4]) |f(1)⟩_4 +  (Subscript[|2⟩, 4]) |f(2)⟩_4 + ...
 
 That is, with one pass, our quantum computer evaluates all possible values for the function f!. If we simply had
 a hundred Qubits then this circuit could evaluate  f(x)  for about  (10^30) values of x. Wow! This is called quantum parallelism. But there's a catch! Can you guess what it is?

In the mid-nineteen 80's people where trying to figure out how quantum parallelism could be exploited, in 1985
David Deutsch provided a simple quantum circuit that demonstrated how interference allows quantum parallelism
to become useful. In many ways this advance signaled the beginning of the modern quantum computer movement.
Before we discuss the Deutsch problem let's introduce another simple, but nifty, example of a quantum computation.

We all know what the classical NOT gate is. It is a function on a single bit which negates its value, 

that is       0 → NOT →1    and 1→NOT→0. Suppose someone asked to construct a classical square root
of the NOT gate. let's call it (Sqrt[NOT]). Now form its definition 

(Sqrt[NOT])(Sqrt[NOT]) = NOT    can you find a classical gate that has this property?   Another way of looking at it is
that 

NOT=(({{0, 1}, {1, 0}})) .  So you need to find a matrix that gives the NOT (PauliX) gate. Check this out

SqrtNOT=1/2{{1+I,1-I},{1-I,1+I}}
MatrixForm[SqrtNOT]

SqrtNOT.SqrtNOT

SqrtNOT.{1,0}

i.e. SqrtNOT |0⟩ = ((1+i)/2) |0⟩ +  ((1-i)/2) |1⟩