Rajendra K. Bera, Chief Mentor, Acadinnet Education Services India Pvt.

---

Abstract

This paper is intended to be a short tutorial for those who have already begun to study quantum computing, are familiar with the basic terminologies of quantum mechanics and its core concepts (quantum superposition, measurement, entanglement, decoherence, etc.) and would like to step back and reflect upon the foundations of quantum computing before getting into the nitty gritty of more complex algorithms, e.g., Shor’s factorization algorithm, Grover’s search algorithm, etc. The important thing to remember is that while the mathematics used to deal with classical and quantum physics is the same, interpreting quantum measurement requires a twist. That interpretation is governed by a separate postulate that tells you the probability with which you will see various parts of the answer in a given experiment. This complication does not exist is classical physics. Once you come to terms with this postulate, you will find quantum computing rather easy to deal with. Measurement is a complex matter and necessitates that the experiment be repeated many times and measurements accumulated before analysis of the results is made to reveal the full answer. The repetitions can be done in a series, in parallel or in any combination of the two. The experiments must be identical in their mathematical description and input data.

Keywords: Quantum, qubit, measurement, superposition, entanglement, algorithm, gate.

1 Introduction

A perplexing aspect of quantum mechanics is that it defies our normal intuition. It is dramatically different from classical physics as built by Newton, Maxwell, and Einstein. Laws of classical physics are deterministic in the sense that given, say, Newton’s laws of motion, and initial conditions (position and momentum) at some instant we deem to be t = 0 for a system and a time history of the force(s) acting on the system, we can, in principle, accurately predict the state of that system at any time in the past or the future. Further, we can measure the present state of the system (position and momentum) without disturbing it.

In quantum mechanics, the situation is completely different. The counterpart of Newton’s second law of motion for a quantum system is the Schrödinger’s wave equation, and the state of the system is described by something called the “wave functionâ€Â, |\psi⟩, which no one understands intuitively. It is so abstract that we understand it only in a mathematical sense. Newton’s first law of motion refers to ‘force-free’ motion.

It has not been possible for physicists (or anyone else for that matter) to understand the wave function in any other way. If we try to measure the state of a quantum system, hell breaks loose; we have no way of deterministically predicting what the result of a measurement will be! And , even in principle, there is no way we can measure a quantum system without disturbing it. That is why physics is divided into two parts: classical physics, and quantum physics.¹

No one knows what transitory changes a quantum system undergoes when it is measured. We do know, however, that while we cannot deterministically anticipate the result of a measurement, we can make an amazingly accurate probabilistic prediction of it. I and a former student of mine, Vikram Menon, have come up with a hypothesis to explain this very unusual aspect of quantum systems.² It is briefly presented in Sec. 9 of this paper. The probabilistic aspect of quantum mechanics is intriguing because Schrödinger’s equation has no built in probabilities; indeed it produces only deterministic results! So where did the probabilities come from? Max Born³ provided an inspired explanation for it in 1926, which provided an entirely new basis for interpreting measurements. Born shared the Nobel Prize in Physics, 1954 (with Walther Bothe) “for his fundamental research in quantum mechanics, especially for his statistical interpretation of the wavefunctionâ€Â. In his Nobel Lecture, Born lucidly explains how he was led to it.⁴ It is an excellent example for the reader to learn from, namely that mathematics encapsulates information in the abstract which can be interpreted in multiple ways depending on the world (real or imaginary) to which it is applied. (See also Sec. 8 under the subheading Form and meaning are separate.)

Just as Isaac Newton discovered that masses are gravitationally attracted to each other (but not the reason behind it) and stated it as a fundamental law of Nature in classical physics as the inverse square law of gravitation, so did Max Born state the probabilistic aspect of quantum physics as a law of Nature. It is amazing that human discovery of laws of nature is analogous to the serendipitous invention of man-made axioms in mathematics. We do not know (and can never know) why the laws or axioms turn out to be as they do. Only “the original creatorâ€Â can enlighten us, if at all. We can only marvel at the intellectual genius of those physicists and mathematicians who are able to read the book of Nature. These discoveries and inventions are driven by universally shared human instinct for reasoning.

2 Axioms of quantum mechanics

Here are the laws (or postulates or axioms) of quantum mechanics stated informally.

• Quantum mechanics describes a physical system through a mathematical object called the state vector (or the wave-function) |ψ⟩, which is complex (i.e., it has real and imaginary parts) and it is a vector of unit length. (Our social systems too are complex because humans have real and imaginary aspirations!)

• |ψ⟩ evolves in a deterministic manner according to the linear Schrödinger equation:

$$- \frac{\hslash^{2}}{2m}\nabla^{2}|\psi(\mathbf{r},\ t)\rangle + V\left( \mathbf{r} \right)|\psi(\mathbf{r},\ t)\rangle = i\hslash\frac{\partial|\psi(\mathbf{r},\ t)\rangle\ }{\partial t},$$

where |ψ⟩ is the wavefunction, ℏ is the reduced Planck’s constant, V is the potential energy of the particle at position r (it assumes the presence of conservative forces only), m is the mass of the particle under consideration, the operators ∇² and $\frac{\partial}{\partial t}$, respectively, describe how the wavefunction changes with space and time. In particular, bear in mind that |ψ⟩ remains a unit vector during its evolution, and any operation on it only changes its orientation.

• Any measurement made on a quantum system leads to the (non-unitary) irreversible collapse of its wave function to a new state governed by a probability rule prescribed by Born. Measurement destroys quantum superposition.

• The state space of a composite quantum system is the tensor product of the state spaces of the component quantum systems.

One cannot overemphasize the fact that it is only when measurements are made that indetermination and probabilities come into quantum theory. Otherwise, things are very deterministic. The collapse of the wave function involves no forces of any kind but it does involve loss of information, hence a measurement cannot be undone. (In classical physics, a measurement is deemed possible without changing the state of the system.)

2.1 An example of what the axioms mean

Consider the simple case of a quantum system capable of being in two distinctly different states |F⟩ and |G⟩. The general state of the wavefunction |ψ⟩ is then given by the linear combination of |F⟩ and |G⟩ as

|ψ⟩ =a |F⟩ + b |G⟩, 

where a and b are complex constants (with real an imaginary parts). When |ψ⟩ is measured, the output will not be

