Quantum Gates: Single Qubit Gates

Leave a reply

A classical computer is built from electrical circuits that consist of logic gates and wires. The logic gates perform intended logical operations of information and wires pass information between logic gates. Similarly, a quantum computer would be built from quantum circuits that consist of quantum gates and wires. However, when it comes down to comparing how operations are performed at elementary gates level, there is no similarity between classical logic gates and quantum gates. Unlike classical logic gates, quantum gates operate not according to logical rules but to physical (quantum mechanical) laws. A single qubit gate acts on not only on qubits $|0\rangle=\begin{bmatrix}1\\0\end{bmatrix}$ and $|1\rangle=\begin{bmatrix}0\\1\end{bmatrix}$ but also on a superposition of $|0\rangle$ and $|1\rangle$, $\alpha|0\rangle+\beta|1\rangle$, where $\alpha$ and $\beta$ are complex numbers. For an obvious reason, single qubit gates are $2\times 2$ matrices. Furthermore, a quantum gate operation is performed through a unitary time evolution, and this means that they are required to be unitary matrices. Recall that a matrix $U$ of complex entries is unitary if $UU^\dagger=I$ where $\dagger$ denotes transpose conjugate i.e. $U^\dagger = \bar U^t$. If we write $U=\begin{bmatrix}a & b\\c & d\end{bmatrix}$, then $U$ is unitary if and only if $|a|^2+|b|^2=|c|^2+|d|^2=1$ and $a\bar c+b\bar d=0$. Any unitary matrix is qualified to be a quantum gate but not all unitary matrices would be interesting or useful gates. For practical purposes, it is important to see which gates are universal if there are any and that which gates are physically implementable. The following are some examples of well-known single cubit gates.

  1. Pauli-X, Pauli-Y, Pauli-Z gates. A matrix $H$ is Hermitian if $H=H^\dagger$. Hermitian matrices play a crucial role in quantum mechanics as Hamiltonians are required to be Hermitian. The eigenvalues of a Hamiltonian are the energies of the corresponding quantum system and of course they all have to be real. Hermitian matrices are guaranteed to have all real eigenvalues. A $2\times 2$ Hermitian matrix can be written in the form $H=\begin{bmatrix}x_0+x_3 & x_1-ix_2\\x_1+ix_2 & x_0-x_3\end{bmatrix}$ where the $x_i$ are all reals. The matrices \begin{equation}\label{eq:pauli}\sigma_0=\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix},\ \sigma_1=\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix},\ \sigma_2=\begin{bmatrix}0 & -i\\i & 0\end{bmatrix},\ \sigma_3=\begin{bmatrix}1 & 0\\0 & -1\end{bmatrix}\end{equation} form a basis for the space of all Hermitian matrices. The $\sigma_i$ in \eqref{eq:pauli} are called the Pauli spin matrices in physics. $\sigma_0$ is just the identity matrix but notice that $\sigma_1,\sigma_2,\sigma_3$ are also unitary matrices. They are called Pauli-X, Pauli-Y, Pauli-Z gates, respectively. Pauli-X gate is also called NOT gate as it acts like the classical NOT gate. \begin{align*}\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}&=\begin{bmatrix}0\\1\end{bmatrix}\\\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}&=\begin{bmatrix}0\\1\end{bmatrix}\end{align*}
  2. Square root of NOT gate. The gate $$\sqrt{\mathrm{NOT}}=\frac{1}{2}\begin{bmatrix}1+i & 1-i\\1-i & 1+i\end{bmatrix}$$ is called square root of NOT gate because $$\sqrt{\mathrm{NOT}}\cdot\sqrt{\mathrm{NOT}}=\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$$ $\sqrt{\mathrm{NOT}}$ is one of the gates that are truly quantum because there is no classical counterpart.
  3. Hadamard gate. $$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1\\1 & -1\end{bmatrix}$$ is called the Hadamard gate. It turns $|0\rangle$ to $\frac{|0\rangle+|1\rangle}{\sqrt{2}}$ and $|1\rangle$ to $\frac{|0\rangle-|1\rangle}{\sqrt{2}}$.

References:

  1. Michael A. Nielsen and Isaac L. Chung, Quantum Computation and Quantum Information, Cambridge University Press, 2000.
  2. Colin P. Williams and Scott H. Clearwater, Explorations in Quantum Computing, Spinger Telos, 1998.

Markov Processes: The Poisson Process

Leave a reply

A Markov process is a stochastic process such that given the present state of the system, the future behavior is independent of the past history.

