The Quantum Game

A handbook for understanding quantum math in articlesPermalink

We all agree that quantum mechanics is weird and fascinating: it can teleport information, connect particles across space and time, and even speed up computations that would take centuries. Our mission at The Quantumist is to make this field a bit more accessible by walking you through the steps and reasonings in a colloquial manner. However, one cannot fully grasp what is going on under the hood without understanding some of the math. We believe math can be seen as a game, and the “rules” of this game determine the symbols you can write and how you can manupulate them. The purpose of this article is to serve as a cheat-sheet for the basic rules that apply when dealing with the math of quantum computing, and is intended for people that want to get their hands dirty. We will expand it in the future with additional notions and tricks we deem useful.

Matrix multiplication refresherPermalink

This section is intended as a light refresh on one basic linear algebra concept that is fundamental for understanding the rest of the article. Feel free to skip it if you feel you already know these notions.

Matrix multiplication is a basic operation useful to understand how quantum states evolve and how quantum gates combine with each other. To perform a matrix multiplication we of course need two matrices to multiply, $A$ and $B$, and we call the resulting matrix $C$. We define $A$ to be of generic size $(m\times n)$ ($m$ rows, $n$ columns), while $B$ is of generic size $(k\times l)$. $A$ and $B$ can contain any kind of numbers, in our example we choose real numbers for simplicity ($\mathbb{R}$) but quantum computing utilizes complex values ($\mathbb{C}$). For now, not much is lost in limiting ourselves to real numbers. Back to our matrices, the size we choose for them is important, as we can only perform a matrix product $A\cdot B$ if the inner dimensions of the product match. In other words, we can only multiply matrices of size $(m\times n)$ and $(k\times l)$ if $n=k$.

Now, let’s see how we can actually compute the matrix product. The generic element $c_{ij}$ of $C$ in row $i$ and column $j$ is computed as the scalar product of the $i$-th row of $A$ with the $j$-th column of $B$. This is also a mnemonic trick: “To compute the element in the $\text{third row}$, $\text{second column}$ of $C$, you must use the $\text{third row}$ of $A$ and the $\text{second column}$ of $B$”.

$$A\cdot B=\left[\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{m1}& \dots & a_{mn}\end{array}\right]\cdot \left[\begin{array}{ccc}{b}_{11}& \dots & b_{1l}\\ ⋮& \ddots & ⋮\\ b_{k1}& \dots & b_{kl}\end{array}\right]=\left[\begin{array}{ccc}{c}_{11}& \dots & c_{1l}\\ ⋮& \ddots & ⋮\\ c_{m1}& \dots & c_{ml}\end{array}\right]=C$$ $$c_{ij}:=\sum _{x=0}^n{a}_{ix}\cdot b_{jx}$$

As an example, let’s take a look at the following, with $m=n=k=3$ and $l=2$, in particular let’s show how to obtain element $c_{32}$:

$$A\cdot B=\left[\begin{array}{ccc}1& 3& 1\\ 4& 3& 1\\ 2& 1& 2\end{array}\right]\cdot \left[\begin{array}{cc}1& 0\\ 4& 1\\ 3& 3\end{array}\right]=\left[\begin{array}{cc}16& 6\\ 19& 6\\ 12& 7\end{array}\right]=C$$ $$c_{32}=2\cdot 0+1\cdot 1+2\cdot 3=7$$

Note that $n=k$ was important in order to have vectors of the same length in the computation for $c_{ij}$.

Matrix notationPermalink

A recap of quantum gatesPermalink

Just as classical computers have logical gates to manipulate information, quantum computers have quantum gates. They serve the purpose of manipulating quantum states - effectively changing the shape of the probability distribution - in order to express some logical function. All quantum gates - and all quantum operators at large - act in a linear fashion. This means we can represent them in a matrix form. Moreover, every generic gate $U$ is unitary, meaning it preserves the total probability sum of the state to $1$ ($U^{†}U=U{U}^{†}=I$). All quantum gates are also reversible, meaning that the input can be unambiguously reconstructed from its output. By contrast, a classical XOR gate is irreversible since its output $0$ can be obtained by both $11$ and $00$. Here is a table summarizing the main single and multi-qubit quantum gates:

Gate	Symbol	Matrix form
Identity	$I$	$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$
Pauli-X	$X$	$\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$
Pauli-Y	$Y$	$\left[\begin{array}{cc}0& -i\\ i& 0\end{array}\right]$
Pauli-Z	$Z$	$\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$
Hadamard	$H$	$\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$
$\phi$ Phase Shift	$P(\phi )$	$\left[\begin{array}{cc}1& 0\\ 0& e^{i\phi }\end{array}\right]$
CNOT	$\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]$
SWAP	$\text{SWAP}$	$\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$
Controlled-Z	$CZ$	$\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& -1\end{array}\right]$
Toffoli	$CCX$	$\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& 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{array}\right]$

