GaeBlogX Arista Networks, Software-Defined Networking

2017-06-10
Yanxi Chen

# Basic Quantum Computing with Least Physics Possible

## Classical Probability Bit

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.

And here is the n-bits representation

So we can do some transformation to the bit:

Or if we have two bits

and want to do an XOR with two dependent bits

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

In other words, physically, in our universe, we can only do $l_1$ norm linear tranformation.

## Quantum Bit (qubit)

For qubit, we are able to do $l_2$ norm. A single qubit is difine as follows:

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

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

## Quantum Transformations

$T$ is a quantum transformation iff

• $T$ is linear: $T\in\mathbb{C}^{d\times d}$
• $T$ is norm preserving $\Leftrightarrow\forall v\in\mathbb{C}^d,\Vert v\Vert^2=\Vert Tv\Vert^2\Rightarrow T\centerdot T^{\dagger}=I$

## Basic Quantum Gates (Between 2/3 qubits)

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 Example

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\}\rightarrow\{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.

$input:\vert0,1>$

1. $\vert0,1>\xrightarrow{H}\vert+,->$
2. $\vert+,->\xrightarrow{U_f}???$

So

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