Entanglion: A Quantum Computing Board Game

Last updated Jun 24, 2022

• Type note
• Status good
• On quantum computing

In this chapter, we will learn about multi-qubit systems and how quantum gates can be used to perform computations.

• We are introduced to the Entanglion game, and its mechanics here. Detailed instructions are available on the website, but a brief summary was provided in this section.

• The rules of Entanglion reflect how Quantum Computers work.
• The red and blue spaceships are qubits.
• The planets are various states that qubits can be in.
• The engine cards $H, X, CNOT,$ and $SWAP$ are Quantum Gate.
• Detection by planetary defenses corresponds to a measurement.

• When we have multiple qubits, we write their states as a tensor product $\otimes$, i.e. $\ket 0 \otimes \ket 1$, which is pronounced as “zero tensor zero”. Although, most of the times, we compress this notation and leave out the tensor product in both writing and speech: $\ket 0 \ket 0$, or further still: $\ket{00}$.
• With $2$ qubits, the Z-basis is ${\ket{00}, \ket{01}, \ket{10}, \ket{11}}$. A general state is a Superposition of these basis states: $$c_0\ket{00} + c_1\ket{01} + c_2 \ket{10} + c_3 \ket{11}.$$ Here, $c_0, c_1, c_2, c_3$ are the amplitudes of different basis states, the total probability is calculated as: $|c_0|^2 + |c_1|^2 + |c_2|^2 + |c_3|^2$ which must be equal to $1$.
• With $3$ qubits, there are $8$ Z-basis states: ${\ket{000}, \ket{001}, \ket{010}, \ket{011}, \ket{100}, \ket{101}, \ket{110}, \ket{111}}$.
• Sometimes, these binary strings are written as decimal numbers $\ket 0, \ket 1, \ket 2, …, \ket 7$. These can be converted using either Little endian convention, or Big endian convention. Here, we will be using the Little endian convention.
• The general state of three qubits is a superposition of these basis vectors: $$\sum_{j = 0}^7 c_j\ket j = c_0\ket0 + c_1\ket1 + … + c_7\ket7,$$ and the probability of getting $\ket j$ when measuring in the $Z$-basis is $|c_j|^2$, so $\sum_j |c_j|^2 = 1$.
• With $n$ qubits, there are $N = 2^n$ $Z$-basis states, which we can label as $n$-bit strings or by the decimal numbers $0$ through $N − 1$.
• If we have just $n = 300$ qubits, then we must keep track of $N = 2^{300} \approx 2.04 \times 10^{90}$ amplitudes, which is more than the Number of atoms in the visible universe. This is evidence, not proof, that Classical computers can’t simulate quantum computers efficiently. It is evidence because classical computers cannot keep track of this many amplitudes, but it is not a proof because it is unknown whether quantum computers need all these amplitudes. That is, if quantum computers can function with much fewer amplitudes (a polynomial number instead of an exponential number in $n$), a classical computer would be able to keep track of all of them.
• A general multi-qubit state can’t be represented in a Bloch sphere because of the many parameters.

• In Linear Algebra, the tensor product is simply the Kronecker product. Then $$c_0\ket{00} + c_1\ket{01} + c_2\ket{10} + c_3\ket{11} = \begin{pmatrix}c_0 \\ c_1 \\ c_2 \\ c_3 \end{pmatrix}.$$
• With $n$ qubits, the Vector has $N=2^n$ elements: $$\ket \psi = \sum_{j=0}^{N-1} c_j\ket j = c_0 \ket0 + c_1\ket1 + … + c_{N-1}\ket{N-1} = \begin{pmatrix}c_0 \\ c_1 \\ \vdots \\ c_{N-1}\end{pmatrix}.$$
• A general Quantum State of $n$-qubits, written as a bra, is: $$\bra \psi = \sum_{j=0}^{N-1} c_j^\bra j = c_0^ \bra 0 + c_1^\bra 1 + … + c_{N-1}^\bra{N-1} = \begin{pmatrix}c_0^* & c_1^* & \dots & c_{N-1}^*\end{pmatrix}.$$