a |F⟩ + b |G⟩.

It will be either

|ψ⟩ =|F⟩,  or       |ψ⟩ =|G⟩.

The probability (prob) with which one or the other will appear in the output is as follows:

prob|F⟩ :prob|G⟩  = |a|²: |b|²; 

|a|²+ |b|²â€„= 1. 

But this will become visible only if a very large number of identical |ψ⟩ systems are available or can be created and a measurement on each system is made. When measured, each system will collapse to either |F⟩or |G⟩ in an unpredictable way in proportion to the probabilities noted above and will remain in that state if left undisturbed. It will not be in any linear combination of |F⟩ and |G⟩.

The collapse of the wave function seems to happen instantly unlike the ordinary time evolution of quantum states (according to the Schrödinger’s equation). We still do not understand the physical mechanism, which causes the collapse. Complex linear superposition of states and collapse of wave functions are unusual features of quantum mechanics. If you get infatuated with quantum mechanics, you will eventually fall in love with it.

When |ψ⟩ is manipulated by any operator, it remains a unit vector, e.g., when |ψ⟩=|F⟩ or |ψ⟩=|G⟩ after measurement; only a and b change such that |a|²+ |b|²â€„= 1. All of quantum computing is about manipulating complex constants.

A simple generalization exists when the wavefunction |ψ⟩ has more than two, say, n, distinctly different states |ψ₁⟩, |ψ₂⟩,  …, |ψ_n⟩. Its linearly superposed state is then described by

|ψ⟩=a₁|ψ₁⟩+ a₂|ψ₂⟩ +  … + a_n|ψ_n⟩,  

where a₁, a₂,  …, a_n are complex constants, which may change if |ψ⟩ is operated upon by either quantum operators or measurement operators. After a measurement, i.e., the application of a measurement operator, |ψ⟩ will collapse to |ψ⟩= |ψ_i⟩ with the index i occurring with certain probabilities as noted below:

prob|ψ₁⟩ :prob|ψ₂⟩ : … : prob|ψ_n⟩ = |a₁|²Â : |a₂|²Â : … : |a_n|²;

|a₁|²+ |a₂|²+ … + |a_n|²â€„= 1. 

Thus, when |ψ⟩ changes either due to Schrödinger evolution or measurement, only the a_i change such that the sum of the |a_i|² always remains 1. This ensures that |ψ⟩ will remain a unit vector and only its orientation will change.

2.2 An example of output weirdness

At first glance, what did you see? |ψ⟩ =a |F⟩ + b |G⟩Â
Fig.1. My wife and my mother-in-law, by the cartoonist W. E. Hill, 1915 (adapted from a picture going back at least to a 1888 German postcard). https://commons.wikimedia.org/wiki/File:Youngoldwoman.jpg (in public domain).

Take a quick glance at Fig. 1 and note in your mind what you saw. Now look at the figure again moving your eyes up and down. Did you see another picture? Did you see anything other than sometime a beautiful girl (the wife of the artist) and another time an old woman (his mother-in-law). You did! More to the point, you did not see any weird combination of your two visual interpretations. It is the same picture (by analogy the wavefunction |ψ⟩) which is a combination of the fair lady |F⟩ and the grand lady |G⟩. When viewed, you were able to see only one of them at any time.

What is not captured in Fig. 1 is that whatever you saw did not get frozen. In a quantum measurement, the wavefunction freezes (or collapses) to the measured value. But what the picture does capture is that a given matrix of pixels can carry more than one meaning in the same space and at the same time. This is a quintessential wave property. Two pieces of matter cannot occupy the same space at the same time, waves and interpretations can.

Hopefully, you now have developed some gut feeling for what one means by superposition and wavefunction collapse in quantum mechanics. By the way, during the interval when your eyes first fell on the picture till the moment you “sawâ€Â the picture, was your brain in a state of superposition? Were you in two minds simultaneously? Is the wavefunction aware of being in a state of superposition? These are questions you might wish to explore further, perhaps philosophically.

3 Unitary transformation in quantum mechanics

The Schrödinger evolution of the wave function, alternatively, can be described in matrix form due to Werner Heisenberg, which is the form used in quantum computing. In this form, the evolution of a closed quantum system is described by a unitary transformation. That is, the state |ψ(t₁)⟩ of the system at time t₁is related to the state |ψ(t₂)⟩ of the system at time t₂ by a unitary operator U which depends only on the times t₁ and t₂,

|ψ(t₂)⟩=U |ψ(t₁)⟩.

A linear operator U whose inverse is its adjoint (conjugate transpose, U^†) is called unitary, that is, U^†U = UU^† = I, where U^† ≡ (U^*)^T ≡ (U^T)^*. Thus, by definition, unitary operators are invertible. Also, by definition, a unitary operator does not change the length of the state vector it acts upon; it only changes that vector’s orientation. This means that if

|ψ(t₁)⟩ =a₁|ψ_a⟩  + b₁|ψ_b⟩ ;   |a₁|²+ |b₁|²â€„= 1,  

then

|ψ(t₂)⟩  = a₂|ψ_a⟩ +b₂|ψ_b⟩ ;   |a₂|²+ |b₂|²â€„= 1.  

4 Quantum computing

Quantum computing is about computing with quantum systems using the rules of quantum mechanics rather than the rules of classical mechanics. The important quantum mechanical phenomena that come into play in the building of a quantum computer are:

• Superposition

• Entanglement

• Decoherence

On a quantum computer, problem specific algorithms are executed that comprise an organized sequence of unitary operations and measurements once relevant input data is provided. Since all unitary operators are invertible, we can always reverse or ‘uncompute’ those computations. (In principle, we can do this on Turing machines using classical physics also.⁵) If a measurement is made, ‘uncomputing’ previous unitary operations are no longer possible. That is, measurements cannot be undone because it is axiomatically tied to the probabilistic nature of quantum measurement and collapse of the wave function.

4.1 Quantum superposition

Let us look at Fig. 1 “My wife, and my mother-in-lawâ€Â once again. You cannot really define a linear combination (superposition) of

|ψ⟩ =a |F⟩ + b |G⟩ = a |my wife⟩ + b |my mother − in − law⟩

