1.10: Quantum Computation- A Short Course
- Page ID
- 137734
The last several tutorials were a bit off the theme of quantum computation. We get back on track with a look at data base searching the quantum way, or the best way to find a needle in a hay stack. This is followed by a demonstration of Simon’s algorithm, an illustration of quantum dense coding and an example of quantum error correction.
Grover Search Algorithm Implementation for Two Items
Chris Monroe's research group recently published an experimental implementation of the Grover search algorithm in Nature Communications 8, 1918 (2017). In this report the Grover search is implemented for N = 3 using the three qubit quantum circuit shown below. In this particular example it is demonstrated that the search algorithm successfully searches for two items in one operation of the circuit. The lead sentence in the paper states "The Grover search algorithm has four stages: initialization (red), oracle (green), amplification (blue) and measurement (black)."
\[\begin{matrix} |0 \rangle & \rhd & \text{H} & \lceil & \; & \rceil & \text{H} & \text{X} & \cdot & \text{X} & \text{H} & \rhd & \text{Measure} \\ \; & \; & \; & | & \; & | & \; & \; & | & \; & \; & \; & \; \\ |0 \rangle & \rhd & \text{H} & | & \text{Oracle} & | & \text{H} & \text{X} & | & \text{X} & \text{H} & \rhd & \text{Measure} \\ \; & \; & \; & | & \; & | & \; & \; & | & \; & \; & \; & \; \\ |0 \rangle & \rhd & \text{H} & \lfloor & \; & \rfloor & \text{H} & \text{X} & \text{Z} & \text{X} & \text{H} & \rhd & \text{Measure} \end{matrix} \nonumber \]
The oracle, highlighted below, contains 3 (|011>) and 5 (|101>).
\[
\mathrm{H} :=\frac{1}{\sqrt{2}} \left( \begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) \qquad \mathrm{X} :=\left( \begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right) \\ \text{Oracle}=\left( \begin{array}{llllllll}{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} \\ {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} & {0} & {0} & {0} & {0} & {1}\end{array}\right) \\ \mathrm{CCZ} :=\left( \begin{array}{ccccccc}{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} \\ {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} & {0} & {0} & {0} & {0} & {-1}\end{array}\right)
\nonumber \]
\[
\mathrm{HHH} :=\mathrm{kronecker}(\mathrm{H}, \mathrm{kronecker}(\mathrm{H}, \mathrm{H})) \qquad \mathrm{XXX} :=\text { kronccker }(\mathrm{X}, \text { kronecker }(\mathrm{X}, \mathrm{X}))
\nonumber \]
The initial Hadamard gates on the three circuit wires feed the Grover search algorithm (in blue) a superposition of all possible queries yielding a superposition of the correct answers.
\[\text{GroverSearch} : = \text{HHH} \cdot \text{XXX} \cdot \text{CCZ} \cdot \text{XXX} \cdot \text{HHH} \cdot \text{Oracle} \cdot \text{HHH} \qquad \text{GroverSearch}\cdot \left( \begin{array}{c}{1} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {0} \\ {-0.707} \\ {0} \\ {-0.707} \\ {0} \\ {0}\end{array}\right)=-\frac{1}{\sqrt{2}}[ |011\rangle+| 101 \rangle ] \nonumber \]
Aspects of Simon's Algorithm
A concealed quantum algorithm calculates f(x) from an input register containing a superposition of all x-values. Pairs of x-values (x,x') generate the same output. Simon's algorithm is an efficient method for finding the relationship between the pairs: \(f(x) = f(x^{'}) = f(x \oplus s)\), where s is a secret string and the addition on the right is bitwise modulo 2 . In a classical calculation one could compute f(x) until some pattern emerged and find the pairs by inspection. This approach is illustrated below.
\[\begin{matrix} \text{Decimal} & \text{Binary} & \; & \text{Binary} & \text{Decimal} \\ |0 \rangle & | 000 \rangle & \xrightarrow{f(0)} & | 011 \rangle & | 3 \rangle \\ |1 \rangle & | 001 \rangle & \xrightarrow{f(1)} & | 001 \rangle & | 1 \rangle \\ |2 \rangle & | 010 \rangle & \xrightarrow{f(2)} & | 010 \rangle & | 2 \rangle \\ |3 \rangle & | 011 \rangle & \xrightarrow{f(3)} & | 000 \rangle & | 0 \rangle \\ |4 \rangle & | 100 \rangle & \xrightarrow{f(4)} & | 001 \rangle & | 1 \rangle \\ |5\rangle & | 101 \rangle & \xrightarrow{f(5)} & | 011 \rangle & | 3 \rangle \\ |5 \rangle & | 101 \rangle & \xrightarrow{f(5)} & | 011 \rangle & | 3 \rangle \\ |6 \rangle & | 110 \rangle & \xrightarrow{f(6)} & | 000 \rangle & | 0 \rangle \\ |7 \rangle & | 111 \rangle & \xrightarrow{f(7)} & | 010 \rangle & | 2 \rangle \end{matrix} \nonumber \]
The table of results reveals the pairs {(0,5), (1,4), (2,7), (3,6)} and that |s> = |101>. Adding |s> bitwise modulo 2 to any |x> reveals its partner |x'>.
The following quantum circuit is a rudimentary implementation of Simon's algorithm. The section in blue is the concealed algorithm. It has been discussed in two other tutorials: Quantum Parallel Calculation and An Illustration of the Deutsch-Jozsa Algorithm. Its operation yields the results shown in the following table.
\[
\left( \begin{array}{ccccc}{x} & {0} & {1} & {2} & {3} \\ {f(x)} & {1} & {0} & {0} & {1}\end{array}\right)
\nonumber \]
\[\begin{matrix} \text{Initial} & \; & 1 & \; & 2 & \; & 3 & \; & 4 & \; & 5 & \; & \text{Final} \\ | 0 \rangle & \rhd & H & \cdots & \cdot & \cdots & \cdots & \cdots & \cdots & \cdots & H & \rhd & \; \\ \; & \; & \; & \; & | & \; & \; & \; & \; & \; & \; \\ | 0 \rangle & \rhd & H & \cdots & | & \cdots & \cdot & \cdots & \cdots & \cdots & H & \rhd & \; \\ \; & \; & \; & \; & | & \; & | & \; & \; & \; & \; \\ | 0 \rangle & \rhd & \cdots & \cdots & \oplus & \cdots & \oplus & \cdots & \text{NOT} & \cdots & \cdots & \rhd & \text{Measure, 0 or 1} \end{matrix} \nonumber \]
Next we prepare a table showing the results of a classical calculation. It is clear that the pairs are (0,3) and (1,2), and that |s> = |11>.
\[\begin{matrix} \text{Decimal} & \text{Binary} & \; & \text{Binary} & \text{Decimal} \\ |0 \rangle & | 000 \rangle & \xrightarrow{f(0)} & | 011 \rangle & | 3 \rangle \\ |1 \rangle & | 001 \rangle & \xrightarrow{f(1)} & | 001 \rangle & | 1 \rangle \\ |2 \rangle & | 010 \rangle & \xrightarrow{f(2)} & | 010 \rangle & | 2 \rangle \\ |3 \rangle & | 011 \rangle & \xrightarrow{f(3)} & | 000 \rangle & | 0 \rangle \end{matrix} \nonumber \]
Now we examine the operation of the quantum circuit that implements Simon's algoritm by two different, but equivalent methods. The matrices representing the quantum gates in the circuit are:
\[
\mathrm{I} :=\left( \begin{array}{cc}{1} & {0} \\ {0} & {1}\end{array}\right) \qquad \mathrm{NOT} :=\left( \begin{array}{cc}{0} & {1} \\ {1} & {0}\end{array}\right) \qquad \mathrm{H} :=\frac{1}{\sqrt{2}} \cdot \left( \begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) \\ \mathrm{CNOT} :=\left( \begin{array}{llll}{1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} \\ {0} & {0} & {1} & {0}\end{array}\right) \\ \mathrm{CnNOT} :=\left( \begin{array}{cccccccc}{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} \\ {0} & {0} & {0} & {0} & {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0}\end{array}\right)
\nonumber \]
The three qubit input state is:
\[
\Psi_{\mathrm{in}} :=\left( \begin{array}{llllllll}{1} & {0} & {0} & {0} & {0} & {0} & {0} & {0}\end{array}\right)^{\mathrm{T}}
\nonumber \]
The concealed algorithm:
\[U_{f} : = \text{kronecker}(\text{I, kronecker(I, NOT))} \cdot \text{kronecker(I, CNOT)} \cdot \text{CnNOT} \nonumber \]
The complete quantum circuit:
\[\text{QuantumCircuit} : = \text{kronecker(H, kronecker(H, I))} \cdot U_{f} \cdot \text{kronecker(H, kronecker(H, I))} \nonumber \]
The operation of the quantum circuit on the input state yields the following result:
\[
\begin{split} \text{QuantumCircuit}\cdot\Psi_{\text { in }}&=\left( \begin{array}{c}{0.5} \\ {0.5} \\ {0} \\ {0} \\ {0} \\ {0} \\ {-0.5} \\ {0.5}\end{array}\right) \\ &= \frac{1}{2}\left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \otimes \left( \begin{array}{l}{1} \\ {0}\end{array}\right)-\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{0} \\ {1}\end{array}\right)\right] \left( \begin{array}{l}{1} \\ {0}\end{array}\right)+\frac{1}{2}\left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \otimes \left( \begin{array}{l}{1} \\ {0}\end{array}\right)+\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{0} \\ {1}\end{array}\right)\right] \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \\ &= \frac{1}{2}[ |00\rangle-| 11 \rangle ] | 0 \rangle+\frac{1}{2}[ |00\rangle+| 11 \rangle ] | 1 \rangle \end{split}
\nonumber \]
The terms in brackets are superpositions of the x-values which are related by \(x^{'} = x \oplus s\). Thus we see by inspection that |s> = |11>. The actual implementation of Simon's algorithm involves multiple measurements in order to determine the secret string. The Appendix modifies the quantum circuit to include the effect of measurement on the bottom wire.
The second method of analysis uses the following truth tables for the quantum gates and the operation of the Hadamard gate to trace the evolution of the input quibits through the quantum circuit.
\[
\text { NOT } \; \begin{pmatrix} 0 & ' & 1 \\ 1 & ' & 0 \end{pmatrix} \\ \text{CNOT} \; \begin{pmatrix} \text{Decimal} & \text{Binary} & ' & \text{Binary} & \text{Decimal} \\ 0 & 00 & ' & 00 & 0 \\ 1 & 01 & ' & 01 & 1 \\ 2 & 10 & ' & 11 & 3 \\ 3 & 11 & ' & 10 & 2 \end{pmatrix} \\ \text{CnNOT} \; \begin{pmatrix} \text{Decimal} & \text{Binary} & ' & \text{Binary} & \text{Decimal} \\ 0 & 000 & ' & 000 & 0 \\ 1 & 001 & ' & 001 & 1 \\ 2 & 010 & ' & 010 & 3 \\ 3 & 011 & ' & 011 & 3 \\ 4 & 100 & ' & 101 & 5 \\ 5 & 101 & ' & 100 & 4 \\ 6 & 110 & ' & 111 & 7 \\ 7 & 111 & ' & 110 & 6 \end{pmatrix} \\ \text{Hadamard operation:}\; \left[ \begin{matrix} 0 & ' & H & ' & \frac{1}{\sqrt{2}} \cdot (0+1) & ' & H & ' & 0 \\ 1 & ' & H & ' & \frac{1}{\sqrt{2}} \cdot (0-1) & ' & H & ' & 1 \end{matrix} \right]
\nonumber \]
\[\begin{matrix} | 000 \rangle \\ \mathrm{H} \otimes \mathrm{H} \otimes \mathrm{I} \\ \frac{1}{\sqrt{2}}[ |0\rangle+| 1 \rangle ] \frac{1}{\sqrt{2}}[ |0\rangle+| 1 \rangle ] | 0 \rangle=\frac{1}{2}[ |000\rangle+| 010 \rangle+| 100 \rangle+| 110 \rangle ] \\ \mathrm{CnNOT} \\ \frac{1}{2}[ |000\rangle+| 010 \rangle+| 101 \rangle+| 111 \rangle ] \\ \mathrm{I} \otimes \mathrm{CNOT} \\ \frac{1}{2}[ |000\rangle+| 011 \rangle+| 101 \rangle+| 110 \rangle ] \\ \mathrm{I} \otimes \mathrm{I} \otimes \mathrm{NOT} \\ \frac{1}{2}[ |001\rangle+| 010 \rangle+| 100 \rangle+| 111 \rangle ] \\ \mathrm{H} \otimes \mathrm{H} \otimes \mathrm{I} \\ \frac{1}{2}[( |00\rangle-| 11\rangle ) | 0 \rangle+( |00\rangle+| 11 \rangle ) | 1 \rangle ] \end{matrix} \nonumber \]
- Appendix:
-
The circuit modification shown below includes the effect of measurement on the bottom wire.
Measure |0> on the bottom wire:
\[\text{QuantumCircuit} : = \text{kronecker} \left( \text{H, kronecker} \left[ \text{H,} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix}^{T} \right] \right) \cdot U_{f} \cdot \text{kronecker(H, kronecker(H, I))} \\ \text{QuantumCircuit}\cdot\Psi_{\text { in }}=\left( \begin{array}{c}{0.5} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {-0.5} \\ {0}\end{array}\right) \\ \left( \begin{array}{c}{0.5} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {-0.5} \\ {0}\end{array}\right)= \frac{1}{2} \cdot\left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)-\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)\right] \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \nonumber \]
Measure |1> on the bottom wire:
\[\text{QuantumCircuit} : = \text{kronecker} \left( \text{H, kronecker} \left[ \text{H,} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 1 \end{pmatrix}^{T} \right] \right) \cdot U_{f} \cdot \text{kronecker(H, kronecker(H, I))} \\ \text{QuantumCircuit}\cdot\Psi_{\text { in }}=\left( \begin{array}{c}{0} \\ {0.5} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0.5}\end{array}\right) \\ \left( \begin{array}{c}{0} \\ {0.5} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0.5}\end{array}\right)= \frac{1}{2} \cdot\left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)-\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)\right] \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \nonumber \]
Quantum Dense Coding
Quantum superdense coding reliably transmits two classical bits through an entangled pair of particles, even though only one member of the pair is handled by the sender. Charles Bennett, Physics Today, October 1995, p. 27
This tutorial is based on Brad Rubin's "Superdense Coding" at the Wolfram Demonstration Project: http:demonstrations.wolfram.com/SuperdenseCoding/. The quantum circuit shown below impliments quantum dense coding. Alice and Bob share the entangled pair of photons in the Bell basis shown at the left. Alice encodes two classical bits of information (four possible messages) on her photon, and Bob subsequently reads her message by performing a Bell state measurement on the modified entangled photon pair. In other words, although Alice encodes two bits on her photon Bob's readout requires a measurement involving both photons. In this example Alice sends |11> to Bob.
\[\begin{matrix} \cdot & \text{X}^{1} & \cdot & \text{Z}^{1} & \cdot & \cdot & H \; \\ \left( \begin{array}{c}{1 / \sqrt{2}} \\ {0} \\ {0} \\ {1 / \sqrt{2}}\end{array}\right) & \; & \left( \begin{array}{c}{0} \\ {1 / \sqrt{2}} \\ {1 / \sqrt{2}} \\ {0}\end{array}\right) & \; & \left( \begin{array}{c}{0} \\ {1 / \sqrt{2}} \\ {-1 / \sqrt{2}} \\ {0}\end{array}\right) & \begin{array}{c}{|} \\ {|} \\ {|} \\ {|}\end{array} & \; & \left( \begin{array}{c}{0} \\ {0} \\ {0} \\ {1}\end{array}\right) = \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \\ \cdot & \mathrm{I} & \cdot & \mathrm{I} & \cdot & \oplus & \mathrm{I} & \; \end{matrix} \nonumber \]
The operation of the circuit is outlined in both matrix and algebraic format. The necessary truth tables and matrix operators are provided in the Appendix.
Matrix Method
\[
\mathrm{H} \otimes \mathrm{I} \cdot \mathrm{CNOT} \cdot \mathrm{Z} \otimes \mathrm{I} \cdot \mathrm{X} \otimes \mathrm{I} \cdot \frac{1}{\sqrt{2}} \left( \begin{array}{l}{1} \\ {0} \\ {0} \\ {1}\end{array}\right)=\left( \begin{array}{l}{0} \\ {0} \\ {0} \\ {1}\end{array}\right)=\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{0} \\ {1}\end{array}\right) =| 11 \rangle
\nonumber \]
Algebraic Method
\[
\frac{ |00 \rangle+| 11\rangle}{\sqrt{2}} \xrightarrow{\mathrm{X}^{1} \otimes \mathrm{I}} \frac{ |10 \rangle+| 01\rangle}{\sqrt{2}} \xrightarrow{\mathrm{Z}^{1} \otimes \mathrm{I}} \frac{-| 10 \rangle+| 01\rangle}{\sqrt{2}} \xrightarrow{CNOT} \frac{-| 11 \rangle+| 01\rangle}{\sqrt{2}} \xrightarrow{\mathrm{H} \otimes \mathrm{I}} \frac{-( |0\rangle-| 1 \rangle ) | 1 \rangle+( |0\rangle+| 1 \rangle ) | 1\rangle}{2}=| 11 \rangle=\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{l}{0} \\ {0} \\ {0} \\ {1}\end{array}\right)
\nonumber \]
- Appendix:
-
Truth tables for the quantum circuit:
\[
\mathrm{X}=\mathrm{NOT} \left( \begin{array}{ccc}{0} & {\mathrm{to}} & {1} \\ {1} & {\mathrm{to}} & {0}\end{array}\right) \quad Z \left( \begin{array}{ccc}{0} & {\text { to }} & {0} \\ {1} & {\text { to }} & {-1}\end{array}\right) \quad \mathrm{H}=\text { Hadamard } \left[ \begin{array}{cc}{0} & {\text { to } \frac{1}{\sqrt{2}} \cdot(0+1)} \\ {1} & {\text { to }} {\frac{1}{\sqrt{2}} \cdot(0-1)}\end{array}\right] \quad \mathrm{CNOT} \left( \begin{array}{ccc}{00} & {\text { to }} & {00} \\ {01} & {\text { to }} & {01} \\ {10} & {\text { to }} & {11} \\ {11} & {\text { to }} & {10}\end{array}\right)
\nonumber \]Circuit elements in matrix format:
\[
\mathrm{I} \equiv \left( \begin{array}{ll}{1} & {0} \\ {0} & {1}\end{array}\right) \quad \mathrm{X} \equiv \left( \begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right) \quad \mathrm{Z} \equiv \left( \begin{array}{cc}{1} & {0} \\ {0} & {-1}\end{array}\right) \quad H \equiv \frac{1}{\sqrt{2}} \cdot \left( \begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right) \quad \mathrm{CNOT} \equiv \left( \begin{array}{llll}{1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} \\ {0} & {0} & {1} & {0}\end{array}\right)
\nonumber \]
Quantum Error Correction
This tutorial deals with quantum error correction as presented by Julian Brown on pages 274-278 in The Quest for the Quantum Computer. Brown's three-qubit example includes an input qubit and two ancillary qubits in the initial state \(|\Psi 00\rangle\). This state is encoded and subsequently decoded, with the possibility that in between it acquires an error. The quantum circuit demonstrates how correction occurs if a qubit is flipped due to decoherence at the intermediate state.
The quantum gates required for the error correction algorithm are:
\[
\mathrm{I} :=\left( \begin{array}{cc}{1} & {0} \\ {0} & {1}\end{array}\right) \qquad \text { CNOT } :=\left( \begin{array}{cccc}{1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} \\ {0} & {0} & {1} & {0}\end{array}\right) \\ \mathrm{CNOT} :=\left( \begin{array}{ccccccc}{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} \\ {0} & {0} & {0} & {0} & {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} \\ {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0}\end{array}\right) \\ \mathrm{IToffoli}:=\left( \begin{array}{lllllll}{1} & {0} & {0} & {0} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {0} & {1} \\ {0} & {0} & {0} & {1} & {0} & {0} & {0} \\ {0} & {0} & {0} & {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {1} & {0} & {0} & {0}\end{array}\right)
\nonumber \]
The encoding and decoding elements of the circuit in terms of these gates are shown in the appropriate place above the circuit diagram.
\[\text{Encode} : = \text{CnNOT} \cdot \text{kronecker(CNOT, I)} \qquad \text{Decode} : = \text{IToffoli} \cdot \text{Encode} \nonumber \]
\[\begin{matrix} \sqrt{\frac{1}{3}} | 0 \rangle+\sqrt{\frac{2}{3}} | 1 \rangle & \cdots & \cdot & \cdots & \cdot & \cdots & \mathrm{E} & \cdots & \cdot & \cdots & \cdot & \cdots & \oplus & \rhd & \sqrt{\frac{1}{3}} | 0 \rangle+\sqrt{\frac{2}{3}} | 1 \rangle \\ \; & \; & | & \; & | & \; & \mathrm{R} & \; & | & \; & | & \; & | & \; & \; \\ |0 \rangle & \cdots & \oplus & \cdots & | & \cdots & \mathrm{R} & \cdots & \oplus & \cdots & | & \cdots & \cdot & \rhd & |0 \rangle\; \text{or}\; | 1 \rangle \\ \; & \; & \; & \; & | & \; & \mathrm{O} & \; & \; & \; & | & \; & | & \; & \; \\ |0 \rangle & \cdots & \cdots & \cdots & \oplus & \cdots & \mathrm{R} & \cdots & \cdots & \cdots & | & \cdots & \cdot & \rhd & |0 \rangle\; \text{or}\; | 1 \rangle \end{matrix} \nonumber \]
Given an initial state, the encoding step creates and entangled Bell state as demonstrated below.
Initial State
\[
\left(\sqrt{\frac{1}{3}}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)=\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0} \\ {0}\end{array}\right)
\nonumber \]
Encode
\[
\text{Encode}=\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0.577} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0.816}\end{array}\right)
\nonumber \]
Encoded state
\[
\left(\sqrt{\frac{1}{3}}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)+\left( \begin{array}{c}{0} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}}\end{array}\right)
\nonumber \]
As an initial example, it is assumed that between encoding and decoding no errors are introduced to the encoded state. This case demonstrates that decoding simply returns the initial state. Susbsequent to this the operation of the circuit when errors occur on each of the wires are examined. These cases demonstrate that the original state appears on the top wire at the completion of the error correction circuit.
No errors:
\[
\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)+\left(\sqrt{\frac{2}{3}}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \\ \text{Decode}\cdot \left( \begin{array}{c}{0.577} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0} \\ {0.816}\end{array}\right)=\left( \begin{array}{c}{0.577} \\ {0} \\ {0} \\ {0} \\ {0.816} \\ {0} \\ {0} \\ {0}\end{array}\right) \quad \left(\sqrt{\frac{1}{3}}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)\cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) =\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0}\end{array}\right)
\nonumber \]
Next it is shown that if the input state, \(| \Psi \rangle\), is corrupted that the decoder corrects the error and returns the original \(| \Psi \rangle\) to the top wire of the circuit. In the example shown below the top qubit is flipped.
Top qubit flipped:
\[
\left( \begin{array}{c}{0} \\ {\sqrt{\frac{1}{3}}}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)+\left( \begin{array}{c}{\sqrt{\frac{2}{3}}} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0}\end{array}\right) \qquad \text{Decode} \cdot\left( \begin{array}{c}{0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {0} \\ {0.577} \\ {0} \\ {0} \\ {0} \\ {0.816}\end{array}\right) \quad \left( \begin{array}{l}{\sqrt{\frac{1}{3}}} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}}\end{array}\right)
\nonumber \]
The circuit can also be expressed using Dirac notation. Truth tables for the gates are provided in the Appendix.
\[
\left(\sqrt{\frac{1}{3}} | 0\rangle+\sqrt{\frac{2}{3}} | 1 \rangle \right) | 00 \rangle \stackrel{\text { encode }}{\longrightarrow} \sqrt{\frac{1}{3}} | 000 \rangle+\sqrt{\frac{2}{3}} | 111 \rangle \xrightarrow[\text{qubit}]{\text{flip top}}\sqrt{\frac{1}{3}} | 100 \rangle+\sqrt{\frac{2}{3}} | 011 \rangle \xrightarrow{\mathrm{CNOT}, \mathrm{I}} \sqrt{\frac{1}{3}} | 110 \rangle +\sqrt{\frac{2}{3}} | 011 \rangle \xrightarrow{\mathrm{CnNOT}} \sqrt{\frac{1}{3}} | 111 \rangle+\sqrt{\frac{2}{3}} | 011 \rangle \xrightarrow{\text{InToffoli}} \sqrt{\frac{1}{3}} | 011 \rangle+\sqrt{\frac{2}{3}} | 111 \rangle=\left(\sqrt{\frac{1}{3}} | 0\rangle+\sqrt{\frac{2}{3}} | 1 \rangle \right) | 11 \rangle
\nonumber \]
Naturally the ancillary qubits are also susceptible to errors. The following examples show that if a qubit flip occurs on the middle or bottom wire, the circuit still functions properly.
Middle qubit flipped:
\[
\left( \begin{array}{l}{\sqrt{\frac{1}{3}}} \\ {0}\end{array}\right) \cdot \left( \begin{array}{c}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)+\left( \begin{array}{c}{0} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0}\end{array}\right) \qquad \text{Decode}\cdot \left( \begin{array}{c}{0} \\ {0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {0.577} \\ {0} \\ {0} \\ {0} \\ {0.816} \\ {0}\end{array}\right) \quad \left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0}\end{array}\right)
\nonumber \]
\[
\left(\sqrt{\frac{1}{3}} | 0\rangle+\sqrt{\frac{2}{3}} | 1 \rangle\right ) | 00 \rangle \xrightarrow{\text { encode }}\sqrt{\frac{1}{3}} | 000 \rangle+\sqrt{\frac{2}{3}} | 111 \rangle \xrightarrow[\text{qubit}]{\text { flip middle }}\sqrt{\frac{1}{3}} | 010 \rangle+\sqrt{\frac{2}{3}} | 101 \rangle\xrightarrow{\mathrm{CNOT}, \mathrm{I}} \sqrt{\frac{1}{3}} | 010 \rangle\xrightarrow{\mathrm{CnNOT}} \sqrt{\frac{1}{3}} | 010 \rangle+\sqrt{\frac{2}{3}} | 110 \rangle \xrightarrow{\text{InToffoli}} \sqrt{\frac{1}{3}} | 010 \rangle+\sqrt{\frac{2}{3}} | 110 \rangle=\left(\sqrt{\frac{1}{3}} | 0\rangle+\sqrt{\frac{2}{3}} | 1 \rangle \right) | 10 \rangle
\nonumber \]
Bottom qubit flipped:
\[
\left(\sqrt{\frac{1}{3}}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)+\left( \begin{array}{c}{0} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}3}} \\ {0}\end{array}\right) \quad \text{Decode}\cdot \left( \begin{array}{c}{0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0.577} \\ {0} \\ {0} \\ {0} \\ {0.816} \\ {0}\\ {0}\end{array}\right)\quad \left( \begin{array}{c}{\sqrt{\frac{1}{3}}} \\ {\sqrt{\frac{2}{3}}}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{c}{0} \\ {\sqrt{\frac{1}{3}}} \\ {0} \\ {0} \\ {0} \\ {\sqrt{\frac{2}{3}}} \\ {0} \\ {0}\end{array}\right)
\nonumber \]
\[
\left(\sqrt{\frac{1}{3}} | 0\rangle+\sqrt{\frac{2}{3}} | 1 \rangle \right)| 00 \rangle \xrightarrow{\text{encode}} \sqrt{\frac{1}{3}} | 000 \rangle+\sqrt{\frac{2}{3}} | 111 \rangle \xrightarrow[\text{quibt}]{\text{flip bottom}}\sqrt{\frac{1}{3}} | 001 \rangle+\sqrt{\frac{2}{3}} | 110 \rangle \xrightarrow{\text{CNOT, I}} \sqrt{\frac{1}{3}} | 001 \rangle+\sqrt{\frac{2}{3}} | 100 \rangle\xrightarrow{\text{CnNOT}}\sqrt{\frac{1}{3}} | 001 \rangle+\sqrt{\frac{2}{3}} | 101 \rangle\xrightarrow{\text{InToffoli}}\sqrt{\frac{1}{3}} | 001 \rangle+\sqrt{\frac{2}{3}} | 101 \rangle=\left(\sqrt{\frac{1}{3}} | 0\rangle+\sqrt{\frac{2}{3}} | 1 \rangle \right) | 01 \rangle
\nonumber \]
- Appendix:
-
CNOT
\[
\left( \begin{array}{ccccc}{\text { Decimal }} & {\text { Binary }} & {\text { to}} & {\text{ Binary }} & {\text { Decimal }} \\ {0} & {00} & {\text { to }} & {00} & {0} \\ {1} & {01} & {\text { to }} & {01} & {1} \\ {2} & {10} & {\text { to }} & {11} & {3} \\ {3} & {11} & {\text { to }} & {10} & {2}\end{array}\right)
\nonumber \]CnNOT
\[
\left( \begin{array}{ccccc}{\text{Decimal}} & {\text{Binary}} & {\text { to }} & {\text { Binary }} & {\text { Decimal }} \\ {0} & {000} & {\text { to }} & {000} & {0} \\ {1} & {001} & {\text { to }} & {001} & {1} \\ {2} & {010} & {\text { to }} & {010} & {2} \\ {3} & {011} & {\text { to }} & {011} & {3} \\ {4} & {100} & {\text { to }} & {101} & {5} \\ {5} & {101} & {\text{to}} & {100} & {4} \\{6} & {110} & {\text { to }} & {111} & {7} \\ {7} & {111} & {\text { to }} & {110} & {6}\end{array}\right)
\nonumber \]IToffoli
\[
\left( \begin{array}{ccccc}{\text { Decimal }} & {\text { Binary }} & {\text { to}} & {\text{ Binary }} & {\text { Decimal }} \\ {0} & {000} & {\text { to }} & {000} & {0} \\ {1} & {001} & {\text { to }} & {001} & {1} \\ {2} & {010} & {\text { to }} & {010} & {2} \\ {3} & {011} & {\text { to }} & {111} & {7} \\ {4} & {100} & {\text { to }} & {100} & {4} \\ {5} & {101} & {\text { to }} & {101} & {5} \\ {6} & {110} & {\text { to }} & {110} & {6} \\ {7} & {111} & {\text { to }} & {011} & {3}\end{array}\right)
\nonumber \]
And now we move to Bell’s theorem and the battle between local realism and quantum mechanics.
Quantum theory is both stupendously successful as an account of the small-scale structure of the world and it is also the subject of unresolved debate and dispute about its interpretation. J. C. Polkinghorne, The Quantum World.
So we end this short course with the conflict between quantum mechanics and the classical view of reality held by Einstein and others known as local realism. Until the work of John Bell this battle was regarded by most scientists as a distracting philosophical debate. According to David Mermin quantum physicists were admonished to ignore the debate and “Shut up and calculate!”
In 1964 Bell demonstrated that experiments were possible for which quantum theory and local realism gave conflicting predictions, thus moving the disagreement from the realm of philosophical debate to the jurisdiction of the laboratory. In Where Does the Weirdness Go? David Lindley summarized Bell’s achievement.
The hallmark of Bell’s work was his success in locating precisely the point at which classical views of reality ran into trouble with quantum mechanics, and in devising a means by which the two viewpoints could be empirically compared. Bell’s sympathies seem often to have lain with Bohm and the effort to establish a hidden variables version of quantum mechanics. His greatest achievement, though, was to demonstrate incontrovertibly the price that must be paid to make such a theory work.
Bell said that if a theory of reality was local it would not agree with quantum mechanics, and if it agreed with quantum mechanics it would contain non-local interactions, in other words “spooky interactions at a distance” to use Einstein’s phrase. Here’s the best description of this spookiness that I have read: “A non-local interaction links up one location with another without crossing space, without decay, and without delay. A non-local event is, in short, unmediated, unmitigated and immediate.” Nick Herbert, Quantum Reality, page 214.
In 1981 Richard Feynman gave a lecture titled “Simulating Nature with Computers.” His thesis was that the simulation of nature at the nanoscopic level required a quantum computer. “I'm not happy with all the analyses that go with just the classical theory, because nature isn't classical, dammit. And if you want to make a simulation of nature, you'd better make it quantum mechanical …”