• Suppose we have two qubits in the state $$\frac{1}{\sqrt 2}\ket{00} + \frac{1}{2}\ket{01} + \frac{\sqrt 3}{4}\ket{10} + \frac{1}{4}\ket{11}.$$ Instead of measuring both qubits, if we only measure the left qubit, then the probability of getting $\ket 0$ is given by the sum of the norm-squares of the amplitudes of those states that have a left qubit of $\ket 0$, i.e. $\ket {00}$ and $\ket {01}$. So the probability of getting $\ket 0$ as the left qubit is: $$\left|\frac{1}{\sqrt 2}\right|^2 + \left|\frac{1}{2}\right|^2 = \frac{3}{4}.$$ Similarly, if the outcome is $\ket 1$, then from the $\ket{10}$ and $\ket{11}$ states, the probability is $$\left| \frac{\sqrt3}{4} \right|^{2} + \left|\frac{1}{4} \right|^{2} = \frac{1}{4}.$$
• Now for the states after measurement, if the outcome is $\ket 0$, then the state collapses to the parts where the left qubit is $\ket 0$, so it becomes $$A \left(\frac{1}{\sqrt 2}\ket{00} + \frac{1}{2}\ket{01} \right),$$ where $A$ is a normalization constant. Similarly, if the outcome is $\ket 1$, then the state collapses to the terms where the left qubit is $\ket 1$, so it becomes $$B \left(\frac{\sqrt 3}{4}\ket{10} + \frac{1}{4}\ket{11} \right),$$ where $B$ is a normalization constant. Normalizing these, we get $A = \frac{2}{\sqrt3}$ and $B = 2$, so measuring the left qubit yields:
  • $\ket 0$ with probability $\frac34$, and the state collapses to $\sqrt\frac{2}{3}\ket{00} + \frac{1}{\sqrt 3}\ket{01}$
  • $\ket 1$ with probability $\frac14$, and the state collapses to $\frac{\sqrt3}{2}\ket{10} + \frac{1}{2}\ket{11}$.
• We can apply these ideas to any number of qubits.

• Measuring both qubits is the same as measuring one after another, assuming the state was not modified between the two measurements.
• If we take the qubit introduced in the last section, the probability of getting $\ket{00}$ is the probability of first getting $\ket 0$ for the left qubit, which was $3/4$, times the probability of getting $\ket 0$ for the right qubit, which was $2/3$. Multiplying these, the probability of getting $\ket{00}$ is $(3/4)(2/3) = 2/4 = 1/2$, which is the same if we had measured both qubits at the same time.

• Product states are those states that can be factored into individual qubit states. For example, $$\begin{aligned}
  \frac{1}{2}(\ket{00} - \ket{01} + \ket{10} - \ket{11}) &= \frac{1}{\sqrt 2}(\ket0 + \ket1) \otimes \frac{1}{\sqrt2}(\ket0 - \ket 1) \
  &= \ket+ \otimes \ket- \
  &= \ket+\ket-.
  \end{aligned}$$

• Entangled states are those quantum states that cannot be factored into Product states. For example, with two qubits, $$\ket{\phi^+} = \frac{1}{\sqrt2}(\ket{00} = \ket{11}),$$ cannot be written as $\ket\psi_1 \ket\psi_0$. ^7c05d1

• If we want to apply one quantum gate to the left- qubit, and another one to the right, we can do so by using a tensor product. e.g. to apply $H$ gate on the left qubit and $X$ gate on the right qubit, we would write: $$(H \otimes X)\ket 0 \ket 0 = \ket + \ket 1 = \frac{1}{\sqrt 2}(\ket{01} = \ket{11}).$$
• One-Qubit Quantum Gates are unable to create Entangled states because each qubit evolves independently of the others.

• CNOT Gate inverts the right Qubit (target qubit) if the left qubit (control qubit) is $1$.
• The Controlled-U Gate applies some Quantum Gate $U$ to the right Qubit if the left qubit is $1$.
• The SWAP Gate simply swaps the two qubits.

• The Toffoli Gate is a three-qubit Quantum Gate that flips the right Qubit if the left and middle qubits are $1$ : $$\begin{aligned}
  \text{Toffoli}\ket{000} &= \ket{000}, \
  \text{Toffoli}\ket{001} &= \ket{001}, \
  \text{Toffoli}\ket{010} &= \ket{010}, \
  \text{Toffoli}\ket{011} &= \ket{011}, \
  \text{Toffoli}\ket{100} &= \ket{100}, \
  \text{Toffoli}\ket{101} &= \ket{101}, \
  \text{Toffoli}\ket{110} &= \ket{111}, \
  \text{Toffoli}\ket{111} &= \ket{110}.
  \end{aligned}$$
• As we know that the Toffoli gate is universal for classical computing, and since it is a Quantum Gate, quantum computers can efficiently do everything a classical computer can efficiently do.
• Toffoli gate, represented as a Matrix: $$\text{Toffoli} =
  \begin{pmatrix}
  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 & 0 & 1 \
  0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \
  \end{pmatrix}.$$
• Its circuit diagram is similar to the CNOT Gate:
  

• We can copy a known Quantum State easily, but the issue arises when we want to copy/clone an unknown quantum state.
• The No-Cloning theorem simply states/proves that the quantum information can not generally be cloned.

• Classically, we can add binary numbers using the ripply-carry adder.

