Quantum Computing - Animated Waves Illustration

Quantum Computing Part I - Intro

edited by István Finta | sept 07, 2023 Couple of years ago I participated in a quantum algorithms related research project, which was very inspiring to me. In this post series I aspire to collect and introduce all the required phenomenon, definitions, information with references which may reduce the initial learning curve and facilitate others to get the big picture quickly. I hope you will find this topic as interesting as I did.
In this first part that quantum mechanical phenomena are described on which quantum computing is based.

Quantum computing, quantum supremacy, entanglement ... these phrases might sound familiar to anybody in our ages.
The quantum information related theory is more than 50 years old. However, the application areas are more current than ever before.
Quantum computing might be a game changer in the field of operations research, combinatorial chemistry, etc. Combined with AI can lead to more powerful AI models. Due to the nature of exponential computational power a quantum computer theoretically can easily breaks the most widespread encryption methods. This means that once it becomes the part of our everyday life certanly significantly changes our way of living.

This post series is an informal overview and the collection of the references of the topic.

Table of content

First (this) part is an introduction to the basics of quantum mechanics. The aim of this historical review is to introduce how scientists discovered the two phenomena which are the basics of quantum computing: superposition and entanglement. The first part heavily relies on the work of J.D.Norton, which is a captivating but still straightforward philosophical summary of modern physics including quantum mechanics.

During the second part we review the mathematical toolset of quantum algorithms and the circuit model is introduced.

The third part gives an overview about existing quantum computers. Additionally in this part I summarize how to access to qiskit, the circuit model based quantum computing framework of IBM.

From the fourth post various use-cases and algorithm implementations are discussed, including the Bernstein-Vazirani algorithm, Shor's algorithm, Grover's algorithm, Quantum Byzantine Agreement, Quantum Machine Learning (QML) and the Quadratic Unconstrained Binary Optimization (QUBO) problems.

Quantum mechanics by definition

According to wikipedia quantum mechanics is a fundamental theory on physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles.
/wikipedia/

With the theory of quantum mechanics such phenomena can be explained when the systems under observations are very small, such as individual atoms or the particles from which they are made of.
Areas where classical physics fails:

quantization of certain physical properties,
quantum entanglement,
principle of uncertainty,
wave-particle duality.

The great significance of a small constant - Plank's observation and the energy unit

At the end of the nineteenth century the material may appeared in two distinguished forms, according to the scientists: particle and wave. In that time the most investigated fundamental particle was the electron.
On the other hand the well-investigated wavelike matter was the light.

Max Planck was working on energy distribution processes and the black body radiation in that time. He knew that the experimental results regarding heat processes contradicted to the known theories and shown particle-like properties. Planck took Wien's formula, which worked well at higher frequencies but was not working well at lower frequencies. He was aware of another theoretical result from Rayleigh which worked well at lower frequencies and patched the two together. The result was a working formula with a side effect: a small valued constant appeared in the calculations. However, the practically working formula required a theoretical explanation. Therefore Planck proposed the following model: there is a cavity with well-separated resonators. Each resonator has finitely many resonant frequencies. In contrast to classical resonators, which may be energized over a continuous range of energies, Planck's resonators might take energies of integer multiplication of their resonant frequencies. That is the physical system (a.k.a. the cavity) might take energies of 0, 1, 2, 3, … energy units, but nothing in between.: E=h*f. Here 'h' is the previously mentioned new constant of nature, the Planck's constant. This is a very small number. The importance of this small number is getting greater and greater, if the phenomenon under observation is getting smaller and smaller. The formula above expresses that the energy radiation is a sort of discrete valued process. This fact shed doubt on the theory that the heat radiation was exclusively a wave phenomenon.

Einstein and the wave-particle duality

Some years later, Einstein studied the high frequency light.
He stated that under certain circumstances high frequency light behaved as just it would comprised of spatially localized bundles of energy. The energy of each bundle, Einstein argued, is proportional to the frequency.
Einstein proved the correctness of his theory with the photoelectric experiments, which was published in a paper in 1905.