in a physical sense, yet you know that in some “complexâ€Â sense the two people are superposed in the picture (i.e., they exist simultaneously at the same place and time). You recognize the superposition at an intellectual level, but not at the measurement level (vision); you see the picture “collapsingâ€Â to one or the other person. In quantum mechanics, the measurement operator is like a prism—it splits the wavefunction into its component parts (akin to white light being split into its rainbow components by a prism). In our example, the “prismâ€Â would split the picture into my wife〉 and my mother-in-law〉 and the probability with which we will see one or the other is given by

prob|F⟩ :prob|G⟩  = prob|my wife⟩ :prob|my mother − in − law⟩  = |a|²: |b|²â€„= 1.

You will not see some weird hybrid form of “my wifeâ€Â and “my mother-in-lawâ€Â.

4.2 Quantum entanglement

Entanglement is a form of quantum superposition. It is a joint and acquired group property of two or more quantum particles, which when entangled, share an instantly responsive bonded existence even when light years apart. Indeed, separation distance is irrelevant. If the state of one is changed, the state of the other is instantly adjusted to be quantum consistent. If a measurement is made on one, both will collapse together. There is no easy explanation of entangled correlations. There is no counterpart of entanglement in classical mechanics.

Einstein called such action-at-a-distance ‘spooky’. He wrote to Max Born in March 1947:

I cannot seriously believe in [the quantum theory] because it cannot be reconciled with the idea that physics should represent a reality in time and space, free from spooky actions at a distance.⁶

4.3 Decoherence

It is the spontaneous disruptive interaction between a quantum system and its environment which destroys quantum superposition. The reason why quantum computers still have not replaced our laptops is that superposition and entanglement are extremely fragile states. Any interaction with the environment and the particles tend to decohere. Preventing decoherence from taking hold before a calculation is completed remains the biggest challenge in building quantum computers. While considerable progress has been made in dealing with this problem, still more needs to be done. (See also Sec. 10 below.)

5 Physical laws are mathematical

When we say F = ma expresses Newton’s second law of motion, what we mean is that if you interpret F as representing a force (a vector with 3-scalar components), m representing the mass of a material body, and arepresenting the acceleration of that material body, then we can very accurately compute the motion of that material body. F = ma means nothing until we give it an interpretation. Surprisingly, all the important laws of physics can be precisely stated in mathematical form. This fact led the 1963 Nobel Laureate in physics, Eugene Paul Wigner, to comment in wonder, The Unreasonable Effectiveness of Mathematics in the Natural Sciences.⁷ It turns out that without knowing mathematics, you cannot develop a deep understanding of physics. This is particularly true for quantum mechanics. Warning: Unless you understand linear algebra and complex variable theory, you will not understand quantum mechanics.

5.1 Interpretation of Schrödinger’s equation

Recall Schrödinger’s equation

$$- \frac{\hslash^{2}}{2m}\nabla^{2}\left| \psi\left( \mathbf{r},\ t \right)\rangle + V\left( \mathbf{r} \right) \right|\psi\left( \mathbf{r},\ t \right)\rangle = i\hslash\frac{\partial|\psi(\mathbf{r},\ t)\rangle\ }{\partial t}.$$

Even though we do not know what the wavefunction |ψ⟩ means, yet, with the following interpretation:

Variable	Classical → quantum
Time, t	t → t
Position, r	r → r
Momentum, p	p →  − iℏ∇
Energy, E	E → $i\hslash\left( \frac{\partial}{\partial t} \right)$

we make a connection with the physical world. Note that we are interpreting two mathematical operators as physical variables: the operator  − iℏ∇ is interpreted to represent the physical variable momentum pand the operator $\text{iℏ}\left( \frac{\partial}{\partial t} \right)$ as the physical variable energy E! Now you can understand why quantum mechanics appears weird. It requires a lot of imagination to connect the real world with complex number mathematics.

Why are quantum systems quantized?

Let us call HÌ‚ the Hamiltonian operator where

$$\widehat{H}\mathbf{\ } \equiv \ - \frac{\hslash^{2}}{2m}\nabla^{2} + V,$$

Then from the table above

Ĥ |ψ⟩ =E |ψ⟩ .

Since the Hamiltonian operator can alternatively be written as a square matrix, we have an equation of the form we call an eigenvalue problem in linear algebra:

Ax = λx.

This equation has the trivial solution, x = 0, but it also has non-trivial solutions for certain discrete values of λ (which we call the eigenvalues of matrix A). So now we see why, for a finite quantum system, energy is quantized. The E values are the eigenvalues of the Hamiltonian operator! A quantum system is quantized because the Schrödinger’s equation describes an eigenvalue problem.

5.2 Heisenberg’s uncertainty principle

We now find another intriguing aspect of quantum mechanics. This comes from the fact that operators, do not always commute. Thus, pr ≠ rp, because

 − iℏ∇r ≠ r(−iℏ∇).

This means that the measurement of position r and momentum p of a particle is no longer independent of the sequence in which they are measured. This is the reason why one cannot measure both position and momentum of a quantum particle with absolute accuracy. And this fact is responsible for the famous Heisenberg’s uncertainty principle in quantum mechanics, which says:

$$\mathrm{\Delta}\text{p\ }\mathrm{\Delta}\text{q\ } \geq \frac{\hslash}{2},\ $$

where Δq is the error in the measurement of any coordinate and ∆p is the error in its canonically conjugate momentum. In quantum mechanics, e.g., position (q) and momentum (p) of a particle are such measurements. The uncertainty principle is categorical. We cannot observe a quantum system without affecting it. The independent, unobtrusive observer simply does not exist. Thus, contrary to Newtonian mechanics, even in principle, it is not possible to know enough about the present to make a complete prediction about the future. The measurement limits in quantum mechanics cannot be overcome by refining measurement technology as we penetrate into the subatomic world. Classical and quantum particles are entirely different entities. The principle sets limits on precision technologies, e.g., metrology and lithography. However, if the particle is prepared entangled with a quantum memory (such as an optical delay line) and the observer has access to the particle stored in the quantum memory, it is possible to predict the outcomes for both measurement choices precisely.⁸ This is a more general uncertainty relation, formulated in terms of entropies. This new relation has been verified experimentally.⁹

5.3 No cloning, no deletion