Applying quantum gates in matrix formPermalink

The result of applying a quantum gate to a state can be calculated simply as a matrix multiplication of the gate with the state. The effect of a gate can be easily understood once one visualizes the problem using linear algebra. To this regard, we recommend an excellent and intuitive explanation of these concepts: 3Blue1Brown’s Essence of linear algebra.

An intuition coming from linear algebra is that gates in matrix formulation are a map to where the base states end up. Let’s take a look at the following example with a Pauli-Y gate on the $|0⟩=[1,0{]}^T$ state:

$$Y|0⟩=\left[\begin{array}{cc}0& -i\\ i& 0\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ i\end{array}\right]$$

Observe how the final output corresponds to the $\text{first column of }Y$. This is trivial, since state $|0⟩$ had a single $1$ in the first position. This, however, is a very useful detail to notice, as it’s valid for gates and states of any size. Moreover, if your state is not a pure state (e.g. not $|0⟩$ or $|1⟩$), you can still compute the output as a sum of base states. The values of the state tells you “how much” of every column to use for composing your state. For example, if we apply the Pauly-Y gate to the superposed state $|+⟩=\frac{1}{\sqrt{2}}[1,1{]}^T$, we obtain:

$$Y|+⟩=\left[\begin{array}{cc}0& -i\\ i& 0\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\frac{1}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}0\\ i\end{array}\right]+\frac{1}{\sqrt{2}}\left[\begin{array}{c}-i\\ 0\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}-i\\ i\end{array}\right]$$

Let’s make a final example with a CNOT gate applied to a larger, 2-qubit state:

$$\text{CNOT}(|00⟩+|11⟩)=\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}{c}\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]+\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]\end{array}\right)=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]+\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]=|00⟩+|10⟩$$

Dirac notationPermalink

Quantum states in Dirac notationPermalink

Doing the math in matrix notation can get out of hand very quickly. Let’s take the case of a qubit system made of three $|0⟩$ states. We represent this in matrix notation as a tensor product of three 2-dimensional vectors:

$$|0⟩\otimes |0⟩\otimes |0⟩=\left[\begin{array}{c}1\\ 0\end{array}\right]\otimes \left[\begin{array}{c}1\\ 0\end{array}\right]\otimes \left[\begin{array}{c}1\\ 0\end{array}\right]={\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\end{array}\right]}^T$$

As you can see, this notation is very cumbersome, especially when dealing with large qubit systems whose vector size grows exponentially. For this reason, quantum scientists developed a shorthand form - Dirac notation - that concisely represents the constituent qubits of a system. In this notation, the 3-qubit system seen before is written as $|000⟩$. Much more compact! Another reason for wanting to work in Dirac notation is that quantum gates often operate on a small part of the whole set of qubits, so it’s useful to represent them as separate systems.

There is more! Scientists came up with many different ways of shortening and re-writing the notation while meaning the same thing. Here is a quick reference of alternative ways you can use to refer to a quantum system (in this case we take $|000⟩$ as an example, but it works with any other multiqubit state). Remember, these are all different ways of writing the same $|000⟩=[1,0,0,0,0,0,0,0{]}^T$ state:

• $|0⟩\otimes |0⟩\otimes |0⟩$: Mathematical definition of stacking together multiple qubits in the same ket.
• $|0⟩|0⟩|0⟩$: Shorthand for the Kronecker product.
• $|0⟩|00⟩$: The way qubits are split in different kets can be moved around.
• ${|0⟩}^{\otimes 3}$: Three concatenated $|0⟩$ states.

Let’s now take a different case. Suppose that we want to write a full superposition of all states in an $n$-qubit system. It would look somewhat like $(|00\dots 0⟩+\cdots +|11\dots 1⟩)/\sqrt{n}$, which is again very long. A shorthand way to represent the same state is the following:

$$\frac{1}{\sqrt{n}}\sum _{x\in \{0,1{\}}^n}|x⟩$$

For example, the 2-qubit superposition $(|00⟩+|01⟩+|10⟩+|11⟩)/2$ becomes $\frac{1}{2}\sum _{x\in \{0,1{\}}^2}|x⟩$. This notation often pops up when dealing with quantum algorithms.

Quantum gates in Dirac notationPermalink

When dealing with quantum computations, you may deal with long and cumbersome operations that cannot be further reduced. A way of speeding up your calculations is to work directly in Dirac notation. To do so, we first need to lay down some rules to make sure we are playing the game correctly.

Rule of behavioursPermalink

