Quantum Computing Part II - Building Blocks of Quantum Algorithms

edited by István Finta | szept 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.
In this second part the math behind the principles is reviewed and the circuit model is introduced.

Quantum theory is a revolutionary advancement in physics and chemistry that emerged in the early twentieth century. Moreover, it is an elegant mathematical theory, which is able to explain the counterintuitive behavior of subatomic particles.
In the late twentieth century it was discovered that quantum theory applies not only to atoms and molecules, but to bits and logic operations in a computer. This realization has brought about a revolution in the science and technology of information processing, making possible kinds of computing and communication up to now unknown in the Information Age.

The concept

Our classical computers perform calculations and process information using the classical model of computation, which dates back to Turing and von Neumann. In this model, all information is reducible to bits. A classical bit may be represented as a base-2 number that takes either the value 1 or the value 0. That is, at any point in its computation, a classical computer's state is entirely determined by the states of all its bits, so that a computer with n bits can exist in one of 2ⁿ possible states, ranging from 00...0 to 11...1.

Quantum bits are represented in a similar way in that they are also base-2 numbers, and they take on the value 1 or 0 when measured and thus collapsed to a classical state. Very much unlike classical bits, in its uncollapsed, quantum state, a quantum bit is in a superposition (linear combination) of (both) the measurable values 1 and 0. This on its own is no special thing, since a computer whose bits can be intermediate between 0 and 1 is just an analog computer, scarcely more powerful than an ordinary digital computer. However, a quantum computer takes advantage of a special kind of superposition that allows for exponentially many logical states at once, all the states from 00...0 to 11...1. This is a powerful feat, and no classical computer can achieve it.

But how? How could we build a quantum computer, with the help of which abstractions, based on the known physical phenomena?

Postulates of quantum mechanics

Each theory is based on several assumptions that cannot be verified theoretically, only experiments shore up that they are in consonance with the nature. In the case of quantum mechanics we have four assumptions called postulates which form a solid base for the theory. According to our state-of-the-art knowledge most of the rules in the universe can be traced back to these postulates.

First Postulate - state space: the actual state of any closed physical system can be described by means of a so-called state vector v having complex coefficients and unit length in a Hilbert space, i.e. a complex linear vector space (state space) equipped with an inner product.
Second Postulate - evolution: the evolution of any closed physical system in time can be characterized by means of unitary transforms depending only on the starting and finishing time of the evolution.
Third Postulate - measurement: any quantum measurement can be described by means of a set of measurement operators {Mm}, where m stands for the possible results of the measurement.
Fourth Postulate - composite systems: the state space of a composite physical system W can be determined using the tensor product of the individual systems W = V⊗Y . Furthermore having defined v ∈ V and y ∈ Y then the joint state of the composite system is w = v⊗y.

State space

Qubit definitions, conditions

In compliance with the first Postulate the simplest quantum system can be described by means of a two-dimensional complex valued vector in a two-dimensional Hilbert space. We call it a qubit and the reader may think of an electron or photon as physical implementations. Column vector ψ will be denoted by |ψ⟩ and pronounced as 'ket ψ' according to Dirac notation.

Quantum bit A qubit is the physical carrier of quantum information. It is the quantum version of a bit, and can be characterized with the followings:

the quantum bit, qubit, q-bit, qbit is a two level (two state) quantum system. CLOSED SYSTEM!
state of a qubit is: |ψ⟩ = α₀|0⟩ + α₁|1⟩
α₀, α₁ are called amplitudes; they are complex numbers
|0⟩ and |1⟩ are the qubit basis states
normalization condition: |α₀|² + |α₁|² = 1
alternative notation (vector notation)

| 0 ⟩ \equiv [\begin{matrix} 1 \\ 0 \end{matrix}]; | 1 ⟩ \equiv [\begin{matrix} 0 \\ 1 \end{matrix}];

α_{0} | 0 ⟩ + α_{1} | 1 ⟩ \equiv α_{0} [\begin{matrix} 0 \\ 1 \end{matrix}] + α_{1} [\begin{matrix} 1 \\ 0 \end{matrix}] \equiv [\begin{matrix} α_{0} \\ α_{1} \end{matrix}]

The previously mentioned points are the description of the qubit.
REMEMBER(!) that before the measurement the qubit has both logical values, i.e. it is in both computational basis states at the same time and the measurement allows the qubit to collapse into one of them. This completely differs from the classical approach which assumes that the coin is in one of the logical states before the measurement and the measurement only reveals this fact.
Computational basis states are orthogonal therefore from a practical point of view the computational basis vectors of a photon can be represented by horizontal and vertical polarization or for an electron, spin up and spin down can play these roles. However, a single qubit without control is worth nothing. Therefore in the following we will show how to formalize the state change on a qubit, the simplest quantum system.

State space