That quantum operators are unitary, presents unusual consequences. One is that if you do not know the state of a quantum system (even if it is a single particle) then you cannot make an exact copy of it. This is known as the no-cloning theorem¹⁰. (You can, of course, prepare a particle in any desired state and make as many copies of it as you like.) The other is that unless a quantum system collapses, you cannot delete information in a quantum system. This is known as the no-deletion theorem¹¹. These results are connected with the quantum phenomenon called entanglement. Quantum algorithm designers make very clever use of quantum superposition and quantum entanglement.

5.4 Ingredients of quantum algorithms

In the weird quantum world, quantum algorithms are replete with clever sequences of unitary operators that move the system according to Schrödinger’s equation, of measurement operators that collapse the system, and very imaginative uses of superposition and entanglement.

A single qubit (the quantum analogue of the classical bit) is the simplest quantum system we can think of. Mathematically, a qubit is described as a unit vector |ψ⟩ = a|0⟩ + b|1⟩, parameterized by two complex numbers a and b, satisfying |a|²+ |b|²â€„= 1. While the qubit can be in either state 〉 or 〉 (analogous to the 0 and 1 states of a classical bit), it can also be in a superposed state of (a|0⟩ + b|1⟩), which a classical bit can never be in. In any non-trivial computation, of course, many more than one qubit will be required.

6 Manipulating qubits

In quantum computing we rely on the following facts:

(1) All quantum gates are reversible by design, i.e., unitary.

(2) Any unitary operation on n qubits can be implemented exactly by stringing together operations composed of 1-qubit Pauli operators and 2-qubit controlled-NOT gates. This is provable. These gates are described below.

6.1 1-qubit unitary operators

Any unitary operator M changing the state of a single qubit can always be set up as a linear combination of 4 unitary operators (also called gates), traditionally represented by (I, X, Y, Z) ≡ (σ₀, σ₁, σ₂, σ₃), i.e.,

M = α I + β X + γ Y + δ Z,   

where α, β, γ, δ are complex constants. The operators (I, X, Y, Z) are called Pauli matrices, and in their alternative symbolic form (σ₀, σ₁, σ₂, σ₃) are called sigma matrices. Each operator is a 2×2 matrix. The Hadamard gate (a linear combination of X and Z gates) is a very important and often used gate.

Hadamard gate, H

The Hadamard gate, $\text{H\ } \equiv \ (X + Z)/\sqrt{2}$ , is an amazing gate. When applied to a qubit in state |0⟩ or |1⟩, it changes the qubit’s state, respectively to

$H|0\rangle\ = \ \frac{\left( |0\rangle\ + \ \middle| 1\rangle \right)}{\sqrt{2}}\ $ and $H|1\rangle\ = \ \frac{\left( |0\rangle\ - \ \middle| 1\rangle \right)}{\sqrt{2}}$.

When a measurement is now made on the qubit, the output in either case will be |ψ⟩=|0⟩ or  |ψ⟩=|1⟩ with equal probability. Thus, quantum physics provides us with a perfect random number generator (something impossible in classical physics). In general, if |ψ⟩=a|0⟩  + b |1⟩, then

$$H|\psi\rangle\ = \text{a\ }\frac{\left( |0\rangle\ + \ \middle| 1\rangle \right)}{\sqrt{2}} + \ b\ \frac{\left( |0\rangle\ - \ \middle| 1\rangle \right)}{\sqrt{2}}.$$

However, if no measurement is made, and the Hadamard gate is applied once again to the output, then

$H(H|0\rangle)\ = \ H\frac{\left( |0\rangle\ + \ \middle| 1\rangle \right)}{\sqrt{2}} =$ |0⟩ and $H(H|1\rangle)\ = \ H\frac{\left( |0\rangle\ - \ \middle| 1\rangle \right)}{\sqrt{2}}$ = |1⟩,

and we get back the original state of the qubit, i.e.,

H(H|ψ⟩)=a|0⟩  + b |1⟩= |ψ⟩.

This is rather amazing. A randomizing operation to a random state produces a deterministic outcome! The Hadamard gate can randomize and de-randomize.

n-qubit Hadamard gate

When the Hadamard gate is applied to n qubits individually, we get,

$\underset{n - \text{times}}{\overset{\text{HH}\cdots H}{︸}}\underset{n - \text{times}}{\overset{\left| 00\cdots 0 \right\rangle}{︸}} = \underset{n - \text{times}}{\overset{\frac{1}{\sqrt{2}}\left( \left| 0 \right\rangle + \left| 1 \right\rangle \right)\frac{1}{\sqrt{2}}\left( \left| 0 \right\rangle + \left| 1 \right\rangle \right)\cdots\frac{1}{\sqrt{2}}\left( \left| 0 \right\rangle + \left| 1 \right\rangle \right)}{︸}}$,

or in the more compact notation $H^{\otimes n}\ \equiv \ \underset{n - times}{\overset{HH\cdots H}{︸}}$, we get

$H^{\otimes n}\underset{n - \text{times}}{\overset{\left| 00\cdots 0 \right\rangle}{︸}} = \frac{1}{\sqrt{2}}\underset{2^{n} - \text{permutations}\mspace{6mu}\text{of}\mspace{6mu} the\mspace{6mu} n - \text{qubit}\mspace{6mu}\text{states}}{\overset{\left( \left| 00\cdots 0 \right\rangle + \left| 00\cdots 1 \right\rangle + \cdots + \left| 11\cdots 1 \right\rangle \right)}{︸}} = \frac{1}{\sqrt{2^{n}}}\sum_{x}^{}\left| x \right\rangle$,

where the sum is over all possible 2ⁿ mutually orthogonal states of n qubits or “valuesâ€Â of x. Thus the Hadamard transform produces an equal superposition of all 2ⁿ possible computational basis states, i.e., x can be viewed as the binary representation of the numbers from 0 to (2ⁿ − 1), and this is done extremely efficiently (as compared to a classical computer) by using only n gates. The n-qubit Hadamard gate is sometimes known as the Walsh-Hadamard gate.

6.2 2-qubit unitary controlled-not operator

The Controlled-NOT operator (gate), C_not is an indispensable operator in quantum computing. It is used to entangle two-qubits. It acts on a qubit-pair such that