Suppose that the size of the population under consideration at time $t$ is represented by a discrete random variable $X(t)$ with probability $$P\{X(t)=n\}=p_n(t),\ n=0,1,2,\cdots$$ At certain instants of time, there will be discrete changes in the population size, due to the loss or death of an individual, or to the appearance or birth of new individuals.

We now consider an example of a stochastic process, which will give rise to a simple model of a Markov process called the Poisson process. Suppose that we are measuring the radiation of a certain radioactive substance. Let $X(t)$ be the total number of particles recorded up to time $t$. Also suppose that the chance of a new particle being recorded is any short time interval is independent of not only the previous states but also the present state. Then the chance of a new addition to the total count during a very short time interval $\Delta t$ can be written as $\lambda\Delta t+o(\Delta t)$ where $\lambda$ is a constant and $o(\Delta t)$ is the chance of two or more simultaneous emissions. The chance of no change in the total count would be $1-\Delta t-o(\Delta t)$. Thus, we obtain \begin{equation}\label{eq:poisson}p_n(t+\Delta t)=p_{n-1}(t)\lambda\Delta t+p_n(t)(1-\lambda\Delta t)\end{equation} where terms that are small compared with $\Delta t$ have been disregarded. \eqref{eq:poisson} results in the following differential-difference equation \begin{equation}\begin{aligned}\frac{dp_n(t)}{dt}&=\lim_{\Delta t\to 0}\frac{p_n(t+\Delta t)-p_n(t)}{\Delta t}\\&=\lambda\{p_{n-1}(t)-p_n(t)\},\ n>0\end{aligned}\label{eq:poisson2}\end{equation}

Note that we have $n=0$ at time $t+\Delta t$ only if $n=0$ at time $t$ and no new particles are emitted in $\Delta t$. This means that we have $$p_0(t+\Delta t)=p_0(t)(1-\lambda\Delta t)$$ and subsequently the differential equation $$\frac{dp_0}{dt}=-\lambda p_0(t)$$ whose solution is $$p_0(t)=e^{-\lambda t}$$ with the initial condition $p_0(0)=1$. This initial condition can be obtained by setting the Geiger counter to $0$ in the beginning of the process. Starting off with $p_0(t)$, iterative applications of \eqref{eq:poisson2} will result in $$p_n(t)=\frac{(\lambda t)^ne^{-\lambda t}}{n!},\ n=0,1,2,\cdots$$ which is a Poisson distribution with parameter $\lambda t$.

References:

  1. Norman T. J. Bailey, The Elements of Stochastic Processes with Applications to the Natural Sciences, John Wiley & Sons, Inc., 1964.

Simple Epidemics: Deterministic Model

Leave a reply

Suppose that we have a homogeneously mixing group of individuals of total size $n+1$ and that the epidemics is started off at $t=0$ by one individual becoming infectious. The remaining $n$ individuals are susceptible. Denote by $x$ and $y$ the numbers of susceptibles and infectives, respectively. Then $x+y=n+1$. Also suppose that the rate of occurrence of new infections is proportional to the number of infectives as well the number of susceptibles. Then we obtain the following differential equation \begin{equation}\label{eq:infectrate}\frac{dx}{dt}=-\beta xy=-\beta x(n-x+1)\end{equation} where $\beta$ is the constant of proportionality called the infection-rate. Let $\tau=\beta t$. \eqref{eq:infectrate} becomes \begin{equation}\label{eq:infectrate2}\frac{dx}{d\tau}=-x(n-x+1)\end{equation} With initial condition $x(0)=n$, the solution of \eqref{eq:infectrate2} is given by $$x(\tau)=\frac{n(n+1)}{n+e^{(n+1)\tau}}$$ The number of infectives at $\tau$ is then given by $$y(\tau)=\frac{n+1}{1+ne^{-(n+1)\tau}}$$ The rate at which new infectives accrue $$w(\tau)=\frac{dy}{d\tau}$$ is called the epidemic curve. It follows from \eqref{eq:infectrate2} that $$w(\tau)=-\frac{dx}{d\tau}=-xy=\frac{n(n+1)^2e^{(n+1)\tau}}{[n+e^{(n+1)\tau}]^2}$$ Using the standard argument from calculus, we find that $w(\tau)$ assumes its maximum when $x=y$ i.e. when the number of susceptibles and the number of infectives are the same and that happens when $\tau=\frac{\ln n}{n+1}$, and the maximum rate at which new infections accrue is $w=\frac{1}{4}(n+1)^2$.

