Quantum Computing [W]
1. Resources

2. Notation and Terminology
1. Complex conjugate
The complex conjugate of x is x*
If x = a + bi, then x* = a − bi
Thus xx* = x*x = a2 + b2
If A is a matrix, A* is the matrix of the complex conjugates of the elements of A (see below)
The transpose of matrix A is AT
The conjugate transpose of A is A (A dagger)
If A = A, A is a Hermitian matrix
$If A = [ A11 ⋯ A1n ⋮ ⋱ ⋮ Am1 ⋯ Amn ] , then A* = [ A11* ⋯ A1n* ⋮ ⋱ ⋮ Am1* ⋯ Amn* ] and AT = [ A11 ⋯ Am1 ⋮ ⋱ ⋮ A1n ⋯ Amn ]$
$And A† = (AT)* = (A*)T = [ A11* ⋯ Am1* ⋮ ⋱ ⋮ A1n* ⋯ Amn* ] and Aij* = Aji†$
3. Unitary matrix
A square matrix U is unitary if its conjugate transpose U is also its inverse, i.e. UU = UU = I (the identity matrix)
4. Norm (or length)
$If x = a + bi, then |x| = a2 + b2$
$Thus |x|2 = a2 + b2 = x ⁢ x* = x* ⁢ x$
$If v = [ v1 v2 ⋮ vn ] = [ a1+b1i a2+b2i ⋮ an+bni ]$
$Then ‖v‖ = |v1|2 + |v2|2 + ⋯ + |vn|2$
5. Dirac notation (aka bra-ket notation)
1. The ket
$| v ⟩ = [ v1 v2 ⋮ vn ]$
2. The bra
$⟨ v | = | v ⟩ † = [ v1* v2* ⋯ vn* ]$
$⟨ A | B ⟩ = | A ⟩ † ⁢ | B ⟩ = [ A1* A2* ⋯ An* ] ⁢ [ B1 B2 ⋮ Bn ]$
$⟨ v | v ⟩ = [ v1* v2* ⋯ vn* ] ⁢ [ v1 v2 ⋮ vn ] = v1* ⁢ v1* + v2* ⁢ v2* + ⋯ + vn* ⁢ vn* = |v1|2 + |v2|2 + ⋯ + |vn|2 = ‖v‖2$
6. State of a single qubit
The state of a qubit can be represented with a 2-dimensional complex vector, i.e. a vector v with two components v0 and v1, each of which can be a complex number.
The components v0 and v1 are probability amplitudes such that |v0|2 is the probability that the qubit, when measured, will be in the 0 state, and |v1|2 is the probability that the qubit, when measured, will be in the 1 state. The probabilities must add up to 1, i.e. |v0|2 + |v1|2 = ||v||2 = 1
7. State of an n-qubit system
The state of an n-qubit system can be represented with a 2n-dimensional complex vector.
If we have one qubit represented by vector v and another qubit represented by vector w, the state of the 2-qubit system can be represented by v ⊗ w where ⊗ is the Kronecker product.
In general, if we have n qubits Q1, Q2, ... Qn, we can represent the state of the n-qubit system with Q1 ⊗ Q2 ⊗ ... ⊗ Qn
The first component of the resulting vector is the probability amplitude for the state in which all n qubits are 0.
The second component is the probability amplitude for the state in which Q1 thru Qn-1 are 0 and Qn is 1.
The last component is the probablity amplitude for the state in which all n qubits are 1.
In general, the j'th component (1 ≤ j ≤ 2n) is the probablity amplitude for the state in which each Qi (1 ≤ i ≤ n) is the i'th most significant bit of (j - 1) if the latter were represented as an n-digit binary number.
8. Changing the state of an n-qubit system
The state of an n-qubit system can be changed by applying a sequence of one or more gates, represented by unitary matrices, to one or more of the qubits. An n-qubit gate (or any transformation of an n-qubit system) is represented by a 2n x 2n unitary matrix. The transformation matrix must be unitary because only then is the norm of the state vector (and the requirement that the probabilities add up to 1) preserved.
Matrices acting on different subsets of qubits can be combined using the Kronecker product to generate a 2n x 2n matrix with which the n-qubit state vector (which has 2n components) can be multiplied to determine the state of the n-qubit system. The identity matrix can be used to represent a transformation that leaves a qubit unchanged.