The Bloch sphere

The geometrical representation of a qubit is: the Bloch sphere.
All the possible linear combinations α₀|0⟩ + α₁|1⟩ in C² correspond to all the points (θ, φ) on the surface of the unit sphere, where α₀ = cos(θ/2) and α₁ = e^iφsin(θ/2).

| ψ ⟩ = α_{0} | 0 ⟩ + α_{1} | 1 ⟩

| ψ ⟩ = cos \frac{θ}{2} | 0 ⟩ + e^{i φ} sin \frac{θ}{2} | 1 ⟩

Several unitary transformations performed on a single qubit may be visualized as rotations and reflections about the x, y, and z axes of the Bloch sphere.

Evolution

Dynamics of quantum systems -> toward gates

The reader can see the original continuous-time form known as the Schrödinger equation where ħ denotes the reduced Planck's constant and H/ħ represents the so-called Hamiltonian, a Hermitian operator characterizing the evolution of the system.
Comparing H to U the former is time invariant. Therefore, in case of constant 'H' the solution of the differential equation can be given in a computationally more convenient way:

Quantum Computing - Circuit Model - Dynamics of quantum systems

That is, if some special conditions hold then the the second Postulate can be interpreted as

| ψ (t_{2}) ⟩ = U (t_{1}, t_{2}) | ψ (t_{1}) ⟩

where |ψ_1,2⟩ ∈ V.
The above definition describes the evolution between discrete time instants, which is more suitable in the context of quantum computing.
Here U is known as the time evolutional operator, which is unitary. It preservs the inner product between vectors in the Hilbert space. Formally

U U^{*} = U^{*} U = U U^{-1} = I,

where U is the unitary matrix, U^* is the conjugate transpose and I is the identity matrix.

Evolution

Quantum logic gates

The linear algebraic representation of a unitary operator U is a quadratic matrix which consists of elements U_i,j denoting the conditional probability amplitude connecting input orthonormal basis vector j with vector i.

U = [\begin{matrix} u_{11} & u_{12} & ... & ... & u_{1 n} \\ u_{21} & u_{22} & ... & ... & u_{2 n} \\ ... \\ ... \\ u_{n 1} & u_{n 2} & ... & ... & u_{n n} \end{matrix}]

With the help of U matrices we have just introduced the term of quantum logic gates or simply quantum gate or gate.
In classical computing, binary values, as stored in a register, pass through logic gates that, given a certain binary input, produce a certain binary output. Mathematically, classical logic gates are described using boolean algebra. Quantum logic gates act in a similar way, in that quantum logic gates applied to quantum registers map the quantum superposition to another, together allowing the evolution of the system to some desired final state.

Quantum logic gates are a convenient way in which to describe the evolution of a quantum state. The action of a gate is to transform an initial state |ψ₀⟩ to a final state |ψ₁⟩. This is simply a matrix-vector multiplication:

| ψ_{1} ⟩ = U | ψ_{0} ⟩

where U represents the quantum logic gate.

Evolution

Single-qubit gate exapmles

In accordance with the above mentioned a single-qubit gate mathematically is a 2x2 unitary matrix.

I gate: the simplest gate is the wire, or I gate denoted by I. It leaves intact the incoming qubit, eg.:

I = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}]

I | 0 ⟩ = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 1 \\ 0 \end{matrix}] = | 0 ⟩

Pauli-X gate denoted by X. It flips the 0 to a 1, or vice versa, eg.:

X = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}]

X | 0 ⟩ = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 0 \\ 1 \end{matrix}] = | 1 ⟩

Pauli-Y gate:

Y = [\begin{matrix} 0 & -i \\ i & 0 \end{matrix}]

Y | 0 ⟩ = [\begin{matrix} 0 & - i \\ i & 0 \end{matrix}] [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 0 \\ i \end{matrix}] = i | 0 ⟩

Pauli-Z gate:

Z = [\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}]

Z | 0 ⟩ = [\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}] [\begin{matrix} 1 \\ 0 \end{matrix}] = [\begin{matrix} 1 \\ 0 \end{matrix}] = - | 0 ⟩

Measurement

Readout of a qubit

The third postulate - measurement (readout) of a qubit - is about the collapse of the wave function according to the followings:

|ψ⟩ = α₀|0⟩ + α₁|1⟩
the probability of a measuring 0 is P₀ = |α₀|²
the probability of a measuring 1 is P₁ = |α₁|²
if the outcome of the measurement is 0, then the state changes to |0⟩
if the outcome of the measurement is 1, then the state changes to |1⟩

Composite quantum systems

The tensor product

The tensor product, a way of combining vector spaces into larger vector spaces, is a very important operation in quantum computation. The tensor product between two vectors |u⟩ ⊗ |v⟩ is so common that it is usually simplified to |u⟩|v⟩ or |uv⟩, and a vector tensored with itself n times is denoted |v⟩^⊗n. Two column vectors |u⟩ and |v⟩ of lengths m and n yield a column vector of length m · n when tensored:

