Basic Quantum Computing

June 10, 2017 4 minute read

Basic Quantum Computing with Least Physics PossiblePermalink

Classical Probability BitPermalink

We will start by talking about classical probability bit. Here is the one bit representation $p_{0}$ , $p_{1}$ are the probability of being $0$ , $1$ respectively.

(\begin{matrix} p_{0} \\ p_{1} \end{matrix}) s . t . p_{0} + p_{1} = 1, p_{0}, p_{1} \in R, 0 \leq p_{0}, p_{1} \leq 1

And here is the n-bits representation

(\begin{matrix} p_{0 \dots 00} \\ p_{0 \dots 01} \\ p_{0 \dots 10} \\ ⋮ \\ p_{1 \dots 11} \end{matrix}) \in R^{2^{n}} s . t . \sum p_{x} = 1, p_{x} \in [0, 1] \in R, x \in {0, 1}^{n}

So we can do some transformation to the bit:

(\begin{matrix} p_{0} \\ p_{1} \end{matrix}) \overset{I}{\to} (\begin{matrix} p_{0} \\ p_{1} \end{matrix})

(\begin{matrix} p_{0} \\ p_{1} \end{matrix}) \overset{N O T}{\to} (\begin{matrix} p_{1} \\ p_{0} \end{matrix})

Or if we have two bits

(\begin{matrix} p_{0} \\ p_{1} \end{matrix}), (\begin{matrix} p_{0} \\ p_{1} \end{matrix})

and want to do an XOR with two dependent bits

(\begin{matrix} p_{00} \\ p_{01} \\ p_{10} \\ p_{11} \end{matrix}) \overset{X O R}{\to} (\begin{matrix} p_{0} \\ 0 \\ 0 \\ p_{1} \end{matrix})

But it is not possible (physically) to do something like this, which kind of does XOR with two independent bits:

