Introduction to Quantum Computing

Third Edition
Quantum Algorithm Example (Grover)
Dr. I.V. Grossu
Linear Algebra Basics
Abstract
Complex Numbers Quantum Entanglement
In this work I tried to create an intuitive introduction to the fascinating domain of
Matrices Partial Measurement
Quantum Computing. Following this purpose, the first two chapters are conceived as
Vector Spaces an overview of the minimum Mathematics and Physics necessary notions, while the Measurement in Computational Basis
third chapter is dedicated to the main Quantum Computing concepts: Qubit,
Quantum Register, Quantum Algorithm, Measurement, and Partial Measurement. Quantum Algorithm
Quantum entanglement is also discussed together with an intuitive analogy, and a
Quantum Mechanics Basics concrete implementation on IBM Q Experience. In this context, I considered also a
Register

de Broglie Wavelength possible compromise between Bohr’s and Einstein’s interpretations. The fourth Qubit
chapter is discussing Grover's algorithm in contrast with classical sequential search.
Wave Function Concept Quantum Computing Basics
Bohr Atomic Model
Electron Spin Electron Spin
Bohr Atomic Model

Quantum Computing Basics Wave Function Concept

Qubit de Broglie Wavelength

Register Quantum Mechanics Basics

Quantum Algorithm
Measurement in Computational Basis Vector Spaces

Partial Measurement Matrices

Quantum Entanglement Complex Numbers

Linear Algebra Basics
Particle collisions are an “eye” to quantum world.
Quantum Algorithm Example (Grover)
Linear Algebra Basics
 Complex Numbers
REFERENCES FOR THIS CHAPTER [1]

z = (x, y); x, y in R
z1 + z2 = (x1, y1) + (x2, y2) = (x1 + x2, y1 + y2)
z1* z2 = (x1x2 – y1y2, x1y2 + x2y1)
C – the set of complex numbers

(0, 1) * (0, 1) = (-1, 0) => (0, 1) = SQRT(-1) = i

(x, y) = (x, 0) + (0, y) = x(1, 0) + y(0, 1) = x + yi
|z| = SQRT(x2+y2) – Pythagoras

i is not an (i)nvention  but a pair of real numbers

with specific operations defined
 Complex Numbers

•   = x – yi -> the complex conjugate of z

z*
z z* = (x + yi)(x - yi)
= xx – xyi + yxi –yyii
= x2 + y2 = |z|2

Euler’s Formula

= - easy to prove (trigonometry)

 Matrices
Matrix Product
 
 Matrices
Examples:
 
 Matrices
Examples
 

AT => transposed of A => aij = aTji

- transpose-conjugate matrix:
 Matrices
Kronecker Product

 
 Vectors in Physics
Quantities with both magnitude and direction (x, y, z)

Examples: velocity, force, position

Multiplication with a scalar:

scalar * (x1, y1) = (scalar * x1, scalar * y1)

Sum (parallelogram’s rule):

v1 + v2 = (x1, y1) + (x2, y2) = (x1 + x2, y1 + y2)
 Vectors in Physics
 Scalar Product:
v1 . v2 = x1x2 + y1y2 = |v1||v2|cos(v1v2)

v1 . v2 = 0 => v1 perpendicular on v2
Example: The work of a force

Vector product:

e.g. angular momentum

In 3D:
|v| = Sqrt(x2 + y2 + z2) => Pythagoras

N-Dimensions generalization:
 Linear Algebra
Vector Spaces
A Vector Space V over a field of complex numbers C is a non-empty set of elements on which two
operations (functions) are defined (a generalization of Vectors):

Multiplication with a vector by a scalar in C

associativity
neutral element 1
distributivity

Addition
associative
commutative
neutral element: 0 vector
for each v in V exists -1 v => the inverse element

=> A space with linear combinations

 Linear Algebra
Vector Spaces
The definition is so general that one could choose a set of
fruits and explicitly defined operations, as long the
A B A+B
required properties are satisfied.

Addition
associative
commutative
neutral element: 0 vector
for each v in V exists -1 v => the inverse element
 Linear Algebra
Hilbert Spaces
A Vector Space with an: Inner Product (.,.) : V X V -> C
 

linear in second argument

(v1, v2)=(v2, v1)*

