$ \definecolor{r}{RGB}{255,44,45} \definecolor{b}{RGB}{27,145,255} \definecolor{g}{RGB}{23,255,45} \definecolor{d}{RGB}{255,255,255} \newcommand{\ket}[1]{ \mathbf{|#1\rangle} } $

Quantum Computing Demystified

It's just math, seriously, it's just a ton of math

by Viliam Rockai

Agenda

  1. Introduction
  2. Math prerequisites
  3. Qubit
  4. Quantum logic gates
  5. Deutsch's oracle
  6. Quantum supremacy
  7. QA

whoami

  • Red hat logo DNAstack logo Exponea logo
  • PhD in Artificial Intelligence: Automatic discovery of concepts in documents written in natural language
  • Had been an avid musician for a long time
  • Like to get familiar with weird/unintuitive stuff like Quantum Mechanics or Functional Programming
  • TV (Star Trek), indie games (Natural Selection 2)

Goals

Distill the theoretical minimum to

  • Understand how a quantum algorithm works under an hour!
  • Be able to implement and execute a quantum algorithm yourself on a real quantum computer!

Anti-goals

  • Explain QM weirdness like superposition, entanglement, teleportation...
  • Mention Schrodinger's cat anywhere outside of this slide

Introduction

$${\displaystyle i\hbar {\frac {d}{dt}}\vert \Psi (t)\rangle ={\hat {H}}\vert \Psi (t)\rangle }$$

$${\displaystyle i\hbar {\frac {\partial }{\partial t}}\Psi (\mathbf {r} ,t)=\left[{\frac {-\hbar ^{2}}{2m}}\nabla ^{2}+V(\mathbf {r} ,t)\right]\Psi (\mathbf {r} ,t)}$$

Math prerequisites

Complex Numbers

Futurama gif

Matrix properties

Transposition

$ M^T = \begin{bmatrix}1&2&3\\0&-6&7\end{bmatrix}^{\mathrm {T} } = \begin{bmatrix}1&0\\2&-6\\3&7\end{bmatrix} $

Matrix properties

Identity

$ {\mathbf {I} _{n}={\begin{bmatrix}1&0&\cdots &0\\0&1&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &1\end{bmatrix}}} $

Matrix properties

Unitary matrix

M is unitary if its conjugate transpose $M^\dagger$ is also its inverse

$ M^{\dagger }M = MM^{\dagger } = I. $

If $M$ is a real number matrix

$ M^{T}M = MM^{T} = I. $

$ \begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} $

Matrix Multiplication

$c_{ij}=a_{i1}b_{1j}+\cdots +a_{im}b_{mj}=\sum _{k=1}^{m}a_{ik}b_{kj}$

$$ \begin{bmatrix} \color{r}{a_{11}} & \color{r}{a_{12}} & \color{r}{a_{13}} & \color{r}{a_{14}} \\ \color{b}{a_{21}} & \color{b}{a_{22}} & \color{b}{a_{23}} & \color{b}{a_{24}} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ \end{bmatrix} \times \begin{bmatrix} \color{r}{b_{11}} & b_{12} & \color{b}{b_{13}} \\ \color{r}{b_{21}} & b_{22} & \color{b}{b_{23}} \\ \color{r}{b_{31}} & b_{32} & \color{b}{b_{33}} \\ \color{r}{b_{41}} & b_{42} & \color{b}{b_{43}} \\ \end{bmatrix} = \begin{bmatrix} \color{r}{c_{11}} & c_{12} & c_{13} \\ c_{21} & c_{22} & \color{b}{c_{23}} \\ \end{bmatrix} $$

$ \color{r}{ c_{11}= a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31} + a_{14}b_{41} } $

$ \color{b}{ c_{23}= a_{21}b_{13} + a_{22}b_{23} + a_{23}b_{33} + a_{24}b_{43} } $

Dawg

Tensor Product $\otimes$

Matrix multiplication on steroids

$ \begin{bmatrix} \color{r}{a_{11}} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix} \otimes \color{r}{ \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix} } \color{d} = { \begin{bmatrix} \color{r} a_{11}{ \begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix}} & \color{d} a_{12}{\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix}} \\ & \\ a_{21}{\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix}} & a_{22}{\begin{bmatrix}b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix}} \\ \end{bmatrix}} $