• We can convert a full-adder to a quantum gate in several ways.
• We can turn the full adder into a reversible circuit by taking the XOR of each of its outputs with and extra bit.
• We can replace all of the gates (two XOR, two AND, and one OR) in full-adder by NAND gates, implement each NAND gate using a Toffoli Gate.
• Or instead of first converting each gate to NAND gate, we can directly convert those classical logic gates to their quantum counterparts, as shown in the table below:
• The extra bits that are used during the calculation are called ancilla bits or * Ancillary bits*, and in quantum circuits, they should be cleaned up by turning them back into zeros, so they can be reused later on and don’t cause unintended entanglements.
• One method for cleaning up Ancillary bits is called uncomputation, where we apply in reverse order the inverses of the gates that were used to calculate the ancillas.

• We can use two quantum registers, $\ket a$ and $\ket b$, to encode the binary numbers. One way to add them reversibly is to replace |b⟩ with the sum: $$\ket a \ket b \rightarrow \ket a \ket s,$$ where $s = a + b$.
• In the intermediate steps of the computation, the quantum adder also needs to keep track of carry bits.
• Our quantum adder should map $\ket a \ket b \ket c \rightarrow \ket a \ket s \ket c$ where : $$\begin{aligned}
  \ket a &= \ket {a_{n-1}} \dots \ket {a_1} \ket {a_0}, \
  \ket b &= \ket {b_n = 0}\ket {b_{n-1}} \dots \ket{b_1}\ket{b_0}, \
  \ket c &= \ket {c_{n-1}} \dots \ket {c_1} \ket {c_0}.
  \end{aligned}$$

• We can implement the sum using two CNOT Gates.
  

• The quantum carry circuit is:

• For a detailed explanation along with circuit diagrams, directly read the section in the book.
• Draper’s adder implemented in Quirk and used to add $\ket a = \ket{0111}$ and $\ket b = \ket{0011}$. Link to circuit.

• The quantum ripple-carry adder uses $4n − 2$ toffoli gates and $4n$ CNOT gates, which is linear in $n$, i.e., $Θ (n)$, so the algorithm is efficient.

• Our quantum ripple-carry adder circuit can be used to act on superpositions. It will calculate the results for both, but we will only be able to get/measure a certain result based on some probability.
• It is incorrect to think of a quantum computer as a massively parallel classical computer because we must measure and only get one result. It might be best to avoid the term “parallel” altogether when describing quantum computing.

• A set of quantum gates that allows us to approximate any quantum gate to any desired precision is called a Universal Gate Set.
• Based on the context, we can infer if we’re talking about classical or quantum universal gate sets.

• Superposition: We must be able to produce superpositions.
• Entanglement: We must be able to entangle qubits. A Quantum Gate must act on at least two qubits to produce entanglement.
• Complex amplitudes: CNOT Gate and H gate only contain real numbers, so they do not produce states with complex amplitudes.
• Contain more than the Clifford group. Because of the Gottesman-Knill theorem, Clifford group is only as powerful as a classical computer.
• It is unknown if these are sufficient requirements for a set of quantum gates to be universal. It may be that a set satisfies all of these properties, but is still not universal.

• { CNOT, One-Qubit Quantum Gates}
• {CNOT, H, T}
• {CNOT, $R_{\pi/8}$ , S}
• { Toffoli, H, S}
• Hadamard Gate plus almost any two-qubit unitary.

• The Solovay-Kitaev theorem says that with any universal gate set, we can approximate a quantum gate on $n$ qubits to precision $ε$ using $Θ (2^n log^c(1/ε))$ gates for some constant $c$.
• The dependence on the number of qubits $2^n$ is expected because an operator on $n$ qubits is a Matrix of $2^n \times 2^n$ entries. The dependence on the precision $log^c(1/ε)$ is great. The precision $\epsilon$ is the “distance” between the approximate quantum gate and the actual quantum gate, which we want to be small. So $1/\epsilon$ is big, but taking the Logarithm of it makes it small. The Polylog is also considered small. Thus this dependence means our approximation quickly converges on the actual quantum gate.

• We can express any Complex Number as two real numbers $(x, y)$ and keep track of the fact that they play different roles.
• So, we can formulate all of quantum computing just in terms of real numbers. Then, a universal set of quantum gates technically does not need to produce states with complex amplitudes. For example, the following sets are also universal for quantum computing:
  • { Toffoli, any single-qubit Basis-changing Gate}
  • The Controlled-Hadamard Gate {CH}
  • { CNOT, any single-qubit gate whose square is basis-changing}

• A qubit can experience full bit flip errors (rotations about the $x$-axis by $\pi = 180^{\circ}$) as well as partial bit flip errors (rotations about the $x$-axis by some angle).
• A qubit can also experience phase flip errors (rotations around the $z$-axis).
• Decoherence is the process of small interactions of the qubit with the environment that move the qubit to a different location on the Bloch sphere. This is the biggest obstacle in building large quantum computers.