During these experiments low frequency light sources could not liberate photoelectrons, independently from the applied intensity, while high frequency light sources could knock electrons out of the cathode.
This, Einstein observed triumphantly, is just what one would expect if light energy were localized in light quanta with energy given by Planck's formula, that is: E=h*f. Therefore the question might raise if which is the true about the radiation? Is this is a wave or aparticle phenomenon?
In 1909, Einstein shown that certain phenomena could only be successfully explained if we use both wave and particle view; the full observed effect came from the sum of two terms, one a particle term, the other a wave term. The need for both is called "wave-particle duality".

Bohr and the stable orbits

At that time, during the experiments on electric discharges in gases surprised the physicists that the emitted light spectrum was not continuous, but discrete.
In 1913, on the pursuit of the orbiting electrons Bohr stated that there are so called stable orbits, on which electrons do not loose energy by radiation.

According to his assumption electrons are able to exist only on these stable orbits.
However, with light energy transfer the electron can jump to a higher level stable orbit. The amount of the transfered energy can't be arbitrary.

It must be proportional exactly with the difference between the two orbits. When the light transfer ceases, the excited electron jumps back to the unexcited stable orbit. During the jump to the lower energy level orbit the electron radiates back the previously absorbed energy.

Bohr discovered that the orbiting electrons always must have whole units of angular momentum: h/2pi, 2 * h/2pi, 3 * h/2pi. Therefore the absorbed and emitted light energy always is something like n* (h * f), according to the observed discrete spectrum.
Bohr's theory was maddening, but used it as a starting point it lead to great achievements in the field of atomic spectra. However, till the middle of the 1920s more and more puzzling questions remained non-answered or contradictioned by Bohr's theory.

New models

To resolve these contradictions theoretical scientists started to work out new models, which work coherently.
Heisenberg, Born and Jordan worked out the matrix mechanics in 1925. It was the first logically consistent formulation of quantum mechanics.

Parallel to Heisenberg's work, in 1923 de Broglie phrased his theory regarding the matter waves.
In 1926 Schrödinger has taken de Broglie's theory and twisted on that and the result is the well known Schrödinger-equation.

Schrödinger later proved that his wave-function based approach is completely equivalent with Heisenberg's matrix mechanics.

The matter-wave hypothesis

According to de Broglie's theory if a wave phenomenon may behave as a praticle under certain circumstances, it is possible that a particle may behave as a wave. More precisely, he stated that every matter has wave phenomenon. Moreover, in his work he associated the λ wavelength with the p momenta in the formula below: p = h / λ. This formula actually nothing, but the generalization of the Einstein's photoelectric theory.

The matter wave account can explain the discreteness of the atomic spectra: standing waves, composed of matter waves, may persist only in a few definite energy states.
This means that from Bohr's theory the stable orbit associated discrete energy levels remained.
However, the matter wave approach eliminated the spatially localized electron, which orbits around the nucleus, without violating the classical electrodynamics. The space around the nucleus is filled with standing waves of the electrons.

The phenomenon of superposition

Our ordinary experience of macroscopic matters is far from the microscopic description introduced so far. Wave-particle duality involves questions like how should we imagine and/or handle this at all? We know about waves that we can sum up two different waves and a resulting one is produced. The experiments still stands and valid in cases like the light waves. The interference, which is the evidence of the wave phenomenon, still occurs in experiments.
According to the theory we should be able to add several of them together as just in case of light waves. Adding matter waves together is actually forming the SUPERPOSITION of the individual matter waves. The superposition has a central role in the theory of matter waves and in quantum theory as a whole.

Let's imagine what happens when multiple component waves with constant wavelength are added together. While the component waves are uniformly spread out in space with definite wavelengths, the resulting one is no longer uniformly spread out and has not a single wavelength.

Wave packets

In case when particles are composed of waves, then how can we find our localized particles at all? According to de Broglie's formula momentum = h / wavelength . That is, a matter wave with a definite wavelength has a definite momentum.

Consider a wave with constant lambda. One can ask where is the particle? The answer is: our particle is spread through the space.