$ = { \begin{bmatrix} \color{r} a_{11}b_{11} & \color{r} a_{11}b_{12} & a_{12}b_{11} & a_{12}b_{12} \\ \color{r} a_{11}b_{21} & \color{r} a_{11}b_{22} & a_{12}b_{21} & a_{12}b_{22} \\ a_{21}b_{11} & a_{21}b_{12} & a_{22}b_{11} & a_{22}b_{12} \\ a_{21}b_{21} & a_{21}b_{22} & a_{22}b_{21} & a_{22}b_{22} \\ \end{bmatrix} }$

Tensor Product $\otimes$

to remember

$ \begin{bmatrix} \color{r} a_{11} \\ a_{21} \\ \end{bmatrix} \otimes \color{r} \begin{bmatrix} b_{11} \\ b_{21} \\ \end{bmatrix} \color{d} = \begin{bmatrix} \color{r} a_{11} {\begin{bmatrix} b_{11} \\ b_{21} \\ \end{bmatrix}} \\ \color{d} a_{21} {\begin{bmatrix} b_{11} \\ b_{21} \\ \end{bmatrix}}\\ \end{bmatrix} = \begin{bmatrix} \color{r} a_{11}b_{11} \\ \color{r} a_{11}b_{21} \\ a_{21}b_{11} \\ a_{21}b_{21} \\ \end{bmatrix} $

Addition modulo 2 $\oplus$

better known as XOR

$$ \begin{array}{ccc} x & y & x \oplus y \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} $$
$0 \oplus y = y$

Qubit

"Regular computer bit is either a 1 or a 0, on or off. A quantum state can be much more complex than that, because as we know things can be both particle and wave at the same times and the uncertainty around quantum states allows us to encode more information into a much smaller computer."
 Justin Trudeu

Coin Toss

Two states: $heads$ or $tails$

$P_{heads} = \frac{1}{2}$, $P_{tails} = \frac{1}{2}$

$P_{heads} + P_{tails} = 1$

$toss = \begin{cases} heads, & \text{50% of the time} \\[2ex] tails, & \text{50% of the time} \end{cases}$

QuCoin Toss

Two states: $\ket{heads}$ or $\ket{tails}$

$P_{\ket{heads}} = \frac{1}{2}$, $P_{\ket{tails}} = \frac{1}{2}$

$P_{\ket{heads}} + P_{\ket{tails}} = 1$

$M(\ket{toss}) = \begin{cases} \ket{heads}, & \text{50% of the time} \\[2ex] \ket{tails}, & \text{50% of the time} \end{cases}$

$\ket{toss} = \overset{?}{P_\ket{heads}}\ket{heads} + \overset{?}{P_\ket{tails}}\ket{tails}$

Coin vs Qucoin Toss

Coin Qucoin
States $heads, tails$ $\ket{heads}, \ket{tails}$
Toss ignored essential part
Result look at measure

Qubit

two-state quantum-mechanical system

$ \ket{\psi} = \color{b}\alpha\color{d} \ket{0} + \color{r}\beta\color{d} \ket{1} = \begin{bmatrix} \color{b}\alpha \\ \color{r}\beta \\ \end{bmatrix} $ $ = \begin{bmatrix} \color{b}\pm\sqrt{P_{\ket{0}}} \\ \color{r}\pm\sqrt{P_{\ket{1}}} \\ \end{bmatrix} $

$ \lvert\alpha\rvert^2 = P_{\ket{0}}, \lvert\beta\rvert^2 = P_{\ket{1}} $

$ \lvert\alpha\rvert^2 + \lvert\beta\rvert^2 = 1 $

$ \ket{toss} = \begin{bmatrix} \pm\sqrt{P_{\ket{heads}}} \\ \pm\sqrt{P_{\ket{tails}}} \\ \end{bmatrix} = \begin{bmatrix} \pm\sqrt{\frac{1}{2}} \\ \pm\sqrt{\frac{1}{2}} \\ \end{bmatrix} $

$\ket{0}$ and $\ket{1}$

$$ \ket{0} = \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} = 1\ket{0} + 0\ket{1} = \ket{0} $$ $$ \ket{1} = \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} = 0\ket{0} + 1\ket{1} = \ket{1} $$

More Qubits

$$ \ket{00} = \ket{0} \otimes \ket{0} = \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} \otimes \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix} $$