C_not|00⟩ = |00⟩,    C_not|01⟩ = |01⟩,    C_not|10⟩ = |11⟩,    C_not|11⟩ = |10⟩. 

Note that the state of the first qubit, called the control qubit, does not change while the state of the second qubit, called the target qubit, changes only if the control qubit is in state |1⟩. This signifies the exclusive-or(XOR) operation (that is, the output is “trueâ€Â if and only if exactly one of the two operands has a value of “trueâ€Â).

Entangling qubits

An application of the H-gate on the first qubit followed by the C_not−gate to a 2-qubit system (with the first qubit as the control qubit) gives the following results when the system’s initial state is 〉, 〉, 〉, and 〉, respectively:

C_not (H I) (〉) = C_not (〉 + 〉)/√2 = (〉 + 〉)/√2,

C_not (H I) (〉) = C_not (〉 − 〉)/√2 = (〉 − 〉)/√2,

C_not (H I) (〉) = C_not (〉 + 〉)/√2 = (〉 + 〉)/√2,

C_not (H I) (〉) = C_not (〉 − 〉)/√2 = (〉 − 〉)/√2.

The final states (last column) are called Bell states (after John Bell).

They are interesting because they are all entangled states, that is, they cannot be attained by manipulating each qubit using the 1-qubit Pauli operators alone. If the states of the entangled particles are used to encode bits, then the entangled joint state represents what is called an ebit (entangled qubit pair). Its joint state is always distributed between two qubits. The states of these qubits are correlated, but undetermined to an observer until measured.

3-qubit Toffoli gate, T

The T gate (named after Tommaso Toffoli who invented it) acts on a qubit-triplet such that

T 〉 = 〉, T 〉 = 〉,

T 〉 = 〉, T 〉 = 〉,

T 〉 = 〉, T 〉 = 〉,

T 〉 = 〉, T 〉 = 〉.

It can be viewed as a controlled-controlled-NOT gate, which negates the last of three qubits, if and only if the first two are 1. The Toffoli gate is its own inverse. Toffoli gates can be constructed using six C_not gates and several 1-qubit gates.¹²

7 Some elementary algorithms

A few simple examples.

7.1 Swapping states between two qubits

The state of two qubits can be swapped by applying the C_not gate as follows in the four possible cases.

〉 → 〉 with the first qubit as control

→ 〉 with the second qubit as control

→ 〉 with the first qubit as control

〉 → 〉 with the first qubit as control

→ 〉 with the second qubit as control

→ 〉 with the first qubit as control

〉 → 〉 with the first qubit as control

→ 〉 with the second qubit as control

→ 〉 with the first qubit as control

The C_not gate has no effect on 〉.

7.2 Computing x∧y (x AND y)

Take 3 qubits, each prepared in state |0⟩, i.e., |ψ⟩ = |000⟩. The first qubit is the placeholder for x, the second for y, and the third for the result of x ∧ y. To create the 4 possible inputs of x and y, apply the Hadamard gate to the first two qubits while I leaves the third qubit untouched:

$${|\psi}_{1}\rangle\ = \ (HHI)\ |000\rangle\ = \ (1/\sqrt{}2)\ (|0\rangle\ + \ |1\rangle)\ (1/\sqrt{}2)\ (|0\rangle\ + \ |1\rangle)\ |0\rangle$$

 = (1/2) (|000⟩ + |010⟩ + |100⟩ + |110⟩).

An application of the Toffoli gate, T, now produces:

|ψ₂⟩ = T|ψ₁⟩ = (1/2) (|000⟩ + |010⟩ + |100⟩ + |111⟩).

Notice that the 3-qubit system is put into equal superposition of the four possible results of x ∧ y. The result of ANDing the first two qubits appears in the third qubit.

7.3 Computing x+y

Take 3 qubits, each prepared in state 〉. Compute x ∧ y. So, we have

|ψ₂⟩ = (1/2) (|000⟩ + |010⟩ + |100⟩ + |111⟩).

Now apply the C_not gate to the first two qubits while I leaves the third qubit untouched, to get:

C_not I |ψ₂⟩ = (1/2) (|000⟩ + |010⟩ + |110⟩ + |101⟩),

where the second qubit is the sum, and the third qubit is the carry bit.

Note that the carry bit in the adder is the result of an AND operation. The carry and AND are really the same thing. The sum bit comes from an XOR gate (that is, the C_not operation).

8 Interpretations of quantum mechanics

To get a hang of quantum mechanics it is important to understand the many ways in which quantum mechanics is interpreted. These interpretations appear so widely different and yet imaginably and logically plausible that it leaves one wondering how much do we really know about the Universe we live in. It led N. David Mermin to suggest in exasperation that we should forget the interpretations and just "shut up and calculate!"¹³ Bear in mind that the wave function is an abstract mathematical object. Neither its origin nor its underlying structure has been disclosed in the laws of quantum mechanics. In particular, the mechanisms for superposition, entanglement, and measurement have not been elucidated. Hence, they too are open to multiple interpretation.

Non-uniqueness of interpretations

What we find in the various interpretations is that while the formalism of quantum mechanics is widely accepted, there is no single interpretation that everyone finds agreeable. The disagreements essentially stem from the incompatibility that exists between two evolutionary paths a quantum system follows—the Schrödinger’s equation, and the “collapseâ€Â mode of measurement.

Indeed, without the measurement postulate telling us what we can observe, the equations of quantum mechanics would be just pure mathematics that would have no physical meaning at all. Note also that any interpretation can come only after an investigation of the logical structure of the postulates of quantum mechanics is made. Let me explain what we mean by an interpretation in the context of quantum mechanics.

Form and meaning are separate

For example, Newtonian mechanics does not define the structure of matter. How we interpret or model the structure of matter is largely an issue separate from Newtonian mechanics. However, any model of the structure of matter we propose is expected to be such that it is compatible with Newton’s laws of motion in the realm where Newtonian mechanics rules. If it is not, then Newtonian mechanics as we know it would have to be abandoned or modified or the model of the structure of matter would have to be abandoned or modified. One may also have a partial interpretation and leave the rest in abeyance till further insight strikes us and leads us to a complete or a new interpretation.

A question such as whether a particular result deduced from Newton’s laws of motion is deducible from a given model of material structure is therefore not relevant.

