In this post, I’ll explain the background idea of quantum computing as an aside topic in order for establishing your intuitive understanding.
As you know, quantum computing uses “Qubits”, instead of “Bits” used in current popular computing by Neumann architecture. The behavior of this “Qubits” is not easy to understand for humans, then it will prevent us to understand quantum computing.
It’s sure that the quantum behaviors will not be intuitively understood by the humans, but the purpose of this post is to make you understand the “idea” of this mechanics with comprehensive physical examples.
In order to build your intuition for regular IT engineers, we refer real physical cases (never use metaphor) as possible and I’ll describe using entry level of physics and mathematics without complicated formula or proofs. (I will explain more advanced topics as a note, if needed.)
“The Feynman Lectures on Physics – Volume III (Quantum Mechanics)” is a good reading for your entry of quantum mechanics (it’s a little bit old and not focusing on quantum computing though), then this post would also refer to several examples and descriptions in this reading.
(I’m also not an expert for quantum physics and referred this book a lot in my learning.)
Curious Behaviors in Particles (Quantum)
Suppose that we have an electron’s gun. With this device, a lot of electrons will be randomly fired by applying some voltage. (Let’s imagine some kind of oven.)
Now we put a wall in front of this gun with 2 holes as below and each triggered electrons will go to this wall. Then only electrons passing through these 2 holes will eventually reach to the 2nd destination wall.
Figure 1 : Experiment by electron’s gun and wall with 2 holes
(From “The Feynman Lectures on Physics – Volume III” Chapter 1)
Now we set the detector at destination wall and we plot the total count (electron’s arrival) in each position on x-axis.
Our concern is how this plotting curve is going to be ?
First, the detector at destination wall definitely records each clicks along with the electron’s arrival. This means that each electron discretely arrives at destination wall. (i.e, Unlike the wave, you can “count” each electrons.)
In order to predict this experiment’s result, now we suppose that you fire a bunch of bullets with your toy gun. (See below.)
As you can easily imagine : If hole2 is covered, the total count of bullet’s arrivals will be the following curve P1. If hole1 is covered, the total count will be P2.
Figure 2 : Result with real materials (1)
Eventually the expected result (total count) on the destination wall will become P1 + P2 as follows.
When you do this experiment with your toy gun, you will definitely be able to get this exact result.
Figure 3 : Result with real materials (2)
However, in the small scaled quantum world, the result is different from things of our experience ! When we count all electron’s arrivals on the destination wall, the result becomes as follows.
Apparently, this is not our expecting result.
Figure 4 : Result with particles (atoms)
Suppose we do the same experiment with water wave. (See below.)
In this case, each wave through hole1 and hole2 will interfere with each other, then wave’s intensity at destination will become as following picture.
As you can see, it’s very similar with the result of our previous electron’s experiment.
Figure 5 : Simple experiment by water
As I mentioned above, each electrons can be detected as each different particles, but it also seems to have some sort of wave‘s characteristics (wave-particle duality).
In the things on a very small scale, we can see such an experience that we never had in our real life.
This kind of phenomenon is also observed in quantum’s spin. Now let’s see another experiment.
Let’s say, we consider the following device, called Stern-Gerlach device. We assume that some particle’s beam (e.g, beam of Ag) is inserted into this device.
Figure 6 : Stern-Gerlach device
In this situation, by ununiformed magnetic fields, the current loop in the atom will be pulled into upward or downward, corresponding to anti-clockwise spin or clockwise spin. (See Figure 7 below.)
Eventually, each atom will be divided by upward or downward in the screen (destination) as Figure 6 above.
Figure 7 : Relation by electron’s spin (current loop) and force in Maxwell’s picture
Note : This picture (above example by a single electron’s motion) simplifies the behavior of electrons. (It’s known that each electron doesn’t exist in a certain position and it spreads into any space with some uncertainty.)
In the real particles, this kind of system is caused by various aspects in particles, such as, combination of multiple elements, symmetricity in a molecule, and so on. Depending on the choice of atoms or molecules, the particles might be divided into 3 states – such as, positive (+), zero (0), and negative (-) – in Stern-Gerlach device.
Now we consider the following experiment with the apparatus by combination of 2 Stern-Gerlach devices.
In the first (left) one, we block the downward beam and only pass the upward beam. In the next (right) device, we observe how the beam is divided by upward or downward.
Figure 8 : Experiment with simple combination of Stern-Gerlach’s devices
With this experiment, we get the result that all beam becomes upward. (No downward beam is observed.)
I think that this would be the same as your expecting result.
However, let’s see the following apparatus by 3 devices.
In this experiment, we combine 3 devices such as : In the first one, we block downward beam. (Only upward beam reaches to the next device.) For the next device, we rotate this device around y-axis and block only downward (i.e, crooked direction) beam. With the final device, we observe both upward and downward in the regular direction.
Figure 9 : Experiment with rotated Stern-Gerlach’s filter
With this experiment, we get the result of both upward and downward ! (i.e, The downward beam can also be appeared again.)
That’s so strange, because we have filtered into only upward beam in the first device.
As you saw in our first example of electron’s gun, these curious results are because of wave-like behaviors.
Note : It’s known that all matter exhibits wave-like behavior and has wavelength (where m is mass, v is velocity, and h is Planck constant). We can comparatively ignore this behavior in almost case with a large material, however, we cannot ignore this behavior in quantum-scaled particles.
See Wikipedia “Matter wave (de Broglie wave)” for details.
With a lot of works in physics, this phenomenon is formulated by introducing the idea of probability amplitude, which idea is based on wave’s motion.
The probability amplitude is a complex number which describes some behavior in quantum physics.
For now, please think it as an analogy of the following wave’s amplitude .
Figure 10 : probability amplitude by simple Euler’s formula
The probability amplitude is not visible and recognizable for humans. As I explain in this section, we can only recognize it as real “probability” . Figuratively speaking, the probability amplitude is some value in unrecognizable world with “complex number” and we can recognize it as “real number”.
Now let’s remind the previous example of electron’s gun again. (See Figure 1.)
In this example, we can set the probability amplitude as :
- : probability amplitude for passing through hole1 and reaching to some position (x) in destination wall
- : probability amplitude for passing through hole2 and reaching to some position (x) in destination wall
The probability of both paths through hole1 and hole2 is not the sum of probability , but it’s the probability of “the sum of probability amplitude”, i.e, .
As you saw in Figure 5, each and will interfer like the ordinary wave and the result will become such like Figure 4.
Let’s remind the example of quantum spin again. (See Figure 6.)
In this example, we denote the state of particles which has passed through upward as . We also denote the state of particles with downward as .
Same like that, we denote the state of particles which has passed through the rotated device (2nd device in Figure 9) as . And we also denote the state of opposite side as .
Here we can set the probability amplitude as follows. (Please take care of the order !) :
- : the probability amplitude of particles passing through after passing through . (the probability amplitude of with initial state )
- : the probability amplitude of particles passing through after passing through . (the probability amplitude of with initial state )
Note : In the previous example (an example with electron’s gun), you can also denote using bra-ket notation ().
With this notation, we can describe the probability amplitude in Figure 8 (experiment with simple 2 Stern-Gerlach devices) as follows.
- : the probability amplitude of finding upward particles in Figure 8
- : the probability amplitude of finding downward particles in Figure 8
In quantum mechanics, there is a basic principle, such as : . For this reason, you can find :
This means that the real possibility of finding upward particles in Figure 8 is 1, and the real possibility of finding downward particles in Figure 8 is 0.
Next we consider the mixed device of Figure 9 (experiment of 3 Stern-Gerlach devices with rotated one).
First, we can write probability amplitude of particles passing on 1st device and on 2nd device as . Then probability amplitude of particles passing on 2nd device and on 3rd device is . How can we write the possibility amplitude of “passing on 1st device, on 2nd device, and on 3rd device” ?
In quantum mechanics, this kind of composite possibility amplitude by after is given by the product . (Please take care for the difference from your familiar “conditional probability”.)
For this principle, each possibility amplitudes for upward and downward in Figure 9 will be :
- : the probability amplitude of finding upward particles in Figure 9
- : the probability amplitude of finding downward particles in Figure 9
Then the real possibility values of these are :
- : the probability of finding upward particles in Figure 9
- : the probability of finding downward particles in Figure 9
Then the ratio of these values is not depending on which one ( or ) is selected in the 1st device. (See the following equation.)
For this reason, the result in Figure 9 includes the downward particles, even when you have filtered into the upward particles in the first (left) device.
By the way, when a particle has passed through the 2nd device in Figure 9, the state is neither of and . (This state is so-called an intermediate state against and .) Against these intermediate states, each and are called base state. As I show you later, intermediate states are all described using the combination of base state.
There exist a lot of set (a lot of pairs, if 2-state system) of base state.
For instance, the pair of and is also one of base state’s set. The choice of base state is something like a choice of base coordinates in a vector space.
It’s known that there exist the following principles for quantum base state, when is a set of base state. (See chapter 5-5 in “The Feynman Lectures on Physics – Volume III”.) :
i.e, when , and (orthogonal) when
- for any state and
With these principles, when all particles with both and is passed on the 2nd device in Figure 9, you will find that all observable state in the 3rd device will be m+ as follows.
This is the same as our experiment’s result in the previous section.
Suppose we have a particle with initial state and this particle goes through some apparatus A (e.g, an apparatus applying some magnetic fields, the combination of multiple Stern-Gerlach devices, and so on). Then the final probability amplitude for is often denoted as using operator A.
For instance, the 2nd rotated device in Fugure 9 is also one of these operator A, then we can also denote this operation as .
In generic gate-model quantum computing, the logic is built by the combination of operators and an operator is sometimes called a gate (circuit).
In this post, we discuss the quantum computing using an analogy of this quantum spin.
Note : There exist several quantum numbers corresponding to position, momentum, spin, or polarization. Unfortunately there’s no single convenient (complete) formula describing all these aspects.
For now, we have considered a complex number value and haven’t divided into bra () and ket ().
However, with the idea of mathimatical vector analysis, this quantum mechanics is abstracted as Hilbert space using vectors and matrices – i.e, each bra / ket as a vector and an operator as a matrix. (See chapter 8 in “The Feynman Lectures on Physics – Volume III”.)
From now on, we define these symbols using vectors and matrices as follows. :
For 2-state system, it can be written as :
For instance, if is given, is equal to :
In this algebra, operator A converts some state into .
Note (Time-Evolution) : When we correctly discuss the actual behavior of particles (which will depend on both time and positions), we’ll dive into complicated details. In this note, we briefly see the behavior of time-evolution.
Suppose we have a particle at rest and it has a definite energy . In this situation, it’s known that this particle has the probability amplitude depending on time (where is a position-dependent constant with ). This means that the probability amplitude differs on time .
For instance, when a particle sits in a uniform magnetic field B and it has the same direction (moment) of spin for time , the probability amplitude is changed by (the actual state is multiplied with this value), where is magnetic moment and is magnetic field.
Furthermore, when we decompose the state where , it’s known that this system can be written as the following differential equation with some constant .
This is also denoted with the following vector differential equation. This equation is called time-dependent Schrodinger equation.
We can get the time-dependent state (probability amplitude) by solving this Schrodinger equation.
(See “The Feynman Lectures on Physics – Volume III”.)
Suppose the state and are given. As I mentioned in the previous section, we can decompose a probability amplitude using base state as follows :
Hence any can be decomposed using base state as follows. This superposed state (i.e, a liner combination of base state) is called a Qubit state. :
Note : As I mentioned above : When it’s a stationary state in some energy (such like, in a uniform magnetic field B), will change depending on time , i.e, where is time-independent with some fixed time .
Hence, in Qubit’s representation, a state is written by using (time-independent). In Qubit’s representation, is equivalent to for any real number .
Especially in the 2-state system, any qubit states (superpositions) will be written as follows. :
In the quantum computation, the following pair of base state is conventionally used in 2-state system :
Using this base state, the previous state is written as follows :
Same as above, we can also decompose the formula for any state , , and apparatus (operator) A as follows :
Each and is the projection for base state ( and ), and each is not depending on and . Hence this equation means that is a linear combination of these projections.
In 2-state’s quantum computation, this A will be the following 2 x 2 matrix :
Now we try the simple calculation by quantum states and operations.
Let’s say, now we suppose all particles have the following spin direction and we assume that this state is denoted by . (These particles go into upward (+z-direction) by previous Stern-Gerlach device.)
Figure 11 : a particle of
When we change the state by the following operation called Hadamard (H) gate (which is also physically implemented as some kind of devices or circuits), the converted state is written as follows.
Now we denote this converted state as .
When we observe this particle with Stern-Gerlach device of the same direction (+z-direction), we can find that the half of particles go to upward, since .
Note : In this experiment, you might think that the half of these particles go into some state and the other half go into another state. But, this is not describing these particles’ behavior correctly.
You should think that all particles go into some same “uncertain state” and we can observe it as real possibilities.
Later (in “Measurement” section) we’ll go into more details.
When you combine 2 apparatus – the particles pass through A and then pass through B -, the corresponding operator C (of this combined apparatus) will be : (where is the product of each matrix A and B.)
With this manner, you can combine a variety of apparatus.
For instance, when you apply Hadamard (H) gate twice, all state goes back to the original state. (Please calculate using matrix.)
Note : Any operators should preserve the state’s norm. Then any operators converting some state to another state should be written as unitary matrix (i.e, a matrix such as ).
See Wikipedia “Quantum logic gate” for other famous unitary operators.
Note : With quantum mechanics, we can explain a variety of physical phenomenon which is never described by classical mechanics, such like half-life of a radioactive element, barrier penetration (the particle transmission into the second piece of material – i.e, not all particles are reflected by the material), so on and so forth.
This post is only focusing on computing, but please read chapter 7-3 in “Feynman Lecture on Physics Volume III”, if you’re interested in these descriptions of physics.
Next we consider the geometric representation of qubits.
Now let’s remind Stern-Gerlach apparatus in Figure 9 again. (See below.)
When we denote the states in 1st and 3rd device as and the rotated states (states in 2nd device) as , the probabilities (not probability amplitudes) of direction for initial states are experimentally known to be :
where is inner product, i.e,
Figure 9 (Again)
Now we set on z-axis, and we set each x and y axis for orthogonal axis (with anti-clockwise order) as follows.
First we assume that we represent the state in the following sphere, where is the angle between and in Stern-Gerlach devices.
Figure 12 : Base sphere
Our concern in this section is how the following and is represented geometrically ?
When it’s given the initial state , then the probability (not probability amplitude) of this state is . As I mentioned above, this is equal to either or .
Here we assume that this is equal to , then :
Then we get .
Using the same calculation, we also get
(Same like this, if we have chosen , then we will get and .)
Hence, we can write as follows. (See the following note.) :
Note : Here we used the qubit’s property, such as : and is equivalent for any real number . (See above note.)
Next we consider the following 2 states, and , on x-y plane.
Figure 13 : 2 states on x-y plane (1)
On this plain (x-y plain), , then we can write and as follows.
When it’s given the initial state , then the probability (not probability amplitude) of the state is :
This should be equal to or .
When we assume it’s equal to , then and we get .
This implies that the relation of and is like the following picture.
Figure 14 : 2 states on x-y plane (2)
Here I don’t go so far, but this holds even when it’s not on x-y plane.
As a result (summary), any state is uniquely written as
using the following and (where ).
Figure 15 : Bloch Sphere representation
Note : Strictly speaking, the dipole and can be written using arbitrary (not “uniquely written”).
This geometric sphere (which describes the qubit’s state) is called Bloch Sphere and it’s useful to consider things, such as the relation of each states, the transformation and combination of quantum logic gates (operations), so on and so forth.
For instance, when you set as one side of a base state’s pair, you can soon get another side of a pair as :
The following well-known Pauli-X (), Pauli-Y (), and Pauli-Z () gates are operations to rotate radians around corresponding x, y, and z axis. (See Wikipedia “Quantum logic gate” for more other logic gates.)
Any single-qubit operation can be written by a linear combination of these gates, since any 2 x 2 matrix can be represented by a linear combination of these matrix.
You will easily be able to find the following equation.
In general, it’s known that the rotation of radians around each axis is written as follows.
You notice that it’s equivalent to the previous , and , if .
Note : Here we still used the qubit’s property, such as : and is equivalent for any real number . (See above note.)
For instance, previous Hadamard (H) gate is written as the combination of radians rotation around z-axis followed by radians rotation around y-axis :
As you can find, the rotation of around z-axis is always itself for any radians.
See chapter 10-7 and chapter 11 in “The Feynman Lectures on Physics – Volume III” for details.
Next, suppose there exist 2 species of particles, in which both are also in 2-state system.
In this situation, there exist 4 states by the combination (up-up, up-down, down-up, and down-down) as a set of base state.
First, this will be equivalent to the following tensor product of each states, and it’s denoted by (where each and are in the 2-state system).
For instance, when we consider 3 respective different states of particles in 2-state system, we should consider the superposition of 2 x 2 x 2 = 8 state system as follows.
When you apply some operator (gate) A and B to respectively and , it’s equivalent to applying to . (See below.)
It’s a beauty of mathematics.
These states are often called separable.
For instance, the following is also a pair of separable states.
On the other hand, let’s consider the following famous state, called Bell State. This state is not separated by tensor product.
This is very strange state, because :
Suppose Alice measures the first qubit and Bob measures the second qubit. When Alice measures the first qubit, she will have a 50% chance of measuring and a 50% chance of measuring . On Bob’s side, he will also have a 50% chance of and a 50% chance of . Whereas, if Alice measures the first qubit and get , Bob should measure the second qubit as with a 100% chance (since ), even when the particles are separated by a large distance and they don’t know each other.
Note : Please refer well-known EPR paradox.
These states can never be separated by tensor product and these are called entangled state.
Here I don’t go so far for physical description about entanglement, but this strange state actually happens in real particles.
For instance, suppose a pair of electrons are generated together. Then one will have clockwise spin and the other will have anti-clockwise. Even when these are separated by a large distance, this pair will continue to maintain zero total spin.
Figure 16 : Entangled State
Entanglement is a very important aspect for quantum computation.
For instance, if you apply some operation to the first qubit in Bell state, the second qubit is also converted into the same state. (Please calculate using vectors and matrices.)
If there’s n qubits, there exist base state and these are simultaneously converted by entangled state.
Let’s look at another practical example.
Suppose some 3-bits parity p = 5 = 101 (2) is given, then we have corresponding 3 qubits as follows. :
Next we prepare the following ancilla qubit .
Now we get the following state. (We denote this state as .) :
In quantum computing, we can entangle or disentangle 2 states with the following Controlled-NOT operation (CNOT). (It’s written as a non-separable 2-qubit operation.)
This CNOT replaces the second qubit, only when the first qubit is . (If the first qubit is , we do nothing for the second qubit.)
Then CNOT converts base state as follows. (Please remind that any states can be written by a linear combination of these base state.)
Now we check each i-th bit (i=0,1,2) in parity p, then we apply CNOT for a pair of and , only when i-th bit is 1. (When i-th bit is 0, we do nothing.) We denote this CNOT operation using suffix, as .
In our case, we apply and , because our parity p = 101 (2).
First, we apply . As I mentioned above, this operator replaces the 4th qubit, only when the 1st qubit is .
Same like this, we next apply , then we get :
Finally, we apply the previous Hadamard operator for only first 3 qubits ( for i=0,1,2).
Now you got 1010 () with a 50% chance and 1011 ( with a 50% chance. As you can find, the first 3 qubits () is always 101 and it’s the same value as our parity p = 101 (2).
Here I don’t go so far, but it’s known that this algorithm holds for any n (> 0) qubits and any parity p. (It’s known as Bernstein-Vazirani algorithm. See my early post for details.)
As you saw in this example, each qubits are converted maintaining each relations and goes into some totally uniformed state with entanglement effects. As a result, we can observe the consistent results.
The entanglement is used in almost all algorithms and this is essential for quantum computation.
As I mentioned above, the only way to identity the state for humans is to observe and check the probabilities by experiments. This is called measurement.
However, there also exists some tricks for measurement. Here I describe these tricks.
Now let’s remind our first example of electron’s gun again.
Any particles should pass through either hole1 or hole2 in our realistic sense (not both !). Then you might think : if you monitor which hole the each particle passes with some detectors (or, you cover either of holes) and track each path of a particle, you could reach to the contradiction of the universe ! (Each particles should be eventually distributed !)
But unfortunately, you cannot track the path of a particle in the result of Figure 4.
First, if you observe which hole a particle passes (see the following picture), you could surely get the result for which hole the each particle passes. i.e, The measurement will succeed.
Figure 17 : Measure (=determine) whether hole1 (or hole2) is passed
However, with this experiments, you no longer see the previous result of Figure 4, and you’ll see the result of Figure 3 instead. (See below.) In short, the original state is changed.
In quantum behavior, when you’ve measured the state of particles (in this case, determining either “hole1” or “hole2”), the uncertain state is no longer maintained. It becomes into another state with non-probabilistic.
Figure 3 (Again)
Also, in quantum computation, once the real probability are found by measurement, these states are no longer used for experiments.
The measurement is an irreversible operation.
Note : We can consider the measurement as an operator (not unitary, but Hermitian operation) of a projection onto and . As I mentioned above, there exist other pairs of base state, then we can also consider a projection onto another base state. This operator will be described as and , when and is a pair of base state.
In Heisenberg picture, any observable (i.e, measurement) is represented by Hermitian, which might not be constant and evolve in time t. In this picture, the eigenvalue of this Hermitian are the observable physical values and the eigenvectors are the states after corresponding measurement. In mathematical properties, the eigenvalues of Hermitian matrix are all real numbers and the set of eigenvectors is complete system (i.e, eigenvectors are orthogonal each other and arbitrary vector in the space is written with these eigenvectors).
Even when there exist entangled multiple qubits, you can measure a part (subset) of these qubits and continue to experiment other part of qubits.
For instance, suppose it’s given the following entangled state. :
Now we measure the first qubit, then we will have possibly the following 2 cases for the second qubit. :
when the first qubit is
when the first qubit is
This technique is also used in famous Shor’s algorithm.
As I showed you in my early posts (see below), now you can easily try gate-model quantum computing experience on your local machine with quantum simulator, such as Quantum Development Kit (Q#) or Cirq (both are open-source).
Please enjoy programming for the future of computing !
- First Understanding for Quantum Algorithms and Programming (Bernstein-Vazirani’s Algorithm)
- Quantum Search (Grover’s Algorithm)
- Quantum Fourier Transformation and Phase Estimation
- Programming Quantum Arithmetics
- Quantum Period Finding (Shor’s Algorithm)
Reference : The Feynman Lectures on Physics – Volume III (Quantum Mechanics)