(v, v) >= 0, equality only for v = 0
in general, not linear in first argument
=> A space with linear combinations (vector space) + distance &
orthogonality
 Vector Spaces in Cn
Cn Physics

•  • 

dual vector; bra

; bracket

Pythagoras
 Vector Spaces in Cn
Cn Physics

•   

Orthonormal Basis:

|i>

Canonical Computational Basis in Cn

(orthonormal)
Quantum Mechanics Basics
 Waves
• 
REFERENCES FOR THIS CHAPTER [1-3]

• Harmonic oscillator:

F = k y, y = A sin(ωt)
Ae i ωt phasor (write more compact expressions)
E = 0.5 k A2 ~ A2

• Wave –> propagation of a perturbation => at distance x,

the same oscillation with a delay x/c:

ν = 1/T; c = λ/T = ν; ω = /T = ν

Euler’s Formula
 Waves
Huygens Principle
In 1678 Huygens proposed a model where each point on a wave front may be
regarded as a source of waves expanding from that point.
 de Broglie Wavelength

Considering a wall with 2 slits

Electron (particle?) => classical (e.g. tennis balls) expected result
 de Broglie Wavelength

Experimental result (e.g. Davisson-Germer) => Electron’s diffraction!

 Wave Function Concept
•• Diffraction
  is present even for very low intensities (one particle at a time => the electron “interferes with itself”)
• Where did the electron pass through?... Both slits!
• This, difficult to understand, non classical behavior is available as long as the system is isolated.
• The measurement process affects the system (“wave function collapse”)
=> only one state can be found by measuring => The main limitation in Quantum Computing!
• One interpretation: “the wave function is all that one could know about the particle. It is a truth that we should
not try to explain by other concepts.”
• Another interpretation: there are “hidden variables” inaccessible in present.

de Broglie wavelength, E = hν, h = 6.626 x 10-34 m2Kg/s – Planck’s constant

wave function example

-> probability density

-> normalization
 Bohr Atomic Model
•• Hydrogen
  spectra is discrete
• Bohr atomic model: only the states corresponding to stationary waves
are allowed => angular momentum quantification

https://www.facebook.com/hossamibrahemm/posts/2021133031242089
 Electron Spin
• Not only the angular momentum is quantified, but also its
projection in a magnetic (Zeeman Effect) or electric field
(Stark Effect)
• The elecron has an intrinsic magnetic momentum [3]
(intuitively related to an intrinsic angular momentum, spin),
with only 2 possible projections.
• An isolated electron is a superposition of both states (no
classical equivalent). Quantification of electron spin projections
Quantum Computing Basics
 QUBIT - Analogy
•REFERENCES
  FOR THIS CHAPTER [1,4-8]

• Consider a semaphore which randomly switches from red to green and back in
such a way that the probabilities of finding it (e.g. by taking a picture) in one
specific color are: r (for red), and g (for green). Obviously:
r+g=1
• Supposing the semaphore switches enough fast from one color to another, one
could approximate it is both red and green in the same time (e.g. the eye will
perceive both lights are on, but with different intensities) .
• Another example: at each moment of time, tossing an unusual, unfair coin (with
unequal probabilities associated to its sides).
 QUBIT
• 
• State-Space Postulate: An isolated physical system has an associated Hilbert space, called the state space. The state of the
system is fully described by a unit vector, called the state vector in that Hilbert space.
• QUBIT: A unit vector in C2 (e.g. electron’s spin)
• Canonical base in C2:

ORTHONORMAL BASIS

• Any two-level quantum-mechanical system (e.g. Josephson Junction) could be used as a qubit. Three-level => qutrit.
• Intuitive image: superposition of “opposite movements”, without classical equivalent.
• The supperposition applies to one single particle, not to a statistic set.
• The superposition applies only to isolated systems.
• The postulate does not give details on how to construct the corresponding Hilbert space.
• By measuring the qubit we’ll find a single value with the corresponding probabilities: |α|2, |β|2 (see next chapters).
 QUBIT
•• It  is important to notice that ψ is a wave function.
• Thus, α and β could be separated also by a phase difference
• A qubit is described not only by a combination of 0 and 1, but also by a
phase factor

-> probability density

• Another way of writing ψ for a qubit (taking into account the phase factor):

• Why θ/2 ? It is more convenient to represent on a sphere (Bloch sphere)

=> θ = 90 for equal probabilities
 Quantum Register - Analogy