Figure 1. Deterministic Epidemic Curve for n=20 (red) and for n=30 (blue).

As a reminder the model we discussed above assumed that the epidemic is started off by one individual (patient zero). Now, we want to generalized the model by assuming that the epidemic is started off by several infectious individuals. Let $x(0)=n$ and $y(0)=a$. Then the equation \eqref{eq:infectrate2} is modified to \begin{equation}\label{eq:infectrate3}\frac{dx}{dt}=-x(n-x+a)\end{equation} The solution of \eqref{eq:infectrate3} is $$x(\tau)=\frac{n(n+a)}{n+ae^{(n+a)\tau}}$$ The corresponding epidemic curve is given by $$w=\frac{an(n+a)^2e^{(n+a)\tau}}{[n+ae^{(n+a)\tau}]^2}$$ Let $W=\frac{w}{n}=\frac{a(n+a)^2e^{(n+a)\tau}}{[n+ae^{(n+a)\tau}]^2}$, $0\leq\tau<\infty$. Then \begin{align*}\int_0^\infty Wd\tau&=\int_{n+a}^\infty\frac{(n+a)}{u^2}du\ (u=n+ae^{(n+a)\tau})\\&=1\end{align*} So, $W$ can be interpreted as the probability density of a new infection occurring. The mean value of the variable $\tau$ is \begin{align*}\bar\tau&=\int_0^\infty\tau Wd\tau\\&=-\frac{1}{n}\int_0^\infty\tau\frac{dx}{d\tau}d\tau\\&=\frac{1}{n}\ln\left(1+\frac{n}{a}\right)\end{align*}

References:

  1. Norman T. J. Bailey, A Simple Stochastic Epidemic, Biometrika, Vol. 37, No. 3/4 (Dec., 1950), 193-202.
  2. The Mathematical Theory of Infectious Diseases and Its Applications, Norman T. J. Bailey, Second Edition, Charles Griffin & Company LTD, 1975.

The Tensor Product

Leave a reply

Let $V$ and $W$ be two vector spaces of dimensions $m$ and $n$, respectively. The tensor product of $V$ and $W$ is a space $V\otimes W$ of dimension $mn$ together with a bilinear map $$\varphi: V\times W\longrightarrow V\otimes W;\ \varphi(v,w)=v\otimes w$$ which satisfy the following universal property: For any vector space $X$ and any bilinear map $\psi: V\times W\longrightarrow X$, there exists uniquely a linear map $\gamma : V\otimes W\longrightarrow X$ such that $\psi(v,w)=\gamma(u\otimes w)$ for all $v\in V$ and $w\in W$.

$$\begin{array}[c]{ccc}V\otimes W & & \\\uparrow\scriptstyle{\varphi} & \scriptstyle{\gamma}\searrow& \\V\times W & \stackrel{\psi}\rightarrow & X\end{array}\ \ \ \gamma\circ\varphi=\psi$$

Often, we use more down to earth definition of the tensor product. Let $\{e_1,\cdots,e_m\}$ and $\{f_1,\cdots,f_n\}$ be bases of $V$ and $W$, respectively. The tensor product $V\otimes W$ is a vector space of dimension $mn$ spanned by the basis $\{e_i\otimes f_j: i=1,\cdots,m,\ j=1,\cdots,n\}$. Let $v\in V$ and $w\in W$. Then $$v=\sum_i v_ie_i\ \mbox{and}\ w=\sum_j w_jf_j$$ The tensor product $v$ and $w$ is then given by $$v\otimes w=\sum_{i,j}v_iw_je_i\otimes f_j$$ It can be easily shown that this definition of the tensor product in terms of prescribed bases satisfies the universality property. Although this definition uses a choice of bases of $V$ and $W$, the tensor product $V\otimes W$ must not depend on a particular choice of bases, i.e. regardless of the choice of bases the resulting tensor product must be the same. This also can be shown easily using some basic properties from linear algebra. I will leave them for exercise for readers.

