Basic notes on Physics.
In the series: Note 3.

Subject: A simple note on Quantum Computing (QC).

Date : 29 October, 2016
Version: 0.4
By: Albert van der Sel
Doc. Number: Note 3.
For who: for beginners.
Remark: Please refresh the page to see any updates.
Status: Ready.



This note is especially for beginners.

Maybe you need to pick up "some" basic "Physics" rather quickly.
So really..., my emphasis is on "rather quickly".

I am not sure of it, but I hope that this note can be of use.
Ofcourse, I hope you like my "style" and try the note anyway.

This note is a trial to show a few highlights on "Quantum Computing" (QC).
When I say "a few", I literally mean a few, since the whole subject is incredably
large by now.

Also due to the nature of the subject, it is optional reading for folks who only
like to learn "practical" physics quickly.

Then you can skip this note, which is no problem, and go for other notes.

However, it's facinating stuff, and it's getting more and more important as time goes on.
That's why it is certainly recommended to aquire at least "some basics" on QC.
But keep in mind that this note is no more than a simple overview on some highlights of QC.

It helps to understand this note, if you have a certain level in "traditional computing",
like some basics of the architecture.
It does not have to be a tremendously high level, just a little is good enough.

But it certainly helps to have a certain basis in math, especially the basics on vectors.
Maybe you like to take a look at my "math note 12: Vector calculus Part 1", first.


This note: Note 3: A simple note on Quantum Computing (QC).

This note is organized in 4 short chapters:

Contents:

1. Introduction and what we need to know first.
2. A few words on Operators, Gates/circuits, kets.
3. Quantum Information vs Classical Information.
4. Quantum Computing.



Chapter 1. Introduction and what we need to know first.

1.1 Temper expectations a bit....

Maybe it's wise to temper the "expectations" somewhat, since present day (real) "Quantum Computing" (QC),
are (still) only used for performing some specific mathematical operations.

Also, in general, It's very difficult to line-up a high number of "quantum bits" (say, e.g, 32 qubits)
for such operations, so it's fair to say that this science is "just starting". However, major steps
were made since the 90s of the former century (around 1994), when Peter Shor published his "quantum algorithm for factoring integers",
which was an enormous stimulus for starting the practical implementations of QC.

It's not to be expected that you will perform all sorts of comodity programs (like email), on a Quantum Computer, very soon.

For now, a number of specific quantum algolrithms are under study, and some have been successfully implemented.

As you will see, those "quantum algolrithms" were developed, and implemented in "quantum circuits", in lab setups.

It's probably fair to say that most lab setups (july 2015) still work with 2, 3, 4 or up to 8 qubits, or a few more.
That is not to say that already some solid state implementations look promising for implementing larger
amounts of qubits.

Then, what we call quantum circuits, most often actually are "events" (like laser pulses, or EM radiation) that
operate on the state of the qubits. We must avoid (for now), the tempting and "reasonable" association, that quantum circuits are
just as manifest and "physically permanent" as real (and traditional) electronic devices are. So, most often, that's not so.

1.2 Bits in classical computing.

