Quantum Computing [W]

• Table of Contents
  1. Resources
  2. Notation and Terminology
  3. Superdense coding
  4. Quantum teleportation
  5. Algorithms
  6. Code

1. Resources
   • Scott Aaronson [W] (MIT)
     • Quantum Computing since Democritus (Apr 2013)
   • Matthew Hayward
     • Quantum Algorithms - Quantum Computing and Shor's Algorithm (1999 - 2015)
   • David Mermin [W] (Cornell)
     • Quantum Computer Science (Sep 2007)
   • Michael Nielsen [W, YouTube]
     • Quantum Computation and Quantum Information, 10th Anniversary Edition (Jan 2011)
     • Quantum Computing for the Determined [YouTube] (Nov 22 - Dec 22, 2010)
   • John Preskill [W] (Caltech)
     • Quantum Computation Course Lecture Notes
     • @ Institute for Quantum Computing [YouTube]
   • Eleanor Rieffel [W] (NASA QuAIL [W])
     • An Introduction to Quantum Computing for Non-Physicists (Jan 2000)
     • Quantum Computing: A Gentle Introduction (Mar 2011 hardcover & Aug 2014 paperback)
       [Google Books, MIT Press, Wikidot]
   • Peter Shor [W] (MIT)
     • @ Physics Stack Exchange
   • Leonard Susskind [W] (Stanford)
     • Quantum Entanglement Course [iTunes, YouTube] (Fall 2006)
   • Umesh Vazirani [W] (UC Berkeley)
     • Quantum Mechanics and Quantum Computation (edX course)
   
   
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 = a² + b²
      If A is a matrix, A^* is the matrix of the complex conjugates of the elements of A (see below)
   2. Conjugate transpose (or adjoint)
      The transpose of matrix A is A^T
      The conjugate transpose of A is A^† (A dagger)
      If A = A^†, A is a Hermitian matrix
      $\text{If}A=\left[\begin{array}{ccc}{A}_{11}& \cdots & A_{1n}\\ ⋮& \ddots & ⋮\\ A_{m1}& \cdots & A_{mn}\end{array}\right]\text{, then}{A}^{*}=\left[\begin{array}{ccc}{A}_{11}^{*}& \cdots & A_{1n}^{*}\\ ⋮& \ddots & ⋮\\ A_{m1}^{*}& \cdots & A_{mn}^{*}\end{array}\right]\text{and}{A}^T=\left[\begin{array}{ccc}{A}_{11}& \cdots & A_{m1}\\ ⋮& \ddots & ⋮\\ A_{1n}& \cdots & A_{mn}\end{array}\right]$
      $\text{And}{A}^{†}={\left(A^T\right)}^{*}={\left(A^{*}\right)}^T=\left[\begin{array}{ccc}{A}_{11}^{*}& \cdots & A_{m1}^{*}\\ ⋮& \ddots & ⋮\\ A_{1n}^{*}& \cdots & A_{mn}^{*}\end{array}\right]\text{and}{A}_{ij}^{*}=A_{ji}^{†}$
   3. Unitary matrix
      A square matrix U is unitary if its conjugate transpose U^† is also its inverse, i.e. UU^† = U^†U = I (the identity matrix)
   4. Norm (or length)
      $\text{If x = a + bi, then}\left|x\right|=\sqrt{a^2+b^2}$
      $\text{Thus}{\left|x\right|}^2=a^2+b^2=x{x}^{*}=x^{*}x$
      $\text{If}v=\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right]=\left[\begin{array}{c}{a}_1+b_{1}i\\ a_2+b_{2}i\\ ⋮\\ a_n+b_{n}i\end{array}\right]$
      $\text{Then}\Vert v\Vert =\sqrt{{\left|v_1\right|}^2+{\left|v_2\right|}^2+\cdots +{\left|v_n\right|}^2}$
   5. Dirac notation (aka bra-ket notation)
      1. The ket
         $|v⟩=\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right]$
      2. The bra
         $⟨v|={|v⟩}^{†}=\left[\begin{array}{cccc}{v}_1^{*}& v_2^{*}& \cdots & v_n^{*}\end{array}\right]$
         $⟨A|B⟩={|A⟩}^{†}|B⟩=\left[\begin{array}{cccc}{A}_1^{*}& A_2^{*}& \cdots & A_n^{*}\end{array}\right]\left[\begin{array}{c}{B}_1\\ B_2\\ ⋮\\ B_n\end{array}\right]$
         $⟨v|v⟩=\left[\begin{array}{cccc}{v}_1^{*}& v_2^{*}& \cdots & v_n^{*}\end{array}\right]\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right]=v_1^{*}{v}_1^{\phantom{*}}+v_2^{*}{v}_2^{\phantom{*}}+\cdots +v_n^{*}{v}_n^{\phantom{*}}={\left|v_1\right|}^2+{\left|v_2\right|}^2+\cdots +{\left|v_n\right|}^2={\Vert v\Vert }^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 v₀ and v₁, each of which can be a complex number.
      The components v₀ and v₁ are probability amplitudes such that |v₀|² is the probability that the qubit, when measured, will be in the 0 state, and |v₁|² is the probability that the qubit, when measured, will be in the 1 state. The probabilities must add up to 1, i.e. |v₀|² + |v₁|² = ||v||² = 1
   7. State of an n-qubit system
      The state of an n-qubit system can be represented with a 2ⁿ-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 Q₁, Q₂, ... Q_n, we can represent the state of the n-qubit system with Q₁ ⊗ Q₂ ⊗ ... ⊗ Q_n
      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 Q₁ thru Q_n-1 are 0 and Q_n 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 ≤ 2ⁿ) is the probablity amplitude for the state in which each Q_i (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 2ⁿ x 2ⁿ 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 2ⁿ x 2ⁿ matrix with which the n-qubit state vector (which has 2ⁿ 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, q₁ and q₂, both set to 0.
         $\text{Initial state}{\Psi }_0=|\mathrm{00}⟩=|0⟩\otimes |0⟩=\left[\begin{array}{c}1\\ 0\end{array}\right]\otimes \left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]$
      2. Apply a Hadamard gate (H) to q₁; leave q₂ unchanged.
         $H\otimes I=\frac{1}{\sqrt{2}}\left[\begin{array}{rr}1& 1\\ 1& -1\end{array}\right]\otimes \left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{rr}1\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]& 1\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\\ 1\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]& -1\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{rrrr}1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& -1& 0\\ 0& 1& 0& -1\end{array}\right]$
      3. Apply a controlled NOT gate (CNOT) to both bits, with q₁ as the control bit.
         $\mathrm{CNOT}(H\otimes I)=\frac{1}{\sqrt{2}}\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\left[\begin{array}{rrrr}1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& -1& 0\\ 0& 1& 0& -1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{rrrr}1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 1& 0& -1\\ 1& 0& -1& 0\end{array}\right]$
      4. Now q₁ and q₂ are entangled in the Bell state |Φ⁺⟩
         $(\mathrm{CNOT}(H\otimes I\left)\right){\Psi }_0=\frac{1}{\sqrt{2}}\left[\begin{array}{rrrr}1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 1& 0& -1\\ 1& 0& -1& 0\end{array}\right]\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{|00⟩+|11⟩}{\sqrt{2}}=\text{Bell state}|{\Phi }^{+}⟩$
      5. q₁ is sent to Alice, and q₂ is sent to Bob.
   2. Encoding the data to be sent
      1. Alice encodes 00 by leaving q₁ unchanged.
         The state of the system is unchanged: (I ⊗ I) Φ⁺ = Φ⁺
         $B_{00}=(I\otimes I){\Phi }^{+}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{|00⟩+|11⟩}{\sqrt{2}}=|{\Phi }^{+}⟩$
      2. Alice encodes 01 by applying the X gate to q₁
         The state of the system becomes (X ⊗ I) Φ⁺ = Ψ⁺
         $B_{01}=(X\otimes I){\Phi }^{+}=\left(\right[\begin{array}{cc}0& 1\\ 1& 0\end{array}]\otimes [\begin{array}{cc}1& 0\\ 0& 1\end{array}\left]\right){\Phi }^{+}=\left[\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}0\\ 1\\ 1\\ 0\end{array}\right]=\frac{|01⟩+|10⟩}{\sqrt{2}}=|{\Psi }^{+}⟩$
      3. Alice encodes 10 by applying the Z gate to q₁
         The state of the system becomes (Z ⊗ I) Φ⁺ = Φ^-
         $B_{10}=(Z\otimes I){\Phi }^{+}=\left(\right[\begin{array}{rr}1& 0\\ 0& -1\end{array}]\otimes [\begin{array}{cc}1& 0\\ 0& 1\end{array}\left]\right){\Phi }^{+}=\left[\begin{array}{rrrr}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& -1& 0\\ 0& 0& 0& -1\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{r}1\\ 0\\ 0\\ -1\end{array}\right]=\frac{|00⟩-|11⟩}{\sqrt{2}}=|{\Phi }^{-}⟩$
      4. Alice encodes 11 by applying the X gate followed by the Z gate on q₁
         The state of the system becomes ((Z X) ⊗ I) Φ⁺ = Ψ^-
         $B_{11}=\left(\right(ZX)\otimes I){\Phi }^{+}=\left(\right(\left[\begin{array}{rr}1& 0\\ 0& -1\end{array}\right]\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right])\otimes I){\Phi }^{+}=\left(\right[\begin{array}{rr}0& 1\\ -1& 0\end{array}]\otimes [\begin{array}{cc}1& 0\\ 0& 1\end{array}\left]\right){\Phi }^{+}$
         $=\left[\begin{array}{rrrr}0& 0& 1& 0\\ 0& 0& 0& 1\\ -1& 0& 0& 0\\ 0& -1& 0& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{r}0\\ 1\\ -1\\ 0\end{array}\right]=\frac{|01⟩-|10⟩}{\sqrt{2}}=|{\Psi }^{-}⟩$
         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:
         $\left(\right(XZ)\otimes I){\Phi }^{+}=\left(\right(\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\left[\begin{array}{rr}1& 0\\ 0& -1\end{array}\right])\otimes I){\Phi }^{+}=\left(\right[\begin{array}{rr}0& -1\\ 1& 0\end{array}]\otimes [\begin{array}{cc}1& 0\\ 0& 1\end{array}\left]\right){\Phi }^{+}$
         $=\left[\begin{array}{rrrr}0& 0& -1& 0\\ 0& 0& 0& -1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{r}0\\ -1\\ 1\\ 0\end{array}\right]=\frac{|10⟩-|01⟩}{\sqrt{2}}=-|{\Psi }^{-}⟩$
      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 q₁ 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 q₁ as the control bit.
      2. Bob applies a Hadamard gate (H) to q₁ and leaves q₂ unchanged.
         $(H\otimes I)\mathrm{CNOT}=\frac{1}{\sqrt{2}}\left[\begin{array}{rrrr}1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& -1& 0\\ 0& 1& 0& -1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{rrrr}1& 0& 0& 1\\ 0& 1& 1& 0\\ 1& 0& 0& -1\\ 0& 1& -1& 0\end{array}\right]$
         $=\sum _k|k⟩⟨B_k|=|00⟩⟨B_{00}|+|01⟩⟨B_{01}|+|10⟩⟨B_{10}|+|11⟩⟨B_{11}|$
         $\text{Since the}{B}_k\text{are}\text{orthonormal}\text{,}\left(\sum _k|k⟩⟨B_k|\right)|B_j⟩=|j⟩\text{since}⟨B_k|B_j⟩=\text{0 if k ≠ j and 1 if k = j}$
      3. Bob measures q₁ and q₂. The measurement result will be the same as whatever Alice encoded.
   
   