We can find another extreme example when the matter wave is just a pulse. In this case we can localize the spatial particle. But what about the momentum of the localized particle? For the answer we have to recognize that our spatially localized particle is not composed from a single matter wave with its single finite wavelength. But it is a superposition of infinite many different matter waves with infinite many different wavelengths.

The first two cases are the extremes. The usual objects in quantum theory are represented by in between cases and called wave packets.
By adding together a finite set of momenta associated matter waves the resulting packet occupies a range of positions in space with the associated range of momenta.

Schrödinger equation

So, by now we have an overview about matter waves. But we have not dealt with question what happens with these waves in time? How do they change, how do they evolve and finally how can we influence this evolution?
A localized particle is comprised of spatially localized matter wave, that is a pulse. The standalone left pulse will spread out in all directions as propagating waves.

The way as the waves propagate is precisely described by the Schrödinger wave equation.
This type of time evolution is called Schrödinger evolution.

i ℏ \frac{\partial | ψ ⟩}{\partial t} = H | ψ ⟩

As we saw before matter waves are spread over the space and experience superposition from many momenta when they pass through each other.

Although, if matter waves would evolve according to the Schrödinger equation only, this would not conform to our ordinary experience regarding the world.

Collapse of the wave packet - the measurement uncertainty

Schrödinger evolution is fully deterministic. However, this statement does not stand in case of the measurement.
We does not know for sure where we find a particle when we try to measure the position of it. We know about the wave packet that it is the superposition of matter waves.
One can raise the question: by knowing that the wave packet is a composition of matter waves, may we have any more information about position after the measurement?

A wave or pulse, which contributes with larger amplitude to the wave packet will have a larger effect regarding the observed position, than the smaller ones.
Max Born realized this fact and phrased in the Born rule: that the amplitude of the component wave or pulse determines the probability of the component as an outcome.
Probability that the wave packet collapse to this component = (amplitude of com)² There is no comforting explanation regarding the evolution of the measurement.
The best we can say is the experiment based rule of thumb, by which:

matter waves undergo Schrödinger evolution if left to themselves or interacting with just a few particles,
matter waves undergo collapse if they interact with macroscopic bodies (like detectors).

Quantum entanglement

The most surprising phenomenon in quantum mechanics is the so called entanglement. The explanation behind of it is still not clarified and an active research area.
The entanglement is when there are two distinct elements of a system, but one part cannot be described without taking the other into consideration (see later the math explanation).

From wikipedia:
The state of a composite system is always expressible as a sum, or superposition, of products of states of local constituents; it is entangled if this sum cannot be written as a single product term.

The paradox is that a measurement made on either of the particles apparently collapses the state of the entire entangled system — and does so instantaneously, before any information about the measurement result could have been communicated to the other particle (assuming that information cannot travel faster than light) and hence assured the "proper" outcome of the measurement of the other part of the entangled pair. In the Copenhagen interpretation, the result of a spin measurement on one of the particles is a collapse (of wave function) into a state in which each particle has a definite spin (either up or down) along the axis of measurement. The outcome is taken to be random, with each possibility having a probability of 50%. However, if both spins are measured along the same axis, they are found to be anti-correlated. This means that the random outcome of the measurement made on one particle seems to have been transmitted to the other, so that it can make the "right choice" when it too is measured.

The distance and timing of the measurements can be chosen so as to make the interval between the two measurements spacelike, hence, any causal effect connecting the events would have to travel faster than light. According to the principles of special relativity, it is not possible for any information to travel between two such measuring events. It is not even possible to say which of the measurements came first. For two spacelike separated events x₁ and x₂ there are inertial frames in which x₁ is first and others in which x₂ is first. Therefore, the correlation between the two measurements cannot be explained as one measurement determining the other: different observers would disagree about the role of cause and effect.
link

Quantum Computing Part I - Intro
Quantum Computing Part II - Building Blocks of Quantum Algorithms
Fidelity Based Random Quantum Circuit Generator, Selector and Post Optimizer