• We use three physical qubits to encode each logical qubit: $$\ket{0_L} = \ket{000}, \qquad \ket{1_L} = \ket{111}.$$ In general, a logical qubit is a Superposition of $\ket{0_L}$ and $\ket{1_L}$: $\alpha\ket{0_L} + \beta\ket{1_L}$.
• Instead of measuring the qubit, which would collapse its superposition state, we use the parity of adjacent qubits to determine if a bit flip error has occurred. We can use CNOT gates to calculate the parity of qubits, and if a bit flip error is detected, we can apply X Gate to correct it.
• In case of partial bit flips, we use the following quantum circuit:
  
  The first four columns are the CNOTs that calculate the parities of adjacent qubits. Then, we measure these parities, as shown by the meter symbols, which results in classical bits. We denote these classical bits/wires using double lines. We end with three X Gates conditioned on these classical bits/parities. If both parities are $1$, then $q_1$ flipped, so we apply an X Gate to it to correct it. If $\text{parity}(q_2, q_1) = 0$ and parity$(q_1, q_0) = 1$, then $q_0$ flipped, so we apply an X gate to it to correct it. Finally, if parity$(q_2, q_1) = 1$ and parity$(q_1, q_0) = 0$, then $q_2$ flipped, so we apply an X gate to it to correct it. We end by resetting the ancillas to $|0⟩$, indicated by the boxes with $|0⟩$ in them.
• The Principle of deferred measurement states that intermediate measurements that are used to control operations can be moved after the operations, and the controls can be replaced by quantum controls.
  • Phrased another way, we can collapse and then do the controlled operations, or we can do the controlled operations in superposition, and then collapse.

• For phase-flip errors, we use logical qubits using three $\ket +$ and $\ket -$, i.e. $$\ket{0_L} = \ket{+++}, \qquad \ket{1_L} = \ket{—},$$ so a general superposition is $\alpha \ket{0_L} + \beta \ket{1_L}$.
• To detect the phase flip error, we measure the parity of consecutive qubits in the $X$-basis, and then apply a Z-gate if an error occurred.
• When we have a partial phase flip, the measurement forces it to be corrected or to become a complete bit flip, which we can correct by applying a Z-gate. The quantum circuit for this procedure is shown below:

• Shor code combines the phase-flip code and bit-flip code to correct both kinds of errors.
• We start off with the phase-flip code, i.e. $$\begin{aligned}
  \ket{0_L} &= \ket{+++} \
  &= \frac{1}{\sqrt2}(\ket{0} + \ket{1}) \frac{1}{\sqrt2}(\ket{0} + \ket{1}) \frac{1}{\sqrt2}(\ket{0} + \ket{1}) \
  &= \frac{1}{2^{3/2}}(\ket{0} + \ket{1})(\ket{0} + \ket{1})(\ket{0} + \ket{1}).
  \end{aligned}$$ Next, to correct the bit-flip error, we use bit-flip encoding to replace each of the three qubits, i.e., $\ket{0} \rightarrow \ket{000}$ and $\ket{1} \rightarrow \ket{111}$, so that each logical qubit is encoded using nine physical qubits: $$\ket{0_L} = \frac{1}{2^{3/2}}(\ket{000} + \ket{111})(\ket{000} + \ket{111})(\ket{000} + \ket{111}).$$
  Same goes for the $\ket{1_L} = \ket{—}$, i.e. $$\ket{1_L} = \frac{1}{2^{3/2}}(\ket{000} - \ket{111})(\ket{000} - \ket{111})(\ket{000} - \ket{111}).$$
• Following that, the state of a general logical qubit is $$\begin{aligned}\alpha\ket{0_L} + \beta \ket{1_L} &= \frac{\alpha}{2^{3/2}}\frac{1}{2^{3/2}}(\ket{000} + \ket{111})(\ket{000} + \ket{111})(\ket{000} + \ket{111}) \newline &+ \frac{\beta}{2^{3/2}} \frac{1}{2^{3/2}}(\ket{000} - \ket{111})(\ket{000} - \ket{111})(\ket{000} - \ket{111}).\end{aligned}$$
• This encoding is called the Shor Code, named after its inventor, Peter Shor.

• The state of multiple qubits is written as as a tensor product.
• With $n$ qubits, there are $2^n$ orthonormal basis states, and a general state is a Superposition of these basis states.
• In a product state, measuring one qubit cannot affect the others, while in an entangled state, measuring one qubit can affect the other qubits.
• A Quantum Gate on $n$ qubits is a $2^n × 2^n$ Unitary matrix.
• A universal set of quantum gates can approximate any Quantum Gate to any desired precision.
• Quantum bits can suffer from both bit-flip and phase-flip errors, but they can be corrected.