The tensor product can be used to describe the state of a quantum memory register. A quantum memory register consists of many 2-state systems (Hilbert spaces of qubits). Let $|\psi^{(1)}\rangle$ and $|\psi^{(2)}\rangle$ be qubits associated with two different 2-state systems. In terms of the standard orthogonal basis $\begin{pmatrix}1\\0\end{pmatrix}$ and $\begin{pmatrix}0\\1\end{pmatrix}$ for each 2-state system, we have \begin{align*}|\psi^{(1)}\rangle&=\begin{pmatrix}\omega_0^{(1)}\\\omega_1^{(1)}\end{pmatrix}=\omega_0^{(1)}\begin{pmatrix}1\\0\end{pmatrix}+\omega_1^{(1)}\begin{pmatrix}0\\1\end{pmatrix}\\|\psi^{(2)}\rangle&=\begin{pmatrix}\omega_0^{(2)}\\\omega_1^{(2)}\end{pmatrix}=\omega_0^{(2)}\begin{pmatrix}1\\0\end{pmatrix}+\omega_1^{(2)}\begin{pmatrix}0\\1\end{pmatrix}\end{align*} Define $\otimes$ on the basis members as follows: \begin{align*}|00\rangle&=\begin{pmatrix}1\\0\end{pmatrix}\otimes\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}1\\0\\0\\0\end{pmatrix},\ |01\rangle=\begin{pmatrix}1\\0\end{pmatrix}\otimes\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}0\\1\\0\\0\end{pmatrix}\\|10\rangle&=\begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}0\\0\\1\\0\end{pmatrix},\ |11\rangle=\begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}0\\0\\0\\1\end{pmatrix}\end{align*} These four vectors form a basis for a 4-dimensional Hilbert space (a 2-qubit memory register). It follows that \begin{align*}|\psi^{(1)}\rangle\otimes|\psi^{(2)}\rangle&=\omega_0^{(1)}\omega_0^{(2)}|00\rangle+\omega_0^{(1)}\omega_1^{(2)}|01\rangle+\omega_1^{(1)}\omega_0^{(2)}|10\rangle+\omega_1^{(1)}\omega_1^{(2)}|11\rangle\\&=\begin{pmatrix}\omega_0^{(1)}\omega_0^{(2)}\\\omega_0^{(1)}\omega_1^{(2)}\\\omega_1^{(1)}\omega_0^{(2)}\\\omega_1^{(1)}\omega_1^{(2)}\end{pmatrix}\end{align*}Similarly, to describe the state of a 3-qubit memory register, one performs the tensor product $|\psi^{(1)}\rangle\otimes|\psi^{(2)}\rangle\otimes|\psi^{(3)}\rangle$.

Quantum memory registers can store an exponential amount of classical information in only a polynomial number of qubits using the quantum property the Principle of Superposition. For example, consider the two classical memory registers storing complimentary sequences of bits $$\begin{array}{|c|c|c|c|c|c|c|}\hline1 & 0 & 1 & 1 & 0 & 0 &1\\\hline 0 & 1 & 0 & 0 & 1 & 1 & 0\\\hline\end{array}$$ A single quantum memory register can store both sequences simultaneously in an equally weighted superposition of the two states representing each 7-bit input $$\frac{1}{\sqrt{2}}(|1011001\rangle+|0100110\rangle)$$

A matrix can be considered as a vector. For example, a $2\times 2$ matrix $\begin{pmatrix}a & b\\c & d\end{pmatrix}$ can be identified with the vector $(a, b, c, d) \in \mathbb{R}^4$. Hence one can define the tensor product of two matrices, called the Kronecker product, in a similar manner to that of two vectors. For example, $$\begin{pmatrix}a_{11} & a_{12}\\a_{21} & a_{22}\end{pmatrix}\otimes\begin{pmatrix}b_{11} & b_{12}\\b_{21} & b_{22}\end{pmatrix}:=\begin{pmatrix}a_{11}\begin{pmatrix}b_{11} & b_{12}\\b_{21} & b_{22}\end{pmatrix} & a_{12}\begin{pmatrix}b_{11} & b_{12}\\b_{21} & b_{22}\end{pmatrix}\\a_{21}\begin{pmatrix}b_{11} & b_{12}\\b_{21} & b_{22}\end{pmatrix} & a_{22}\begin{pmatrix}b_{11} & b_{12}\\b_{21} & b_{22}\end{pmatrix}\end{pmatrix}\\=\begin{pmatrix}a_{11}b_{11} & a_{11}b_{12} & a_{12}b_{11} & a_{12}b_{12}\\a_{11}b_{21} & a_{11}b_{22} & a_{12}b_{21} & a_{12}b_{22}\\a_{21}b_{11} & a_{21}b_{12} & a_{22}b_{11} & a_{22}b_{12}\\a_{21}b_{21} & a_{21}b_{22} & a_{22}b_{21} & a_{22}b_{22}\end{pmatrix}$$

References:

[1] A. Yu. Kitaev, A. H. Shen and M. N. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics Volume 47, American Mathematical Society, 2002