3. Superdense coding
1. Preparing the Bell state
1. Start with two qubits, q1 and q2, both set to 0.
$Initial state Ψ0 = |00⟩ = |0⟩ ⊗ |0⟩ = [ 1 0 ] ⊗ [ 1 0 ] = [ 1 0 0 0 ]$
2. Apply a Hadamard gate (H) to q1; leave q2 unchanged.
$H ⊗ I = 12 ⁢ [ 11 1-1 ] ⊗ [ 10 01 ] = 12 ⁢ [ 1 [ 10 01 ] 1 [ 10 01 ] 1 [ 10 01 ] -1 [ 10 01 ] ] = 12 ⁢ [ 10 1 0 01 0 1 10-1 0 01 0-1 ]$
3. Apply a controlled NOT gate (CNOT) to both bits, with q1 as the control bit.
$CNOT ⁢ ( H ⊗ I ) = 12 ⁢ [ 1000 0100 0001 0010 ] ⁢ [ 10 1 0 01 0 1 10-1 0 01 0-1 ] = 12 ⁢ [ 10 1 0 01 0 1 01 0-1 10-1 0 ]$
4. Now q1 and q2 are entangled in the Bell state |Φ+
$( CNOT ⁢ ( H ⊗ I ) ) ⁢ Ψ0 = 12 ⁢ [ 10 1 0 01 0 1 01 0-1 10-1 0 ] ⁢ [ 1 0 0 0 ] = 12 ⁢ [ 1 0 0 1 ] = | 0 0 ⟩ + | 1 1 ⟩ 2 = Bell state | Φ+ ⟩$
5. q1 is sent to Alice, and q2 is sent to Bob.
2. Encoding the data to be sent
1. Alice encodes 00 by leaving q1 unchanged.
The state of the system is unchanged: (I ⊗ I) Φ+ = Φ+
$B00 = ( I ⊗ I ) ⁢ Φ+ = 12 ⁢ [ 1 0 0 1 ] = | 0 0 ⟩ + | 1 1 ⟩ 2 = | Φ+ ⟩$
2. Alice encodes 01 by applying the X gate to q1
The state of the system becomes (X ⊗ I) Φ+ = Ψ+
$B01 = ( X ⊗ I ) ⁢ Φ+ = ( [ 01 10 ] ⊗ [ 10 01 ] ) ⁢ Φ+ = [ 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 ] ⁢ 12 ⁢ [ 1 0 0 1 ] = 12 ⁢ [ 0 1 1 0 ] = | 0 1 ⟩ + | 1 0 ⟩ 2 = | Ψ+ ⟩$
3. Alice encodes 10 by applying the Z gate to q1
The state of the system becomes (Z ⊗ I) Φ+ = Φ-
$B10 = ( Z ⊗ I ) ⁢ Φ+ = ( [ 10 0-1 ] ⊗ [ 10 01 ] ) ⁢ Φ+ = [ 1 0 0 0 0 1 0 0 0 0-1 0 0 0 0-1 ] ⁢ 12 ⁢ [ 1 0 0 1 ] = 12 ⁢ [ 1 0 0 -1 ] = | 0 0 ⟩ - | 1 1 ⟩ 2 = | Φ- ⟩$
4. Alice encodes 11 by applying the X gate followed by the Z gate on q1
The state of the system becomes ((Z X) ⊗ I) Φ+ = Ψ-
$B11 = ( ( Z ⁢ X ) ⊗ I ) ⁢ Φ+ = ( ( [ 10 0-1 ] ⁢ [ 01 10 ] ) ⊗ I ) ⁢ Φ+ = ( [ 01 -10 ] ⊗ [ 10 01 ] ) ⁢ Φ+$
$= [ 0 0 1 0 0 0 0 1 -1 0 0 0 0-1 0 0 ] ⁢ 12 ⁢ [ 1 0 0 1 ] = 12 ⁢ [ 0 1 -1 0 ] = | 0 1 ⟩ - | 1 0 ⟩ 2 = | Ψ- ⟩$
Note that (Z X) = i Y
Also note that if you instead apply the Z gate followed by the X gate like Michael Nielsen does in his video, "Superdense coding: how to send two bits using one qubit," you get the following:
$( ( X ⁢ Z ) ⊗ I ) ⁢ Φ+ = ( ( [ 01 10 ] ⁢ [ 10 0-1 ] ) ⊗ I ) ⁢ Φ+ = ( [ 0-1 10 ] ⊗ [ 10 01 ] ) ⁢ Φ+$
$= [ 0 0-1 0 0 0 0-1 1 0 0 0 0 1 0 0 ] ⁢ 12 ⁢ [ 1 0 0 1 ] = 12 ⁢ [ 0 -1 1 0 ] = | 1 0 ⟩ - | 0 1 ⟩ 2 = - | Ψ- ⟩$
5. To summarize in simplified form:
1. Classical 00 → quantum 00 + 11
2. Classical 01 → quantum 01 + 10
3. Classical 10 → quantum 00 − 11
4. Classical 11 → quantum 01 − 10
6. Alice sends q1 to Bob.
If this qubit were to be intercepted and measured by itself, no information about what Alice encoded would be learned since each of the four states of the quantum system (Bell states) has an equal probability of a measurement resulting in 0 or 1.
3. Decoding the sent data
1. Bob applies a controlled NOT gate (CNOT) to both bits, with q1 as the control bit.
2. Bob applies a Hadamard gate (H) to q1 and leaves q2 unchanged.
$( H ⊗ I ) ⁢ CNOT = 12 ⁢ [ 10 1 0 01 0 1 10-1 0 01 0-1 ] ⁢ [ 1000 0100 0001 0010 ] = 12 ⁢ [ 10 0 1 01 1 0 10 0-1 01-1 0 ]$
$= ∑ k |k⟩ ⁢ ⟨Bk| = |00⟩ ⁢ ⟨B00| + |01⟩ ⁢ ⟨B01| + |10⟩ ⁢ ⟨B10| + |11⟩ ⁢ ⟨B11|$
$Since the Bk are orthonormal, ( ∑ k |k⟩ ⁢ ⟨Bk| ) ⁢ |Bj⟩ = |j⟩ since ⟨ Bk | Bj ⟩ = 0 if k ≠ j and 1 if k = j$
3. Bob measures q1 and q2. The measurement result will be the same as whatever Alice encoded.