• In
  the frame of the same “semaphores
analogy”, one could consider two  
independent semaphores, randomly
switching, enough fast, from red to green
and back, with the corresponding
probabilities:
(r1, g1), and (r2, g2)
• Another example: at each moment of time,
tossing two unfair, independent coins.
• The probabilities of compound states could
be obtained by multiplication of individual
probabilities:
r1 * r2, r1 * g2, g1 * r2, g1 * g2
  =()()=1
• One could also use Kronecker product:
 Quantum Register

• Composite Systems Postulate: The state  

space of a composite system is the tensor
product of the state space of the
components.

• => the composite space canonical base is

obtained by Kronecker multiplication of
component spaces canonical bases.

• This postulate gives the “recipe” for

constructing the Hilbert space of a composite
system.

• Register: Set of qubits treated as a

composite system (e.g. 2 QUBITS => C4)
 Unitary Operators
•Linear
  Operator: function Aop:V->W (V, W - vector spaces)

This is equivalent with considering a corresponding matrix A:

Aop(|v>) = A |v> (matrix multiplication)

Adjoint operator: => (transpose-conjugate matrix)

Unitary Operator U: U+U = UU+ = I =>

Unitary operators are preserving the norm
 Unitary Operators

• 50 qubits => 250 states

• It should be a big number… how big?
• Folding a piece of paper 50 times you’ll get almost the distance to Sun!
• assuming the paper thickness is 0.1mm, one gets 112,589,990 Km
• The exponential is also behind the power of nuclear reactors
• The probability of each of this big number of states are changing in a single step
when applying an unitary operator
 Quantum Algorithm
• 
Evolution Postulate: The time evolution of an isolated quantum system is described by a unitary
transformation.

• Quantum algorithm: a prescription of a sequence of unitary operators applied to an initial

state:

• A quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a
small number of qubits.
• Unlike many classical logic gates, quantum logic gates are reversible (unitary operators).
• In ”semaphores analogy”, an unitary operator is a device capable of changing the red/green
probability distribution.

Unitary Operator Examples:

Pauli Matrices:
 Unitary Operator Examples
• 

swaps two qubits =>

 Hermitian Operators
•Adjoint
  operator: => (transpose-conjugate matrix)

Hermitian (self-adjoint) operator: O+=O

• A Hermitian operator is diagonalizable => there exists an orthonormal basis vi of V

such that:

- eigenvalues, |vi> - eigenvectors

• The eigenvalues of a Hermitian operator are real numbers

• A real symmetric matrix is Hermitian
 Measurement
• 
Measurement Postulate: A projective measurement is described by a Hermitian operator O,
called observable in the state space of the system being measured. The observable O has a
diagonal representation:

• Pλ takes into account the fact that the same eigenvalue λ could correspond to many eigenvectors.
• The measurement process is irreversible.
• The possible results of measurement of the observable O are the eigenvalues λ.
• The probability of obtaining the result λ is:

• In “semaphores analogy”, measurement is associated with a device capable of stopping systems’

oscillations, which results in “freezing” the semaphores into one compound state.
 Measurement in Computational Basis
• 

The measurement result is an integer value 0 <= k <= 2n-1

The probability of obtaining the value k is:
 Partial Measurement
• 
Measure only some qubits => for 2 subsystems: A, B => measuring the observable:
For m qubits and n qubits one could write:

Measuring the m qubits, the probability to obtain the result k is:

If the result is k, the state immediately after is:

Partially measurement results in affecting the remaining qubits.

 Partial Measurement
• 
Example 1:

Measuring the first qubit => p0 = 2/3, p1 = 1/3

If the result is 0, the state immediately after is (the state of the second qubit is a superposition):

Example 2:

If the result is 0, respectively 1, the states immediately after measurements are:

Measuring one qubit is instantaneously (?) affecting the other qubit too.
 Application
A simple random number generator implemented on IBM Q Experience: https://quantum-computing.ibm.com/
 Quantum Entanglement
 2-qubit register => C4
Consider the following unit vector:

Which is the state of each qubit in this case?

(Kronecker product)

But, the corresponding system of equations has no solution!

The quantum state of the composite system as a whole, but we cannot attribute the state of the parts.
A single qubit can be in a superposed state, but it cannot be entangled, as its state is not composed of subsystems.
 Quantum Entanglement - Analogy