All gates act in easy to describe ways. The outcome of passing a superposition through a gate can be obtained by applying the gate separately on each basis state and summing the results. Moreover, you can deduce this behavior by looking at the columns of the matrix form of the gate, in the same way we did for the matrix prodct. Let’s take a look at an example that shows how to transition from matrix notation to the Dirac one.

Let’s consider gate $H$ applied on $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$: $H|+⟩=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]\frac{1}{\sqrt{2}}=(H|0⟩+H|1⟩)/\sqrt{2}$ Remember how all kets actually represent column vectors? We use that same rule to convert back from vectors to ket, and rewrite the application of $H$ in a different way. Now, we can read the columns of H (in $red$ and $blue$) to understand how they will change the states they’re applied to:

$$(H|0⟩+H|1⟩)/\sqrt{2}=(|0⟩+|1⟩+|0⟩-|1⟩)/2=|0⟩$$

Indeed, the first column of $H$ is $[1,1{]}^T/\sqrt{2}$ and $|0⟩$ is transformed in a state with the same meaning: $|0⟩+|1⟩=[1,1{]}^T/\sqrt{2}$.

Here is a table summarizing the behaviours of the main gates:

Gate	Symbol	Mapping	Description
Identity	$I$	$|0⟩⟶|0⟩$ $|1⟩⟶|1⟩$	Does nothing
Pauli-X	$X$	$|0⟩⟶|1⟩$ $|1⟩⟶|0⟩$	Quantum NOT. Turns $0$ to $1$ and viceversa
Pauli-Y	$Y$	$|0⟩⟶i|1⟩$ $|1⟩⟶-i|0⟩$	Similar to $X$, but multiplies by $i$ or $-i$
Pauli-Z	$Z$	$|0⟩⟶|0⟩$ $|1⟩⟶-|1⟩$	Similar to $I$, but flips the sign of nonzero inputs
Hadamard	$H$	$|0⟩⟶(|0⟩+|1⟩)/\sqrt{2}$ $|1⟩⟶(|0⟩-|1⟩)/\sqrt{2}$	Creates a superposition
$\phi$ Phase Shift	$P(\phi )$	$|0⟩⟶|0⟩$ $|1⟩⟶e^{i\phi }|1⟩$	Shifts $|1⟩$ inputs by a specific phase
CNOT	$\text{CNOT}$	$|00⟩⟶|00⟩$ $|01⟩⟶|01⟩$ $|10⟩⟶|11⟩$ $|11⟩⟶|10⟩$	If the first qubit is $1$, it flips the second qubit
SWAP	$\text{SWAP}$	$|00⟩⟶|00⟩$ $|01⟩⟶|10⟩$ $|10⟩⟶|01⟩$ $|11⟩⟶|11⟩$	Swaps the two qubits
Controlled-Z	$CZ$	$|00⟩⟶|00⟩$ $|01⟩⟶|01⟩$ $|10⟩⟶|10⟩$ $|11⟩⟶-|11⟩$	Flips the sign of the target qubit if both qubits are in the $1$ state
Toffoli	$CCX$	$|010⟩⟶|010⟩$ $|110⟩⟶|111⟩$ $|111⟩⟶|110⟩$	Flips the third qubit if both first and second qubits are $1$ (only some examples shown)

Rule of parallel gatesPermalink

Gates stack like states do. In other words, one can represent three parallel $H$ gates with a tensor product: $H\otimes H\otimes H$. A shorthand notation is $H^{\otimes 3}$. The resulting gate can handle 3-qubit systems, so $H^{\otimes 3}|000⟩$ would be a valid operation.

Rule of matching sizesPermalink

In Dirac notation, a gate is always applied to the state to its right. States and the gates we pass them through must match in size. For example, the operation $\text{CNOT}|000⟩$ doesn’t make sense because the $\text{CNOT}$ gate expects 2 qubits as input, while we are feeding it a 3-qubit system. A correct way to apply a $\text{CNOT}$ to only the first two qubits would be $(\text{CNOT}\otimes I)|000⟩$ or $\text{CNOT}|00⟩|0⟩$.

Let’s now see how one can use these shortcuts to work through the math without using the lengthy matrix notation.

Example 1 - Single-qubit gates in Dirac notationPermalink

Write the result of applying the gate $YHX$ on state $|1⟩$

$$\begin{array}{rlrl}YHX|1⟩& =YH|0⟩& & \text{Start by flipping the qubit}\\ & =Y(|0⟩+|1⟩)/\sqrt{2}& & \text{Use H to build the superposition}\\ & =(Y|0⟩+Y|1⟩)/\sqrt{2}& & \text{Carry the Y inside }\\ & =(i|1⟩-i|0⟩)/\sqrt{2}& & \text{Apply Y separately to each basis state}\end{array}$$