4. Quantum teleportation
1. Prepare two qubits QA and QB in the Bell state (same as the first step of the superdense coding protocol).
2. Send QA to Alice and QB to Bob.
3. Alice has a third qubit QC in an unknown state which she will "teleport" to Bob. What she will really be doing is sending Bob two classical bits representing one of four actions Bob can perform on QB to transform it into whatever state QC was in.
4. Initial state of the 3-qubit system (after QA and QB have been prepared in the Bell state Φ+):
$Ψ0 = QC ⊗ Φ+ = [ a b ] ⊗ 12 ⁢ [ 1 0 0 1 ] = 12 ⁢ [ a 0 0 a b 0 0 b ] = ( a |0⟩ + b |1⟩ ) ⁢ ( |00⟩ + |11⟩ 2 ) = 12 ⁢ ( a⁢|000⟩ + a⁢|011⟩ + b⁢|100⟩ + b⁢|111⟩ )$
5. Alice applies the same gates that Bob did in the last step of the superdense coding protocol. She applies a controlled NOT gate (CNOT) to QC and QA, with QC as the control bit. Then she applies a Hadamard gate (H) to QC.

The state of the 3-qubit system is now the following:
$ΨA = ( ( (H⊗I) ⁢ CNOT ) ⊗ I ) ⁢ Ψ0 = ( 12 ⁢ [ 10 0 1 01 1 0 10 0-1 01-1 0 ] ⊗ [ 10 01 ] ) ⁢ Ψ0$
$= 12 ⁢ [ 1000 0010 0100 0001 0010 1000 0001 0100 1000 00-10 0100 000-1 0010 -1000 0001 0-100 ] ⁢ 12 ⁢ [ a 0 0 a b 0 0 b ] = 12 ⁢ [ a b b a a -b -b a ]$
$= 12 ⁢ ( a⁢|000⟩+ b⁢|001⟩+ b⁢|010⟩+ a⁢|011⟩+ a⁢|100⟩- b⁢|101⟩- b⁢|110⟩+ a⁢|111⟩ )$
$= |00⟩ ⁢ ( a⁢|0⟩+ b⁢|1⟩ 2 ) + |01⟩ ⁢ ( b⁢|0⟩+ a⁢|1⟩ 2 ) + |10⟩ ⁢ ( a⁢|0⟩- b⁢|1⟩ 2 ) + |11⟩ ⁢ ( - b⁢|0⟩+ a⁢|1⟩ 2 )$
6. Now Alice measures QC and QA and sends the result (two classical bits) to Bob.
7. If Bob receives 00, his qubit QB must be in the following state (note that |a|2 + |b|2 = 1):
$( a⁢|0⟩+ b⁢|1⟩ 2 ) ‖ a⁢|0⟩+ b⁢|1⟩ 2 ‖ = ( a⁢|0⟩+ b⁢|1⟩ 2 ) |a2|2 + |b2|2 = ( a⁢|0⟩+ b⁢|1⟩ 2 ) |a|2 + |b|2 4 = ( a⁢|0⟩+ b⁢|1⟩ 2 ) 12 ⁢ |a|2 + |b|2 = a⁢|0⟩+ b⁢|1⟩ |a|2 + |b|2 = a⁢|0⟩+ b⁢|1⟩ = [ a b ]$