4. Quantum teleportation
   1. Prepare two qubits Q_A and Q_B in the Bell state (same as the first step of the superdense coding protocol).
   2. Send Q_A to Alice and Q_B to Bob.
   3. Alice has a third qubit Q_C 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 Q_B to transform it into whatever state Q_C was in.
   4. Initial state of the 3-qubit system (after Q_A and Q_B have been prepared in the Bell state Φ⁺):
      ${\Psi }_0=Q_C\otimes {\Phi }^{+}=\left[\begin{array}{c}a\\ b\end{array}\right]\otimes \frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}a\\ 0\\ 0\\ a\\ b\\ 0\\ 0\\ b\end{array}\right]=(a|0⟩+b|1⟩)\left(\frac{|\mathrm{00}⟩+|\mathrm{11}⟩}{\sqrt{2}}\right)=\frac{1}{\sqrt{2}}(a|\mathrm{000}⟩+a|\mathrm{011}⟩+b|\mathrm{100}⟩+b|\mathrm{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 Q_C and Q_A, with Q_C as the control bit. Then she applies a Hadamard gate (H) to Q_C.
      
      The state of the 3-qubit system is now the following:
      ${\Psi }_A=\left(\right((H\otimes I)\mathrm{CNOT})\otimes I){\Psi }_0=(\frac{1}{\sqrt{2}}\left[\begin{array}{rrrr}1& 0& 0& 1\\ 0& 1& 1& 0\\ 1& 0& 0& -1\\ 0& 1& -1& 0\end{array}\right]\otimes \left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]){\Psi }_0$
      $=\frac{1}{\sqrt{2}}\left[\begin{array}{rrrrrrrr}1& 0& 0& 0& 0& 0& 1& 0\\ 0& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& -1& 0\\ 0& 1& 0& 0& 0& 0& 0& -1\\ 0& 0& 1& 0& -1& 0& 0& 0\\ 0& 0& 0& 1& 0& -1& 0& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}\mathrm{a}\\ 0\\ 0\\ \mathrm{a}\\ \mathrm{b}\\ 0\\ 0\\ \mathrm{b}\end{array}\right]=\frac{1}{2}\left[\begin{array}{r}\mathrm{a}\\ \mathrm{b}\\ \mathrm{b}\\ \mathrm{a}\\ \mathrm{a}\\ \mathrm{-b}\\ \mathrm{-b}\\ \mathrm{a}\end{array}\right]$
      $=\frac{1}{2}(a|\mathrm{000}⟩+b|\mathrm{001}⟩+b|\mathrm{010}⟩+a|\mathrm{011}⟩+a|\mathrm{100}⟩-b|\mathrm{101}⟩-b|\mathrm{110}⟩+a|\mathrm{111}⟩)$
      $=|\mathrm{00}⟩\left(\frac{a|0⟩+b|1⟩}{2}\right)+|\mathrm{01}⟩\left(\frac{b|0⟩+a|1⟩}{2}\right)+|\mathrm{10}⟩\left(\frac{a|0⟩-b|1⟩}{2}\right)+|\mathrm{11}⟩\left(\frac{-b|0⟩+a|1⟩}{2}\right)$
   6. Now Alice measures Q_C and Q_A and sends the result (two classical bits) to Bob.
   7. If Bob receives 00, his qubit Q_B must be in the following state (note that |a|² + |b|² = 1):
      $\frac{\left(\frac{a|0⟩+b|1⟩}{2}\right)}{\Vert \frac{a|0⟩+b|1⟩}{2}\Vert }=\frac{\left(\frac{a|0⟩+b|1⟩}{2}\right)}{\sqrt{{\left|\frac{a}{2}\right|}^2+{\left|\frac{b}{2}\right|}^2}}=\frac{\left(\frac{a|0⟩+b|1⟩}{2}\right)}{\sqrt{\frac{{\left|a\right|}^2+{\left|b\right|}^2}{4}}}=\frac{\left(\frac{a|0⟩+b|1⟩}{2}\right)}{\frac{1}{2}\sqrt{{\left|a\right|}^2+{\left|b\right|}^2}}=\frac{a|0⟩+b|1⟩}{\sqrt{{\left|a\right|}^2+{\left|b\right|}^2}}=a|0⟩+b|1⟩=\left[\begin{array}{c}a\\ b\end{array}\right]$
      
      This is the same as the initial state of Alice's qubit Q_C — so Bob leaves Q_B unchanged (or applies the identity matrix I).
   8. Similarly, if Bob receives 01, Q_B is in the state b|0⟩ + a|1⟩
      He can apply the X gate to Q_B to transform its state into the initial state of Q_C
      $X\left[\begin{array}{c}b\\ a\end{array}\right]=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}b\\ a\end{array}\right]=\left[\begin{array}{c}a\\ b\end{array}\right]$
   9. If Bob receives 10, Q_B is in the state a|0⟩ − b|1⟩
      He can apply the Z gate to Q_B to transform its state into the initial state of Q_C
      $Z\left[\begin{array}{r}\mathrm{a}\\ \mathrm{-b}\end{array}\right]=\left[\begin{array}{rr}1& 0\\ 0& -1\end{array}\right]\left[\begin{array}{r}\mathrm{a}\\ \mathrm{-b}\end{array}\right]=\left[\begin{array}{c}a\\ b\end{array}\right]$
   10. Finally, if Bob receives 11, Q_B is in the state −b|0⟩ + a|1⟩
       He can apply the X gate followed by the Z gate to transform the state of Q_B into the initial state of Q_C
       $(ZX)\left[\begin{array}{r}\mathrm{-b}\\ \mathrm{a}\end{array}\right]=(\left[\begin{array}{rr}1& 0\\ 0& -1\end{array}\right]\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right])\left[\begin{array}{r}\mathrm{-b}\\ \mathrm{a}\end{array}\right]=\left[\begin{array}{rr}0& 1\\ -1& 0\end{array}\right]\left[\begin{array}{r}\mathrm{-b}\\ \mathrm{a}\end{array}\right]=\left[\begin{array}{c}a\\ b\end{array}\right]$
   
   
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.