Introduction to Quantum Computing¶
Ludovic Noirie
2019/09/25
http://ludovic-noirie.fr/sciences/quantum-computing
Outline¶
Outline, Sources, Python libraries, Web sites
Quantum Mechanics
Quantum Computers and Qubits
Quantum Logic Gates
Quantum Algorithms
Quantum Computers in Reality
Short version: "slides" only (horizontal navigation)
Long version: "slides" + "sub-slides" (horizontal + vertical navigation)
$\ $
Look at sub-slides for sources, Python libraries and web sites
Sources of this notebook¶
Quantum mechanics
Jean-Louis Basdevant's lecture I followed when I was student:
$[$Bas1993$]$ J.-L. Basdevant: Mécanique Quantique. École Polytechnique, 1993.
Quantum computers
Essentially some Wikipedia pages:
https://en.wikipedia.org/wiki/Quantum_computing
https://en.wikipedia.org/wiki/Qubit
https://en.wikipedia.org/wiki/Quantum_register
https://en.wikipedia.org/wiki/Quantum_logic_gate
https://en.wikipedia.org/wiki/Quantum_Fourier_transform
https://en.wikipedia.org/wiki/Quantum_algorithm
Ronald de Wolf's lecture notes:
$[$Wol2019$]$ R. de Wolf: Quantum Computing - Lecture Notes. QuSoft, CWI and University of Amsterdam, 2019.
https://homepages.cwi.nl/~rdewolf/qcnotes.pdf
Other sources are given in the slides.
Python libraries for quantum processing¶
To illustrate what quantum computers can do in this notebook, I used the ProjectQ Python library: https://projectq.readthedocs.io/en/latest/index.html.
Github: https://github.com/projectq-framework/ProjectQ
Installation:
python -m pip install projectq
The setup will try to build a C++-Simulator, which is much faster than the Python implementation.
If it fails:
python -m pip install --global-option=--without-cppsimulator projectq
import numpy as np
import projectq.ops as QG
import projectq.libs.math as QM
# [not working] import projectq.libs.revkit as QO
from projectq import MainEngine
# create a main compiler engine
QC = MainEngine()
LaTeX librairy for quantum circuit drawing¶
Quantum gate drawing using LaTeX with https://github.com/CQuIC/qcircuit
LaTeX $\Rightarrow$ PDF $\Rightarrow$ PNG
Quantum computers on web sites¶
https://wybiral.github.io/quantum/
by Davy Wybiral with contributions of Jiman Hwang.
A simple and intuitive quantum circuit simulator designed with a friendly GUI (drag-and-drop), up to 10 qubits.
https://algassert.com/quirk
by Craig Gidney.
A more complete quantum circuit simulator with drag-and-drop, up to 16 qubits.
http://www.quantumplayground.net/#/home
by a group of Google engineers.
It simulate quantum registers up to 22 qubits, and uses its own scripting language with debugging and 3D quantum state visualization features.
https://quantumexperience.ng.bluemix.net/qx/editor
by IBM, need to sign in.
A simulator and also a real quantum computer with 5 qubits, using an IMB Q device made of 5-qubits publically available.
GUI with drag-and-drop for the design of the circuit.
Quantum Mechanics¶
Postulates of Quantum Mechanics
Quantum Mechanics interpretation ?
$\ $
You can skip this par in a first step and go back after (some people may be lost with Hilbert spaces, operators on Hilbert spaces and tensor products).
To see the content: look at the sub-slides
Postulates of Quantum Mechanics¶
The following formulation of the Quantum Mechanics postulates are the English translation of the following source:
$[$Bas1993$]$ J. L. Basdevant : Mécanique Quantique. École Polytechnique, 1993.
Note: $[text]$ indicates that $text$ is not in the postulate wording, but it has been added for clarification. Texts in italic are additional comments.
First Postulate $[$ Superposition principle $]$¶
The state of a system is completely defined, at each time, by an element $\left|\psi\left(t\right)\right\rangle$ of the appropriate Hilbert space $\mathcal{E}_{H}$ $[$ on complex numbers, with the Hermitian form $\left\langle\,\cdot\,\right.\left|\,\cdot\,\right\rangle\,:\,\left(\varphi,\psi\right) \rightarrow \left\langle \varphi \right.\left| \psi \right\rangle$$]$.
Usually, the element $\left|\psi\left(t\right)\right\rangle$ is chosen to be normalized: $\left\langle \psi\left(t\right) \right.\left| \psi\left(t\right) \right\rangle=1$. But in fact, the state of a system is completely defined by a ray of the Hilbert space $\mathcal{E}_{H}$, as the note in $[$Bas1993, tome 1, §V.4.2, p. 121$]$ says that two colinear and non-null vectors represent the same state, and the propability computation of the second postulat on measurement can be rewritten with renormalisation by the noms of the potentially non-unitary vectors. So it is more correct to say that the state of a system is completely defined, at each time, by an element of the projective space $\mathrm{\textbf{P}}\left(\mathcal{E}_{H}\right)$ of the appropriate Hilbert space $\mathcal{E}_{H}$.
Second Postulate on the measure¶
$[$ Observable : $]$
A self-adjoint linear operator $\hat{A}$ $[$ i.e., $\hat{A}^\dagger := \,^t \hat{A}^{\star} = \hat{A}$ $]$ acting in $\mathcal{E}_{H}$ is associated to any physical quantity $A$: $\hat{A}$ is the observable representing the physical quantity $A$.
$[$ Quantization principle : $]$
If $\left|\psi\right\rangle$ is the state of a system at the time we measure the physical quantity $A$, whatever $\left|\psi\right\rangle$, the only possible results are the eigenvalues $a_\alpha$ of the observable $\hat{A}$.
$[$ Spectral decomposition principle : $]$
If $\left|\psi\right\rangle$ is the state of a system, the probability to find the value $a_\alpha$ in a measurement of $A$ is: $$ \mathrm{Prob} \left(a_\alpha\right) = \sum_{r_\alpha=1}^{n_\alpha} \left|\left\langle \alpha,r_\alpha \right.\left| \psi \right\rangle\right|^2 \ \left[= \left(1 / \left\|\psi_\alpha\right\| \right) \left|\left\langle \psi_\alpha \right.\left| \psi \right\rangle\right|^2 \right]. $$
$[$ Wave function collapse : $]$
The state of a system immediately after a measurement giving the value $a_\alpha$ is $\left| \psi_\alpha\right\rangle / \left\|\psi_\alpha\right\|$.
The following notations are not in the wording of the second postulate but in the discussions in $[$Bas1993, tome 1, chapitre V, p. 122$]$:
- $\left( \left|\alpha,r_\alpha\right\rangle \right)_{1 \leq r_\alpha \leq n_\alpha}$ is an orthonormal basis of the eigenspace $\mathcal{E}_{\alpha}$ corresponding to the eigenvalue $a_\alpha$ of the observable $\hat{A}$.
- The state $\left| \psi_\alpha \right\rangle$ is the projection of the state $\left|\psi\right\rangle$ on $\mathcal{E}_{\alpha}$: $$ \left| \psi_\alpha \right\rangle = \sum_{r_\alpha=1}^{n_\alpha} \left|\alpha,r_\alpha\right\rangle \left\langle \alpha,r_\alpha \right. \left|\psi\right\rangle. $$
The observable $\hat{A}$ can be written in the eigen vector basis:
$$\hat{A} = \sum_{\alpha = 1}^{n_A} a_\alpha \sum_{r_\alpha=1}^{n_\alpha} \left|\alpha,r_\alpha\right\rangle \left\langle \alpha,r_\alpha \right|$$
Third Postulate on the evolution $[$ Schrödinger equation $]$¶
If $\left|\psi\left(t\right)\right\rangle$ is the state of a system at time $t$, while the system is not observed, its evolution with time follows the equation: $$ i \hslash \frac{d}{dt} \left|\psi\left(t\right)\right\rangle = \hat{H} \left|\psi\left(t\right)\right\rangle, $$ where $\hat{H}$ is the energy observable or Hamiltonian of the system.
The evolution is unitary, because the hermitian product of two state vectors solutions remains constant. Proof:
$ \begin{array}{rcl} \frac{d \left\langle\psi_2\right. \left|\psi_1\right\rangle }{dt} &=& \frac{d \left\langle\psi_2\right| }{dt} \left|\psi_1\right\rangle + \left\langle\psi_2\right| \frac{d \left|\psi_1\right\rangle }{dt} \\ &=& \frac{1}{-i\hslash} \left\langle\psi_2\right| \hat{H}^\dagger \left|\psi_1\right\rangle + \frac{1}{i\hslash} \left\langle\psi_2\right| \hat{H} \left|\psi_1\right\rangle \\ &=& \frac{1}{i\hslash} \left\langle\psi_2\right| \left(\hat{H}-\hat{H}^\dagger\right) \left|\psi_1\right\rangle = 0. \end{array}$
This means that any orthonormal basis is transformed into another orthonormal basis, i.e., $\left|\psi\left(t\right)\right\rangle = U\left(t\right) \left|\psi\left(0\right)\right\rangle$ with $U\left(t\right)^\dagger U\left(t\right) = I$.
If $\hat{H}$ does not depend on time $t$, $U\left(t\right) = e^{-\frac{i t}{\hslash} \hat{H}} = \sum_{k=0}^{\infty} \left(-\frac{it}{\hslash}\right)^k \hat{H}^k$.
In fact, the unitary evolution implies the form of the Schrödinger equation.
Proof:
(H1) Suppose that the evolution is unitary, i.e., it conserves the hermitian product,
which is equivalent to:
1) The evolution is a linear transformation,
2) It transforms unitary vectors into unitary vectors.
Then the evolution with time $t$ of the state representation must be written
$\left|\psi\left(t\right)\right\rangle = U\left(t\right) \left|\psi\left(0\right)\right\rangle$,
with a unitary operator $U\left(t\right)$, i.e.,
$U\left(t\right)^\dagger U\left(t\right) = U\left(t\right) U\left(t\right)^\dagger = I$.
Thus we also have
$\left|\psi\left(0\right)\right\rangle = U^\dagger\left(t\right) \left|\psi\left(t\right)\right\rangle$.
(H2) Suppose that $U\left(t\right)$ is differentiable.
The equation $U\left(t\right)^\dagger U\left(t\right) = U\left(t\right) U\left(t\right)^\dagger = I$ of (H1) gives with (H2) $\frac{d U\left(t\right)}{dt} U\left(t\right)^\dagger = - U\left(t\right) \frac{d U^\dagger\left(t\right)}{dt}$.
If one writes $H\left(t\right) = i \hslash \frac{d U\left(t\right)}{dt} U^\dagger\left(t\right)$ then $H\left(t\right)$ is hermitian, because $H^\dagger\left(t\right) = -i \hslash U\left(t\right) \frac{d U^\dagger\left(t\right)}{dt} = i \hslash \frac{d U\left(t\right)}{dt} U\left(t\right)^\dagger = H\left(t\right)$.
The equation $\left|\psi\left(t\right)\right\rangle = U\left(t\right) \left|\psi\left(0\right)\right\rangle$
gives with (H2)
$\frac{d \left|\psi\left(t\right)\right\rangle}{dt}
= \frac{d U\left(t\right)}{dt} \left|\psi\left(0\right)\right\rangle
= \frac{d U\left(t\right)}{dt} U^\dagger\left(t\right) \left|\psi\left(t\right)\right\rangle
= \frac{1}{i \hslash} H\left(t\right)\left|\psi\left(t\right)\right\rangle$,
which gives the Schrödinger equation:
$i \hslash \frac{d}{dt} \left|\psi\left(t\right)\right\rangle = H\left(t\right) \left|\psi\left(t\right)\right\rangle$, with $H\left(t\right)$ hermitian.
$H\left(t\right)$ is thus an observable.
(H3) Suppose that, for a isolated system, an orthonormal basis $\left|\varphi_k\right\rangle$ of time-invariant states exists (only the phase may change, because it is not observable, true states being rays).
This means that if $\left|\psi\left(0\right)\right\rangle = \left|\varphi_k\right\rangle$ then $\left|\psi\left(t\right)\right\rangle = e^{-i \theta\left(t\right)} \left|\varphi_k\right\rangle$ and $H\left(t\right) \left|\psi\left(t\right)\right\rangle = i \hslash \frac{d}{dt} \left|\psi\left(t\right)\right\rangle = \hslash \theta'\left(t\right) e^{-i \theta\left(t\right)} \left|\varphi_k\right\rangle$ , which implies $H\left(t\right) \left|\varphi_k\right\rangle = \hslash \theta'\left(t\right) \left|\varphi_k\right\rangle$.
Thus $\left|\varphi_k\right\rangle$ is an eigenvector of the observable $H\left(t\right)$ with eigenvalue (measure) $E_k \left(t\right) = \hslash \theta'\left(t\right)$.
(H4) Suppose that, for a isolated system, the associated measured are also time-invariant: $E_k \left(t\right) = E_k$. Let's call them 'energies'.
Then the observable $H\left(t\right) = H = \sum_k E_k \left|\varphi_k\right\rangle \left\langle\varphi_k\right|$ is the observable of 'energy'.
The superposition of 'energy' eigen vectors is generally not invariant:
If
$\left|\psi\left(0\right)\right\rangle = \sum \sqrt{P_k} \left|\varphi_k\right\rangle$
then
$\left|\psi\left(t\right)\right\rangle = \sum \sqrt{P_k} e^{-i E_k t / \hslash} \left|\varphi_k\right\rangle$.
But 'energy' is conserved: the probability of measuring $E_k$ is time-invariant and equal to $P_k$.
Source of inspiration: video "Schrodinger equation - Derivation and how to use it" on "Looking Glass Universe" YouTube chain https://www.youtube.com/watch?v=DEgWbrMv6-k.
$[$ Fourth Postulate on composed systems - Tensor product $]$¶
We postulate that a system with $N$ degrees of freedom is described in the tensor product Hilbert space of the respective Hilbert spaces in which are described these $N$ degrees of freedom.
This postulate is not as explicit as the other ones in $[$Bas1993, tome 1, §V$]$. This is a simple sentence in $[$Bas1993, tome 1, §V.6, p. 126$]$. The notion of composed system correspond exactely to the concept of degrees of freedom of the global system, each subsystem beeing one degree of freedom.
If each subsystem $S_k$ is described by the Hilbert space $\mathcal{H}_{S_k}$ then the full system $S$ is described by the tensor product $\mathcal{H}_{S} = \otimes_{k=1}^{N} \mathcal{H}_{S_k} = \mathcal{H}_{S_1} \otimes \cdots \otimes \mathcal{H}_{S_N}$.
States that can be written $\left|\psi\right\rangle = \otimes_{k=1}^{N} \left|\psi_k\right\rangle = \left|\psi_1\right\rangle \otimes \cdots \otimes \left|\psi_N\right\rangle$ are separable states. All the other states are entangled states.
Tensor product:
$\left|\psi\right\rangle = \otimes_{k=1}^{N} \left(\Sigma_{l=1}^{n_k} x_{k,l}\left|\varphi_{k,l}\right\rangle \right)
= \sum_{\left(1 \leq l_k \leq n_k\right)_{1 \leq k \leq N}} \left( \prod_{k=1}^{N} x_{k,l_k} \right) \left( \otimes_{k=1}^{N} \left|\varphi_{k,l}\right\rangle \right) $
About entanglement: Schmidt decomposition theorem
$\mathcal{H}_{S_A}$ and $\mathcal{H}_{S_B}$ are two Hilbert spaces of finite dimensions $n_A$ and $n_B$. We consider the tensor product $\mathcal{H}_{S} = \mathcal{H}_{S_A} \otimes \mathcal{H}_{S_B}$.
Then, for any quantum state $\left|\psi\right\rangle \in \mathcal{H}_{S}$, one can find an orthonormal basis $\left|\alpha_{i}\right\rangle$ with $1 \leq i \leq n_A$, for $\mathcal{H}_{S_A}$, an orthonormal basis $\left|\beta_{i}\right\rangle$ with $1 \leq i \leq n_B$, for $\mathcal{H}_{S_B}$, and $m$ strictly positive real values $\lambda_i$ with $1 \leq i \leq m \leq min\left\{n_A,n_B\right\}$, such as:
$\left|\psi\right\rangle = \sum_{i=1}^{m} \lambda_i \left|\alpha_i\right\rangle \otimes \left|\beta_i\right\rangle$.
$\left|\psi\right\rangle$ being a quantum state, we have $\sum_{i=1}^{m} \lambda_i^2 = 1$.
Proof:
The Schmidt decomposition is essentially a restatement of the singular value decomposition in a different context...
Separable vs. entangled states:
For separable states, $m=1$, and for entangled states, $m>1$.
Quantum Mechanics interpretation ?¶
This part can be skipped: For Quantum Computing, one does not need to "understand" Quantum Mechanics but just needs to know the formalism.
Two papers that makes me "better understand" Quantum Mechanics:
$[$Rov1996$]$ C. Rovelli: Relational quantum mechanics. International Journal of Theoretical Physics, 35:1637–1678, 1996.
https://arxiv.org/abs/quant-ph/9609002.
$[$Woo1981$]$ W. K. Wootters: Statistical distance and Hilbert space. Physical review D, 23(2):357–362, 1981.
https://doi.org/10.1103/PhysRevD.23.357.
Relational Quantum Mechanics $[$Rov1996$]$¶
See also https://en.wikipedia.org/wiki/Relational_quantum_mechanics.
Quantum mechanics is a theory about the physical description of physical systems relative to other systems, and this is a complete description of the world.
This means that the state of a system is relative to the observer. A quantum state encodes the information an observer has about the observed system.
$[$Rov1996$]$ is also a tentative of Quantum Mechanics reconstruction
Postulate 1: There is a maximum amount of relevant information that may be obtained from a quantum system.
Postulate 2: It is always possible to obtain new information from a system.
This means that probabilities are natural. Observation is information retrieving for the observer, and information means probabilities (see Shannon's theory of information).
Relational Quantum Mechanics (RQM) "solves" quantum paradoxes: Schrödinger's cat¶
$[$Sch1935$]$ E. Schrödinger: Die gegenwärtige Situation in der Quantenmechanik (The present situation in quantum mechanics). Naturwissenschaften, 23(48):807–812, 1935.
https://doi.org/10.1007%2FBF01491891.
Is the cat dead or alive? With RQM, it depends on the observer:
An observer who is outside the box does not know and encodes his/her knowledge in a superposition (dead + alive) state.
An observer who is inside the box makes the measurement so he/she knows and encodes his/her knowledge in a separable (dead or alive, depending on the measurement result) state.
Relational Quantum Mechanics (RQM) "solves" quantum paradoxes: Einstein-Podolsky-Rosen paradox¶
$[$EPR1935$]$ A. Einstein, B. Podolsky and N. Rosen, "Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?" Phys. Rev., 47(10):777-780, 1935.
https://doi.org/10.1103/PhysRev.47.777.
Absolute realism, locality of interactions and completeness of Quantum Mechanics are incompatible.
- EPR conclusion: Quantum Mechanics is incomplete, because absolute realism and locality (Special Relativity theory) must hold.
- Mainstream current conclusion: Locality does not holds, because of Bell's inequality violation (Alain Aspect's experiments).
- RQM conclusion: Absolute realism does not hold, because quantum states are relative to the observer.
$[$SR2007$]$ M. Smerlak and C. Rovelli: Relational: EPR. Found. Phys., 37(3):427-445, 2007. https://arxiv.org/abs/quant-ph/0604064.
Statistical distance $[$Woo1981$]$¶
i) Statistical distance between probability vectors
ii) Statistical distance between quantum states
Statistical distance between probability vectors $[$Woo1981$]$¶
We consider the probability space $P_n = \left\{ \left(p_i\right)_{1 \leq i \leq n} \in \left[0,1\right]^n | \sum_{i=1}^{n} p_i = 1 \right\}$.
We consider two probability vectors $p \in P_n$ and $q \in P_n$, and $C_n\left(p,q\right)$ the set of curves on $P_n$ starting at $p$ and ending at $q$.
We fix $N \in \mathbb{N}$. We note $nb\left(p,q,N,c\right)$ the minimal number of probability vectors "statistically distinguishable" in $N$ trials that covers the curve $c \in C_n\left(p,q\right)$.
Question:
When can we say that two probability vectors are "statistically distinguishable" in $N$ trials?
Distinguishability angular diameter around a probability vector:
If the expected frequencies are $p = \left(p_i\right)_{1 \leq i \leq n}$ and the measured frequencies are $\hat{p} = \left(\hat{p}_i\right)_{1 \leq i \leq n}$ with $\hat{p}_i = p_i + \Delta p_i$, the probability distribution to observe $p'$ is the multinomial distribution $\mathrm{Prob}\left(\hat{p}\right) = \frac{N!}{\prod_{i=1}^{n}\left(\hat{p}_i N\right)!}\prod_{i=1}^{n} p_i^{\hat{p}_i N}$.
When $N \rightarrow \infty$, $y = N \sum_{i=1}^{n} \frac{\Delta p_i^2}{p_i}$ follows a $\chi^2$ distribution with $n-1$ degrees of liberty.
The angle $\theta$ between the unitary vectors $p' = \left(\sqrt{p_i}\right)_{1 \leq i \leq n}$ and $\hat{p}' = \left(\sqrt{\hat{p}_i}\right)_{1 \leq i \leq n}$ verifies $\cos \theta = \sum_{i=1}^{n} \sqrt{p_i \hat{p}_i} = \sum_{i=1}^{n} p_i \sqrt{1+\frac{\Delta p_i}{p_i}}$.
When $N \rightarrow \infty$, $\frac{\Delta p_i}{p_i} \rightarrow 0$ and $1 - \cos \theta \rightarrow \theta^2/2$, thus $\theta^2/2 \approx 1 - \sum_{i=1}^{n} p_i \left(1+\frac{1}{2}\frac{\Delta p_i}{p_i}-\frac{1}{8}\frac{\Delta p_i^2}{p_i^2}\right) = \frac{y}{8N}$.
Finally $\theta^2 \approx \frac{y}{4N}$ and $\mathbb{E}\left(\theta^2\right) \approx \frac{n-1}{4N}$.
We can define the distinguishable diameter around the probability vector $p$ after $N$ trials by:
$$\Delta \theta \left( p, N \right) \sim 2 \sqrt{\mathbb{E}\left(\theta^2\right)} \rightarrow \Delta \theta \left( n, N \right) = \sqrt{\frac{n-1}{N}}.$$
Definition:
The statistical distance $\theta_W \left(p,q\right)$ between two probability vectors $p \in P_n$ and $q \in P_n$ measure the distinguishability between these two probability vectors: $$\theta_W \left(p,q\right) = \inf_{c \in C_n\left(p,q\right)} \lim_{N \rightarrow \infty} nb\left(p,q,N,c\right) \times \Delta \theta \left( n, N \right).$$
Theorem:
The statistical distance $\theta_W \left(p,q\right)$ between two probability vectors $p \in P_n$ and $q \in P_n$ is equal to the angle between the unitary vectors $p' = \left(\sqrt{p_i}\right)_{1 \leq i \leq n}$ and $q' = \left(\sqrt{q_i}\right)_{1 \leq i \leq n}$: $$\theta_W \left(p,q\right) = \arccos\left(p' \cdot q'\right) = \arccos\left(\sum^{n}_{i=1}\sqrt{p_i q_i}\right).$$
Statistical distance between quantum states $[$Woo1981$]$¶
We consider the finite Hilbert space $\mathcal{E}_{H} = \mathbb{C}^n$ of dimension $n$.
We consider two quantum states $\psi$ and $\varphi$ represented by the two unitary vectors $\left|\psi\right\rangle \in \mathbb{C}^n$ and $\left|\varphi\right\rangle \in \mathbb{C}^n$.
We note $\left( \left|\alpha_i\right\rangle \right)_{1,n_\alpha}$ the orthonormal basis representing the possible quantum states after a given complete measurement $A$ and $\Omega$ the set of all possible complete measurements. Any orthonormal basis represents at least one possible complete measurement $A \in \Omega$.
We note $A_\psi$ a complete measurement such as $\left|\alpha_1\right\rangle = \psi$ and $A_\varphi$ a complete measurement such as $\left|\alpha_1\right\rangle = \varphi$.
Definitions:
The statistical distance between quantum states $\psi$ and $\varphi$ relatively to the measurement $A$ is the statistical distance of between the corresponding probability vectors: $$\theta_A \left( \psi, \varphi \right) = \theta_W \left( \left(\left|\left\langle \alpha_i\right.\left| \psi \right\rangle\right|^2\right)_{1 \leq i \leq n}, \left(\left|\left\langle \alpha_i\right.\left| \varphi \right\rangle\right|^2\right)_{1 \leq i \leq n} \right).$$
The absolute statistical distance between quantum states $\psi$ and $\varphi$ is the maximal value of the relative statistical distances: $$\theta \left( \psi, \varphi \right) = \sup_{A \in \Omega} \theta_A \left( \psi, \varphi \right).$$
Theorem:
The absolute statistical distance between quantum states $\psi$ and $\varphi$ is reached when $A = A_\psi$ or $A = A_\varphi$ and is equal to the angle between the two rays representing the two quantum states $\psi$ and $\varphi$: $$\theta \left( \psi, \varphi \right) = \arccos\left( \left| \left\langle \psi \right.\left| \varphi \right\rangle \right| \right).$$
Quantum Computers and Qubits¶
Generic Quantum Computer system
Qubits
Quantum registers
Generic Quantum Computer system¶
A quantum computer is simply a quantum system $S$ obeying the laws of Quantum Mechanics
Like a classical computer, the usage of a quantum computer can be divided in 4 steps:
(1) Initial register value = Input quantum system state
(2) Quantum processing = Interactions inside the quantum system
(3) Final register value = Output quantum system state
(4) Measurement of the final register value = Observable outcomes
(1) Initial register value = Input quantum system state (complex vector)
$$\left| \psi_{in} \right\rangle = \left| \psi_{input} \right\rangle \otimes \left| \psi_{internal} \right\rangle \in \mathcal{H}_{S} = \mathcal{H}_{input} \otimes \mathcal{H}_{internal}$$$\ $
$\bullet$ Hilbert spaces (complex vector spaces) $\mathcal{H}_{input} = \mathcal{H}_{a} = \mathbb{C}^{N_a}$ and $\mathcal{H}_{internal} = \mathcal{H}_{b} = \mathbb{C}^{N_b}$
$\bullet$ Tensor product of Hilbert spaces
$\mathcal{H}_S = \mathcal{H}_a \otimes \mathcal{H}_b = \mathbb{C}^N$ with $N = N_a N_b$
Note: $\mathcal{H}_a \times \mathcal{H}_b \subset \mathcal{H}_a \otimes \mathcal{H}_b$
but $\mathcal{H}_a \times \mathcal{H}_b \neq \mathcal{H}_a \otimes \mathcal{H}_b$
$\bullet$ Separable input state (tensor product of complex vectors)
$\left|\psi_{in}\right\rangle = \left(\Sigma_{k=1}^{N_{a}} x^{(a)}_k \left|\varphi^{(a)}_k\right\rangle \right) \otimes \left(\Sigma_{l=1}^{N_{b}} x^{(b)}_l\left|\varphi^{(b)}_l\right\rangle \right)
= \sum_{k = 1}^{N_a} \sum_{l = 1}^{N_b}
x_{k,l} \left|\varphi^{(a)}_k\right\rangle \otimes \left|\varphi^{(b)}_l \right\rangle$
with $x_{k,l}=x^{(a)}_k x^{(b)}_l$
for $\left|\psi_{in}\right\rangle \in \mathcal{H}_a \times \mathcal{H}_b$
$\bullet$ Generic (separable or entangled) input state:
$\left|\psi\right\rangle = \sum_{k = 1}^{N_a} \sum_{l = 1}^{N_b} x_{k,l} \left|\varphi^{(a)}_k\right\rangle \otimes \left|\varphi^{(b)}_l \right\rangle = \sum_{i = 1}^{N} x_i \left|\varphi_i\right\rangle$
$\bullet$ Hermitian product $\left\langle \varphi | \psi\right\rangle = \sum_{i = 1}^N y^*_{i} x_{i}$
(2) Quantum processing = Interactions inside the quantum system = Unitary evolution according to Schrödinger equation
$$\left| \psi_{out} \right\rangle = U_{program} \left| \psi_{in} \right\rangle$$$\ $
$\bullet$ Unitary operator (unitary square matrix with complex numbers) = Quantum logic gate:
$U_{program} = U \in \mathbb{C}^{N^2}$ with $U^\dagger U = I$, $U^\dagger = \,^t U^*$
$\bullet$ Linearity: $U \sum_{i = 1}^{N} x_i \left|\varphi_i\right\rangle = \sum_{i = 1}^{N} x_i U \left|\varphi_i\right\rangle$
$\bullet$ Quantum serial processing = Matrix multiplication: $U = U_{t} \times U_{t-1} \times \cdots \times U_{2} \times U_{1}$
$\bullet$ Quantum parallel processing = Matrix tensor product on $\mathcal{H}_S = \mathcal{H}_a \otimes \mathcal{H}_b$: $U = U^{(a)} \otimes U^{(b)}$
$\left(U^{(a)} \otimes U^{(b)}\right)
\left(\left|\varphi^{(a)}_k\right\rangle \otimes \left|\varphi^{(b)}_l \right\rangle\right)
= \left(U^{(a)}\left|\varphi^{(a)}_k\right\rangle\right)
\otimes \left(U^{(b)}\left|\varphi^{(b)}_l \right\rangle\right)$
(3) Final register value = Output quantum system state:
$$\left| \psi_{out} \right\rangle \in \mathcal{H}_{S} = \mathcal{H}_{output} \otimes \mathcal{H}_{garbage}$$$\ $
$\bullet$ Hilbert spaces (complex vector spaces) $\mathcal{H}_{output} = \mathcal{H}_{a'} = \mathbb{C}^{N_{a'}}$ and $\mathcal{H}_{garbage} = \mathcal{H}_{b'} = \mathbb{C}^{N_{b'}}$
$\bullet$ Tensor product of Hilbert spaces $\mathcal{H}_S = \mathcal{H}_{a'} \otimes \mathcal{H}_{b'}= \mathbb{C}^N$ with $N = N_{a'} N_{b'}$
$\bullet$ Generic (for almost all cases entangled) output state:
$\left|\psi\right\rangle = \sum_{k = 1}^{N_a} \sum_{l = 1}^{N_b} y_{k,l} \left|\varphi^{(a)}_k\right\rangle \otimes \left|\varphi^{(b)}_l \right\rangle$
(4) Measurement of the final register value = Observable outcomes
$\ $
$\bullet$ Hermitian observable operator $A$ (hermitian matrix $A = A^\dagger = \,^t A ^*$)
$\bullet$ Measurement on output register only: $A = A_{output} \otimes I_{garbage}$
$\bullet$ Quantum computer: observable output register states = classical bits on output register:
$\Rightarrow$ Observable $A_{output}$ = sum of projectors on classical register values $\left| y \right\rangle$ with eigenvalues $y$
$\Rightarrow$ Register measurement ($^*$): $A_{output} = \sum_{y=0}^{N_{output}-1} y \cdot \left| y \right\rangle \left\langle y \right|$
$\bullet$ Final register after measurement is an eigenvector $\left| \psi_m \right\rangle \in \left\{\lambda \cdot \left| y_m \right\rangle | \lambda \in \mathbb{C} \right\} \otimes \mathcal{H}_{garbage}$ of the measurement operator/matrix $A$ such as
$\left| \psi_m \right\rangle = \left| y_m \right\rangle \otimes \left| g\left(y_m,\psi_{out}\right) \right\rangle
= c_{norm} \cdot \left( \left| y_m \right\rangle \left\langle y_m \right| \otimes I^{\otimes n_{garbage}} \right) \left| \psi_{out} \right\rangle$
with probability $\left| \left\langle \psi_m \right. \left| \psi_{out} \right\rangle\right|^2$
$\ $
($^*$) Qubit parallel measurement ($N_{output} = 2^{n_{output}}$): $A_{output} = \sum_{y = \left(y_k\right)_{0 \leq k \leq n_{output}-1} \in \left\{0,1\right\}^{n_{output}}} \left( \otimes_{k=0}^{n_{output}-1} y_k 2^k \cdot \left| 1_k \right\rangle \left\langle 1_k \right| \right)$
Qubits¶
Qubit definition¶
The smallest non-degenerated Hilbert space is $\mathcal{H}_{2} = \mathbb{C}^2$. The elements of $\mathcal{H}_{2}$ are qubits.
The two qubits $\left| 0 \right\rangle = \left[{\begin{array}{cc} 1 \\ 0 \end{array}}\right]$ and $\left| 1 \right\rangle = \left[{\begin{array}{cc} 0 \\ 1 \end{array}}\right]$ form an orthonormal basis of $\mathcal{H}_{2}$.
The qubits (= quantum bits) are all the possible superpositions (normalized to 1).
The subset of classical bits is simply $\left\{\left| 0 \right\rangle,\left| 1 \right\rangle\right\}$: the potential measurement outcome of the (z-axis direction) spin observable observable $A_{z-spin} = 1/2 \left| 0 \right\rangle \left\langle 0 \right| - 1/2 \left| 1 \right\rangle \left\langle 1 \right|$.
For any unitary operator $U \in \mathrm{U}\left(2\right)$, i.e., such as $U^\dagger \times U = I$, $U \left| 0 \right\rangle$ and $U \left| 1 \right\rangle$ form another orthonormal basis of $\mathcal{H}_{2}$ (unitary operators = transformations between orthonormal bases).
Qubit physical realization¶
Any physical system with spin $1/2$ is a qubit, with possible measured values $1/2$ and $-1/2$.
Spin is a kind of intrinsic angular momentum of a "very small" quantum system.
$\bullet$ A system with spin $s \in 1/2 \cdot \mathbb{N}$ has the possible measurement outcomes $-s$, $-s+1$, ..., $s-1$, $s$, and $\mathcal{H}_{spin(s)} = \mathbb{C}^{2s+1}$.
$\bullet$ Bosons have spins $s \in \mathbb{N}$
$\bullet$ Fermions have spins $s \in \frac{1}{2} + \mathbb{N}$
$\bullet$ Any fundamental fermion has spin $1/2$: quarks (up $u$, down $d$, charm $c$, strange $s$, top $t$ and bottom $b$), leptons (electron $e$, muon $\mu$, tauon $\tau$ and neutrinos $\nu_{e}, \nu_{\mu}, \nu_{\tau}$), and their anti-particles $\bar{x}$.
The usual choice of a basis of states is $\left( \left| 0 \right\rangle, \left| 1 \right\rangle \right) = \left( \left| \uparrow \right\rangle, \left| \downarrow \right\rangle \right)$ (z-axis of Bloch sphere).
Other bases are for example $\left( \left| i \right\rangle, \left| -i \right\rangle\right) = \left( \left| \rightarrow \right\rangle, \left| \leftarrow \right\rangle\right)$ (y-axis of Bloch sphere) and $\left( \left| + \right\rangle, \left| - \right\rangle\right) = \left( \left| \circlearrowleft \right\rangle, \left| \circlearrowright \right\rangle \right)$ (x-axis of Bloch sphere).
Photons have spin 1, with potential values $-1$, $0$ and $1$. But because of relativistic effects (speed of light), value $0$ is forbidden. Thus a photon is also a qubit with possible values $-1$ and $1$, corresponding to left and right circular polarization of light. Another basis is the one with vertical vs. horizontal polarizations.
For polarization of photons, with $\left| \leftrightarrow \right\rangle = \left| 0 \right\rangle$ and $\left| \updownarrow \right\rangle = \left| 1 \right\rangle$, we have the following relationships:
$\left| \circlearrowright \right\rangle = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 \\ i \end{array}}\right] = \frac{1}{\sqrt{2}} \left| \leftrightarrow \right\rangle + \frac{i}{\sqrt{2}} \left| \updownarrow \right\rangle$
$\left| \circlearrowleft \right\rangle = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 \\ -i \end{array}}\right] = \frac{1}{\sqrt{2}} \left| \leftrightarrow \right\rangle - \frac{i}{\sqrt{2}} \left| \updownarrow \right\rangle$.
Bloch sphere representation of Qubit¶
Any qubit can be represented by the general form of a unitary vector in $\mathcal{H}_{2} = \mathbb{C}^2$:
$\left| \psi \right\rangle = \left( e^{i\eta} \cdot \right) \left[{\begin{array}{cc} \cos\left(\theta/2\right) \\ \sin\left(\theta/2\right) e^{i\varphi} \end{array}}\right] = \left( e^{i\eta} \cdot \right) \cos\left(\theta/2\right) \left| 0 \right\rangle + \left( e^{i\eta} \cdot \right) \sin\left(\theta/2\right) e^{i\varphi} \left| 1 \right\rangle$
with $\theta \in \left[0,\pi\right]$ and $\varphi \in \left[0,2\pi\right[$.
$\Rightarrow$ Bloch sphere physical interpretation of any qubit:
$\bullet$ Directed axis of rotation of the 1/2-spin in our physical 3D euclidian (real) space
$\bullet$ Orthogonal states being antipodal points (= same line with opposite rotations)
$\bullet$ $[$Physical meaning: Elementary fermions = qubits $\Rightarrow$ Our 3D physical space comes from qubits...$]$
See The usual choice of basis corresponds to the z-axis of Bloch sphere:
$\left| 0 \right\rangle = \left| \uparrow \right\rangle$
$\left| 1 \right\rangle = \left| \downarrow \right\rangle$
Any other pair of antipodal points in the Bloch sphere form an orthonormal basis of $\mathcal{H}_{2} = \mathbb{C}^2$.
Basis of y-axis of Bloch sphere:
$\left| i \right\rangle = \left| \rightarrow \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle + i \left| 1 \right\rangle\right)$
$\left| -i \right\rangle = \left| \leftarrow \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle - i \left| 1 \right\rangle \right)$
Basis of x-axis of Bloch sphere:
$\left| + \right\rangle = \left| \circlearrowleft \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle + \left| 1 \right\rangle \right)$
$\left| - \right\rangle = \left| \circlearrowright \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle - \left| 1 \right\rangle \right)$
Quantum registers¶
A quantum register is the association of $n$ qubits that are processed together.
A state of a quantum register is an element of the tensor product of $n$ $\mathcal{H}_{2}$:
$\left| x \right\rangle \in \mathcal{H}_{2^n}
= \mathcal{H}_{2} \otimes \cdots \otimes \mathcal{H}_{2}
= \mathcal{H}_{2}^{\otimes n} = \mathbb{C}^{2^n}$.
States $\left| x=b_{n-1} b_{n-2} \cdots b_{1} b_{0} \right\rangle = \left| b_{n-1} \right\rangle \otimes \left| b_{n-2} \right\rangle \otimes \cdots \otimes \left| b_{1} \right\rangle \otimes \left| b_{0} \right\rangle$ with $\left(b_k\right)_{1\leq k \leq n}\in \left\{0,1\right\}^n$, i.e., with $x \in \left\{0, 1, 2, \cdots, 2^n-1\right\}$, form an orthonormal basis of $\mathcal{H}_{2^n}$.
Mesuring the state of the register in this basis corresponds to get the value $x$, by measuring the values $\left| 0 \right\rangle$ or $\left| 1 \right\rangle$ for each qubit $\left| b_{k} \right\rangle$.
Complexity: $n$ qubits gives $N = 2^n$ values $x$.
$n \sim 270$ qubits $\Rightarrow$ $N \sim 2^{270} = (2^{10})^{27} \sim 10^{81} \sim $ number of atoms in the observable universe...
Quantum Logic Gates¶
Quantum logic gates for qubits
Quantum logic gates for quantum registers
Quantum registers
Quantum logic gates for qubits¶
A quantum logic gate on a qubit is any unitary operator acting on a qubit.
The set of unitary operators on qubits is $\mathrm{U}\left(2\right) = \left\{ U \in \mathbb{C}^{2 \times 2} | U^\dagger \times U = I \right\} = \left\{ U \in \mathbb{C}^{2 \times 2} | U \times U^\dagger = I \right\}$.
The generic form is $U = \left[{\begin{array}{cc} a & b \\ c & d \end{array}}\right]$ with $\left| a \right|^2 + \left| c \right|^2 = 1$, $\left| b \right|^2 + \left| d \right|^2 = 1$, and $ a \times b^* + c \times d^*= 0$ (we also have $\left| a \right|^2 + \left| b \right|^2 = 1$, $\left| c \right|^2 + \left| d \right|^2 = 1$).
So another generic form is $U = \left[{\begin{array}{cc} \cos\left(\theta/2\right) e^{i\phi_a} & -\sin\left(\theta/2\right) e^{i\phi_b} \\ \sin\left(\theta/2\right) e^{i\phi_c} & \cos\left(\theta/2\right) e^{i\phi_d} \end{array}}\right]$ with $\theta \in \left[0,\pi\right]$ and $\phi_a + \phi_d = \phi_b + \phi_c$ modulo $2\pi$.
$\ $
Look at sub-slides for the detailed description of quantum logic gates on qubits
Generic python functions used in this notebook to test quantum gates on qubits
def qubitExperiment(nbExp,gate,thProbaUnchanged):
res="Input qubit => Output qubit for "+str(nbExp)+" experiments\n"
for inputQubit in range(0,2): # Test first with |0> then with |1>
res+=str(inputQubit)+" => "
s = 0;
for i in range(0,nbExp): # Test 'nbExp' times
r = gate(inputQubit)
s+=r
res+=str(r)+" "
res+=": "+"{:>5.0%}".format(s/nbExp)+"\n"
if theoreticalProbaUnchanged>-1: # If not -1, print the theoretical values
res+="Expected probabilities: "+"{:.2%}".format(1-thProbaUnchanged)
res+=" & "+"{:.2%}".format(thProbaUnchanged)
print(res) # Print the results of all experiments
def createQubit(bit):
qubit = QC.allocate_qubit() # Create a qubit with value |0>
if bit == 1: # Change it to |1> if bit = 1
QG.X | qubit # by using the NOT gate (X)
return qubit # Return the qubit initialized to |bit>
def measureQubit(qubit):
QG.Measure | qubit # Measure the qubit
QC.flush() # Flush the Quantum Computer
return int(qubit) # Return the result of measurement
Quantum NOT¶
The quantum NOT inverts the qubits $\left| 0 \right\rangle$ and $\left| 1 \right\rangle$.
$U_{NOT} = \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right]$
$U_{NOT} \left| 0 \right\rangle = \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right] \left[{\begin{array}{cc} 1 \\ 0 \end{array}}\right] = \left[{\begin{array}{cc} 0 \\ 1 \end{array}}\right] = \left| 1 \right\rangle$
$U_{NOT} \left| 1 \right\rangle = \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right] \left[{\begin{array}{cc} 0 \\ 1 \end{array}}\right] = \left[{\begin{array}{cc} 1 \\ 0 \end{array}}\right] = \left| 0 \right\rangle$
def NOTgate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the gate NOT (=X)
QG.X | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 0
qubitExperiment(32,NOTgate,theoreticalProbaUnchanged)
Hadamard gate¶
The Hadamard gate $U_{H}$ produces uniform random qubits, which allows parallelization of operations. $U_{H}$ is hermitian and unitary, so it is a square root of the identity: $U_H \times U_H = I$.
$U_{H} = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right]$
$U_{H} \left| 0 \right\rangle = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right] \left[{\begin{array}{cc} 1 \\ 0 \end{array}}\right] = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 \\ 1 \end{array}}\right] = \frac{1}{\sqrt{2}} \left| 0 \right\rangle + \frac{1}{\sqrt{2}} \left| 1 \right\rangle$
$U_{H} \left| 1 \right\rangle = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right] \left[{\begin{array}{cc} 0 \\ 1 \end{array}}\right] = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 \\ -1 \end{array}}\right] = \frac{1}{\sqrt{2}} \left| 0 \right\rangle - \frac{1}{\sqrt{2}} \left| 1 \right\rangle$
$U_{H} \left| x \right\rangle = \frac{1}{\sqrt{2}} \left| 0 \right\rangle + \frac{\left(-1\right)^{x}}{\sqrt{2}} \left| 1 \right\rangle = \sum_{y=0}^{1} \frac{\left(-1\right)^{x y}}{\sqrt{2}} \left| y \right\rangle$
def HadamardGate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the Hadamard gate H
QG.H | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 0.5
qubitExperiment(32,HadamardGate,theoreticalProbaUnchanged)
Phase gates¶
The phase gate of phase $\phi$ rotates the phases of the qubits $\left| 0 \right\rangle$ and $\left| 1 \right\rangle$ by $\phi$.
$U_{Ph_\phi} = e^{i\phi} I = \left[{\begin{array}{cc} e^{i\phi} & 0 \\ 0 & e^{i\phi} \end{array}}\right]$
$U_{R_\phi} \left| 0 \right\rangle = \left[{\begin{array}{cc} e^{i\phi} \\ 0 \end{array}}\right] = e^{i\phi} \left| 0 \right\rangle$
$U_{R_\phi} \left| 1 \right\rangle = \left[{\begin{array}{cc} 0 \\ e^{i\phi} \end{array}}\right] = e^{i\phi} \left| 1 \right\rangle$
def PhasePi8gate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply a phase of pi/8 to all: qubits
QG.Ph(np.pi/8) | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 1
qubitExperiment(32,PhasePi8gate,theoreticalProbaUnchanged)
Phase-shift gates¶
The phase-shift gate of phase $\phi$ lets the qubit $\left| 0 \right\rangle$ unchanged and rotate the phase of the qubit $\left| 1 \right\rangle$ by $\phi$.
$U_{R_\phi} = \left[{\begin{array}{cc} 1 & 0 \\ 0 & e^{i\phi} \end{array}}\right]$
$U_{R_\phi} \left| 0 \right\rangle = \left[{\begin{array}{cc} 1 & 0 \\ 0 & e^{i\phi} \end{array}}\right] \left[{\begin{array}{cc} 1 \\ 0 \end{array}}\right] = \left[{\begin{array}{cc} 1 \\ 0 \end{array}}\right] = \left| 0 \right\rangle$
$U_{R_\phi} \left| 1 \right\rangle = \left[{\begin{array}{cc} 1 & 0 \\ 0 & e^{i\phi} \end{array}}\right] \left[{\begin{array}{cc} 0 \\ 1 \end{array}}\right] = \left[{\begin{array}{cc} 0 \\ e^{i\phi} \end{array}}\right] = e^{i\phi} \left| 1 \right\rangle$
Phase-shift on qubit $\left| 0 \right\rangle$: $U_{NOT} U_{R_\phi} U_{NOT}$.
The phase-shift gates form the subgroup $\mathrm{U}\left(1\right)$ of $\mathrm{U}\left(2\right)$:
$U_{R_{\alpha}} U_{R_{\beta}} = U_{R_{\alpha+\beta}}$,
$U_{R_{0}} = I$ and
$U_{R_{\alpha}} U_{R_{-\alpha}} = I$.
def PhaseShiftPi8gate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply a phase shift of pi/8
QG.R(np.pi/8) | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 1
qubitExperiment(32,PhaseShiftPi8gate,theoreticalProbaUnchanged)
Pauli gates¶
With $A = X$, $Y$ or $Z$, $U_A$, the Pauli matrix $U_A$ represents the rotation around the $A$-axis of the Bloch sphere by $\pi$. $U_A$ is hermitian and unitary, so they are suare root of the identity: $U_A \times U_A = I$. The three Pauli matrices with the identity form a basis for the vector space of 2 × 2 Hermitian matrices (and also the natural basis of the quaternions by multiplying the Pauli matrices by $-i$).
$U_{X} = \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right] = U_{NOT}$
$U_{Y} = \left[{\begin{array}{cc} 0 & -i \\ i & 0 \end{array}}\right] = \left[{\begin{array}{cc} 1 & 0 \\ 0 & -i \end{array}}\right] \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right] \left[{\begin{array}{cc} 1 & 0 \\ 0 & i \end{array}}\right] = U_{R_{-\pi/4}} U_{NOT} U_{R_{\pi/4}}$
$U_{Z} = \left[{\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}}\right] = U_{R_\pi}$
def Ygate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the Pauli gate Y
QG.Y | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 0
qubitExperiment(32,Ygate,theoreticalProbaUnchanged)
Rotation gates¶
With $A = X$, $Y$ or $Z$, the rotation matrix $U_{R_A\left(\theta\right)}$ represents the rotation around the $A$-axis of the Bloch sphere by $\theta$.
They are defined by the exponential of the Pauli matrices $U_A$:
$U_{R_A\left(\theta\right)} = e^{-i \theta/2 \cdot U_A} = \cos\left(\theta/2\right) I - i\sin\left(\theta/2\right)U_A$.
$U_{R_X\left(\theta\right)} = \left[{\begin{array}{cc} \cos\left(\theta/2\right) & -i\sin\left(\theta/2\right) \\ -i\sin\left(\theta/2\right) & \cos\left(\theta/2\right) \end{array}}\right]$
$U_{R_Y\left(\theta\right)} = \left[{\begin{array}{cc} \cos\left(\theta/2\right) & -\sin\left(\theta/2\right) \\ \sin\left(\theta/2\right) & \cos\left(\theta/2\right) \end{array}}\right]$
$U_{R_Z\left(\theta\right)} = \left[{\begin{array}{cc} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{array}}\right]$
We thus have $U_A = i U_{R_A\left(\pi\right)} = U_{iR_A\left(\pi\right)}$ for $A = X$, $Y$ or $Z$, $U_H = U_{R_Y\left(-\pi/2\right)}$ and $U_{R_\phi} = e^{i\phi/2} U_{R_Z\left(\phi/2\right)}$.
def RxPi3Gate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the rotation gate R with angle pi/3
QG.Rx(np.pi/3) | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = np.cos(np.pi/6)*np.cos(np.pi/6)
qubitExperiment(32,RxPi3Gate,theoreticalProbaUnchanged)
Roots of gates¶
A square root of $U_{G} \in \mathrm{U}\left(2\right)$ is any quantum gate $U_{\sqrt{G}} \in \mathrm{U}\left(2\right)$ such as $U_{\sqrt{G}} U_{\sqrt{G}} = U_{G}$.
For example, the square root of NOT is
$U_{\sqrt{NOT}} = \left[{\begin{array}{cc} \frac{1+i}{2} & \frac{1-i}{2} \\ \frac{1-i}{2} & \frac{1+i}{2} \end{array}}\right]$
because
$U_{\sqrt{NOT}} U_{\sqrt{NOT}} = \left[{\begin{array}{cc} \frac{1+i}{2} & \frac{1-i}{2} \\ \frac{1-i}{2} & \frac{1+i}{2} \end{array}}\right] \left[{\begin{array}{cc} \frac{1+i}{2} & \frac{1-i}{2} \\ \frac{1-i}{2} & \frac{1+i}{2} \end{array}}\right] = \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right] = U_{NOT}$.
A $n$-root of $U_{G} \in \mathrm{U}\left(2\right)$ is any quantum gate $U_{G^{1/n}} \in \mathrm{U}\left(2\right)$ such as $U_{G^{1/n}}^n = U_{G}$.
def SQRTNOT(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the square root NOT gate
QG.SqrtX | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 0.5
qubitExperiment(32,SQRTNOT,theoreticalProbaUnchanged)
Clifford gates¶
The Clifford Gates are:
(1) The Hadamard gate:
$U_{H} = \frac{1}{\sqrt{2}} \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right]$.
(2) The $S$ and $S^\dagger$ gates:
$U_{S} = U_{\sqrt{Z}} = U_{R_{\pi/2}} = \left[{\begin{array}{cc} 1 & 0 \\ 0 & i \end{array}}\right]$, $U_{S^\dagger} = U_{S}^\dagger = U_{R_{-\pi/2}} = \left[{\begin{array}{cc} 1 & 0 \\ 0 & -i \end{array}}\right]$.
(3) The $T$ and $T^\dagger$ gates:
$U_{T} = U_{\sqrt{S}} = U_{R_{\pi/4}} = \left[{\begin{array}{cc} 1 & 0 \\ 0 & e^{i\pi/4} \end{array}}\right]$, $U_{T^\dagger} = U_{T}^\dagger = U_{R_{-\pi/4}} = \left[{\begin{array}{cc} 1 & 0 \\ 0 & -e^{i\pi/4} \end{array}}\right]$.
def Sgate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the S gate
QG.S | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 1
qubitExperiment(32,Sgate,theoreticalProbaUnchanged)
def TdaggerGate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the T-dagger gate
QG.Tdag | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = 1
qubitExperiment(32,TdaggerGate,theoreticalProbaUnchanged)
Generic quantum logic gates for qubits¶
A generic form is:
$U = \left[{\begin{array}{cc} \cos\left(\theta/2\right) e^{i\phi_a} & -\sin\left(\theta/2\right) e^{i\phi_b}
\\ \sin\left(\theta/2\right) e^{i\phi_c} & \cos\left(\theta/2\right) e^{i\phi_d} \end{array}}\right]$
with $\theta \in \left[0,\pi\right]$ and $\phi_a + \phi_d = \phi_b + \phi_c$ modulo $2\pi$.
This can be also written:
$U = \left[{\begin{array}{cc} e^{i\gamma/2} & 0 \\ 0 & e^{i\gamma/2} \end{array}}\right]
\left[{\begin{array}{cc} e^{-i\beta/2} & 0 \\ 0 & e^{i\beta/2} \end{array}}\right]
\left[{\begin{array}{cc} \cos\left(\theta/2\right) & -\sin\left(\theta/2\right) \\ \sin\left(\theta/2\right) & \cos\left(\theta/2\right) \end{array}}\right]
\left[{\begin{array}{cc} e^{-i\alpha/2} & 0 \\ 0 & e^{i\alpha/2} \end{array}}\right]$,
i.e., $U = U_{Ph_{\gamma/2}} U_{R_Z\left(\beta\right)} U_{R_Y\left(\theta\right)} U_{R_Z\left(\alpha\right)}$,
with $\alpha = \phi_b - \phi_a$, $\beta = \phi_c - \phi_a$ and $\gamma = \phi_b + \phi_c$.
Each term can be expressed with quantum gates $U_{NOT}$, $U_{H}$ and $U_{R_{\phi}}$:
$U_{PS\left(\phi_0,\phi_1\right)} = \left[{\begin{array}{cc} e^{i\phi_0} & 0 \\ 0 & e^{i\phi_1} \end{array}}\right] = U_{NOT} U_{R_{\phi_0}} U_{NOT} U_{R_{\phi_1}}$ for any $\left(\phi_0,\phi_1\right)$;
$\begin{array}{ccl} \left[{\begin{array}{cc} \cos\left(\theta/2\right) & -\sin\left(\theta/2\right) \\ \sin\left(\theta/2\right) & \cos\left(\theta/2\right) \end{array}}\right] &=& \frac{1}{2} \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right] \left[{\begin{array}{cc} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{array}}\right] \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right] \\ &=& U_H U_{PS\left(-\theta/2,\theta/2\right)} U_H. \end{array}$
$U_{NOT}$ can also be expressed with quantum gates $U_{H}$ and $U_{R_{\phi}}$:
$\begin{array}{ccl} U_{NOT} &=& \left[{\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}}\right] \\ &=& \frac{1}{2} \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right] \left[{\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}}\right] \left[{\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}}\right] \\ &=& U_H U_{R_\pi} U_H. \end{array}$
Thus any quantum gate on qubits can be expressed as a product of Hadamard gates and phase-shift gates: they are generated by the sub-group $U(1)$ of phase-shift gates and the Hadamard gate.
def CosSinPi8Gate(bit):
# Create a qubit with value = bit (0 or 1)
qubit = createQubit(bit)
# Apply the Hadamard gate H
QG.H | qubit
# Apply a phase shift of pi/8
QG.R(np.pi/8) | qubit
# Apply the NOT gate
QG.X | qubit
# Apply a phase shift of -pi/8
QG.R(-np.pi/8) | qubit
# Apply the NOT gate
QG.X | qubit
# Apply the Hadamard gate H
QG.H | qubit
# Measure the qubit
result = measureQubit(qubit)
return result
theoreticalProbaUnchanged = np.cos(np.pi/8)*np.cos(np.pi/8)
qubitExperiment(32,CosSinPi8Gate,theoreticalProbaUnchanged)
Diagrams of 1-qubit gates¶
Explore quantum gates on qubits with:
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.qubitGate.htm
Quantum logic gates for quantum registers¶
A quantum gate on a quantum register is any unitary operator acting on a quantum register.
The set of unitary operators on quantum registers of $n$ qubits is $\mathrm{U}\left(2^n\right) = \left\{ U \in \mathbb{C}^{2^n \times 2^n} | U^\dagger \times U = I \right\} = \left\{ U \in \mathbb{C}^{2^n \times 2^n} | U \times U^\dagger = I \right\}$.
$U = \left[{\begin{array}{ccccccc} U_{0,0} & U_{0,1} & \cdots & U_{0,y} & \cdots & U_{0,2^n-2} & U_{0,2^n-1} \\ U_{1,0} & U_{1,1} & \cdots & U_{1,y} & \cdots & U_{1,2^n-2} & U_{1,2^n-1} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ U_{x,0} & U_{x,1} & \cdots & U_{x,y} & \cdots & U_{x,2^n-2} & U_{x,2^n-1} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ U_{2^n-2,0} & U_{2^n-2,1} & \cdots & U_{2^n-2,y} & \cdots & U_{2^n-2,2^n-2} & U_{2^n-2,2^n-1} \\ U_{2^n-1,0} & U_{2^n-1,1} & \cdots & U_{2^n-1,y} & \cdots & U_{2^n-1,2^n-2} & U_{2^n-1,2^n-1} \end{array}}\right]$
with $\left| 0 \right\rangle = \left| 0 0 \cdots 0 0 \right\rangle$, $\left| 1 \right\rangle = \left| 0 0 \cdots 0 1 \right\rangle$, $\left| x \right\rangle = \left| x_{n-1} x_{n-2} \cdots x_{1} x_{0} \right\rangle$, $\left| 2^n-2 \right\rangle = \left| 1 1 \cdots 10 \right\rangle$ and $\left| 2^n-1 \right\rangle = \left| 1 1 \cdots 11 \right\rangle$.
$\ $
Look at sub-slides for the detailed description of quantum logic gates on quantum register
Generic python functions used in this notebook to test quantum gates on quantum registers
def quregisterExperiment(nbExp,logNbIn,gate,param=[],formatIn="",formatOut=""):
res="Input quregister => Output quregister for "+str(nbExp)+" experiments\n"
for x in range(0,2**logNbIn): # Test with |x> , x = 0 to nbIn-1
res+=("{"+formatIn+"} => ").format(x)
for i in range(0,nbExp): # Test 'nbExp' times
r = gate(x,param)
res+=("{"+formatOut+"} ").format(r)
res+="\n"
print(res) # Print the results of all experiments
def createQuregister(n,x):
qureg = QC.allocate_qureg(n) # Create a quregister of n qubits |0>
QM.AddConstant(x) | qureg # Change value to |x>
return qureg # Return the quregister |x>
def measureQuregister(qureg):
QG.All(QG.Measure) | qureg # Measure the quregister
QC.flush() # Flush the Quantum Computer
n = len(qureg) # Size of the quregister
y = 0 # Transform quregister into integer
for i in range(0,n): # with this for loop
y = 2*y + int(qureg[n-i-1])
return y # Return the result of measurement
Kronecker product quantum gates¶
Each qubit $\left| x_k \right\rangle$, $k \in \left\{ 0, 1, 2, \cdots, n-1\right\}$, of the register $\left| x \right\rangle =\left| x_{n-1} x_{n-2} \cdots x_{1} x_{0} \right\rangle$ is processed independently with the single-qubit quantum gate $U^{\left(k\right)}$.
The resulting unitary operator is the Kronecker product of the quantum gates $U^{\left(k\right)}$:
$\begin{array}{rcl} U &=& \left(U_{x,y}\right)_{0 \leq x \leq 2^n-1, 0 \leq y \leq 2^n-1} \\ &=& \otimes_{k'=1}^{n} U^{(n-k')} = U^{(n-1)} \otimes \cdots \otimes U^{(1)} \otimes U^{(0)} \\ &=& \left(\prod_{k=0}^{n-1}U_{x_k,y_k}^{(k)}\right)_{0 \leq x \leq 2^n-1, 0 \leq y \leq 2^n-1}. \end{array}$
More generally, the Kronecker product of the quantum gates $U^{\left(l\right)} \in \mathbb{C}^{2^{n_l} \times 2^{n_l}}$ such as $\sum_{l=0}^{l_{max}-1} n_l = n$ acting on quantum sub-registers $\left| r_l \right\rangle = \otimes_{k=0}^{n_l-1} \left| x_{\sum_{l'=0}^{l} n_{l'} - k - 1} \right\rangle$ is:
$\begin{array}{rcl} U &=& \left(U_{x,y}\right)_{0 \leq x \leq 2^n-1, 0 \leq y \leq 2^n-1} \\ &=& \otimes_{l=1}^{l_{max}} U^{\left(l_{max} - l\right)} \\ &=& \left(\prod_{l=0}^{l_{max-1}-1}U_{x_l,y_l}^{(k)}\right)_{0 \leq x \leq 2^n-1, 0 \leq y \leq 2^n-1}. \end{array}$
Diagrams of Kronecker product gates
Quantum Hadamard transform gate, parallelization and random generator¶
The quantum Hadamard transform gate on a quantum register of $n$ qubits is the Kronecker product $U_{H}^{\otimes n}$ of Hadamard gates $U_{H}$ on each qubit.
$U_{H}^{\otimes n} \left| x \right\rangle = \otimes_{k=0}^{n-1}\left(U_H \left| x_k \right\rangle \right) = \otimes_{k=0}^{n-1} \sum_{y_k=0}^{1} \frac{(-1)^{x_k y_k}}{\sqrt{2}} \left| y_k \right\rangle = \frac{1}{2^{n/2}} \sum_{y=0}^{2^n-1} \left(-1\right)^{x \cdot y} \left| y \right\rangle$ with $x \cdot y = \oplus_{k=0}^{n-1} x_k y_k$.
This gate is used to process in parallel all the register values $\left| x \right\rangle$ for $x \in \left\{ 0, 1, 2, \cdots, 2^n-1\right\}$, unitary operators being linear.
A random generator can be made by applying the quantum Hadamard transform gate to the register value $\left| 0 \right\rangle$:
$U_{H}^{\otimes n} \left| 0 \right\rangle = \left(U_H \left| 0 \right\rangle \right)^{\otimes n} = \left( \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle + \left| 1 \right\rangle \right) \right)^{\otimes n} = \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} \left| x \right\rangle.$
After measurement, the probability to get the state $\left| x \right\rangle$ for $x \in \left\{ 0, 1, 2, \cdots, 2^n-1\right\}$ is $1/2^n$. This is a perfect random generator.
Diagram of an Hadamard transform gate
def randomGenerator(x,param):
n = param[0] # number of qubits in the quregister
# Create a quregister with n qubits, value x
qureg = createQuregister(n,x)
# Apply the Hadamard gate H to all qubits
QG.All(QG.H) | qureg
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(32,3,randomGenerator,[3])
Action on a sub-register of a quantum register¶
A quantum register can be split into two sub-registers, for example, if $\left| r \right\rangle = \otimes_{k=0}^{n-1} \left| x_{n - k - 1} \right\rangle$, then for $0<m<n-1$, $\left| r \right\rangle = \left| r_1 \right\rangle \otimes \left| r_0 \right\rangle$, with $\left| r^{0} \right\rangle = \otimes_{k=0}^{m-1} \left| x_{m - k - 1} \right\rangle$ and $\left| r^{1} \right\rangle = \otimes_{k=m}^{n-1} \left| x_{n - k - 1} \right\rangle$.
An operator $U \in \mathbb{C}^{2^n \times 2^n}$ which acts only on the sub-register $\left| r^{0} \right\rangle$, with sub-operator $U^{0} \in \mathbb{C}^{2^m \times 2^m}$ can be written:
$U = I^{\otimes \left( n-m \right)} \otimes U^{0} = \left[\begin{array}{ccccc} U^{0} & 0 & \cdots & 0 & 0 \\ 0 & U^{0} & \cdots & 0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & \cdots & U^{0} & 0 \\ 0 & 0 & \cdots & 0 & U^{0} \end{array}\right].$
Diagram of a sub-register gate
def singleQubitHadamard(x,param):
n = param[0] # number of qubits in the quregister
# Create a quregister with n qubits, value x
qureg = createQuregister(n,x)
# Apply the Hadamard gate H to last qubit
QG.H | qureg[0]
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(32,3,singleQubitHadamard,[3])
Quantum SWAP gate¶
The quantum SWAP gate swaps the qubits of the 2-qubit register: $U_{SWAP} \left| b_1 b_0 \right\rangle = \left| b_0 b_1 \right\rangle $.
$U_{SWAP} = \left[{\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}}\right]$
Diagram of a SWAP gate
def SWAPgate(x,param):
# Create a quregister with 2 qubits, value x = 0
qureg = createQuregister(2,x)
# Apply the Swap gate SWAP
# which is equivalent to:
# QG.MatrixGate([
# [1, 0, 0, 0] ,
# [0, 0, 1, 0] ,
# [0, 1, 0, 0] ,
# [0, 0, 0, 1] ]) | qureg
QG.Swap | (qureg[0],qureg[1])
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(16,2,SWAPgate,formatIn=":02b",formatOut=":02b")
Quantum square-root of SWAP gate¶
The square root of the SWAP gate verifies $U_{\sqrt{SWAP}} \times U_{\sqrt{SWAP}} = I$.
$U_{\sqrt{SWAP}} = \left[{\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{1+i}{2} & \frac{1-i}{2} & 0 \\ 0 & \frac{1-i}{2} & \frac{1+i}{2} & 0 \\ 0 & 0 & 0 & 1 \end{array}}\right]$
Any quantum gate on quantum registers can be expressed as the combination of Hadamar gates $U_H$, phase-shift gates $U_{R_\phi}$ and square root of SWAP gates $U_\sqrt{SWAP}$.
Diagram of a square root of SWAP gate
def rootSWAPgate(x,param):
# Create a quregister with 2 qubits, value x
qureg = createQuregister(2,x)
# Apply the root of the SWAP gate
# which is equivalent to:
# rootswap = QG.MatrixGate([
# [1, 0 , 0 , 0] ,
# [0, (1+1j)/2, (1-1j)/2, 0] ,
# [0, (1-1j)/2, (1+1j)/2, 0] ,
# [0, 0 , 0 , 1] ]) | qureg
QG.SqrtSwap | (qureg[0],qureg[1])
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(32,2,rootSWAPgate)
Generic controlled gates¶
The quantum controlled gate $U_{cG} \in \mathrm{U}\left(2^{n+1}\right)$ of any generic quantum gate $U_{G} \in \mathrm{U}\left(2^{n}\right)$ acts on a $(1+n)$-qubit register such as, for any $\left| x \right\rangle \in \mathcal{H}_{2^n}$:
$U_{cG} \left| 0x \right\rangle = \left| 0 \right\rangle \otimes \left| x \right\rangle$,
$U_{cG} \left| 1x \right\rangle = \left| 1 \right\rangle \otimes U_G \left| x \right\rangle$.
$U_{cG} = \left[{\begin{array}{cc} I^{\otimes n} & 0 \\ 0 & U_G \end{array}}\right] = \left[{\begin{array}{cc} I_{2^n} & 0 \\ 0 & U_G \end{array}}\right]$
Diagram of a generic controlled gate
Controlled NOT gate¶
The controlled NOT gate (CNOT, or cX) is the control gate for the NOT gate:
$U_{CNOT} \left| 0b \right\rangle = \left| 0 \right\rangle \otimes \left| b \right\rangle$,
$U_{CNOT} \left| 1b \right\rangle = \left| 1 \right\rangle \otimes \left| \neg b \right\rangle$.
$U_{CNOT} = \left[{\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}}\right]$
It realises a XOR operation: $U_{CNOT} \left| ab \right\rangle = \left| a \right\rangle \otimes \left| a \oplus b \right\rangle$.
Diagram of a controlled NOT gate
def CNOTgate(x,param):
# Create a quregister with 2 qubits, value x
qureg = createQuregister(2,x)
# Apply the controlled NOT gate CNOT
# which is equivament to:
# QG.MatrixGate([
# [1, 0, 0, 0] ,
# [0, 1, 0, 0] ,
# [0, 0, 0, 1] ,
# [0, 0, 1, 0] ]) | qureg
QG.CNOT | (qureg[1],qureg[0])
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(16,2,CNOTgate,formatIn=":02b",formatOut=":02b")
No cloning theorem¶
CNOT gate can "duplicate" $\left| 0 \right\rangle$ or $\left| 1 \right\rangle$ qubits:
$U_{CNOT} \left| 00 \right\rangle = \left| 0 \right\rangle \otimes \left| 0 \right\rangle$, $\ U_{CNOT} \left| 10 \right\rangle = \left| 1 \right\rangle \otimes \left| 1 \right\rangle$.
But it cannot duplicate other qubits:
$U_{CNOT} \left| 0 \right\rangle \otimes \left( \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle \right)$
$= \alpha \left| 0 \right\rangle \otimes \left| 0 \right\rangle + \beta \left| 1 \right\rangle \otimes \left| 1 \right\rangle
\neq \left( \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle \right) \otimes \left( \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle \right)$.
No cloning theorem
$\forall\, \mathcal{H}$, $\ \not\exists \, \left(U,\left| \psi \right\rangle,\theta\right) \in \mathcal{U}\left(\mathcal{H}\otimes\mathcal{H}\right) \times \mathcal{H} \times \mathbb{R}^{\mathcal{H}}\ | \ $ $\ \forall \varphi \in \mathcal{H}$, $\ U \, \left| \varphi \right\rangle \otimes \left| \psi \right\rangle = e^{i\theta\left(\varphi\right)} \, \left| \varphi \right\rangle \otimes \left| \varphi \right\rangle$.
$[$WZ1982$]$ W. K. Wootters & W. H. Zurek: A single quantum cannot be cloned. Nature, 299:802-803, 1982. http://copilot.caltech.edu/documents/525-299802a0.pdf
Proof:
$\left\langle \phi \right.\left| \varphi \right\rangle = \left\langle \phi \right.\left| \varphi \right\rangle \left\langle \psi \right.\left| \psi \right\rangle
= \left\langle \phi \right| \otimes \left\langle \psi \right| \,I\, \left| \varphi \right\rangle \otimes \left| \psi \right\rangle
= \left\langle \phi \right| \otimes \left\langle \psi \right| \, U^\dagger U \, \left| \varphi \right\rangle \otimes \left| \psi \right\rangle$
$= e^{i\left(\theta\left(\varphi\right)-\theta\left(\phi\right)\right)}
\left\langle \phi \right| \otimes \left\langle \phi \right| \, I \, \left| \varphi \right\rangle \otimes \left| \varphi \right\rangle
= e^{i\left(\theta\left(\varphi\right)-\theta\left(\phi\right)\right)}
\left\langle \phi \right.\left| \varphi \right\rangle^2$
which implies $\left|\left\langle \phi \right.\left| \varphi \right\rangle\right| = \left|\left\langle \phi \right.\left| \varphi \right\rangle\right|^2$,
i.e., $\left|\left\langle \phi \right.\left| \varphi \right\rangle\right| = 1$ or $\left|\left\langle \phi \right.\left| \varphi \right\rangle\right| =0$.
Toffoli (CCNOT) gate¶
The Toffoli (or CCNOT for controlled-controlled NOT) gate $U_{CCONT} \in \mathrm{U}\left(2^{3}\right)$ acts on a $3$-qubit register: $U_{CCNOT} \left| abc \right\rangle = \left| a \right\rangle \otimes \left| b \right\rangle \otimes \left| c \oplus \left(a \wedge b \right) \right\rangle$.
$U_{cG} = \left[{\begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \underline{1} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \underline{1} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \underline{1} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & \underline{0} \ \end{array}}\right]$
It realizes the NAND operation: $U_{CCNOT} \left| ab1 \right\rangle = \left| a \right\rangle \otimes \left| b \right\rangle \otimes \left| \neg \left(a \wedge b \right) \right\rangle$.
Diagram of a Toffoli gate
def CCNOTgate(x,param):
# Create a quregister with 3 qubits, value x
qureg = createQuregister(3,x)
# Apply the Toffoli gate CCNOT
# which is equivament to:
# QG.C(QG.NOT,2) | (qureg[2],qureg[1],qureg[0])
QG.Toffoli | ([qureg[2],qureg[1]],qureg[0])
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(16,3,CCNOTgate,formatIn=":03b",formatOut=":03b")
Classical boolean gate¶
OR and AND cannot be realized with a 2-qubit gate.
$U_{AND} = \left[{\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}}\right] \notin \mathrm{U}\left(2^{2}\right)$.
$U_{OR} = \left[{\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{array}}\right] \notin \mathrm{U}\left(2^{2}\right)$.
The NAND gate being a universal gate for classical logic, any classical boolean function can be implemented using Toffoli gates (and SWAP gates for reordering of qubits if required).
NOT is $\ \neg a = \neg \left(a \wedge a \right)$:
$\left| \psi_{out} \right\rangle
= U_{CCNOT} \left| a11 \right\rangle
= \left| a \right\rangle
\otimes \left| 1 \right\rangle
\otimes \left| \neg \left(a \right) \right\rangle$
AND is $\ a \wedge b = \neg \neg \left(a \wedge b \right)$:
$\begin{array}{rcl}
\left| \psi_{out} \right\rangle
&=&
\left( I^{\otimes 2} \otimes U_{CCNOT} \right)
\left( U_{CCNOT} \otimes I^{\otimes 2} \right)
\left| ab111 \right\rangle
\\
&=& \left( I^{\otimes 2} \otimes U_{CCNOT} \right)
\left| ab \right\rangle
\otimes \left| \neg \left(a \wedge b \right) \right\rangle
\otimes \left| 11 \right\rangle
\\
&=& \left| ab \right\rangle
\otimes \left| \neg \left(a \wedge b \right) \right\rangle
\otimes \left| 1 \right\rangle
\otimes \left| a \wedge b \right\rangle.
\end{array}$
Simpler AND using the NOT gate:
$\begin{array}{rcl}
\left| \psi_{out} \right\rangle
&=& \left( I^{\otimes 2} \otimes U_{NOT} \right)
U_{CCNOT}
\left| ab1 \right\rangle
\\
&=& \left( I^{\otimes 2} \otimes U_{NOT} \right)
\left| ab \right\rangle
\otimes \left| \neg \left(a \wedge b \right) \right\rangle
\\
&=& \left| ab \right\rangle
\otimes \left| a \wedge b \right\rangle.
\end{array}$
Still another simpler AND:
$\left| \psi_{out} \right\rangle
= U_{CCNOT} \left| ab0 \right\rangle
= \left| ab \right\rangle
\otimes \left| a \wedge b \right\rangle$
def ANDgate(x,param):
# Create an input quregister with 2 qubits, value x
quregin = createQuregister(2,x)
# Create an output quregister with 1 qubits, value 1
quregout = createQuregister(1,1)
# Apply the Toffoli gate CCNOT
QG.Toffoli | ([quregin[1],quregin[0]],quregout[0])
# Apply the NOT gates to the last bit
QG.NOT | quregout
# Measure the quregister
result = measureQuregister(quregout)
return result
quregisterExperiment(32,2,ANDgate,formatIn=":02b")
OR is $\ a \vee b = \neg \left(\neg a \wedge \neg b \right)$:
$\begin{array}{rcl}
\left| \psi_{out} \right\rangle
& = &
\left( I^{\otimes 3} \otimes U_{CCNOT} \right)
\left( I \otimes U_{SWAP} ^{\otimes 2} \otimes I \right)
\left( U_{CCNOT} ^{\otimes 2} \right)
\left| a11b11 \right\rangle
\\ &=&
\left( I^{\otimes 3} \otimes U_{CCNOT} \right)
\left( I \otimes U_{SWAP} \otimes U_{SWAP} \otimes I \right)
\left| a1(\neg a)b1(\neg b) \right\rangle
\\ &=&
\left( I^{\otimes 3} \otimes U_{CCNOT} \right)
\left| a1b(\neg a)(\neg b)1 \right\rangle
\\ &=&
\left| a1b(\neg a)(\neg b)(a \vee b) \right\rangle.
\end{array}$
Simpler OR using the NOT gate:
$\begin{array}{rcl}
\left| \psi_{out} \right\rangle
& = & U_{CCNOT}
\left( U_{NOT} \otimes U_{NOT} \otimes I \right)
\left| ab1 \right\rangle
\\
&=& U_{CCNOT}
\left| (\neg a) (\neg b) 1 \right\rangle
\\
&=& \left| (\neg a) (\neg b) \right\rangle
\otimes \left| a \vee b \right\rangle.
\end{array}$
def ORgate(x,param):
# Create an input quregister with 2 qubits, value x
quregin = createQuregister(2,x)
# Create an output quregister with 1 qubits, value 1
quregout = createQuregister(1,1)
# Apply the NOT gates to each qubit of input quregister
QG.All(QG.NOT) | quregin
# Apply the Toffoli gate CCNOT
QG.Toffoli | ([quregin[1],quregin[0]],quregout[0])
# Measure the quregister
result = measureQuregister(quregout)
return result
quregisterExperiment(32,2,ORgate,formatIn=":02b")
Diagrams of boolean gates
Fredkin (CSWAP) gate¶
The Fredkin gate is the controlled gate of the SWAP gate.
$U_{CSWAP} \left| 0ab \right\rangle = \left| 0 \right\rangle \otimes \left| ab \right\rangle$,
$U_{CSWAP} \left| 1ab \right\rangle = \left| 1 \right\rangle \otimes \left| ba \right\rangle$.
$U_{CSWAP} = \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 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}}\right]$
If $ \left| y_2 y_1 y_0 \right\rangle = U_{CSWAP} \left| x_2 x_1 x_0 \right\rangle$ then $\sum y_i = \sum x_i$.
Like the Toffoli gate, it is also universal for classical computation.
Diagram of Fredkin gates
def CSWAPgate(x,param):
# Create a quregister with 3 qubits, value x
qureg = createQuregister(3,x)
# Apply the Fredkin gate CSWAP
QG.C(QG.Swap) | (qureg[2], qureg[1], qureg[0])
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(16,3,CSWAPgate,formatIn=":03b",formatOut=":03b")
Ising coupling gates¶
Ising coupling gates can be implemented natively in some trapped-ion quantum computers. They all have a continuous angular parameter.
Ising (XX) coupling gate¶
$U_{XX_\phi} = \frac{1}{\sqrt{2}} \left[{\begin{array}{cccc} 1 & 0 & 0 & -i e^{i\phi} \\ 0 & 1 & -i & 0 \\ 0 & -i & 1 & 0 \\ -i e^{-i\phi} & 0 & 0 & 1 \end{array}}\right]$
Ising (YY) coupling gate¶
$U_{YY_\phi} = \left[{\begin{array}{cccc} \cos\left(\phi\right) & 0 & 0 & i \sin\left(\phi\right) \\ 0 & \cos\left(\phi\right) & -i \sin\left(\phi\right) & 0 \\ 0 & -i \sin\left(\phi\right) & \cos\left(\phi\right) & 0 \\ i \sin\left(\phi\right) & 0 & 0 & \cos\left(\phi\right) \end{array}}\right]$
Ising (ZZ) coupling gate¶
$U_{ZZ_\phi} = \left[{\begin{array}{cccc} e^{i\phi/2} & 0 & 0 & 0 \\ 0 & e^{-i\phi/2} & 0 & 0 \\ 0 & 0 & e^{-i\phi/2} & 0 \\ 0 & 0 & 0 & e^{i\phi/2} \end{array}}\right]$
Diagrams of Ising coupling gates
def matrixIsing(axis,phi):
if axis=="XX":
a = np.sqrt(1/2)
b = -1j*np.sqrt(1/2)
c = -1j*np.exp(1j*phi)*np.sqrt(1/2)
d = -1j*np.exp(-1j*phi)*np.sqrt(1/2)
m = [[a,0,0,c], [0,a,b,0], [0,b,a,0], [d,0,0,a]]
elif axis=="YY":
c = np.cos(phi)
s = np.sin(phi)
m = [[c,0,0,1j*s], [0,c,-1j*s,0], [0,-1j*s,c,0], [1j*s,0,0,c]]
else: # case axis == "ZZ"
a = np.exp(1j*phi/2)
b = np.exp(-1j*phi/2)
m = [[a,0,0,0], [0,b,0,0], [0,0,b,0], [0,0,0,a]]
return m
def IsingGate(x,param):
# Create a quregister with 2 qubits, value x
qureg = createQuregister(2,x)
# Apply the Ising matrix of type axis and angle theta
QG.MatrixGate(matrixIsing(axis=param[0],phi=param[1])) | qureg
# Measure the quregister
result = measureQuregister(qureg)
return result
param = ["XX",np.pi/4]
quregisterExperiment(16,2,IsingGate,param,formatIn=":02b",formatOut=":02b")
Deutsch gates¶
The Deutsch gate of parameter $\theta$ is the controlled-controlled gate of $i U_{R_X\left(2\theta\right)} = \left[{\begin{array}{cc} i\cos\left(\theta\right) & \sin\left(\theta\right) \\ \sin\left(\theta\right) & i\cos\left(\theta\right) \end{array}}\right]$:
$U_{D\left(\theta\right)} = U_{CC i R_X\left(2\theta\right)} = \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 & i\cos\left(\theta\right) & \sin\left(\theta\right) \\ 0 & 0 & 0 & 0 & 0 & 0 & \sin\left(\theta\right) & i\cos\left(\theta\right) \end{array}}\right]$
Diagram of the Deutsch gate
Entanglement gates¶
The entanglement gate produces n entangled qubits. For $n$ = 2 qubits:
$U_{Entanglement} \left| 00 \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 00 \right\rangle + \left| 11 \right\rangle \right)$
$U_{Entanglement} \left| 01 \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 00 \right\rangle - \left| 11 \right\rangle \right)$
$U_{Entanglement} \left| 10 \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 01 \right\rangle + \left| 10 \right\rangle \right)$
$U_{Entanglement} \left| 11 \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 01 \right\rangle - \left| 10 \right\rangle \right)$
$U_{Entanglement} = U_{CNOT} \times U_{SWAP} \times \left(I \otimes U_{H}\right) = \frac{1}{\sqrt{2}} \left[{\begin{array}{cccccccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 \\ 1 & -1 & 0 & 0 \end{array}}\right]$
Diagram of the entanglement gate
For 2 qubits:
def EntGate(x,param):
n = param[0]
# Create a quregister with 2 qubits, value x
qureg = createQuregister(n,x)
# Apply the entanglement gate, which is equivalent to:
# QG.H | qureg[0]
# for k in range(1,n+1):
# QG.CNOT | (qureg[0],qureg[k])
QG.Entangle | qureg
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(16,2,EntGate,[2],formatIn=":02b",formatOut=":02b")
Quantum teleportation¶
$[$BBC+1993$]$ C. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. Wootters: Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70:1895-1899, 1993. http://www2.fisica.unlp.edu.ar/materias/qc/teleport.pdf
Teleportation from Alice to Bob of qubit $\left| \varphi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle$.
Notation: $\left( x_{000}, x_{001}, x_{010}, x_{011}, x_{100}, x_{101}, x_{110}, x_{111}\right) = x_{000} \left| 000 \right\rangle + x_{001} \left| 001 \right\rangle + x_{010} \left| 010 \right\rangle + x_{011} \left| 011 \right\rangle + x_{100} \left| 100 \right\rangle + x_{101} \left| 101 \right\rangle + x_{110} \left| 110 \right\rangle + x_{111} \left| 111 \right\rangle$
(1) Alice prepares the qubit to be teleported (last qubit) and an entangled pair of qubits (first and middle qubits)
$\frac{1}{\sqrt{2}} \left( \left| 00 \right\rangle + \left| 11 \right\rangle \right) \otimes \left( \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle \right) = \frac{1}{\sqrt{2}} \left( \alpha , \beta , 0 , 0 , 0 , 0 , \alpha , \beta \right)$
(2) Alice sends (quantum communication) the first qubit to Bob
(3) Alice processes a CNOT gate on the middle qubit controlled by the last qubit then an Hadamard gate on the last qubit
$\frac{1}{\sqrt{2}} \left( \alpha , \beta , 0 , 0 , 0 , 0 , \alpha , \beta \right) \rightarrow \frac{1}{\sqrt{2}} \left( \alpha , 0 , 0, \beta , 0, \beta , \alpha, 0 \right) \rightarrow \frac{1}{2} \left( \alpha , \alpha , \beta, -\beta , \beta, -\beta , \alpha, \alpha \right)$
(4) Alice sends (classical communication) the measurements on the two last qubits to Bob
$\frac{1}{2} \left( \alpha , \alpha , \beta, -\beta , \beta, -\beta , \alpha, \alpha \right) \ \Rightarrow$ Wave collapse with $\frac{1}{4}$ probability each:
$\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right) \otimes \left| 00 \right\rangle$
$\left(\alpha \left| 0 \right\rangle - \beta \left| 1 \right\rangle\right) \otimes \left| 01 \right\rangle$
$\left(\alpha \left| 1 \right\rangle + \beta \left| 0 \right\rangle\right) \otimes \left| 10 \right\rangle$
$\left(\alpha \left| 1 \right\rangle -\beta \left| 0 \right\rangle\right) \otimes \left| 11 \right\rangle$
(5) Bob processes a controlled Pauli X ($CNOT$) on the first qubit controlled by the middle classical bit, then a controlled Pauli Z ($CR_{\pi}$) controlled by the last classical bit
$
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 00 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 00 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 00 \right\rangle
$
$
\left(\alpha \left| 0 \right\rangle - \beta \left| 1 \right\rangle\right)
\otimes \left| 01 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle - \beta \left| 1 \right\rangle\right)
\otimes \left| 01 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 01 \right\rangle
$
$
\left(\alpha \left| 1 \right\rangle + \beta \left| 0 \right\rangle\right)
\otimes \left| 10 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 10 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 10 \right\rangle
$
$
\left(\alpha \left| 1 \right\rangle - \beta \left| 0 \right\rangle\right)
\otimes \left| 11 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle - \beta \left| 1 \right\rangle\right)
\otimes \left| 11 \right\rangle
\rightarrow
\left(\alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle\right)
\otimes \left| 11 \right\rangle
$
The result is the teleportation of $\left| \varphi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle$ by Alice to Bob, using a mix of quantum and classical communication channels
Diagram of quantum teleportation on 1 qubit
Quantum teleportation circuit on Quirk
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.QTeleport.htm
def QTeleportation(x,param): # x = 0 or 1
n = 3
# Create a quregister with 3 qubits, value x = 000 or 001
qureg = createQuregister(n,x)
# Create an entangled pair with qubits 1 and 2:
QG.H | qureg[1]
QG.CNOT | (qureg[1],qureg[2])
# Process the qubits 0 and 1:
QG.CNOT | (qureg[0],qureg[1])
QG.H | qureg[0]
# Measure the qubits 0 and 1
QG.Measure | qureg[0]
QG.Measure | qureg[1]
# Process the qubit 2
QG.CNOT | (qureg[1],qureg[2])
QG.CZ | (qureg[0],qureg[2])
# Final measurement
result = measureQuregister(qureg)
return result
quregisterExperiment(16,1,QTeleportation,[],formatIn=":03b",formatOut=":03b")
Quantum Fourier transform gates¶
By convention, the quantum Fourier transform gate $QFT_N$ corresponds to the classical inverse discrete Fourier transform, and the inverse quantum Fourier transform gate $QFT_N^{-1}$ corresponds to the classical discrete Fourier transform.
Usually $N=2^n$ (n qubits), $\omega_N = e^{i2\pi/N}$:
$U_{QFT_N} \left| x \right\rangle = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \omega_N^{xy} \left| y \right\rangle$,
$U_{QFT_N^{-1}} \left| x \right\rangle = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \omega_N^{-xy} \left| y \right\rangle$.
$U_{QFT_N} = \frac{1}{\sqrt{N}} \left[{\begin{array}{cccccc} 1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_N & \omega_N^2 & \omega_N^3 & \cdots & \omega_N^{N-1} \\ 1 & \omega_N^2 & \omega_N^4 & \omega_N^6 & \cdots & \omega_N^{2\left(N-1\right)} \\ 1 & \omega_N^3 & \omega_N^6 & \omega_N^9 & \cdots & \omega_N^{3\left(N-1\right)} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & \omega_N^{N-1} & \omega_N^{2\left(N-1\right)} & \omega_N^{3\left(N-1\right)} & \cdots & \omega_N^{\left(N-1\right)\left(N-1\right)} \end{array}}\right]$
$U_{QFT_N^{-1}} = U_{QFT_N}^{-1} = U_{QFT_N}^\dagger = U_{QFT_N}^\star$ and $U_{QFT_2} = U_{QFT_2^{-1}} = U_{H}$.
Diagram of the Quantum Fourier Transform gate
Diagram of the Inverse Quantum Fourier Transform gate
Quantum Fourier transform vs. classical Fourier transform
Classical Fast Fourier Transform: $O\left(N \log N\right) = O\left(2^n n\right)$ gates.
Quantum Fourier Transform: $O\left(\log^2 N\right) = O\left(n^2\right)$ gates.
Approximation possible removing $R_\phi$ gates with small $\phi$: $O\left(\log\log N \log N\right) = O\left(n \log n\right)$ gates.
Quantum Fourier Transform gate on Quirk
$QFT$ with 8 qubits:
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.QFTgate8.htm
$QFT$ with 4 qubits:
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.QFTgate.htm
$QFT^{-1}$ with 4 qubits:
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.IQFTgate.htm
$QFT \times QFT^{-1}$ with 8 qubits:
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.QFTxIQFT.htm
def QFTgate(x,param):
n = param[0]
# Create a quregister with 2 qubits, value x
qureg = createQuregister(n,x)
# Apply the quantum Fourier transform gate QFT:
QG.QFT | qureg
# Measure the quregister
result = measureQuregister(qureg)
return result
quregisterExperiment(16,3,QFTgate,[3])
Quantum oracle gates¶
Consider a function $f : x \in X \mapsto y \in Y$ where $X = \left\{0,1,2,\cdots,N-1\right\}$ and $Y = \left\{0,1,2,\cdots,M-1\right\}$, with usually $N = 2^n$ and $M = 2^m$.
The quantum oracle gate associated with f is $U_f$ such as for all $x \in X$ and $y \in Y$, $U_f \left(\left| x \right\rangle \otimes \left| y \right\rangle \right) = \left| x \right\rangle \otimes \left| y + f(x) \ modulo \ M \ \right\rangle$. When $M = 2^m$, $y + f(x) \ modulo \ M = y + f(x) \ modulo \ 2^n$.
$U_{f} = \left[{\begin{array}{cccccc} U_{\sigma_{f\left(0\right)}} & 0 & 0 & 0 & \cdots & 0 \\ 0 & U_{\sigma_{f\left(1\right)}} & 0 & 0 & \cdots & 0 \\ 0 & 0 & U_{\sigma_{f\left(2\right)}} & 0 & \cdots & 0 \\ 0 & 0 & 0 & U_{\sigma_{f\left(3\right)}} & \cdots & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & 0 & 0 & \cdots & U_{\sigma_{f\left(N-1\right)}} \\ \end{array}}\right]$
with $U_{\sigma_k}$ corresponding to the cyclic permutation of $M$ elements with a shift value $k$.
More particularly, if $M = N$, $U_f \left(\left| x \right\rangle \otimes \left| 0 \right\rangle \right) = \left| x \right\rangle \otimes \left| f(x) \right\rangle$.
This kind of gate is used in many quantum algorithms.
Diagram of a generic oracle gate
# Matrix to be used for quantum oracle gates
# f is an array of bits of length N = 2^n, n = number of bits of input
# mbits is the number of bits of output: M = 2^m possible values
def matrixOracle(f,mbits):
N = len(f)
M = 2**mbits
mtrix = np.zeros((N*M, N*M))
for x in range(0,N):
for y in range(0,M):
z = y + f[x]
if z>=M:
z = z-M
mtrix[M*x+y][M*x+z] = 1
return mtrix
Universal quantum logic gates¶
Definition¶
A set $G \in \mathrm{U}\left(n\right)$ of universal quantum gates is any finite set of quantum gates that can approximate any quantum opetrator $U \in \mathrm{U}\left(n\right)$, i.e., for any $U \in \mathrm{U}\left(n\right)$, for any desired accuracy $\epsilon >0$, one can find a finite sequence $S = g_k g_{k-1} \cdots g_2 g_1$ with $g_i \in G$ for all $i \in \left\{1, \cdots, k< \infty\right\}$ that is an $\epsilon$-approximation of the quantum operator $U$, i.e., $d\left(U, S\right) = \left\| U − S \right\| = \sup_{\psi | \left\|\psi\right\| = 1} \left\| (U − S)\psi \right\| < \epsilon$.
Note: it is not possible to express exactly any quantum opetrator by a finite sequence of a finite set of quantum gates, because the set of quantum operators is uncountable.
Solovay-Kitaev theorem¶
In its simplest form the Solovay-Kitaev theorem shows that, roughly speaking, if a set of $n$-qubit quantum gates generates a dense subset of $\mathrm{SU}\left(n\right)$, then that set is guaranteed to fill $\mathrm{SU}\left(n\right)$ quickly, i.e., it is possible to obtain good approximations to any desired gate using surprisingly short sequences of gates from the given generating set.
More precisely, let $G$ be an instruction set for $\mathrm{SU}\left(n\right)$, i.e., the group generated by $G$ is dense in $\mathrm{SU}\left(n\right)$, and let a desired accuracy $\epsilon >0$ be given. There is a constant $c < 4$ such that for $U \in \mathrm{SU}\left(n\right)$ there exists a finite sequence $S$ of gates from $G$ of length $O(log^c(1/\epsilon))$ and such that $d\left(U, S\right) < \epsilon$.
$[$DN2005$]$ C. M. Dawson and M. A. Nielsen: The Solovay-Kitaev algorithm. arXiv:quant-ph/0505030, 2005. https://arxiv.org/abs/quant-ph/0505030.
Some sets of universal quantum gates¶
One simple set of 2-qubit universal quantum gates is $G = \left\{U_H, U_{T}, U_{CNOT} \right\}$ (with $U_{SWAP}$ to get the right wired quantum cirtcuit if qubits cannot be moved).
Some single-gate set are also universal (with $U_{SWAP}$ to get the right wired quantum cirtcuit if qubits cannot be moved), e.g., $G = \left\{U_{D\left(\theta\right)} \right\}$ with $\theta/\pi \notin \mathbb{Q}$.
Another set of universal quantum gates consists of the Ising gates and the phase-shift gate. These are the set of gates natively available in some trapped-ion quantum computers.
Quantum Algorithms¶
General form of quantum algorithms¶
The general form of quantum algorithm is the following:
(1) Prepare some qubits.
You may or may not have an input register with value given by the user.
You may or may not have an internal register that need to be prepare to some fixed values. It may be seen as an input but the value is fixed.
We call register the aggregation of the input register + internal register.
(2) Apply the quantum Hadamard transform gate on a part of the register.
This allows parallel processing on all integer values allowd in this part of the register.
(3) Apply a quantum unitary operator on the full register.
This unitary operator may be decomposed in smaller pieces (with wiring = quantum circuit) acting on smaller registers.
(4) Produce interferences on a part of the register.
This can be done for example with the quantum Hadamard transform gate or the quantum Fourier transform gate.
(5) Measure the output register which is a part of the register.
Mesure the values of the qubits of the output register (there may be only one qubit).
Note:
A quantum program may be included in a classical program as a subroutine.
Deutsch-Jozsa algorithm¶
$[$DS1992$]$ D. Deutsch and R. Jozsa: Rapid solutions of problems by quantum computation. Proceedings of the Royal Society of London A. 439 (1907): 553–558, 1992.
https://doi.org/10.1098%2Frspa.1992.0167.
See also https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm.
Deutsch-Jozsa problem statement¶
We have some unknown function $f : \left\{0,1\right\}^n \rightarrow \left\{0,1\right\}$. But we know that the function is either constant (0 on all outputs or 1 on all outputs) or balanced (returns 1 for half of the input domain and 0 for the other half). The task then is to determine if $f$ is constant or balanced on the $N = 2^n$ input values.
Deutsch-Jozsa problem classical solution¶
In the best case, one needs $2$ measurements on different input values to be sure that $f$ is unbalanced.
After $k \leq N/2 = 2^{n-1}$ measurements on different input values choosen randomly, if one obtains different output values, one is sure that $f$ is unbalanced. If one obtains the same output value, one can suppose that $f$ is constant. If $f$ is unbalanced, the probability of error is $\epsilon_k \leq 2^{-k}$. For $k = N/2$, $\epsilon_{N/2} = \left({\begin{array}{c} N \\ N/2 \end{array}}\right)^{-1} \sim \sqrt{\frac{\pi N}{2}} \cdot 2^{-N} = \sqrt{\frac{\pi}{2}}\cdot 2^{-2^n+n/2}$.
In the worst case, one needs $2^{n-1}+1$ measurements on different input values to be sure that $f$ is constant or unbalanced.
Deutsch-Jozsa quantum algorithm¶
The Deutsch-Jozsa algorithm uses the quantum oracle gate $U_f$ with the function $f$.
(1) Prepare $n+1$ qubits with value:
$\left| \phi_1 \right\rangle = \left| 0 \right\rangle^{\otimes n} \otimes \left| 1 \right\rangle$.
(2) Apply the quantum Hadamard transform gate on $\left| \phi_1 \right\rangle$:
$\left| \phi_2 \right\rangle = U_{H}^{\otimes(n+1)} \left(\left| 0 \right\rangle ^{\otimes n} \otimes \left| 1 \right\rangle\right) = \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^n-1} \left| x \right\rangle \otimes \left( \left| 0 \right\rangle - \left| 1 \right\rangle \right).$
(3) Apply the quantum oracle gate $U_f$ on $\left| \phi_2 \right\rangle$:
$\begin{array}{rcl} \left| \phi_3 \right\rangle &=& U_{f} \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^n-1} \left| x \right\rangle \otimes \left( \left| 0 \right\rangle - \left| 1 \right\rangle \right) \\ &=& \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^n-1} \left| x \right\rangle \otimes \left( \left| f\left(x\right) \right\rangle - \left| 1 \oplus f\left(x\right) \right\rangle \right) \\ &=& \frac{1}{\sqrt{2^{n+1}}} \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right)} \left| x \right\rangle \otimes \left( \left| 0 \right\rangle - \left| 1 \right\rangle \right). \end{array}$
We note $\left| y_{out} \right\rangle = \frac{1}{\sqrt{2}} \left( \left| 0 \right\rangle - \left| 1 \right\rangle \right)$ and $\left| x_{out} \right\rangle = \frac{1}{\sqrt{2^{n}}} \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right)} \left| x \right\rangle$.
(4) Apply the quantum Hadamard transform gate on $\left| x_{out} \right\rangle$ only:
$\begin{array}{rcl} \left| \phi_4 \right\rangle &=& \left( U_{H}^{\otimes n} \otimes I \right) \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right)} \left| x \right\rangle \otimes \left| y_{out} \right\rangle \\ &=& \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right)} \sum_{x'=0}^{2^n-1} (-1)^{x \cdot x'} \left| x' \right\rangle \otimes \left| y_{out} \right\rangle \\ &=& \frac{1}{\sqrt{2^n}} \sum_{x'=0}^{2^n-1} \left( \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right) \oplus x \cdot x'} \right) \left| x' \right\rangle \otimes \left| y_{out} \right\rangle \end{array}$
(5) Probability $P$ to measure $\left| x' \right\rangle = \left| 0 \right\rangle^{\otimes n}$:
$P = \left| \left\langle 0 \right|^{\otimes n} \frac{1}{\sqrt{2^n}} \sum_{x'=0}^{2^n-1} \left( \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right) \oplus x \cdot x'} \right) \left| x' \right\rangle \right|^2 = \frac{1}{2^n} \left| \sum_{x=0}^{2^n-1} \left(-1\right)^{f\left(x\right)} \right|^2$
If $f$ is constant, $P = 1$ (constructive interference), else $f$ is balanced and $P = 0$ (destructive interference).
One quantum measurement is enough!
Diagram of the Deutsch-Jozsa quantum algorithm
def DeutschJoszaAlgo(nbExp,f):
n = int(np.log2(len(truthtable)))
res="f={}\nIs f constant with {} experiments?\n".format(f,nbExp)
mtrix = matrixOracle(f,1)
for i in range(0,nbExp): # Test 'nbExp' times
x = createQuregister(n,0)
y = createQubit(1)
QG.All(QG.H) | x
QG.H | y
QG.MatrixGate(mtrix) | (y, x)
QG.All(QG.H) | x
rx = measureQuregister(x)
ry = measureQuregister(y) # theoretically useless...
if (rx==0):
p=1
else:
p=0
res+=("{} ").format(p)
return res
nbExp = 32
truthtable = [1,1,1,1,1,1,1,1]
print(DeutschJoszaAlgo(nbExp,truthtable)+"\n")
truthtable = [0,1,1,1,0,1,0,0]
print(DeutschJoszaAlgo(nbExp,truthtable)+"\n")
Deutsch-Jozsa algorithm on Quirk
Realization with $truthtable = \left[0,0,0,0,0,0,0,0\right]$ ($B = 0$), $truthtable = \left[1,1,1,1,0,0,0,0\right]$ ($B = 4$) or $truthtable = \left[1,1,1,1,1,1,1,1\right]$ ($B = 8$):
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.DJalgo.htm
Schor's algorithm¶
$[$Sho1994$]$ P. W. Shor: Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124-134. https://doi.org/10.1109%2Fsfcs.1994.365700.
Integer factorization problem statement¶
Given an odd composite number $N \in \mathbb{N}$ which is not a power of a prime, find an integer $d$, $1 < d < N$, that divides N.
If $N$ is even, this is trivial.
If $N$ is a power of a prime, this can be tested by checking that $N^{1/k}$ is not an integer for any $k \leq log_2\left(N\right)$.
Integer factorization problem classical solution¶
See https://en.wikipedia.org/wiki/Integer_factorization#Current_state_of_the_art.
The number of bits for $N$ is $b = \lceil log_2(N) \rceil$. There is no known algorithm that is polynomial in time, i.e., they are slower than $O\left(b^k\right)$, for any $k \in \mathbb{N}$.
There are published algorithms that are faster than $O((1 + \epsilon)^b)$ for all positive $\epsilon$, i.e., they are sub-exponential.
The best published asymptotic running time is for the general number field sieve (GNFS) algorithm, which is $O\left(e^{(64/9)^{1/3}b^{1/3}log^{2/3}(b)}\right)$.
Classical part of Shor's algorithm¶
(1) Pick a random number $a < N$
(2) Compute $\gcd(a,N)$, the greatest common divisor of $a$ and $N$. This may be done using the Euclidean algorithm.
(3) If $\gcd(a,N) \neq 1$, then this number is a nontrivial factor of $N$ and we are done.
(4) Otherwise, use the quantum period-search subroutine to find $r$, which denotes the period of the following function: $f\left(x\right)= a^x \bmod N$, i.e., the smallest $r \in \left\{1,2,\cdots,N\right\}$ such as $a^r \bmod N = 1$
(5) If $r$ is odd, then go back to step 1.
(6) If $a^{r/2} = -1 \bmod N$, then go back to step 1.
(7) Otherwise, at least one of $\gcd\left(a^{r/2} + 1 , N \right)$ and $\gcd\left(a^{r/2} - 1 , N \right)$ is a nontrivial factor of N and we are done.
Indeed: $\left(a^{r/2}+1\right)\left(a^{r/2}-1\right) = a^r-1 = K \times N$ with $a^{r/2} \neq -1$ (step 6) and $a^{r/2} \neq 1$ (step 4).
Quantum period-search subroutine of Shor's algorithm¶
For this subroutine, $N$ and $a$ are given. Find $Q = 2^q$ such that $N^2 \leq Q < 2 N^2$, which implies that $Q/r > N$. The Shor's algorithm uses the quantum oracle gate $U_f$ with the function $f\left(x\right)=a^x \bmod N$.
(1) Prepare $2q$ qubits with value:
$\left| \phi_1 \right\rangle = \left| 0 \right\rangle^{\otimes q} \otimes \left| 0 \right\rangle^{\otimes q}$.
(2) Apply the quantum Hadamard transform gate on the first half of the qubits of $\left| \phi_1 \right\rangle$:
$\left| \phi_2 \right\rangle = U_{H}^{\otimes(q)} \otimes I^{\otimes(q)} \left( \left| 0 \right\rangle^{\otimes q} \otimes \left| 0 \right\rangle^{\otimes q} \right) = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} \left| x \right\rangle \otimes \left| 0 \right\rangle^{\otimes q}.$
(3) Apply the quantum oracle gate $U_f$ on $\left| \phi_2 \right\rangle$:
$\begin{array}{rcl} \left| \phi_3 \right\rangle &=& U_{f} \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} \left| x \right\rangle \otimes \left| 0 \right\rangle^{\otimes q} \\ &=& \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} \left| x \right\rangle \otimes \left| f\left(x\right) \right\rangle. \end{array}$
(4) Apply the quantum Fourier transform gate on the first half of the qubits of $\left| \phi_3 \right\rangle$ only, with $\omega=e^{i 2\pi / Q}$:
$\begin{array}{rcl} \left| \phi_4 \right\rangle &=& \left( U_{QFT_Q} \otimes I^{\otimes q} \right) \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} \left| x \right\rangle \otimes \left| f\left(x\right) \right\rangle \\ &=& \frac{1}{Q} \sum_{x=0}^{Q-1} \sum_{x'=0}^{Q-1} \omega^{x x'} \left| x' \right\rangle \otimes \left| f(x) \right\rangle \\ &=& \frac{1}{Q} \sum_{y=0}^{N-1} \sum_{x'=0}^{Q-1} \left( \sum_{x | y=f(x), x=0}^{Q-1} \omega^{x x'} \right) \left| x' \right\rangle \otimes \left| y \right\rangle. \end{array}$
(5) Probability $P\left( x',y \right)$ to measure $\left| x' \right\rangle \otimes \left| y \right\rangle$:
$f$ is periodic, so if $r$ is the period, $x_0 = \min\left\{x \in \left\{0,\cdots,Q-1\right\} \left| f(x)=y \right. \right\}$ and $m = \left\lfloor\frac{Q-1-x_0}{r}\right\rfloor$,
$P\left( x',y \right) = \left| \frac{1}{Q} \left( \sum_{x | y=f(x), x=0}^{Q-1} \omega^{x x'} \right) \right|^2 = \frac{1}{Q^2} \left| \sum_{k=0}^{m} \left(\omega^{x' r}\right)^k \right|^2$,
which is maximal if $\omega^{x' r} = e^{i 2\pi x' r / Q} \sim 1$, i.e., $x' r / Q$ close to an integer.
The probability to mesure $x'$ such as $x' r = Q n$ is very high $\Rightarrow \frac{x'}{Q} \sim \frac{n}{r}$.
(6) Performing classical continued fraction expansion on $\frac{x'}{Q}$:
$\Rightarrow \frac{x'}{Q} \sim \frac{d}{s}$ with $s < N$ and $\left| \frac{x'}{Q} - \frac{d}{s} \right| < \frac{1}{2Q}$.
Put $\frac{d}{s}$ in irreducible form.
With high probability $r = s$.
(7) Check classically if $a^s = 1 \ modulo\ N$.
If yes: $r = s$.
If not:
(i) Try some multiple of $s$: $s' = k s $ (cases when $\frac{d}{s}$ is not irreductible).
(ii) Try with $s'' = s'+1$, $s'-1$, ..., $s' + \delta s'$, $s' - \delta s'$ (cases when $x' r \sim Q n$ but $x' r \neq Q n$).
If yes: $r = s''$
If not: back to step (1) of the classical part of this quantum period-search subroutine.
Diagram of the period-search quantum subroutine of Shor's algorithm
Complexity of Shor's quantum algorithm
Classical (GNFS): $O\left(e^{(64/9)^{1/3}b^{1/3}log^{2/3}(b)}\right) = e^{\tilde{O}\left(b^{1/3}\right)}$.
Quantum (Shor): $\tilde{O}\left(b^3\right)$.
Shor's quantum algorithm on Quirk
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.ShorAlgo.htm
Grover's search quantum algorithm¶
$[$Gro1996]$]$ Grover L.K.: A fast quantum mechanical algorithm for database search. Proceedings 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212.
https://arxiv.org/abs/quant-ph/9605043
Problem:
Find the unique input $\omega$ to a black box function $f$ that produces a particular output value (function inversion):
$f: \left\{0, 1, \cdots, N-1\right\} \rightarrow \left\{0, 1\right\}$ such as $f\left(x\right) = 1 \Leftrightarrow x = \omega$, with $N = 2^n$.
Efficiency:
$\left\lfloor\frac{\pi\sqrt{N}}{4}\right\rfloor$ evaluations with probability $P = \sin^2\left( \left(\left\lfloor\frac{\pi\sqrt{N}}{4}\right\rfloor + \frac{1}{2}\right) \times 2\arcsin\left(\frac{1}{\sqrt{N}}\right) \right) \geq 1-\frac{1}{N}$ vs. $O\left(N\right)$ evaluations for the classical solution.
Applications:
It could be used to reverse-engineer cryptographic hash functions.
Diagram of the Grover's search quantum algorithm
Grover's search quantum algorithm on Quirk
http://ludovic-noirie.fr/sciences/quantum-computing/link/Quirk.GroverAlgo.htm
Other quantum algorithms¶
There are many quantum algorithms that are better than the classical algorithms to solve the same given problems.
See a list in https://en.wikipedia.org/wiki/Quantum_algorithm.
Another quite exhaustive list at http://quantumalgorithmzoo.org/
Applications: number factorization, function inversion, solution search, solution counting, quantum walk, quantum simulation, optimization, combinatorial optimization, linear systems, linear differential equation solving, least-squares fitting, machine learning, big data analysis, ...
Quantum phase estimation¶
See https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm.
Problem:
Find an eigenvalue of a unitary operator, i.e., the phase of an eignevalue, because the absolute value of any eigenvalue of a unitary operator is 1.
Applications:
Shor's algorithm uses in fact the quantum phase estimation algorithm. Other quantum algorithms use it too...
Quantum counting algorithm¶
See https://en.wikipedia.org/wiki/Quantum_counting_algorithm.
Problem:
Count the number $M$ of solutions for a given search problem.
Relation with other quantum algorithms:
The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.
Applications:
Grover's search algorithm for an initially-unknown number of solutions, speeding up NP-complete problems, quantum existence problem (is $M>0$ ?).
Quantum algorithm for linear systems of equations¶
See
https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations#Classical_efficiency.
Problem:
$A$ is hermitian, $b$ is a unitary vector, what is the value of $\left\langle x \right| M \left| x \right\rangle$ where $A x = b$ and $M$ is a given operator. $A$ is also supposed to be sparse (see details in the link below).
Efficiency:
If $N \times N$ is the size of the matrix $A$ and $\kappa = \lambda_\max\left(A\right) / \lambda_\min\left(A\right) $ (the condition number) then the quantum algorithm runs in $O\left(\log(N)\kappa^2\right)$ steps vs. $O\left(N\kappa\right)$ steps for the classical algorithm ($O\left(N \sqrt{\kappa}\right)$ for positive semidefinite matrices).
Note: the best classical algorithm to solves $A x = b$ is the Gaussian elimination which runs in $O\left(N^3\right)$.
Applications:
Linear differential equation solving, least-squares fitting, machine learning and big data analysis.
Quantum walk¶
Problem:
Consider an undirected graph $G$ with $N$ vertices with a subset $M$ of "marked" vertices: find a marked vertex.
Random walk algorithm:
(0) Start at some specific vertex $v$ of the graph.
(1) Check if $v \in M$ and stop if yes
(2) Random walk if not: choose one of its neighbors at random, set $v$ to be that neighbor, go back to step (1).
Efficiency:
$\epsilon = \left|M\right|/N << 1$ is ratio of marked vertices and $\delta = 1 - max_{k \geq 2}\left|\lambda_k\right|$ is the spectral gap of the random walk transition matrix (bistochastic: $\lambda_1 = 1$) .
Classical random walk cost $\sim \ C_0 + \frac{1}{\epsilon} \left( C_1 + \frac{1}{\delta} C_2\right)$ vs. Quantum random walk cost $\sim \ C'_0 + \frac{1}{\sqrt{\epsilon}} \left( C'_1 + \frac{1}{\sqrt{\delta}} C'_2\right)$.
Applications:
Quantum walks give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem, the triangle finding problem, and evaluating NAND trees. The Grover's search algorithm can also be viewed as a quantum walk algorithm on a complete graph.
Quantum simulation¶
Problem (and applications):
Study quantum systems that are difficult to study in the laboratory and impossible to model with a classical supercomputer.
Classical supercomputers are inadequate for simulating quantum systems with as few as 30 particles
History of quantum simulators:
A universal quantum simulator is a quantum computer proposed by Yuri Manin in 1980 and Richard Feynman in 1982.
Feynman showed that a classical Turing machine would experience an exponential slowdown when simulating quantum phenomena, while his hypothetical universal quantum simulator would not.
David Deutsch in 1985, took the ideas further and described a universal quantum computer.
$[$Deu1985$]$ D. Deutsch: Quantum theory, the Church-Turing principle, and the universal quantum Turing machine.
In Proceedings of the Royal Society of London, volume A400, pages 97-117, 1985.
https://doi.org/10.1098%2Frspa.1985.0070
In 1996, Seth Lloyd showed that a standard quantum computer can be programmed to simulate any local quantum system efficiently.
$[$LLo1996$]$ S. Lloyd: "Universal quantum simulators". Science, 273(5278):1073–8, 1996.
https://doi.org/10.1126%2Fscience.273.5278.1073
Quantum Computers in the Real World¶
Qubits in the real world¶
From https://en.wikipedia.org/wiki/Quantum_computing#Physical_realizations
- Superconducting quantum computing: qubit implemented by the state of small superconducting circuits (Josephson junctions)
- Trapped ion quantum computer: qubit implemented by the internal state of trapped ions
- Optical lattices: qubit implemented by internal states of neutral atoms trapped in an optical lattice
- Quantum dot computer, spin-based (e.g. the Loss-DiVincenzo quantum computer): qubit given by the spin states of trapped electrons
- Quantum dot computer, spatial-based: qubit given by electron position in double quantum dot
- Coupled Quantum Wire: qubit implemented by a pair of Quantum Wires coupled by a Quantum Point Contact
- Nuclear magnetic resonance quantum computer (NMRQC) implemented with the nuclear magnetic resonance of molecules in solution, where qubits are provided by nuclear spins within the dissolved molecule and probed with radio waves
- Solid-state NMR Kane quantum computers: qubit realized by the nuclear spin state of phosphorus donors in silicon
- Electrons-on-helium quantum computers: qubit is the electron spin
- Cavity quantum electrodynamics (CQED): qubit provided by the internal state of trapped atoms coupled to high-finesse cavities
- Molecular magnet: qubit given by spin states
- Fullerene-based ESR quantum computer: qubit based on the electronic spin of atoms or molecules encased in fullerenes
- Linear optical quantum computer: qubits realized by processing states of different modes of light through linear elements e.g. mirrors, beam splitters and phase shifters
- Diamond-based quantum computer: qubit realized by the electronic or nuclear spin of nitrogen-vacancy centers in diamond
- Bose-Einstein condensate-based quantum computer
- Transistor-based quantum computer – string quantum computers with entrainment of positive holes using an electrostatic trap
- Rare-earth-metal-ion-doped inorganic crystal based quantum computers: qubit realized by the internal electronic state of dopants in optical fibers
- Metallic-like carbon nanospheres based quantum computers
$\ $
A large number of candidates demonstrates that the topic, in spite of rapid progress, is still in its infancy.
Quantum computers in real world¶
See https://en.wikipedia.org/wiki/List_of_quantum_processors
See also by Olivier Ezratty:
https://www.frenchweb.fr/comprendre-linformatique-quantique-panorama-des-acteurs
- D-Wave 2000Q (2017): 2048 qubits (2011: 128 qubits), fidelity = ???
Annealing quantum processors (usable only for combinatorial optimization problems with many local minima)
Use of Josephson junctions (T°<0.015K, 25 kW)
- Google Bristlecone (2018): 72 qubits, fidelity $\sim99\%$
Gate model (universal) quantum processors
Superconducting circuits
- IBM Q 20 Tokyo (2017) 20 qubits (prototype 50 qubits), fidelity $\sim93\%$
Gate model (universal) quantum processors
Superconducting circuits
- Rigetti 19Q Acorn (2017): 19 qubits, fidelity = ???
Gate model (universal) quantum processors
Aluminium circuits on a silicon wafer? Superconducting circuits?
$\ $
The construction of a quantum computer: beyond the publicity stunts, a nice puzzle (C-NET, 2019/05/14)
http://ludovic-noirie.fr/sciences/quantum-computing/link/CNET.20190514.htm
Simulated quantum computers¶
Simulating generic quantum computers¶
Very limited size of simulated generic quantum computers: $n$ qubits gives $N = 2^n$ values $x$ and unitary operators with $N^2 = 2^{2n}$ complex coefficients.
$n \sim 135$ qubits $\Rightarrow$ $N^2 \sim 2^{270} = (2^{10})^{27} \sim 10^{81} \sim $ number of atoms in the observable universe...
RAM required to store $n$-qubit register:
- $2^n$ complex numbers $\times\ 2$ real numbers $\times\ 8$ bytes (double precision)
- 16 qubits: 1 GB
- 32 qubits: 64 GB
- 48 qubits: 4096 TB
$\ $
Some references for simulated generic quantum computers
IBM cloud simulator "statevector to 32Q": 32 qubits
https://www.ibm.com/quantum-computing/technology/simulatorQiskit IBM on your PC: ??? qubits (probably $\leq 20$)
https://qiskit.org/ https://github.com/Qiskit
Simulating specific quantum computers¶
Gottesman–Knill theorem
A quantum circuit using only the following elements can be simulated efficiently on a classical computer:
(1) Preparation of qubits in computational basis states
(2) Quantum gates from the Clifford group: Hadamard gates, controlled NOT gates, phase gates.
(3) Measurements in the computational basis
Several important types of quantum algorithms use only Clifford gates, most importantly the standard algorithms for entanglement purification and for quantum error correction. From a practical point of view, stabilizer circuits have been simulated in $O(n \log n)$ time using the graph state formalism.
$\Rightarrow n \sim 1000s$ qubits with $\sim n \log n$ gates in few hours in 2004.
References for simulated specific quantum computers
https://en.wikipedia.org/wiki/Gottesman%E2%80%93Knill_theorem
CHP: CNOT-Hadamard-Phase
https://www.scottaaronson.com/chp/$[$Got1998$]$ D. Gottesman: The Heisenberg Representation of Quantum Computers. arXiv:quant-ph/9807006v1, 1998.
https://arxiv.org/abs/quant-ph/9807006v1$[$AF2004$]$ S. Aaronson, D. Gottesman: Improved simulation of stabilizer circuits. Phys. Rev. A. 70(5):052328, 2004.
https://arxiv.org/abs/quant-ph/0406196IBM cloud simulator "stabilizer to 50,000Q - coming soon": 50000 qubits stabilizer
https://www.ibm.com/quantum-computing/technology/simulatorIBM cloud simulator "extended-stablizer to 63Q - coming soon": 63 qubits stabilizer
https://www.ibm.com/quantum-computing/technology/simulator
Advantages of quantum computers¶
(1) A quantum computer can theoretically find a solution to some problem faster than classical computers: see the examples of quantum algorithms.
(2) Quantum computer does not consume energy during quantum processing, but just for the preparation (initialization) and the measurement (output measurement): The system is isolated and its evolution is governed by the Schrödinger equation (reversible), which conserves the energy.
Proof:
Consider a basis $\left| \varphi_k \right\rangle$, $k \in \left\{0, 1, \cdots, N-1 \right\}$ ($N = 2^n$ for a register of n qubits), of eigenvectors of the Hamiltonian $\hat{H}$ (the Hamiltonian does not depends on time for isolated systems), with eigenvalues $E_k$ (energy of state $\left| \varphi_k \right\rangle$).
At any time $t$, $\left|\psi\left(t\right)\right\rangle = \sum \alpha_k \left(t\right) \left| \varphi_k \right\rangle$.
The Schrödinger equation gives $i \hslash \frac{d}{dt} \sum \alpha_k \left(t\right) \left| \varphi_k \right\rangle = \hat{H} \sum \alpha_k \left(t\right) \left| \varphi_k \right\rangle = \sum \alpha_k \left(t\right) E_k \left| \varphi_k \right\rangle.$
Thus we have $\alpha_k \left(t\right) = \alpha_k \left(0\right) e^{-i \frac{E_k}{\hslash} t}$ and the probability to measure the energy $E_k$ is constant.
(3) Quantum computation and telecommunication systems cannot be spied.
If Eve intercepts a qubit and makes a measurement, it changes its state: this can be detected by Alice and/or Bob.
Thanks to the no-cloning theorem, Eve cannot make a copy of an unknown qubit.
Main application: quantum cryptography using "BB84" protocol (quantum key distribution - QKD):
https://en.wikipedia.org/wiki/BB84
$[$BB1984$]$ C. H. Bennett, G. Brassard, Giles: Quantum cryptography: Public key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 175: 8, 1984.
Today's capabilities for quantum cryptography: over ~100km fiber length without "quantum repeater".
1 Mbit/s over 50km standard fiber in 2014:
$[$2014$]$ L. C. Comandar, B. Fröhlich, M. Lucamarini, K. A. Patel, A. W. Sharp, J. F. Dynes, Z. L. Yuan, R. V. Penty, and A. J. Shields: Room temperature single-photon detectors for high bit rate quantum key distribution, Appl. Phys. Lett. 104, 021101, 2014.
https://doi.org/10.1063/1.4855515
Cerberis3 QKD System commercially available, ~ 1.4 kbit/s at 50 km
ID Quantique, SK Telecom & Nokia Secure Optical Transport System Using Quantum Key Distribution (QKD), 2018
https://www.idquantique.com/idq-sk-telecom-nokia-secure-optical-transport-system-using-qkd/
Drawbacks of quantum computers¶
Difficulty to design efficient and usable quantum algorithms¶
Quantum computing algorithm design is very different to classical computing: one needs to think (very) differently.
Even for known algorithms: "Oracle gates" implementation is not trivial...
Requirements for a usable quantum computer¶
$[$Div2000$]$ D. P. DiVincenzo,: The Physical Implementation of Quantum Computation. Fortschritte der Physik, 48(9–11):771–783, 2000.
(1) A scalable physical system with well characterized qubits (usable large number of qubits)
(2) The ability to initialize the state of the qubits to a simple fiducial state, such as $\left|0 0 \cdots 0\right\rangle$ (initialization problem)
(3) Long relevant decoherence times, much longer than the gate operation time (problem of decoherence)
(4) A "universal" set of quantum gates (ability to make any quantum gate)
(5) A qubit-specific measurement capability (qubits easy to read without errors)
Quantum decoherence¶
Quantum coherence occurs because of (non-avoidable) interactions of any quantum system with the external world.
Quantum coherence change the state of the quantum register in some irreversible ways (it acts like measurements: it partly break the superposition of entangled states).
Amplification cannot be used: no-cloning theorem!
Quantum threshold theorem:
https://en.wikipedia.org/wiki/Quantum_threshold_theorem
A quantum computer with a physical error rate below a certain threshold can,
through application of quantum error correction schemes,
suppress the logical error rate to arbitrarily low levels.
Current estimates put the threshold for the surface code on the order of 1%.
At a 0.1% probability of a depolarizing error,
the surface code would require approximately 1000-10000 physical qubits per logical data qubit,
though more pathological error types could change this figure drastically.
A very different approach to the stability-decoherence problem is to create a topological quantum computer with anyons, quasi-particles used as threads and relying on braid theory to form stable logic gates.
Some skepticism about quantum computers¶
Gil Kalai (Hebrew University in Jerusalem): The Argument Against Quantum Computers, interview Quanta Magazine, 2018/02/07
http://ludovic-noirie.fr/sciences/quantum-computing/link/QMag.20180207.htm
"I think that the effort required to obtain a low enough error level for any implementation of universal quantum circuits
increases exponentially with the number of qubits, and thus, quantum computers are not possible".
Mikhail Dyakonov (Univ. Montpellier): The Case Against Quantum Computing, IEEE Spectrum, 2018/11/15
http://ludovic-noirie.fr/sciences/quantum-computing/link/IEEEsp.20181115.htm
"Could we ever learn to control the more than $10^{300}$ continuously variable parameters defining the quantum state of such a system?
My answer is simple. No, never."
David Schneider: The U.S. National Academies Reports on the Prospects for Quantum Computing, IEEE Spectrum, 2018/12/05
http://ludovic-noirie.fr/sciences/quantum-computing/link/IEEEsp.20181205.htm
"The report summary makes clear that the challenges are enormous and that 'there is no guarantee that all of these challenges will be overcome'".
"'Quantum computing is valuable for driving foundational research that will help advance humanity’s understanding of the universe.
As with all foundational scientific research, discoveries in this field could lead to transformative new knowledge and applications.'"