Likewise, as long as an interpretation (or model) of superposition, entanglement, and measurement does not require the axioms of quantum mechanics to be altered, none of the predictions made by quantum mechanics would be incompatible with that interpretation. This assertion is important because in our (Bera-Menon) interpretation we make no comments on the Hamiltonian (in the Schrödinger’s equation), which captures the detailed dynamics of a quantum system. Quantum mechanics does not tell us how to construct the Hamiltonian. In fact, real life problems seeking solutions in quantum mechanics need to be augmented by physical theories that are compatible with the axioms of quantum mechanics. Those axioms provide only the scaffolding around which detailed physical theories are to be built.

We now briefly describe three wildly different interpretations—(1) the Copenhagen view, (2) Bohm’s pilot wave, and (3) Everett’s many worlds.

8.1 Copenhagen view

This is the most popular interpretation used by quantum physicists. In the Copenhagen interpretation (around 1927), one cannot describe a quantum system independently of a measuring apparatus. Indeed, it is meaningless to ask about the state of the system in the absence of a classical measuring system. The role of the observer is central since it is the observer who decides what he wants to measure.

In this interpretation, a particle’s position is essentially meaningless; measurement causes a collapse of the wave function and the collapsed state is randomly picked to be one of the many possibilities allowed for by the system’s wave function; the fundamental objects handled by the equations of quantum mechanics are not actual particles that have an extrinsic reality but “probability wavesâ€Â that merely have the capability of becoming “realâ€Â when an observer makes a measurement. Entanglement is treated as a mysterious phenomenon. The preferred interpretation assumed in this paper is the Copenhagen interpretation.

8.2 Bohm’s pilot wave

In Bohm’s interpretation (1952), the whole universe is entangled; its parts cannot be separated. Entanglement is not a mystery; it is mediated by a very special unknown anti-relativistic quantum information field (pilot wave, derivable from Schrödinger’s equation) that does not diminish with distance and that binds the whole universe together. It is an all pervasive field that is instantaneous; it is not physically measurable but manifests itself in terms of non-local (unmediated, instantaneous, and unaffected by the nature of the intervening medium) correlations.

In this interpretation, an electron, e.g., has a well-defined position and momentum at any instant. However, the path an electron follows is guided by the interaction of its own pilot wave with the pilot waves of other entities in the universe.

In fact, Bohm treats measurement as an objective process in which the measuring apparatus and what is observed interact in a well-defined way. At the conclusion of this interaction, the quantum system enters into one of a set of ‘channels’, each of which corresponds to the possible results of the measurement while the other channels become inoperative. In particular, there is no ‘collapse’ of the wave function, yet the wave function behaves as if it had collapsed to one of the channels.¹⁴

8.3 Everett’s many worlds

Everett’s interpretation¹⁵ is perhaps the most bizarre and yet perhaps the simplest (it is free of the measurement problem because Everett omits the measurement postulate) and, instead, requires us to believe that we inhabit one of an infinite number of parallel worlds!

He assumes that when a quantum system in a given world is faced with a choice, i.e., choosing between alternatives as in a measurement, the system splits into a number of systems (worlds) equal to the number of options available. Thus, the world of a qubit in state (〉 + 〉)/√2 will split into two worlds if the qubit is measured. The two worlds will be identical to each other except for the different option chosen by the qubit—in one it will be in state 〉 and in the other it will be in state 〉. Each world will also carry its own copy of the observer(s), and each observer copy will see the specific outcome that appears in his respective world. Of course, the worlds can overlap and interact in the overlapping regions. Decoherence, that is, (spontaneous) interactions between a quantum system and its environment will cause the worlds to separate into non-interacting worlds.

9 A novel view on measurement

In 2009, I and my student Vikram Menon proposed a sub-Planck-structure for the wave function, and within that structure the meaning of superposition, entanglement, and measurement without affecting the postulates of quantum mechanics.¹⁶ The sub-Planck scale provides us with the freedom to construct mechanisms for our interpretation that are not necessarily bound by the laws of quantum mechanics (just as atomic structure is not bound by Newtonian mechanics). In particular, our interpretation need not even satisfy the Schrödinger wave equation because quantum mechanics is not expected to rule in the sub-Planck scale. The high point of our interpretation is that it is able to explain the measurement postulate as the inability of a classical measuring device to measure at a precisely predefined time.

Superposition

In our interpretation we assume that the sub-Planck scale structure of the wave function is such that the wave function is in only one state at any instant but oscillates between its various “superposedâ€Â component states (eigenstates). (There is no expenditure of energy in maintaining the oscillations.) That is, the superposed states appear as time-sliced in a cyclic manner such that the time spent by an eigenstate in a cycle is related to the complex amplitudes (a, b) appearing in the qubit’s wave function, |ψ⟩= a|0⟩ + b|1⟩. The cycle time T_c of the qubit’s oscillation between states |0⟩  and |1⟩ is much smaller than the Planck time (<< 10^−43 sec). It is not necessary for us to know the value of  T_c. We only assert that it is a universal constant. Within a cycle, the time spent by the particle in state |0⟩ is T₀ = |a|² T_c and in state |1⟩ is T₁ = |b|² T_c so that T_c=  T₀+ T₁. See Fig. 2.

Fig. 2 A time multiplexed view of quantum superposition.

Measurement

Our hypothesized measurement mechanism acts instantaneously (through entanglement) but the instant of actual measurement occurs randomly over a small but finite interval Δt_m, which is much greater than Planck time (otherwise its actual value is immaterial), from the time the measurement apparatus is activated. In particular, we regard measurement as the joint product of the quantum system and the macroscopic classical measuring apparatus. To avoid bias, we assume that the device can choose any instant in the interval ∆t_m with equal probability.

(〉 ± 〉)/√2 (〉 ± 〉)/√2
Fig. 3. A time multiplexed view of quantum entanglement

Thus the source of indeterminism built into quantum mechanics is interpreted here as occurring due to the classical measuring device’s inability to measure at a precisely predefined time. We do not explain how the collapse of the wave function occurs when a measurement is made, only why the measurement outcome is probabilistic. Once a measurement is made, the wave function assumes the collapsed state.

Entanglement