| U ⟩ \otimes | V ⟩ = [\begin{matrix} u_{1} \\ u_{2} \\ ... \\ ... \\ u_{m} \end{matrix}] \otimes [\begin{matrix} v_{1} \\ v_{2} \\ ... \\ ... \\ v_{n} \end{matrix}] = [\begin{matrix} u_{1} v_{1} \\ u_{1} v_{2} \\ ... \\ ... \\ u_{1} v_{n} \\ u_{2} v_{1} \\ u_{2} v_{2} \\ ... \\ ... \\ u_{2} v_{n} \\ u_{3} v_{1} \\ ... \\ ... \\ ... \\ u_{m} v_{n} \end{matrix}] =

| U ⟩ | V ⟩ = | U V ⟩

Tensor products are so ubiquitous because they are the mathematical abstraction that desribes the interaction between two quantum systems: the vector space describing one quantum system tensored with the vector space describing another is the vector space made up of linear combinations of all of the vectors in the two vector spaces.

Composite quantum systems

Quantum registers

Like classical computers, quantum computers use quantum registers made up of multiple qubits. That is a quantum register is the abstraction of composite vector spaces. When collapsed, quantum registers are bit strings whose length determines the amount of information they can store. In superposition, each qubit in the register is in a superposition of |1⟩ and |0⟩, and consequently a register of n qubits is in a superposition of all 2 n possible bit strings that could be represented using n bits. The state space of a size-n quantum register is a linear combination of n basis vectors, each of length 2ⁿ:

| ψ_{n} ⟩ = \overset{2^{n} - 1}{\sum_{i = 0}} a_{i} | i ⟩

Here |i⟩ is the base-10 integer representation of a length-n number in base-2.
Additionally, according to the normalization condition:

\overset{2^{n} - 1}{\sum_{i = 0}} {| a_{i} |}^{2} = 1

A three-qubit register would thus have the above expansion:

| ψ_{2} ⟩ = a_{0} | 000 ⟩ + a_{1} | 001 ⟩ + a_{2} | 010 ⟩ + a_{3} | 011 ⟩ +

a_{4} | 100 ⟩ + a_{5} | 101 ⟩ + a_{6} | 110 ⟩ + a_{7} | 111 ⟩

In vector form

| ψ_{2} ⟩ = a_{0} [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] + a_{1} [\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] + a_{2} [\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] +

a_{3} [\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] + a_{4} [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}] + a_{5} [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}] + a_{6} [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{matrix}] +

a_{7} [\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{matrix}]

Quantum entanglement

The Bell state

In the followings we will check a very simple quantum circuit. As I mentioned before the common application of the CNOT gate is to maximally entangle two qubits into the Bell state; this forms part of the setup of the superdense coding, quantum teleportation, and entangled quantum cryptography algorithms.
Let's see the circuit.

Quantum Computing - Circuit Model - Bell State

The simplest case takes a computational basis as the input, and contains a Hadamard gate and a CNOT gate. As an example, the pictured quantum circuit takes the two qubit input and transforms it to the first Bell state. Explicitly, the Hadamard gate transforms into a superposition of. This will then act as a control input to the CNOT gate, which only inverts the target (the second qubit) when the control (the first qubit) is 1. Thus, the CNOT gate transforms the second qubit as follows.

| ψ_{0} ⟩ = | 0 ⟩ \otimes | 0 ⟩ = | 00 ⟩

= [\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \end{matrix}]

| ψ_{1} ⟩ =

H \otimes | 00 ⟩ =

H \otimes | 0 ⟩ | 0 ⟩ =

\frac{| 0 ⟩ + | 1 ⟩}{\sqrt{2}} | 0 ⟩ =

\frac{| 00 ⟩ + | 10 ⟩}{\sqrt{2}} =

\frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ 0 \\ 1 \\ 0 \end{matrix}]

| ψ_{2} ⟩ = CNOT | ψ_{1} ⟩ = CNOT \frac{| 00 ⟩ + | 10 ⟩}{\sqrt{2}} =

\frac{| 00 ⟩ + | 11 ⟩}{\sqrt{2}} =

\frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}]

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

Quantum Computing Part II - Building Blocks of Quantum Algorithms

The concept

Postulates of quantum mechanics

State space

Qubit definitions, conditions

State space

The Bloch sphere

Evolution

Dynamics of quantum systems -> toward gates

Evolution

Quantum logic gates

Evolution

Single-qubit gate exapmles

Measurement

Readout of a qubit

Composite quantum systems

The tensor product

Composite quantum systems

Quantum registers

Quantum entanglement

The Bell state

Related posts

Related references, links