Example 2 - Multiple-qubit gates in Dirac notationPermalink

Write the result of applying the gate $(X^{\otimes 3})(X\otimes \text{CNOT})(\text{CNOT}\otimes I)$ on state $|101⟩$

$\begin{array}{rlrl}(X^{\otimes 3})(X\otimes \text{CNOT})(\text{CNOT}\otimes I)|101⟩& =(X^{\otimes 3})(X\otimes \text{CNOT})|111⟩& & \text{Controlled flip operation on second qubit}\\ & =(X^{\otimes 3})|\phantom{}010⟩& & \text{Flip of first qubit and controlled flip of third qubit}\\ & =|101⟩& & \text{Flip of all qubits}\end{array}$ Notice how the gate used in the example respects the rule of matching sizes, and notice how by applying the rule of behaviours we solved an otherwise very large matrix multiplication in just a few steps!

Reading quantum circuitsPermalink

Oftentimes, papers and books present quantum algorithms using the circuit that describes them. Going from the diagram to the math and viceversa can be confusing, therefore we summarized here some useful rules to keep in mind in order to correctly interpret the notation.

• Gates in series correspond to consecutive matrix products

$$|s^{\prime }⟩=TXH|s⟩$$

Figure 1: Three gates in series on a single qubit.

• Gates in parallel correspond to a tensor product

$$|s^{\prime }⟩=(\text{CNOT}\otimes I)(I\otimes \text{CNOT})(H\otimes X\otimes I)|s⟩$$

Figure 2: Multiple gates in parallel on 3 qubits. Note how s is actually a 3-qubit system.

As a sanity check, remember that the formula you obtain must satisfy the “rule of matching sizes”. Translating a diagram and finding something like $CNOT|0⟩$ is a sign that something went wrong.

ConclusionPermalink

If you got this far, congratulations! This article is very dense and tries to summarise many concepts in the simplest way possible. Don’t worry if you couldn’t memorize all notions, it’s normal to feel this way. The purpose of this article is to be a quick guide to return to in case you stumble upon some confusing math later on. Remember to come back from time to time, as new tips and tricks may be added later on. See you soon!

Quantum gate summary tablePermalink

Gate	Symbol	Mapping	Matrix form	Description
Identity	$I$	$|0⟩⟶|0⟩$ $|1⟩⟶|1⟩$	$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$	Does nothing
Pauli-X	$X$	$|0⟩⟶|1⟩$ $|1⟩⟶|0⟩$	$\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$	Quantum NOT. Turns $0$ to $1$ and viceversa
Pauli-Y	$Y$	$|0⟩⟶i|1⟩$ $|1⟩⟶-i|0⟩$	$\left[\begin{array}{cc}0& -i\\ i& 0\end{array}\right]$	Similar to $X$, but multiplies by $i$ or $-i$
Pauli-Z	$Z$	$|0⟩⟶|0⟩$ $|1⟩⟶-|1⟩$	$\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$	Similar to $I$, but flips the sign of nonzero inputs
Hadamard	$H$	$|0⟩⟶(|0⟩+|1⟩)/\sqrt{2}$ $|1⟩⟶(|0⟩-|1⟩)/\sqrt{2}$	$\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$	Creates a superposition
$\phi$ Phase Shift	$P(\phi )$	$|0⟩⟶|0⟩$ $|1⟩⟶e^{i\phi }|1⟩$	$\left[\begin{array}{cc}1& 0\\ 0& e^{i\phi }\end{array}\right]$	Shifts $|1⟩$ inputs by a specific phase
CNOT	$\text{CNOT}$	$|00⟩⟶|00⟩$ $|01⟩⟶|01⟩$ $|10⟩⟶|11⟩$ $|11⟩⟶|10⟩$	$\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]$	If the first qubit is $1$, it flips the second qubit
SWAP	$\text{SWAP}$	$|00⟩⟶|00⟩$ $|01⟩⟶|10⟩$ $|10⟩⟶|01⟩$ $|11⟩⟶|11⟩$	$\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$	Swaps the two qubits
Controlled-Z	$CZ$	$|00⟩⟶|00⟩$ $|01⟩⟶|01⟩$ $|10⟩⟶|10⟩$ $|11⟩⟶-|11⟩$	$\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& -1\end{array}\right]$	Flips the sign of the target qubit if both qubits are in the $1$ state
Toffoli	$CCX$	$|010⟩⟶|010⟩$ $|110⟩⟶|111⟩$ $|111⟩⟶|110⟩$	(Omitted for readability)	Flips the third qubit if both first and second qubits are $1$ (only some examples shown)

SourcesPermalink

Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667