Entangled states binding two or more qubits appear in our interpretation as the synchronization of the sub-Planck level oscillation of the participating qubits, as shown in Fig. 3 for the two-qubit system Bell states, (〉 ± 〉)/√2 and (〉 ± 〉)/√2. A measurement on one of the entangled qubits will collapse both simultaneously to the respective state they are in at the instant of measurement (such as Ï„₁ or Ï„₂ in Fig. 3). We do not know how Nature might accomplish the required synchronization.

It is, of course, clear that our interpretation cannot violate Heisenberg’s uncertainty principle since the latest measurement on a system collapses the system according to the measurement postulate. Thus, there can be no direct correlation between any earlier results of measurement on the system, and the succeeding measurement. Unlike the Copenhagen interpretation, in our interpretation it is not meaningless to ask about the state of the system in the absence of a measuring system.

10 Quantum Supremacy

So far we have benefitted from a euphoric rise in classical computing speeds tracing Moore’s law in historical time using the von Neumann architecture and CMOS hardware. While Richard Feynman had enthusiastically talked about “There’s plenty of room at the bottomâ€Â¹⁷ well ahead of his time at the annual American Physical Society meeting at Caltech on December 29, 1959 it did not arouse much attention at the time, but was well noticed in the 1990s. Quantum computing is both beyond Von Neumann architecture and beyond CMOS hardware. It represents an out of the world of classical physics transformative technology in computing. At the moment, building a universal, fault tolerant quantum computer still appears to be a distant goal.¹⁸

In the last few years, a flurry of activity has taken place in approaching quantum supremacy. Google and IBM top the list of competing contenders. In November 2017, IBM announced its 50-qubit processor, an improvement over its earlier 20, 15, and 5 qubit ones, respectively, in 2017, 2017, 2016. They used superconducting qubits operating at cryogenic temperatures.¹⁹ “IBM has been exploring superconducting qubits since the mid-2000s, increasing coherence times and decreasing errors to enable multi-qubit devices in the early 2010s. Continued refinements and advances at every level of the system from the qubits to the compiler allowed us to put the first quantum computer in the cloud in 2016.â€Â²⁰ Every processor has fault tolerance considerations accounted for. By the end of 2023, IBM hopes to have a 1,000-plus qubit device, called IBM Quantum Condor in operation. Beyond that million-plus qubit processors. It is a part of an ambitious dream, “The future’s quantum computer will pick up the slack where classical computers falter, … to run revolutionary applications across industries, generating world-changing materials or transforming the way we do business.â€Â²¹ Building such computers provide some of the biggest challenges in the history of technological progress. Such quantum computers will provide an unimaginable quantum leap to human progress.

In October 2019, Google made a “quantum supremacyâ€Â²² claim in a paper published in Nature, in which they claimed:

Here we report the use of a processor with programmable superconducting qubits to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 2⁵³ (about 10¹⁶). … Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times—our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years. … A key systems engineering advance of this device is achieving high-fidelity single- and two-qubit operations, not just in isolation but also while performing a realistic computation with simultaneous gate operations on many qubits.²³ [Internal citations omitted.]

Google’s claim was immediately contested by IBM, in a blog post,²⁴ which claimed that an ideal simulation of the same task can be performed on a classical system in 2.5 days and with far greater fidelity, and not the 10,000 years as claimed by Google. They do have a point. As they point out:

The concept of “quantum supremacyâ€Â showcases the resources unique to quantum computers, such as direct access to entanglement and superposition. However, classical computers have resources of their own such as a hierarchy of memories and high-precision computations in hardware, various software assets, and a vast knowledge base of algorithms, and it is important to leverage all such capabilities when comparing quantum to classical. ²⁵

The winner of the “quantum supremacyâ€Â contest in a combative sense is yet to be decided! There are technological hurdles to be overcome and mysteries to be resolved. A new experiment, known as the TEQ collaboration²⁶ might throw some new light on our ignorance. “The overall objective of TEQ²⁷ is the identification of the fundamental limitations to the applicability of quantum mechanics towards the establishment of a novel paradigm for quantum-enhanced technology that makes use of large-scale devices.â€Â²⁸

References

Arute, et al (2019). Arute, F., et al. Quantum Supremacy Using a Programmable Superconducting Processor. Nature, 23 October 2019. https://www.nature.com/articles/s41586-019-1666-5 and https://www.nature.com/articles/s41586-019-1666-5.pdf

Bennett (1982). Bennett, C. H. The Thermodynamics of Computation – a Review, International Journal of Theoretical Physics, Vol. 21, No. 12, 1982, pp. 905-940. https://www.cc.gatech.edu/computing/nano/documents/Bennett%20-%20The%20Thermodynamics%20Of%20Computation.pdf

Bera (2018a). Bera, R. K. The Essence of Quantum Computing, Part I – Foundations. Advanced Computing & Communications, Vol. 02, Issue 01, March 2018, pp. 6-31. https://acc.digital/the-essence-of-quantum-computing/

Bera (2018b). Bera, R. K. The Essence of Quantum Computing, Part II – Algorithms. Advanced Computing & Communications, Vol. 02, Issue 02, June 2018, pp. 24-50. https://acc.digital/the-essence-of-quantum-computing-3/

Bera (2020). Bera, R. K. The Amazing World of Quantum Computing. Springer Nature, Singapore, March 2020, https://link.springer.com/book/10.1007/978-981-15-2471-4

Bera & Menon (2009). Bera, R.K., and Menon, V. A New Interpretation of Superposition, Entanglement, and Measurement in Quantum Mechanics. arXiv:0908.0957v1 [quant-ph], 07 August 2009. http://arxiv.org/abs/0908.0957.

Bera & Menon (2018). Bera, R. K., and Menon, V. The Essence of Quantum Computing, Part III – Measurement and Interpretation. Advanced Computing & Communications, Vol. 02, Issue 03, September 2018, pp. 20-32. https://acc.digital/the-essence-of-quantum-computing-part-3-of-3-part-series/

Berta (2010). Berta, M., et al, The Uncertainty Principle in the Presence of Quantum Memory. Nature Physics, Vol. 06, Issue 09, September 2010, pp. 659-662. https://www.nature.com/articles/nphys1734; https://www.nature.com/articles/nphys1734.pdf

Bohm (1951). Bohm, D. Quantum Theory. Prentice-Hall, 1951.

