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 p0$p_0$, p1$p_1$ are the probability of being 0$0$, 1$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 l1 norm linear tranformation.

Quantum Bit (qubit)Permalink

For qubit, we are able to do l2 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∈C2×2. Before talking about transformations, we first introduce k-qubits as follows

and our transformation becomes T∈C2k×2k

Some NotationsPermalink

Quantum TransformationsPermalink

T is a quantum transformation iff

• T is linear: T∈Cd×d
• T is norm preserving ⇔∀v∈Cd,‖v‖2=‖Tv‖2⇒T⋅T†=I

Basic Quantum Gates (Between 2/3 qubits)Permalink

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}→{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:|0,1>

1. |0,1>H→|+,−>
2. |+,−>Uf→???

So

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