Everybody knows the "normal" digital computer. It works with registers (e.g. in cpu's), memory cells, buses, etc...,
all for storing (or transporting) sequences of "0's" and "1's", which physically are Voltages.
So, in a certain implementation, if we take a look at a memory cell, a "1" might correspond to 3.3 Volt,
while a "0" corresponds to 0 Volt.

Now, suppose you have an 8 bits register, for example holding "10110001". You can easily read out that register (observing it),
whithout changing that content. Also, you can copy the content to another register, or to a remote computer etc.. No problems here.
Note that the state of for example, a memory cell, is completely known at some time, and you can read it, while that
operation does not change the value of the memory cell.
Indeed, it's important to note that the contents of memory cells do not change if you just "observe" them (read them).

1.3 The Quantum Bit: qubit.

In the Quantum World, things are a bit different. And so is QC.
The "basic" entity in QC is the "qubit", which is the "quantum bit", and it plays a similar role as the "1" and "0"
in classical computing.

However, the state of a qubit is unknown, up to the point when you observe it.
It may sound strange (which it is), and I try to explain it now.

A qubit is a Quantum System, like an ion, or electron, or photon (etc...), where the state of an observable (a property) has
truly the role of the qubit. For example, it can be the "spin" of an electron, or the "polarization" of a photon.
For example, the spin can be "up" (or 1) or "down" (0) when measured along some "axis" (for example, the z direction), but unmeasured,
the spin is a linear combination of both "up" and "down" at the same time.
Actually, it resembles a "vector" in 2 dimensional space, so in general, the qubit can be written as:

|Ψ> = a|0> + b|1>

In Quantum language, the spin is a "superposition" of the basis (or eigen-) states |0> and |1>.
As it is, when you do not "look" at the qubit (that is: read it, or measure it), you do not know the state of the spin. The only thing
you know is that it is a combination of the basis vectors |0> and |1>, where the coeficients 'a' and 'b', relate tho the
probability of finding the spin as |0> (a), or |1> (b). For 'a' and 'b' must hold: |a|2 + |b|2 =1,
so the sum of all probabilities must (evidently) add up to '1'.

"|Ψ> = a|0> + b|1>" just "looks" pretty much the same as a "highschool math" simple 2 dimensional vector, which can be written
as a sum of basis vectors, like |0> along the x-axis, and |1> along the y-axis.

Note:
Actually, in the 2-dim vector space analogy, we should (maybe) have used (0,1) and (0,-1) to decribe "up" and "down".
However, (0,-1) = -1 x (0,1), so here we just don't have 2 independent basis vectors which can "span" (or describe) this 2-dim space.
This is why I choose the analogy of |0> along the x-axis, and |1> along the y-axis.


it's also very important to realize that |Ψ> is a superposition of |0> and |1> simultaneously.
You may also say that |Ψ> has a two-dimensional state space, formed with an orthonormal basis usually depicted by |0> and |1>.

It's very characteristic of Quantum Mechanics that an observable is some unknown vector in 2 dim space, or n dim space,
or infinitesemale space, where it can be written as a superposition of basis vectors (or superposition of eigen vectors).
You do not know the state. If you measure the observable, the state "collapse" into one of the basis vectors with a certain probability.
So, actually, you did not know what the state was, before the measurement, and that information is lost...

What is this? Is this true? Well, many folks are involved in interpretations of Quantum Mechanics,
and many models have been proposed.
You can't say that it is all resolved. Many questions from physics remain, and it also is important for other fields, e.g. philosophy.

One nice example of a superpostion might be the "position" of an elementary particle, which often in QM language is seen as
a "wave packet". In QM, particles often exibit a wave-like character, and waves, often exibit a particle-like character.
When we look at the "position" of a particle (even at rest), then it resembles a "church bell" shaped wave/probability distribution.
It's very likely to find the particle in the center of the "bell", but there still is a non-zero probability to find
it at the very edges of the (church-like) bell wavepacket.

Superpositions (in the tradional sense) can be found in math too, in nummerous places. For example, any continuous function,
can be written as a large summation of Sinusoidal functions (or cosinus), with certain phases and coefficients.
The more of such parts you add, the more accurate your summation will resemble the original function (Fourier analysis).

1.4 Multiple qubits.

Case 1:

You don't need to remember this, but a two (non-entangled) qubit system has the following four basis vectors |00>, |01>, |10>, and |11>.
This two (non-entangled) qubit system is in a superposition of those 4 basis (or eigen) states:

|Ψ>= a00 |00> + a01 |01> + a10 |10> + a11 |11>

Just as was the case with the single qubit's superposed state, the coefficients (a00,a01,a10,a11) tell us the probability of finding
a certain state after a measurement. For instance, |a00|2 is the probability of obtaining |00>.
Folks then say that after the measurement, the state |Ψ> "collapsed" (or decohered) into |00> (with a probability |a|2).
The "|00>" is a shorthand for saying that the first qubit then was found to be |0>, and the second one was found to be as |0> too.
Note that the equation above is just the (outer) product of 2 qubits, like in "(a|0> + c|1>) X (b|0> + d|1>)".
The qubits are not "intertwined" (entangled), and a measurement on qubit "1", does not fully determinate for what we may find for qubit "2".
So, for example, say that the first qubit was found to be |0>, then, if we observe qubit 2, we still may find that qubit 2
has a certain probability that it will be found in the state |0>, or as to be in the state |1>.

A three qubit register (non-entangled), would then be described as:

|Ψ>= a1 |000> + a2 |001> + .... + a8 |111>

In this case, the vector can be expanded into 8 basis states (|000> up to |111>).

If we would have this as a superposition of 8 states with equal probability, we would have:

|Ψ>= 1/√8 |000> + 1/√8 |001> + .... + 1/√8 |111>

We will use this one in chapter 4.

Case 2:

When two qubits are fully "intertwined", in such a way, that a measurement on one, affects the state of the second one,
then they are called 'entangled'.
So, what you find if you measure qubit 1, will immediately determine the state for qubit 2.
Maybe you don't see this as to be very remarkable right now, but it actually really is vey "remarkable".
Here is an example of two entangled qubits:

1,2 >= 1/√2 . ( |00> + |11> )

Note that the superposition, this time, only means the superposition of the two states |00> and |11>
It simply means that if you measure qubit 1 as to be |0>, it determines that qubit 2 will be observed as |0> as well.
This is true regardless of the distance between those two qubits. So, you could have qubit 1 to be in Lab 1,
and transferred qubit 2 to Lab 2, 150 miles away from Lab 1. Remember, before you observed qubit 1, the system was in
a superposition 1/√2 . ( |00> + |11> ), so each basis state (|00>, |11>) have a 50% chance of being found
in a measurement. But this is true for Lab 1, as well as for Lab 2.
But strangely, what you will measure in Lab 1, will immediately determine what you can find in Lab 2.

Even if this does not strike you as "remarkable", it's Ok, since the purpose was simply to illustrate two types of n qubit systems,
as we have seen in "case 1" and "case 2".

1.5 Quantum parallel processing.

We have seen that a single qubit can be in a superposition of 0 and 1. Now, a "register" of n qubits can be in a superposition
of all 2n possible "values" (states actually), at the same time !
Now compare that to a traditional "classical" register.
Suppose we have 4 classical memory cells. Now, it can hold 1111, or 1010, or other combination, but only one at the same time.
If we have 4 qubits, in a quantum register, we have all states simultanuously (like |0000>, |0101> etc...).

We are not there yet, but I hope that already in this phase, you start to see that "Quantum parallel processing", absolutely
has no classical equivalent.

But this is not the whole story. Measuring a statevector, projects it, or let it collapse, to one basis state.
This way, you have no advantage of the "parallel processing", unless you could do an extremely weak measurement which
does not disturbs the quantum system. Although some ideas have developed into that direction, it's not how present day
quantum computers work.
Most of the "trick" to obtain usefull information, is in the "quantum algolritm" itself.
In this note, we will take an "ultra-light" look at one of the simplest ones, namely "Grover's search algolrithm".

1.6 General statement on QC:

Let's try to formulate a general statement on QC:

In quantum systems, indeed the computational space increases exponentially with the number of qubits.
This, in principle, enables exponential parallelism.
This could lead to exponentially faster quantum algorithms, than which is possible using classical methods.
A main problem is that accessing the results, or the result, requires a measurement of some sort,
and that is the hard part, and it requires new non-traditional programming techniques.

How it often does work, is often like this: Generally, a "quantum algolrithm", implemented in the operations of
"quantum circuits", or "gates", will try to filter out the "solution" amongst the many "alternatives" from the superpositions.

Using qubits this way, and the implementation of gates (which in practice might mean using a laser, or other EM radiation,
or applying voltages etc..), most often encounters all sorts of technical obstacles like decoherence.

Solving the technical hurdles, and finding algolritms (implementing gates), and searching/testing/optimizing the practical
implementations of qubits and gates, and research in Quantum Information Technology, are some main ingredients in QC.

Above, is a very general statement on how it works. However, I hope you will enter the following sections for more details.


Chapter 2. Operators, Gates and circuits.

2.1 A few words on classical gates.

Now, let's go back to the classical computer for a moment. The logic of operations on strings of bits
are performed by "logical" gates like NOT gate, AND gate, XOR gate etc.., all implemented in the chips.
Typically, such a gate has one or more input lines, where the "input bits (voltages)" are put on, and one or
more output lines with the result of the logical operation.

Large series of those boolean gates, ultimatly makes it possible to "add", "multiply" and "move" numbers, and many other operations,
fast and in large quantities, which ultimately makes your computer to do useful work.
Below you a representation of a fundamental classical gate, the "AND" gate, and it's "truth table", which shows the possible
"input bits" and the corresponding "output bit". Many of such sort classical gates exists in your computer chipsets.

Fig 1. The classical AND gate.



Note: note that the AND gate is not reversable. From the output bit, you cannot deduce what the original input was,
except if the output bit is found to be "1".

2.2 A few words on quantum gates.


In Quantum Computing, "quantum gates" may play a role too, and it can be a diverse role. In this case, the "physical implementation"
of a gate might be something that surprises you. For example, it might be an Electromagnetic field, a laserpulse, an optical device,
a solid state device, or anything else suitable to 'put" a qubit (or a basis state of a qubit), into another state.
The "quantum gate" or "quantum circuit" or "quantum logic gates" (all synonyms) are actually simple unitary operations
on qubits. We need to explain that.

We know that the state "|Ψ> = a|0> + b|1>" is a (simultaneous) superposition of the basis states |0> and |1>.
If you like, just view |Ψ> as a 2 dimensional vector.
If we do not "measure" (observe) "|Ψ>", it's state is unknown.
Here is an example of a 3 dimensional state:

|Φ > = a11 > + a22 > + a33 >

You can easily extent it to an "n" dimensional space, and nothing fundamentally changes, really.

We have not explicitly discussed it yet, but the coefficients like "a" and "b" are actually socalled "complex numbers",
but that is not so terribly important for our present discussion.

Although the qubit can exist in infinitely many superposition states (remember, it can be any combination a|0> + b|1>,
where a en b are unknown coefficients, and only |a|2 + |b|2 =1 needs to hold), if we observe it,
it can only be one of the two "projections" |0> or |1>, which are the two basis states, or also called "eigen" states.

Maybe this is something you may call the catch of QM: you may have lots of states of a quantum system at the same time,
which forms a basis for "Quantum parallel processing", but once you measure it, you are left with just one state.

So, our quantum states (like a qubit), can be expressed in terms of vectors in a vector space, or "state space" (also called "Hilbert" space).
Now, the "traditional" algebra with respect to vectorspaces, also defines "Operators", which maps a vector to another vector.
In this sense, the "matrix way" of doing Quantum mechanics works quite the same way.

Ofcourse, many sorts of Operators (or mappings) are possible. But, those Operators which are symmetric, or in better words,
are reversible, preserve certain properties of a state vector, like the "lenght" (or the norm).
A special group of such operators (let's call such an operator "A"), have a socalled "conjugate transpose"
operator, notated by A, for which hold that A . A = I.
"I" then is an operator, which maps any vector onto itself, so, in effect it does "nothing".
The equation 'A . A = I, is quite ok, since applying A, and next A,
makes the total operation reversable.

In textbooks, you may find terms like "Unitary matrices" or "Hermitian operators" and the like, but I don't want
to go too much into that stuff. But indeed, for a Unitary matrix M, it holds that M.M*=I.
For us, in this text, we treat them all as equal.

Why can an operator be represented by a matrix? Well, technicaly, even the most simplest operator of all,
like multiplication with a scalar "c" (just a number), like so:

|Φ> = c . |Ψ>

then c can be seen as a simple 1x1 matrix.

Ok, maybe the former statement is a bit shallow, but generally, M x M matrices operate on vectors.
Although Quantum Mechanics uses complex numbers in matrix elements, in the simplest case I may use real numbers.
The figure below shows an example of a simple operator: a rotation of a vector over 90 degrees:

Fig 2. Rotation operator and it's associated matrix.



You may see it this way: the first row in the matrix, "performs" work along the x-axis, and the second row in the matrix,
"performs" work along the y-axis. So, this 2x2 object transforms (or maps) the vector (1,0) to (0,1).

A great thing of having matrices associated with operators (or gates) is that it enables an easy "calculus" on state vectors.

Note:
Now, here is a physical problem, and maybe a bit of a philisophical problem too.
Since A.A |Ψ> = I |Ψ> = |Ψ>, does such a Unitary Operation then changes the state
of a state vector? This is more difficult than it seems. For a "general" Operator, acting on |Ψ>, it surely
changes the state vector. However, we already have seen that the Unitary ones are reversable, and they
preserve the "length" (better word: the norm) of a state vector.

As a side note: for quantum gates, it is postulated that they must be reversible. Later more on that.

And indeed, in some cases such a Unitary operator can be used to transform a state vector to be expanded in another set
of basis vectors, which seems to be a legitimate action. Nothing changes then, does it?
I pospone this question to a later subsection.
But anyway, according to the math, it's really 'reversable' on the state of vectors.

In this text, I ignore complex numbers, which might not be a smart move, but I do it anyway. Silly Albert, ofcourse ;-)

Let's take a look at one of the currently existing quantum gates, and it's corresponding matrix.

Quantum gates are supposed to be reversible, and the associated operator is supposed to be unitary.
This means that if you have a "register" of qubits, and let an operator work on, say qubit 1, then
our register will not fully "collapse" into a basis state.
However, at a certain point, it may be so that the researcher wants to perform a "measurement", or perturbative action,
on the system, for certain reasons.

In general, a quantum computer as it exists in labs today, would have an implementation of a certain number of qubits
(like 3, or 4, or 8, but generally still not a very large number), and an "array" or series of quantum gates
which may operate on one or more qubits.
In section 3 we will try to explain it, and provide for some examples.
Now, take a look at the figure below. It represents a quantum gate, which is the quantum version
of the "classical NOT gate".
Indeed. It is suppose to "flip" a qubit. If the qubit would be in a "pure" basis state, like |1>, then the gate would
project it into |0>.

Fig 3. An example of a quantum gate.



(The example above is "not the best one", but it should be easy to understand.)

Nowadays, there already exists quite a few quantum gates, like the Hadamard gate, Pauli-X/Y/Z gates, CNOT gate,
Swap gate, and quite a few other ones. And you bet.., exciting future implementations are bound to happen.

Since a "qubit" is a superpostion of two basis states, and thus a 2 dimensional vector, an operator would be a 2x2 matrix.
Similarly, a "qutrit" which would be in a superpostion of three basis states, and thus a 3 dimensional vector,
then an operator would be a 3x3 matrix.
Also, an operator on system of 2 qubits (see case 2 in section 1), as a superposition of 4 basis states,
then an operator would be a 4x4 matrix, etc.. etc..

Note:
By the way, also in classical computing, we have reversable and non-reversable gates, but only reversible
gates never erase any information when they act on input bits. You can run the operation forwards or backwards.

2.3 A few words on quantum circuits.

We know that |0> is a qubit, and |1> is a qubit, although both are in an "known" state.

|Ψ> = a|0> + b|1>, is an unmeasured (unknown) qubit, and is a (simultaneous) superposition of the
basis states |0> and |1>.

In section 2.2 we have seen Operators acting on quantum systems, like a qubit. Also, we have seen that such a unitary
Operator can be represented by a unitary matrix.
While a "quantum circuit" is synonymous to a "quantum gate", the latter is a "technical symbol" that makes it easier
to draw larger (and more complex) "circuitry".

You know, one key element in QC, is how you place (or distribute) such elementary circuits, one after the other, while
each one operates one one or more qubits. So, a number of such quantum circuits in succession, equates to a series of operations
on our qubits.

Actually, many physicists in the field, regard designing such "circuitry", as "programming" a quantum computer.

By the way: I am not suggesting that a more complex circuit always means that the individual circuits "operating in succesion".
It can be more complex than that, but it's not important for this elementary introduction.

Fig 4. A few examples of elementary quantum circuits (symbolic representation of a quantum gate).



Figure 4 is for illustrational purposes only. Just look at it, and with respect to what I have in mind, that will do.
Remember, that the physical (real world) implementation of a gate, can be some sort of physical event,
like an electromagnetic field or anything else suitable for that particular implementation of the register of qubit(s).

So, there are quite a few elementary "circuits", all corresponding to an operator (and thus a matrix is associated with it too).
Typically, building some larger circuit from the elementary "circuits", is often a part of Quantum Computing too.

Example:

It can be interesting to see, when a measurements is done, which sort of setup gives a deterministic result,
or when you can only expect results with a certain probability.
Please take a look at figure 5 below:

Fig 5. Deterministic output, versus output with a certain probability .



- deterministic output (so to speak).

Really: Don't worry a bit about the gates shown in figure 5. My whole purpose is solely, to illustrate the difference between
a deterministic measurement (so to speak), where the outcome is actually already known beforehand, and another measurement
where there is a probability of finding a certain value.

In the first figure, suppose the upper input is a "|0>", and the lower input is a "|0>" too. Remember, these are just basis states.
Then we apply the operator "Px" to the upper qubit. There is no operator on the lower input.

Now, suppose that this first gate is a Pauli gate, that maps |0> to |1>.

This means that the inputs on the second gate will be |1> and |0>.
Since we have not covered all sorts of gates (or circuits), we take for granted that the second gate just "produces" |1> and |1>.
Since these can be considered to be "basis states", there is no magic involved, and it is clear what the measuring devices
on the far right will find. It's certain that "1" will be found. Remember, all qubits in this case were actually all in a "known" state.

- output with a certain chance.

In the second figure, we do not start with |0> and |0>. No, this time we start with "1/√2 .(|0> + |1>)" and "|0>".
So, this time one of the qubits is in an unknown state.
Now, the first gate effectively does nothing, so what we have as input for the second gate is still "1/√2 .(|0> + |1>)" and "|0>".

The second gate is marvellous for creating entangled systems, and in this particular case, it will give "1/√2 .(|00> + |11>)"
It's an entangled 2 qubit system (see also section 1.4).
Ofcourse, it's a superposition of |00> and |11> with an equal chance of measuring either state.
So, the measuring devices on the far right will approximately have a 50% chance of finding "0" or "1".

What was new? Nothing really. I just wanted to show a small quantum circuit, where in one case, probability was absent,
and in the other case, probability was unavoidable.
Actually, it was really not new, since we already knew that measuring a quantum state in superpostion, only allows us
to find a basis state with a certain probability.

2.4 A few notes on "bra" and "ket" notation.

With just a few quidelines, and some basic knowledge of vectors, it's possible to "follow"
the main lines (or the "red line") of thought on articles on QC.

In the sections above, we already have seen some representations of "states" or vectors.

An expression as |Ψ> = a|0> + b|1> might be seen as an expansion of |Ψ> on basis states (basis vectors).
Since such vectors are member of socalled Hilbert spaces, it's possible to define the "complex conjugate".
Usually, the vector |Ψ> is called a "ket" and the associated "complex conjugate" is called a "bra" and is denoted by <Ψ|.
Hence the term "bra ket" notation (by Dirac).

I would like to make it much simpler now, by making the analogy with vectors (points) in R3
This is not perfect, and is an oversimplification, but I like us to quickly understand as to how an expression like
|A><B| can be interpreted.

If we indeed use the oversimplification in R3, then a (normal) vector (or ket) B can be viewed as a column vector:

B = |B > = ┌ b1
│ b2
└ b3

While the (conjugate) (or bra) vector A can be viewed as a row vector:

A = < A| = [a1,a2,a3]

The inner product of a bra and a ket (as denoted by Dirac) is then notated as <A|B>.
From basic linear algebra, we usually write it as A · B.
However, we stick to the "braket" notation.

It is further calculated as you know from elementairy linear algebra. Maybe you like to review "math note 12" again.


<A|B> = [a1,a2,a3] · ┌ b1
│ b2
└ b3
= a1b1 + a2b2 + a3b3

Which is a number, as we also know from elementary vector calculus.

Usually, as an interpretation, <A|B> can be viewed as the length of the projection of |A> on |B>.
Or, since any vector can be represented by a superposition of basis vectors, then <Φ|φi>
represents the probability that Φ collapses (or "projects" or "change state") to the state φi.

Again, I use a simple way to show things. When not viewing vectors as members of R3, but as members
of complex Hibert spaces, then going from a row vector A to the column vector A, would also mean that we need
to take the "complex conjugate" of every element of the row (or column). Thus:

So, suppose < A| = [a1,a2,a3], then |A > would be:

┌ a1*
│ a2*
└ a3*

where each ai* is the complex conjugate of a1.

Ofcourse "Operators" (mappings) are defined too in Hilbert spaces. Above, we already have seen something about it.
Indeed, linear mappings, or linear operators, can be associated with matrices.

=> Here is an example. Suppose we have the mapping "O", and ket |B>.
Then in many cases the mapping actually performs the following:

O |B> = |C>

meaning that the columnvector (ket) |B> is mapped to columnvector |C>.
Or, the operator maps the ket |B> to ket |C>

We can write that as:

┌ a11 a12 a13
│ a21 a22 a23
└ a31 a32 a33
┌ B1
│ B2
└ B3
= ┌ a11*B1+a12*B2+a13*B3
│ a21*B1+a22*B2+a23*B3
└ a31*B1+a32*B2+a33*B3
= ┌ C1
│ C2
└ C3

=> Operators can "work" on a "bra" too, resulting in another "bra":

<A| O = <C|

where, in our simple model, B and C are row vectors.

We can write that as:

[ A1 A2 A3 ] ┌ a11*B1+a12*B2+a13*B3
│ a21*B1+a22*B2+a23*B3
└ a31*B1+a32*B2+a33*B3
= [ C1 C2 C3 ]

The above is interresting by itself, but it's also a sort of foreplay to make the following "plausible".
Usually, the expression:

|φ > < φ| can be assoiciated with an Operator or matrix.

Let's try this:

|B > < A|   =   ┌ B1
│ B2
└ B3
[ A1 A2 A3 ]   =   ┌ B1*A1+B1*A2+B1*A3
│ B2*A1+B2*A2+B2*A3
└ B3*A1+B3*A2+B3*A3

So, it seems to be plausible, that |B > < A| is a matrix, or operator.

Two important items to remember:

(1):   < A|B > : inproduct, or inner product, usually the projection of A on B.

(2):  |B > < A| : usually corresponds to a matrix or linear operator.


Next, we will spend a few words on Classical Information versus Quantum Information.


Chapter 3. Classical Information versus Quantum Information.

We are now ready to compare some aspects of Quantum Information, to "Classical" information.
To narrow this down a bit, let's compare information of qubits to "classical bits".

If you would consider a special case of Classical Information, like for example "bits" in a digital computer memory,
then some obvious observations can be made.
For example, the state of a computer register, is completely "known" at a certain moment. It might contain a bitstring like "1001 1101",
and this can be read, copied to tape, or disk, or another computer, or multiple disks etc..

=> (1) For Classical information, it is generally true that:
  • you can read a register, or memory location, without altering it. It's "state" will not be altered.
  • you can "clone" classical bits without any problem.
  • you can "broadcast" classical bits to many destinations without any problem.
  • If "power keeps on" and futher you do nothing at all, a memory location keeps that same bit string for years.
  • if you don't know the state (content) of a register (or memory location) you can still copy it.
=> (2) For Quantum information, it is generally true that:
  • You don't know the "value" of a qubit. It's "unknown". You only know it can be represented by a superposition of states.
  • If try to "read" it, you interact with it, which "alters" it state.
  • You cannot "copy" a qubit, since you cannot read or measure it precisely. It's a superposition, unless you "collaps" or "project" it.
  • In general, if you "measure" a superposition of states, you get different outcomes all the time. At best you can get (over time) an expectation value.
  • In general, if you "measure" a Quantum System, you get "a value "which you might consider as "classical" but it does not represent the former (fuzzy) Quantum state. That is lost.
  • Quantum Information cannot be fully converted precisely to classical information, and the other way around.
How about that? Would you (largely) agree with the listings above?


Chapter 4. Quantum Computations.

Above, we have seen something on qubits, and "registers" of qubits (entangled, or not), operators, and quantum circuits.

Often, building some larger circuit from the elementary "circuits", in order to solve a certain "problem",
is often regarded as a "key part" of Quantum Computing.

Arranging the layout of the circuits, and their order, then looks quite similar to "programming" in classical systems.

Quantum computing is often like this: Generally, a "quantum algolrithm", implemented in the operations of "quantum circuits",
will try to filter out the "solution" amongst the many "alternatives" from the superpositions.

Please don't think that high numbers of qubits is commonplace. When you would scout scientific articles, typical numbers still
are 4, 5, 8, 12 or, in exceptional cases, a little higher.
This is not to say, that a certain "implementation" (which I didn't noticed) uses much higher numbers of qubits.

An important question is this: Are quantum computers really "real"? That is, do they already exists today (like now, in july 2015)?
Yes, for a smaller number of qubits, in lab setups, they do. And they can operate on some very specific mathematical problems,
formulated in "quantum algolrithms".

It's important to take notice of the fact "quantum algolrithms", since you certainly cannot throw any type of problem on current quantum computers.

And even in the foreseeable future, it's likely that quantum computers will be used for mathematical/physical problems only,
although the scope will certainly widens up (like calculating on cosmological problems, or high-energy physics).
(Well, ofcourse never say never...)

Note:
A rather peculiar implementation, by the commercial company D-Wave, is quite noteworthy since they use "sockets" of 512 quantum "elements".
I hestitate to call it "qubits", since the folks at D-Wave most certainly use a special type of quantum computing (quantum annealing).
D-Wave is quite different from what we have seen in this text, and a few criticists don't believe it's the "real" thing.
However, quite a few physicists seem to find it an interesting path. Although D-wave is (so I believe) not fully open with respect
with the exact technology used, the papers I could find describe the use of "quantum tunneling" to the 'low states',
which then (could) correspond to "the solution" of some problem. That would be quantum computing in my book.
If you are interested, you should Google a bit on 'D-wave quantum computing' or 'quantum annealing'.

I started this text, by "tempering expectations" a bit (section 1.1), since "only" some specific types of mathematical problems
have been succesfully "implemented" (or performed) on (true) quantum computers.
But don't forget: the science behind it, and the efforts to achieve it, is mindblowing.

What sort of "problems" ("quantum algolrithms"), at this point suitable for current quantum computers, are we talking about?
Well, they come from "number theory" and other disciplines of mathematics. Some famous are:
  • Grover's search algorithm (find a specific item among N other unstructured items).
  • Shor's factoring algorithm (split a number into it's basis prime numbers.
  • Hoggs algorithm.
  • Also very likely are cases of pattern matching, or solving specific polynomials etc..
  • And.., Quantum Computing is actually close to Quantum Teleportation and dense coding.
It is generally believed that (true) quantum computers will, for example, have as one of their first practical uses, the "breaking"
of strong encryptions like RSA. Or, the other way around, playing a role in super securing systems.
It could break encryption in days or hours (depending on it's power), whereas a classical super computer
could take several years to complete the same task. Ofcourse, these are not absolute numbers, but the example only serves
to provide some comparison between a powerful quantum computer and a classical supercomputer.


Note:
For me personally, my interest is primarily in what fundamentals can be derived or found, with resepct to fundamental concepts
in Quantum Mechanics, like "non locality", or even "hidden variables". I believe that when quantum computing matures more and more,
there is a good chance that as a "spin-off" we probably get a better insight in de underlying methods of Nature.
For example, some recent articles already discuss quantum circuits in relation to "non locality", and it's very likely
that more and more attention will go to this sort of subjects. Here is an example of such an article.
For example, "hidden variables" were more or less declared as "dead" since the Bell tests were performed with a sufficient "scientific body".
However, you might be amazed by the fact that some top physicists never wrote that concept off.
As a serious article on QC which is quite pro "hidden variables" (in a new jacket), you might look at this example.

If you are interested, then Google a bit on "hidden variables" and "non locality"

Now let's try to characterize a quantum computer:

4.1 Description of a Quantum Computer:

From what we have seen in sections 1 and 2, I think I could convince you, that if a series of elementary quantum circuits,
would operate on a certain number of qubits, that indeed a form of "computing" might be implemented.
For example, maybe somebody could create an "adder" of a number of circuits, which is a fundamental piece in classical computing.
But that's not the key point. It's not the heart of a quantum computer.

=> This is much better:
In a quantum computer, the computational space increases exponentially with the number of qubits (the register of qubits)
which thus enables exponential parallelism. Please remeber that generally 'N' qubits represents 2N states
simultaneously.This, while a classical register can hold only one bit sequence at a certain moment.
Now, this really is "a" key point.

=> Another "typical" element of quantum computing, can be illustrated by the following example. Suppose we have some mathematical problem.
For example, finding an item among N other unstructured items. It can be proven that a classical computer would need (on average) "N/2" queries
before hitting the correct result, while a quantum computer would then need on average "√N" queries.

It also means that "the larger a problem is" (N is larger), the "performance" of the quantum computer stands out more and more.
For example, with N=10000, a classical computer then would need (on average) 5000 iterations, while a quantum computer would then
need (on average), 100 iterations.
The numbers for the quantum computer are not absolute. It's just depends on the algolrithm. In this example, the numbers
apply for Grovers search algolrithm.

=> So, often, the total process of solving a quantum algolrithm (a problem) consists of multiple steps, or "operations",
which also can be seen from the number of "circuits" in a circuit diagram.

Thus, if you you see a circuit diagram, with a number of circuits (or gates), they all represent "operations" or steps, which is also
in accordance of what we have learned in section 2 (operators and gates). Indeed, an "Operator = a gate = a circuit".

If you would take a look at the diagram below, it's not a real diagram, like one that really exists with classical circuit boards.
It only represents the Operations (thus circuits), performed on the qubits one after the other.
Note that the "input register" then converts (so to speak) to the "output register" after all steps are done.
However, a seperate ouput register coud be possible too.

Fig 6. Diagram with circuits, representing the operations, or circuits, performed on the input. .



Hopefully, you now have a "better" idea of a typical small-scale quantum computer, as is often used in lab setups.

So, often:
  1. Start with a number of qubits, say 8 qubits. Initially, they all might be in the pure |0> state.
    Then they might be put in a superposition, or entangled state.
    Due to how a number of current quantum algolritms work, the input register might then represent all possible solutions of a certain problem.
    Then, the operations of the quantum circuits will try to "filter" the correct solution from the superposition,
    in an efficient way (or at least, different from a classical approach).
  2. Next, optionally, a first circuit may entangle all, or a subset, of the qubits. It just depends if the researchers
    need this to happen as a first step, and how the quantum algolrithm is implemented in this particular setup.
  3. Next, one or more circuits operates on all, or a subset, of the qubits. The operation of those circuits form the core
    of the algolrithm. These steps just depends on the algolrithm that is used in this particular case.
    Physically, the "circuits" are laser pulses, or radio waves, or whatever physical event, in order to map the state of the qubits.
  4. Next, the input register (or a formerly entangled output register) has a "good chance" that the values are in accordance
    as expected with the algolrithm.
  5. It's important yo know, that the "input" register might also function as the final "output" register.
As said before, small-scale quantum computers have been realized in lab setups, where typically a smaller number of qubits
are involved. Some of the algolrithms shown above, were succesfully performed in such setups.

It's not so easy to demonstrate it, since a good-working knowledge of number theory is required.
But, a "Jip and Janneke" explanation is possible, and I shall use Grover's search algorithm for that.

4.2 Grover's search algorithm (should explain the "core" of this note):

It's possible to introduce this one, with only a minimum on math.
The figure below, tries to illustrate a classical search versus a quantum algolrithm.

Fig 7. Classical search vs Grover's quantum algolrithm.



4.2.1. Classical search:

Suppose you have "N" unordered numbers to choose from. Suppose only one is searched for, or in other words, is the correct one.
A good example is a query on a classical database. The query then "knows" the value we want to find, but it still have
to work it's way through a table, until that particular value is found.

Suppose an unordered table has 100 unique records. You only need to find one particular record.

Classically, on average, how many "trials" would you need? On average, it's about "N/2".
Ofcourse, if you are lucky, you would have succes (for example) just after 3 trials. But, ofcourse, if you would
have no luck, you might need (for example) 87 trials before you hit the right answer.

So, without "formally" proving it, I suppose that "intuitively", we understand that with N items to choose from,
you need "N/2" queries on average, before hitting the right answer.
So, suppose N=4, on average, we need 2 queries. Suppose N=100, on average, we need 50 queries. Etc.. etc..

Ofcourse there must exist some "Oracle" which knows precisely the record we are looking for.
If the Oracle is a "classical query", then it might be something like "SELECT * FROM TABLE WHERE RECNO=55".
The query just needs to plough through the table until this specific unique RECNO is found.

Keypoint is, that there must exist a function, or query, or whatever, which knows the value we are looking for..
It's very important you see it that way. You are looking for some specific value, which you know, but you must find it,
using some query, or function, or something like that.
We only want to compare such a classical way of doing things, with a true Quantum Algolrithm.

4.2.2. The Quantum Algolrithm (Grover's algolrithm):

Globally, the quantum algolrithm works like this.

It's based on "amplitude amplification", or sometimes also known as "inverse the rest, except the solution".

Suppose we want to try Grover's algolrithm using 3 qubits.

We start by having those qubits in the |0> state. Next, they will placed in a state of superposition, where every state
has an equal probability to be found (when measured, or observed).
Then, Grover's algolrithm will be "applied", in a number of "iterations", where ofcourse our goal is, to minimize those iterations.

Step 1:

We have 8 qubits, all in the state "0", so we must correctly describe it as |000>.
Recall that a system of 3 qubits in general must be written as:

|Ψ>= a1 |000> + a2 |001> + .... + a8 |111>

Since in this case, we know that all three are known to be "0", the 3 qubit state then must be |000>.

Step 2:

Simulating a classical database, where all entries have equal chance to be found, we put our system
in a superpostion where each state has an equal probability to be found (or to be measured as the last step).
This also can be interpreted as that each state has the "same amplitude" (thus the same probability).

For this step, the Hadamard transform (or Hadamard gate) can be used , since it maps n qubits which are "0"
into a superposition of all 2n states with equal "weight", that is, equal probability.

Sometimes this is expressed as:

H3 |000>

Where the superscript 3 means that we have 3 "inputs", and the "H" means that we use the Hadamard gate.
The new three qubit state then is:

|Ψ>= 1/√8 |000> + 1/√8 |001> + 1/√8 |010> + 1/√8 |100> + 1/√8 |110> + 1/√8 |011> + 1/√8 |101> + 1/√8 |111>


Step 3:

Now, choose a certain state of these component states. Then that one will function as "the record" which must be found
by the quantum algolrithm. So, we could choose |010> or |111> or anyone of these 8 components.

So, let's take for example |111>

Step 4: marking the Solution.

Now, one Quantum feature of this quantum algolrithm, is to "inspect" all entries at the same time.
Note that! This is not to be taken lightly.

The term "Inspecting" does not mean "making a measurement". It might mean that we apply an operator (by some gate),
like implementing a "phase shift" or "inversion", or anything else, on the components.

Now, just as the "classical query", for example, "SELECT FROM TABLE WHERE ID=55", at which we can see that this classical counterpart
knows what to look for. It only needs to plough through the table.

This is also true for a special function, called the "oracle". That function has knowledge of which state we need to find.
Using a certain phase shift, the function will invert the amplitude of the |111> component, without modifying it furher.
For the other components, it does nothing.
Note, that in quantum terms, the probability associated with any component has not changed. The square of the amplitudes
of all components is still the same.

However, we can say that the solution is "marked".

Step 5: Applying the "diffusion" operator in "iterations".

We can now use a (series) of gate(s), which "diffuse" or lower the amplitudes of the unmarked components.
At each iteration, those amplitudes will get lower, so the marked solution will stand out more and more.
The "art" is ofcourse, to use the minimum needed number of iterations.
For this example, using 3 qubits, only 2 iterations are needed, which give a (about) 94% chance to find the
solution |111> when a measurement is performed.

Further comments:

The algolritm is "statistical", meaning that after "m" iterations of step 5, there is a very good chance of finding
the correct answer. The larger "m" is, the better that chance will become.

When comparing the classical case, with the quantum algolrithm, when "N" becomes larger, the better the quantum algolrithm
performs compared to the classical case.

It can be proven that:

- Classical search: you need on average "N/2" iterations.
- Grover's search: you need on average in the Order of "√ N" iterations.

When N gets larger and larger, the more the quantum algolrithm "stands out" to be better performing.

This algolrithm was translated by me here, in a sort of "Jip Janneke" language. Hope it helped a bit.

Further noteworthy is the fact that Grover's search algolrithm converges to "√ N" iterations, while some other
quantum algolrithms take a 'true' advantage of an exponentially increased computing space.
These can be found in more advanced notes.

However, the principle of "universal computing", applying to quantum computers, is established.



That's it ! Hope you liked it.