Born (1926). Born, M. Zur Quantenmechanik der Stoßvorgänge. [On the Quantum Mechanics of Collisions]. Zeitschrift für Physik, Vol. 37, No. 12, 1926, pp.863-867. doi:10.1007/BF01397477.

Born (1954). Born, M. The Statistical Interpretation of Quantum Mechanics. Nobel Lecture, December 11, 1954. https://www.nobelprize.org/uploads/2018/06/born-lecture.pdf

Corliss (1997). Corliss, W. R. Science Frontiers #114, Nov-Dec 1997. http://www.science-frontiers.com/sf114/sf114p12.htm

European Commission (2020). Periodic Reporting for period 2 - TEQ (Testing the Large-Scale Limit of Quantum Mechanics). Reporting period: 2019-01-01 to 2020-06-30. Testing the Large-Scale Limit of Quantum Mechanics. Horizon 2020. European Commission, 2020. https://cordis.europa.eu/project/id/766900/reporting

Everett (1957). Everett, III, H. “Relative Stateâ€Â Formulation of Quantum Mechanics. Reviews of Modern Physics, Vol. 29, No. 03, July 1957, pp. 454-462. http://www.univer.omsk.su/omsk/Sci/Everett/paper1957.html

Feynman (1960). There’s Plenty of Room at the Bottom. Engineering and Science, February 1960, pp. 22-36. https://calteches.library.caltech.edu/1976/1/1960Bottom.pdf

Gambetta (2020). Gambetta, J. IBM’s Roadmap For Scaling Quantum Technology. IBM Research Blog, 15 September 2020. https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/

Li, et al (2011). Li, S-F., et al, Experimental Investigation of the Entanglement-assisted Entropic Uncertainty Principle. Nature Physics, Vol. 07, Issue 10, October 2011, pp. 752-756. https://www.nature.com/articles/nphys2047.pdf

Mermin (2004). Mermin, N. D. Could Feynman Have Said This? Physics Today, Vol. 57, No. 05, 01 May 2004, pp. 10–11. doi:10.1063/1.1768652

Moore (2017). Moore, S. K. IBM Edges Closer to Quantum Supremacy with 50-Qubit Processor. IEEE Spectrum, 15 November 2017. https://spectrum.ieee.org/tech-talk/computing/hardware/ibm-edges-closer-to-quantum-supremacy-with-50qubit-processor

Pati & Braunstein (2000). Pati, A. K., and Braunstein, S. L. Impossibility of Deleting an Unknown Quantum State. Nature, Vol. 404, 09 March 2000, pp. 164-5, http://www-users.cs.york.ac.uk/~schmuel/papers/pb00.pdf

Pednault, et al (2019). Pednault, E., et al. On “Quantum Supremacyâ€Â. IBM, 21 October 2019. https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/

Prevedel (2011). Prevedel, R., et al. Experimental Investigation of the Uncertainty Principle in the Presence of Quantum Memory and Its Application to Witnessing Entanglement. Nature Physics, Vol. 07, Issue 10, October 2011, pp. 757-761. https://www.nature.com/articles/nphys2048.pdf

Shinde & Markov (2009). Shinde, V. V., and Markov, I. L. On the CNOT-cost of TOFFOLI Gates. arXiv:0803.2316 [quant-ph], 15 March 2008. http://arxiv.org/abs/0803.2316; also as Quant. Inf. Comp. 9(5-6):461-486 (2009).

Skibba (2020). Skibba, R. A New Experiment Hopes to Solve Quantum Mechanics’ Biggest Mystery. Smithsonian Magazine, 05 February 2020. https://www.smithsonianmag.com/science-nature/new-experiment-hopes-solve-quantum-mechanics-biggest-mystery-180974132/

Villalonga (2020). Villalonga B., et al. Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation. arXiv:1905.00444v2 [quant-ph] 7 May 2020. https://arxiv.org/pdf/1905.00444.pdf

Wigner (1960). Wigner, E. P. The Unreasonable Effectiveness of Mathematics in the Natural Sciences. Communications in Pure and Applied Mathematics, Vol. 13, No. 1, February 1960. https://www.maths.ed.ac.uk/~v1ranick/papers/wigner.pdf

Wooters & Zurek (1982). Wootters, W. K., and Zurek, W. H. A Single Quantum Cannot be Cloned. Nature, Vol. 299, 28 October 1982, pp. 802-803. https://www.nature.com/articles/299802a0

---

1. See, e.g., Bera (2018a, b).↩ï¸Å½

2. Bera & Menon (2009). See also: Bera (2020), Chapter 12.↩ï¸Å½

3. Born (1926).↩ï¸Å½

4. Born (1954). Strongly recommended for reading.↩ï¸Å½

5. Bennett (1982).↩ï¸Å½

6. Quote taken from Corliss (1997).↩ï¸Å½

7. Wigner (1960).↩ï¸Å½

8. Berta (2010).↩ï¸Å½

9. Li, et al (2011), and Prevedel (2011).↩ï¸Å½

10. Wooters & Zurek (1982).↩ï¸Å½

11. Pati & Braunstein (2000).↩ï¸Å½

12. See, e.g., Shinde and Markov (2009).↩ï¸Å½

13. Mermin (2004).↩ï¸Å½

14. Bohm (1951).↩ï¸Å½

15. Everett (1957).↩ï¸Å½

16. Bera & Menon (2009); Bera & Menon (2018).↩ï¸Å½

17. Feynman (1960).↩ï¸Å½

18. Villalonga (2020).↩ï¸Å½

19. Moore (2017).↩ï¸Å½

20. Gambetta (2020).↩ï¸Å½

21. Gambetta (2020).↩ï¸Å½

22. The term “quantum supremacy,â€Â was proposed by John Preskill in 2012, and was meant to describe the point where quantum computers can do things that classical computers cannot. See Pednault, et al (2019).↩ï¸Å½

23. Arute, et al (2019).↩ï¸Å½

24. Pednault, et al (2019).↩ï¸Å½

25. Pednault, et al (2019).↩ï¸Å½

26. Skibba (2020).↩ï¸Å½

27. Project website http://tequantum.eu/↩ï¸Å½

28. European Commission (2020).↩ï¸Å½