$$ \ket{10} = \ket{1} \otimes \ket{0} = \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix} \otimes \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \\ \end{bmatrix} $$

Quantum Logic Gates

Digital Logic Gates

And

Performs a logical operation on one or more binary inputs and produces a single binary output

A
&
A & B
B
A B A & B
0 0 0
0 1 0
1 0 0
1 1 1

Quantum Logic Gates

  • Unitary matrix
    • Preserves the norm
    • $\sum{P} = 1$
  • Reversible
    • Same number of inputs and outputs
    • $2^{n}\times2^{n}$
$\ket{\psi_1}$
$G_1$
$\ket{\psi_2}$
$\ket{x}$
$G_2$
$\ket{x'}$
$\ket{y}$
$\ket{y'}$

Not Gate

$\ket{0}$
$X$
$\ket{1}$
$ X \equiv \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} $
$ X\begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \begin{bmatrix}\beta \\ \alpha\end{bmatrix} $

Hadamard Gate

$\ket{\psi_1}$
$H$
$\ket{\psi_2}$
$ H \equiv \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} $
$ H\begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \alpha\frac{\ket{0} + \ket{1}}{\sqrt{2}} + \beta\frac{\ket{0} - \ket{1}}{\sqrt{2}} $

Hadamard Gate

Properties

$\ket{\psi}$
$H$
$H$
$\ket{\psi}$
$ \color{r}H\ket{0}\color{d} = H\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \color{r}\frac{\ket{0} + \ket{1}}{\sqrt{2}}\color{d} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} = \color{r}\ket{+}\color{d} $
$ \color{b}H\ket{1}\color{d} = H\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \color{b}\frac{\ket{0} - \ket{1}}{\sqrt{2}}\color{d} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix} = \color{b}\ket{-}\color{d} $

Quantum Computing

Deutsch's algorithm

The most useless algorithm ever

Deutsch’s algorithm determines whether

$f:\{0,1\}\rightarrow \{0,1\}$

is balanced or constant.

Constant: $f(0) = f(1)$ Balanced: $f(0) \neq f(1)$
2

The function

Classical approach

$x$
$f$
$f(x)$
Input Function
Constant Constant Balanced Balanced
$x$ $f(x) = 0$ $f(x) = 1$ $f(x) = 0 \oplus x$ $f(x) = 1 \oplus x$
$0$ $0$ $1$ $0$ $1$
$1$ $0$ $1$ $1$ $0$

The function

Quantum attempt for constant

$\ket{x}$
$$ U_f = \begin{bmatrix} 0 & 0\\ 1 & 1\\ \end{bmatrix} $$
$\ket{1}$

$$ U_f\ket{0} = \begin{bmatrix} 0 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} $$

$$ U_f\ket{1} = \begin{bmatrix} 0 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} $$

$$ \begin{align} U_f U_{f}^T & = \begin{bmatrix} 0 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} 0 & 1\\ 0 & 1\\ \end{bmatrix} \\ & = \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \neq I \\ \end{align} $$

2

The function

Quantum attempt for balanced

$f(x) = 0 \oplus x$

$\ket{x}$
$\ket{x}$

$f(x) = 1 \oplus x$

$\ket{x}$
$X$
$\ket{1 \oplus x}$
1

The Oracle

Confused Travolta
David Deutsch
$x$
$x$
$y$
$y \oplus f(x)$
$U_f$
$$ U_f = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$
$$ U_f^TU_f = I $$

Deutsch's algorithm circuit

$\ket{0}$
$H$
$x$
$x$
$y$
$y \oplus f(x)$
$U_f$
$H$
$\ket{0}$
$\ket{0}$
$X$
$H$
$\ket{0}$
$\ket{0}$
$H$
$x$
$x$
$y$
$y \oplus f(x)$
$U_f$
$H$
$\ket{0}$
$X$
$H$
$\uparrow\psi_0$
$\uparrow\psi_1$
$\uparrow\psi_2$
$\uparrow\psi_3$
$\uparrow\psi_4$
$\uparrow\psi_5$

Initialization

$\ket{\Psi_0} = \ket{0} \ket{0}$

Qubit flip

$\ket{\Psi_1} = \ket{0} \ket{1}$

Superposition

$ \ket{\Psi_2} = \frac{1}{2} \left( \ket{0}\ket{0} - \ket{0}\ket{1} + \ket{1}\ket{0} - \ket{1}\ket{1} \right) $