[2] Colin P. Williams and Scott H. Clearwater, Explorations in Quantum Computing, Springer TELOS, 1998

What is an angle?

Leave a reply

The notion of an angle is so basic (and we use it everyday indeed) that anyone with basic math knowledge would know what it is, right? Turns out it is not the case. I often was surprised to find out that even math majors in upper level math courses can’t explain what an angle is. They commonly answer like this: First draw two rays that intersect at a point and then draw an arc between them. They would call this arc an angle.

Figure 1. An angle

But then there can be so many different choices of arcs between two such rays. So which arc is an angle? The arc that defines an angle is one that is a part of the unit circle.

Figure 2. An angle

A measurement of an angle requires a unit. It is speculated that the degree measurement was invented by ancient Sumerians. Sumer is the earliest known civilization which was in southern Mesopotamia (modern day southern Iraq) and it dates back before 3,000 B.C. The biblical Genesis appears to have originated from Sumerian creation myth Enûma Eliš which predates Torah (Hebrew Bible). The first man’s name is Adamu and it does have the story of the Great Deluge. Sumerians had own writing system using cuneiform (wedge-shaped marks on clay tablets) and they built massive structures called ziggurats. Amazingly, those ziggurats still remain to this day in modern day Iraq. Sumerians possessed highly advanced level of knowledge in math and science including astronomy. Here is how they introduced the degree unit of angle measurement: Divide the unit circle into 360 equal sections (imagine 360 equal pizza slices). The length of the arc of each section is then defined to be $1^\circ$ and the circumference of the unit circle is $360^\circ$.

Figure 3. Degree angle measurement

Why the number 360? A common speculation is that Sumerians thought 1 year = 360 days, a complete rotation. Oh yes, they appear to have known that Earth is rotating around the Sun on a circular (actually elliptic) orbit. I have a different theory though. I do believe that Sumerians actually knew 1 year = 365 days. But if they used the number 365 to define $1^\circ$, it would have been an awfully ugly and inconvenient angle measurement. I believe that they knew this and used 360 instead.

On the other hand, you know from elementary geometry that the circumference of a circle with radius $r$ is $2\pi r$. So the unit circle has circumference $2\pi$. Hence we must have $$2\pi=360^\circ$$ However, something looks really awkward. The right hand side has a unit while the left hand side doesn’t. So it was given a unit called radian (denoted by rad), i.e. $$2\pi\ \mathrm{rad}=360^\circ$$ or $$\pi\ \mathrm{rad}=180^\circ$$ Note that 1 rad is merely a number (it’s same as the number 1) while $1^\circ$ is not. So in calculus we don’t use degree angle measurement but only use radian angle measurement.

Given an angle $\theta$, there is a corresponding point $(x,y)$ on the unit circle as shown in Figure 4.

Figure 4. Sine and cosine by unit circle

In order to make this correspondence more transparent, one may want to represent $x$ and $y$ in terms of the angle $\theta$. This is how cosine and sine of an angle were introduced: \begin{equation}\label{eq:trig}x=\cos\theta,\ y=\sin\theta\end{equation} The unit circle centered at the origin satisfies the equation \begin{equation}\label{eq:circ}x^2+y^2=1\end{equation} Using \eqref{eq:trig}, \eqref{eq:circ} can be written as \begin{equation}\label{eq:circ2}(\cos\theta)^2+(\sin\theta)^2=1\end{equation} But this looks a bit ugly, so a better looking notations were introduced: $$\cos^2\theta:=(\cos\theta)^2,\ \sin^2\theta:=(\sin\theta)^2$$ Thereby, \eqref{eq:circ2} is written as $$\cos^2\theta+\sin^2\theta=1$$ For an obvious reason, $\cos\theta$ and $\sin\theta$ along with $\tan\theta$, $\cot\theta$, $\sec\theta$, and $\csc\theta$ are called circular functions. I bet though most of you who are reading this have never heard of the name circular functions. The reason is that nowadays those quantities are defined more commonly (and shamefully) by using right triangles. (See Figure 5.) Hence they are called by more familiar name, trigonometic functions.

Figure 5. Sine and cosine by right triangle

An ancient Babylonian clay tablet which dates to 3,700 years ago, around the time when King Hammurabi ruled the Babylonian Empire, was recently decoded by scientists. It turns out that the tablet contains the oldest trigonometric table. In general, trigonometry is thought to have originated by Greek astronomer Hipparchu around 120 B.C. This remarkable discovery tells that ancient Babylonians already have known trigonometry 1,000 years before Greeks did. More details about the clay tablet can be read here.