This is the same as the initial state of Alice's qubit QC — so Bob leaves QB unchanged (or applies the identity matrix I).
8. Similarly, if Bob receives 01, QB is in the state b|0⟩ + a|1⟩
He can apply the X gate to QB to transform its state into the initial state of QC
$X ⁢ [ b a ] = [ 01 10 ] ⁢ [ b a ] = [ a b ]$
9. If Bob receives 10, QB is in the state a|0⟩ − b|1⟩
He can apply the Z gate to QB to transform its state into the initial state of QC
$Z ⁢ [ a -b ] = [ 10 0-1 ] ⁢ [ a -b ] = [ a b ]$
10. Finally, if Bob receives 11, QB is in the state −b|0⟩ + a|1⟩
He can apply the X gate followed by the Z gate to transform the state of QB into the initial state of QC
$( Z ⁢ X ) ⁢ [ -b a ] = ( [ 10 0-1 ] ⁢ [ 01 10 ] ) ⁢ [ -b a ] = [ 01 -10 ] ⁢ [ -b a ] = [ a b ]$

5. Algorithms
1. Quantum Fourier transform [W]
2. Grover's algorithm [W]
3. Shor's algorithm [W]

6. Code
Superdense coding and quantum teleportation can be expressed in terms of the same three higher-level functions prepareBell(), encodeBell(), and measureBell():
1. Superdense coding (see qc.py)
 prepareBell(qA, qB) encodeBell(a1, a2, qA) # Alice b1, b2 = measureBell(qA, qB) # Bob 
2. Quantum teleportation (see qc.py)
 prepareBell(qA, qB) b1, b2 = measureBell(qC, qA) # Alice encodeBell(b1, b2, qB) #Bob 
3. See qc.py for more details.