(\begin{matrix} p_{00} \\ p_{01} \\ p_{10} \\ p_{11} \end{matrix}) \overset{X O R^{'}}{\to} (\begin{matrix} p_{0} \cdot p_{0} \\ p_{0} \cdot p_{1} \\ p_{1} \cdot p_{0} \\ p_{1} \cdot p_{1} \end{matrix})

In other words, physically, in our universe, we can only do $l_{1}$ norm linear tranformation.

Quantum Bit (qubit)Permalink

For qubit, we are able to do $l_{2}$ norm. A single qubit is difine as follows:

(\begin{matrix} α \\ β \end{matrix}) \in C^{2} s . t . | α |^{2} + | β |^{2} = 1, | α | := \sqrt{α \cdot \bar{α}} P r o b [m = 0] = | α |^{2} = (\begin{matrix} 1 \\ 0 \end{matrix}) P r o b [m = 1] = | β |^{2} = (\begin{matrix} 0 \\ 1 \end{matrix})

Certainly we can do transformation to one qubit. In this case, the transformation we have is $T \in C^{2 \times 2}$ . Before talking about transformations, we first introduce k-qubits as follows

(\begin{matrix} α_{0 \dots 00} \\ α_{0 \dots 01} \\ α_{0 \dots 10} \\ ⋮ \\ α_{1 \dots 11} \end{matrix}) \in C^{2^{k}} s . t . \sum_{x \in {0, 1}^{k}} | α_{x} |^{2} = 1

and our transformation becomes $T \in C^{2^{k} \times 2^{k}}$

Some NotationsPermalink

v = (\begin{matrix} α_{1} \\ α_{2} \\ ⋮ \\ α_{d} \end{matrix}) \in C^{d} v^{†} = (\bar{α_{1}}, \dots, \bar{α_{d}}) < v, w >= v^{†} \cdot w = \bar{< w, v >} =< v | w > v ⊥ w \Leftrightarrow v^{†} w = 0 ‖ v ‖ = \sqrt{\sum_{i = 1}^{d} α_{i} \bar{α_{i}}} = v^{†} v T = (\begin{matrix} T_{11} & \dots & T_{1 d} \\ ⋮ & ⋱ & ⋮ \\ T_{d 1} & \dots & T_{d d} \end{matrix}) \bar{T} = (\begin{matrix} \bar{T_{11}} & \dots & \bar{T_{d 1}} \\ ⋮ & ⋱ & ⋮ \\ \bar{T_{1 d}} & \dots & \bar{T_{d d}} \end{matrix}) (\begin{matrix} α_{0} \\ α_{1} \end{matrix}) \otimes (\begin{matrix} α_{0} \\ α_{1} \end{matrix}) = (\begin{matrix} α_{0} β_{0} \\ α_{0} β_{1} \\ α_{1} β_{0} \\ α_{1} β_{1} \end{matrix}) C^{k} \otimes C^{l} = C^{k l} i f | \tilde{Φ} >= U | Φ >, | \tilde{Ψ} >= U | Ψ >, t h e n < Φ | Ψ >=< \tilde{Φ} | \tilde{Ψ} > a n d < \tilde{Φ} | =< Φ | U^{†} | 0 >:= (\begin{matrix} 1 \\ 0 \end{matrix}) | 1 >:= (\begin{matrix} 0 \\ 1 \end{matrix}) | + >:= (\begin{matrix} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{matrix}) = 1 / \sqrt{2} (| 0 > + | 1 >) | - >:= (\begin{matrix} 1 / \sqrt{2} \\ - 1 / \sqrt{2} \end{matrix}) = 1 / \sqrt{2} (| 0 > - | 1 >) H := 1 / \sqrt{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) H | 0 >= | + > H | 1 >= | - > H | + >= | 0 > H | - >= | 1 > | X, Y >:= | X > \otimes | Y > i f f : {0, 1}^{k} \to {0, 1}, t h e n | X, Z > \overset{U_{f}}{\to} | X, Z + f (X) >

Quantum TransformationsPermalink

$T$ is a quantum transformation iff

$T$ is linear: $T \in C^{d \times d}$
$T$ is norm preserving $\Leftrightarrow \forall v \in C^{d}, ‖ v ‖^{2} = ‖ T v ‖^{2} \Rightarrow T \cdot T^{†} = I$

Basic Quantum Gates (Between 2/3 qubits)Permalink

S W A P := (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) i . e . (X, Y) \overset{S W A P}{\to} (Y, X) C N O T := (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}) i . e . (X, 0 / 1) \overset{C N O T}{\to} {\begin{array}{rcl} (X, 0 / 1) & if & X = 0 \\ (X, 1 / 0) & if & X = 1 \end{array} C C N O T := (\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix}) i . e . (X, Y, Z) \overset{C C N O T}{\to} (X, Y, Z \oplus X \land Y) (X, Y, 0) \overset{C C N O T}{\to} (X, Y, X \land Y)

Note: all transformations are inversible. Specifically, for the above 3 trans., the inverse of them are themselves. Namely, apply it twice and we will be back to the original position.

To implement some classical function $f$ , we need the input bits as well as some extra bits for input to have extra space to work with.

One Small Quantum Algorithm ExamplePermalink

Here we will talk about a small example of quantum algorithms, just to get a feel of how quantum gates works and why it is sometimes more efficient than classical algorithms.

Deutsch Problem

Given $f {0, 1} \to {0, 1}$ , we ask if $f (0) = f (1)$ . Classically we have to evaluate twice: both $f (0)$ and $f (1)$ . Quantumly we can solve it with one transformation and evaluate it.

$i n p u t : | 0, 1 >$

$| 0, 1 > \overset{H}{\to} | +, - >$
$| +, - > \overset{U_{f}}{\to} ? ? ?$

| b, - > \overset{U_{f}}{\to} \dots \to | (- 1)^{f (b)} b, - > A n d | +, - > \overset{U_{f}}{\to} 1 / \sqrt{2} ((- 1)^{f (0)} \cdot | 0 > + (- 1)^{f (1)} \cdot | 1 >) \otimes | - >\to {\begin{array}{rcl} \pm | + > & if & f (0) = f (1) \\ \pm | - > & if & f (0) \neq f (1) \end{array}

So if we measure the result, we will see $” 0 ” i f f f (0) = f (1)$ , and $” 1 ” i f f f (0) \neq f (1)$

Share on

Twitter Facebook LinkedIn

Yanxi Chen

Basic Quantum Computing

Basic Quantum Computing with Least Physics PossiblePermalink

Classical Probability BitPermalink

Quantum Bit (qubit)Permalink

Some NotationsPermalink

Quantum TransformationsPermalink

Basic Quantum Gates (Between 2/3 qubits)Permalink

One Small Quantum Algorithm ExamplePermalink

Share on

Comments

You May Also Enjoy

鸡肝酱Pâté

萝卜/芋头糕

潮汕肉丸

焦糖炼奶