Evaluation

$ \ket{\psi_3} = \frac{1}{2} ( \ket{0} \ket{f(0)} - \ket{0} \ket{1 \oplus f(0)} + \ket{1} \ket{f(1)} - \ket{1} \ket{1 \oplus f(1)} ) $

Evaluation / Case 1: constant $f(x)$

$\ket{\psi_3} = \frac{1}{2} \bigl( \ket{0}$ $\ket{f(0)}$ $- \ket{0}$ $\ket{1 \oplus f(0)}$ $+ \ket{1}$ $\ket{f(0)}$ $- \ket{1}$ $\ket{1 \oplus f(0)}$ $ \bigr) $

$ = \frac{1}{2} \Bigl[ $ $\bigl(\ket{0} + \ket{1}\bigr)$ $\otimes \color{r}\ket{f(0)}\color{d} -$ $\bigl(\ket{0} + \ket{1}\bigr)$ $ \otimes \color{b}\ket{1 \oplus f(0)}\color{d} \Bigr] $

$= \frac{1}{2} \Bigl[ \color{g}\bigl( \ket{0} + \ket{1} \bigr) \color{d} \otimes \bigl( \color{r}\ket{f(0)}\color{d} - \color{b}\ket{1 \oplus f(0)}\color{d} \bigr) \Bigr] $

$= \frac{1}{\sqrt{2}} \ket{+} \otimes \bigl(\color{r}\ket{f(0)}\color{d} - \color{b}\ket{1 \oplus f(0)}\color{d}\bigr)$

Evaluation / Case 2: balanced $f(x)$

$ \ket{\psi_3} = \frac{1}{2} \bigl( \ket{0} $$\ket{f(0)}$$ - \ket{0} $$\ket{f(1)}$$ + \ket{1} $$\ket{f(1)}$$ - \ket{1} $$\ket{f(0)}$$ \bigr) $

$ = \frac{1}{2} \Bigl[ $$\bigl(\ket{0} - \ket{1}\bigr)$$ \otimes \color{r}\ket{f(0)}\color{d} - $$\bigl(\ket{0} - \ket{1}\bigr)$$ \otimes \color{b}\ket{f(1)}\color{d} \Bigr] $

$ = \frac{1}{2} \Bigl[ \color{g} \bigl( \ket{0} - \ket{1} \bigr) \color{d} \otimes \bigl( \color{r}\ket{f(0)}\color{d} - \color{b}\ket{f(1)}\color{d} \bigr) \Bigr] $

$ = \frac{1}{\sqrt{2}} \color{g}\ket{-}\color{d} \otimes \bigl( \color{r}\ket{f(0)}\color{d} - \color{b}\ket{f(1)}\color{d} \bigr) $

Back to normal

Constant: $$ \ket{\psi_3} = \frac{1}{\sqrt{2}} \ket{+} \otimes ( \ket{f(0)\rangle - |1 \oplus f(0)} ) $$ $$ \ket{\psi_4} = \frac{1}{\sqrt{2}} \ket{0} \otimes (\ket{f(0)\rangle - |1 \oplus f(0)}) $$ Balanced: $$ \ket{\psi_3} = \frac{1}{\sqrt{2}} \ket{-} \otimes ( \ket{f(0)\rangle - |f(1)} ) $$ $$ \ket{\psi_4} = \frac{1}{\sqrt{2}} \ket{1} \otimes (\ket{f(0)\rangle - |f(1)}) $$

Measurement

Constant:

$ \ket{\psi_4} = \frac{1}{\sqrt{2}} $$\ket{0}$$ \otimes (\ket{f(0)\rangle - |1 \oplus f(0)}) $

Balanced:

$ \ket{\psi_4} = \frac{1}{\sqrt{2}} $$\ket{1}$$ \otimes (\ket{f(0)\rangle - |f(1)}) $

What's next

The Deutsch-Josza algorithm

$\ket{0}$
$H$
$U_f$
$H$
$\ket{0}$
$H$
$H$
$\vdots$
$\vdots$
$\vdots$
$\ket{0}$
$H$
$H$
$\ket{1}$
$H$
Approach # of Queries
Digital $2^{(n-1)} + 1$
Quantum $1$

Exponential speedup

Q&A

Useful Materials

Internet

Book

Slides