• In semaphores analogy, one could consider two synchronized semaphores with: r1 = g1 = 0.5, and r2 =
g2 = 0.5
• As the two semaphores are not independent, it is not possible any more to obtain the compound
states probabilities by multiplying individual probabilities (Kronecker product).
• Another example: at each moment of time, tossing two tied coins.
• As result of existing bindings, stopping one semaphore results in “freezing” the other one in the same
light. What looks quite strange in quantum mechanics is that this should happen instantaneously, as if
the measurement effect is “propagating” with an infinity velocity. This was one of the famous Bohr-
Einstein debate subjects. I would suggest also that Bohr’s interpretation might be applicable with a
space/time limitation (compromise between the two points of view). Thus, after an enough long time,
the system might equally probable “fall” (the “constraint thread” breaks) into only one of its
compound states (either both semaphores red, or both green).
 Quantum Entanglement – IBM Q Experience
 Implementation on IBM Q Experience: https://quantum-computing.ibm.com/
1. Hadamard: applied on first qubit: q[0] =>
2. Conditional not: applied on qubits q[0], q[1] (change the second qubit only when the first one is 1) => Bell state
3. Partial measurement: the results are stored in the classical register c[0], c[1]
4. The deviation from the expected result could be considered a quantum computer precision test
5. Similarly, one can consider
Quantum Algorithm Example
 Quantum Algorithm Example
• 
REFERENCES FOR THIS CHAPTER [1,5,6]

Search algorithm :

f is an unknown function (e.g. provided by a developer in a dll):

Classical sequential search O(N):

for x = 0 to N-1
if f(x) = 1 then
print x
stop
end if
end for
 Quantum Algorithm Example
• 
Grover’s algorithm [1,5-6] :

• Initialize the register to the diagonal state:

|i>,

• Apply U=RDRf for t times, where :

Rf -> we are provided with access to a black-box subroutine:

RD -> Grover’s diffusion operator:

• Measure the register in computational basis. The result is x0, with probability
 Quantum Algorithm Example
•   points for understanding Grover’s algorithm:
ey

• One solution for overcoming the probabilistic nature of quantum computing could be to check the result validity (if this does not involve
significant costs). For instance, it is easy to check a value is satisfying a polynomial equation.
• Another solution is to run the program multiple times and apply statistics.
• For a concrete implementation on IBM’s 5-qubit computer [7,8], consult reference [5]
• Rf is, in fact:

• The action of RD to an arbitrary state results in flipping the amplitude of each state about the mean amplitude

• Rf => the amplitude of |x0> becomes below <a>, while all other states above <a>.
• RD => the amplitude of |x0> becomes above the mean, while all other states below
• Applying U repeatedly will increase the amplitude of |x0>
 Quantum Algorithm Example
 
// C# .Net Simulation
public static void Test()
{
var register = Grover(3, 5);
}

// Grover's Algorithm Test

public static Matrix Grover(int qubits, int x0)
{
var n = (int)Math.Pow(2, qubits);
var oracle =
MatrixFactory.NewGroverOracleMatrix(n, x0);
var grover = 0.0064 * 7 + 0.9409 ≈ 1 (rounding issues)
MatrixFactory.NewGroverDiffusionMatrix(n);
var register =
MatrixFactory.NewDiagonalState(n);
var steps = (int)((Math.PI / 4.0) *
Math.Sqrt(n));
for(int step = 1; step <= steps; step++)
{
register = oracle * register;
register = grover * register;
}
return register;
}
References
1. R. Portugal, Quantum Walks and Search Algorithms, Quantum Science and
Technology, Springer, New York 2013, DOI 10.1007/978-1-4614-6336-8
2. Cursul de fizica Berkeley, vol. IV, Cuantica, Editura Didactica si Pedagogica, 1983
3. Florin Popescu, Florin Marica, Fizica Atomica – Note de curs, Universitatea din
Bucuresti, 1998
4. https://quantummechanics.ucsd.edu/ph130a/130_notes/node68.html
5. Patrick J. Coles et. al., Quantum Algorithm Implementations for Beginners,
https://arxiv.org/pdf/1804.03719.pdf
6. https://en.wikipedia.org/wiki/Grover%27s_algorithm
7. https://www.research.ibm.com/ibm-q/
8. https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=beginners-guide&pag
e=introduction