Towards Quantum Computational Mechanics
Burigede Liu
a,
∗
, Michael Ortiz
b
, Fehmi Cirak
a
a
Department of Engineering, University of Cambridge, Cambridge, CB2 1PZ, UK
b
Division of Engineering and Applied Science, California Institute of Technology, Pasadena, CA 91125, USA
Abstract
The rapid advancements in quantum computing as ushered in a new era for computer simulations, presenting ground-
breaking opportunities across diverse disciplines. Central to this revolution is the quantum processor’s capacity to
entangle qubits, unlocking unprecedented possibilities for addressing computational challenges on an extreme scale,
far beyond the reach of classical computing. In this study, we explore how quantum computing can be employed to
enhance computational mechanics. Our focus is on the analysis of Representative Volume Element (RVE) within the
framework of multiscale solid mechanics. We introduce an innovative quantum algorithm designed to solve the RVE
problem. This algorithm is capable of compute RVEs of discretization size
N
in
O
(Poly log(
N
)) time, thus achieving
an exponential speed-up over traditional classical computing approaches that typically scales linearly with
N
. We
validate our approach with case studies including the solution of one and two dimensional Poisson’s equation, as well
as an RVE of a composite bar with piece-wise constant phases. We provide quantum circuit designs that requires only
O
(Poly log(
N
)) universal quantum gates,underscoring the e
ffi
ciency of our approach. Our work suggests a major way
in which quantum computing can be combined with and brought to bear on computational mechanics.
Keywords:
Quantum computing, multiscale analysis, quantum Fourier transform
Contents
1 Introduction
2
2 Computational homogenisation
4
2.1
Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Periodic solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Fourier discretisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3 Essentials of quantum computing
7
3.1
Notation and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.2
Quantum systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.2.1
One-qubit systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.2.2
Multi-qubit systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.3
Quantum gates and circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3.1
One-qubit gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3.2
Multi-qubit gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.3.3
Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.4
Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.5
Quantum algorithm complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
∗
Corresponding author
Email addresses:
bl377@cam.ac.uk
(Burigede Liu),
ortiz@aero.caltech.edu
(Michael Ortiz),
fc286@cam.ac.uk
(Fehmi Cirak)
Preprint submitted to Elsevier
December 8, 2023
arXiv:2312.03791v1 [quant-ph] 6 Dec 2023
4 Quantum computing algorithms
14
4.1
Multi-controlled operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.2
Encoding of polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.3
State preparation via function encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4.4
Encoding of arbitrary functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.5
Quantum Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.6
Base swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
5 Quantum computational homogenisation
22
5.1
Periodic Poisson problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.1.1
One-dimensional case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.1.2
Two-dimensional case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
5.2
Solution of the unit cell problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.2.1
Incremental problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.2.2
Fixed-point iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
6 Conclusions
32
Appendix A
Kronecker Product
34
Appendix B
State preparation
34
Appendix C
Complexity of the polynomial encoding algorithm
35
1. Introduction
The phenomenal advances in computational mechanics from its early beginnings in the late 1950s to today follow
the exponential increase in computing power over the same period of time [23, 37]. This progress is most evident from
the increase of finite element problem sizes from less than hundreds (
<
10
2
) to hundreds billions (
>
10
11
) of elements
over the same time period [12, 26]. As widely known, Moore’s law stipulates a two-fold increase in the density of
transistors on a circuit every two years. The consensus is that future improvements in computing power will be limited
because of the physical limitations in shrinking logic gate sizes further. A naive scaling up of current computing
technologies without an increase is transistor densities is believed as highly problematic because of excessive cost
and energy consumption. Using quantum systems to perform computations provides one possible solution to this
impasse. Quantum computers were envisaged in early 1980s by Feynman [19], Benio
ff
[5] and Manin [28]. Feynman
was motivated by the impossibility of simulating a reasonably sized
quantum system
with classical computers. For
instance, the state of a quantum system consisting of
n
p
particles contained in a box in
R
3
is described by a complex-
valued
wave function
ψ
(
x
) :
R
3
n
p
7→
C
. The discretisation of this configuration space with only ten cells in each
dimension leads to a discretised system with 10
3
n
p
degrees of freedom, rendering the problem unsolvable beyond a
few particles.
Feynman argued to e
ffi
ciently simulate quantum systems, one needs non-classical computers that must use phe-
nomena unique to quantum mechanics. The same argument was put forward by Manin in his book in Russian;
see [34]. In contrast to both, Benio
ff
was concerned with energy dissipation in classical computers resulting from the
irreversibility of the elementary operations. For instance, in a classical computer an AND gate has two binary inputs
and one binary output and is irreversible as it is impossible to deduce from the single output the respective inputs.
This irreversibility is associated with a loss of energy [6, 27]. Benio
ff
proposed an alternative quantum-based classi-
cal computer design in which every operation is encoded as the solution of the reversible time-dependent Schr
̈
odinger
equation governing quantum mechanics. The notion of a quantum computer, as envisaged by Feynman and Manin,
was finally formalised in the seminal work by Deutsch [16] a few years later. In the same work, Deutsch discussed
the advantages of a quantum computer in solving problems beyond the simulation of quantum systems, which led to
an initial flurry of quantum algorithms, like Grover’s algorithm of unstructured search [21] and Shor’s algorithm for
prime factorisation [39].
2
To develope an intuitive understanding of quantum computing, adopting a physical viewpoint of computing is
expedient. Briefly, computing is always tied to a physical representation, and a computer is a machine. As Deutsch
stated:
”a computing machine is any physical system whose dynamical evolution takes it from one of a set of ’input’
states to one of a set of ’output’ states”.
The input state of a quantum computer is chosen from the configuration
space of a quantum system. According to the postulates of quantum mechanics, the configuration of the system
with
n
quantum particles is described by a
state vector
|
q
⟩
, see [36].
1
The ket
|·⟩
merely indicates that q is a quantum
mechanical vector. Each particle is referred as a
qubit
and has two states. These two-states can be, for instance, the
up and down spin states of a spin 1
/
2 particle, ground and excited states of an atom, or the horizontal and vertical
polarisation of a photon [17]. Owing to
quantum entanglement
, the state vector of
n
qubits is the Hilbert space
C
2
n
,
i.e.
|
q
⟩ ∈
C
2
n
. Notice that this space is exponentially larger than the configuration space of
n
classical particles which
is only
C
2
n
, see [24]. The time evolution of the state vector
|
q
(
t
)
⟩
is governed by the Schr
̈
odinger equation and the state
vector
|
q
(
T
)
⟩
at time
t
=
T
is given by the unitary mapping
U
C
:
|
q
(0)
⟩7→|
q
(
T
)
⟩
. The evolution operator
U
C
∈
C
2
n
×
2
n
is unitary, i.e.
U
−
1
C
=
U
†
C
, i.e. length preserving and bijective. A
universal quantum computer
can implement any
such unitawhitry operator
U
C
. Hence, as a physical system a quantum computer performs computation by evolving a
chosen
|
q
(0)
⟩
to
|
q
(
T
)
⟩
using a prudently designed unitary
U
C
. Therefore, quantum computers are sometimes referred
as
analog machines
and their ability to simultaneously evolve the t state vector
|
q
(
t
)
⟩
as
quantum parallelism
.
We provided so far a simplified and abstract description of quantum computing which requires further elabora-
tion. In computational mechanics the initial state
|
q
(0)
⟩
may represent the forcing, the final state
|
q
(
T
)
⟩
the solution
and
U
C
the discretised inverse solution operator. A classical forcing vector
q
∈
C
N
, with
N
=
2
n
, is encoded
as the components, usually called
amplitudes
,
q
i
(0)
∈
C
of a state vector
|
q
(0)
⟩
=
P
i
q
i
(0)
|
i
⟩
of a system with
n
qubits. The basis vectors
|
i
⟩∈{|
0
⟩
,
|
1
⟩
,...
|
2
n
−
1
⟩}
provide a labelling of the 2
n
possible states of the quantum
system. This encoding is referred to as
state preparation
and, for instance, can be accomplished with the unitary
mapping
U
I
(
q
) :
|
0
...
0
⟩7→|
q
(0)
⟩
. Here,
|
0
...
0
⟩
is a known initial state and
U
I
(
q
) a unitary matrix. Algorithms for
state preparation can be found, e.g., in [3, 30, 38]. Subsequent application of the previously mentioned unitary
U
C
performs the desired computation. As widely studied, any unitary matrix can be constructed as the composition of a
few elementary unitary matrices [4, 15]. These elementary unitaries are of size 2
×
2 and 4
×
4 and are applied to a
single or two qubits as a time. In gate-based quantum computing the composition of the unitaries
U
I
and
U
C
from
elementary unitaries, also referred to as gates, are visualised in circuit diagrams. On a more practical level, a quantum
algorithm is implemented by designing the arrangement of the elementary gates in a quantum SDK, like Qiskit [13],
Cirq [11], PyQuil [40] and Pennylane [7]. See also the textbooks [1, 25, 35, 46] on known quantum algorithms and
their circuit implementations. The state vector
|
q
(
T
)
⟩
after the completion of the computation is interrogated by
mea-
surement
. According to the measurement postulate of quantum mechanics, the magnitude of the amplitude
|
q
i
|
2
is
equal to the probability to find the quantum system in the state labelled
|
i
⟩
, see [36]. After the state is
collapsed
into
the state
|
i
⟩
repeated measurements will yield the same result
|
i
⟩
. More specifically, we can only infer the statistics of
components of
|
q
(
T
)
⟩
or, more generally, the statistics of the projection of
|
q
(
T
)
⟩
to some subspace.
As detailed, quantum computing relies exclusively on unitary operations and measurement, so it is essential to
reassess existing computational mechanics approaches for their suitability and develop new methods. In this paper,
we consider the homogenisation of microstructured materials, like multi-phase composites consisting of materials
with di
ff
erent properties or polycrystalline materials. The characteristic length scale of the microstructure is much
smaller than the size of the macroscopic specimen to be analysed. Therefore, it is reasonable to derive the e
ff
ective
material properties, like di
ff
usivity or Young’s modulus, of the homogenised macroscopic boundary value problem
from micro-level boundary value problems, fully considering the microstructure. In computational homogenisation,
the micro- and macro-level boundary value problems are all suitably discretised and solved sequentially. The micro-
level domain is usually a rectangular prism called the representative volume element (RVE). The boundary conditions
for the RVE are chosen as periodic, and the prescribed average of the gradient of the solution, or strain gradient, is
given by the macroscale boundary value problem. We solve the periodic microscale problem by discretising all fields
using a band-limited Fourier interpolation, also known as Whittaker-Shannon interpolation, [10, 43]. In computational
homogenisation, this approach was first pioneered by Moulinec and Suquet [31]; see also the recent review paper [20].
The resulting discrete system of equations is classically solved using a fixed-point iteration and the Fast Fourier
1
The state vector
|
q
⟩
and wave function
ψ
(
x
) are equivalent representations of a quantum system. In quantum computing usually only state
vectors are used.
3
Transform (FFT). The FFT has the computational complexity
O
(
N
log
N
), where
N
is the number of degrees of
freedom. The corresponding quantum algorithm, the Quantum Fourier Transform (QFT), has remarkably the polylog
complexity
O
((log
N
)
2
), i.e. a polynomial of log
N
, see [14]. The solution of the RVE problem on a quantum computer
requires, beyond QFT and the already mentioned state preparation, the implementation of simple algebraic operations,
like the division by a scalar, in the Fourier space. To this end, we first approximate functions by piecewise polynomials
using Chebyshev interpolation and subsequently encode the polynomials utilising a sequence of elementary rotation
gates [41, 45]. Furthermore, we propose a quantum version of the fixed-point iteration to minimise the number of
costly measurement operations.
2. Computational homogenisation
We review the computational homogenisation of periodic composites with a scalar solution field governed by the
non-homogenous Poisson equation [29, 31, 32]. Such problems arise, for instance, in electrical and heat conduction,
flow in porous media or antiplane elasticity. In computational homogenisation the solution field is determined by
solving iteratively a sequence of macroscopic specimen level and microstructure level problems. The gradient of the
solution field of the specimen-level problem serves as the input to the microstructure-level problems. In turn, the
specimen level fluxes are obtained by averaging the microstructure level fluxes.
2.1. Problem formulation
The microstructure-level problem is given by the representative volume element (RVE). We refer to this problem
as an RVE even in the one and two-dimensional case as typical in the literature. We assume an RVE domain in the
shape of the square
□
=
(0
,
L
)
2
∈
R
2
with an edge length of
L
, and the coordinates of the points
x
∈
□
are denoted
by
x
=
(
x
0
x
1
)
T
. Note that the microstructure level problem is usually referred to as an RVE even in case of one and
two-dimensional problems. We consider, for the sake of concreteness, an antiplane elasticity problem and name our
variables accordingly. The shear modulus
μ
(
x
) in the RVE is periodic, i.e.,
μ
(
x
0
,
x
1
)
=
μ
(
x
0
+
L
,
x
1
)
=
μ
(
x
0
,
x
1
+
L
)
.
(1)
Furthermore, the RVE is subject to the uniform average strain vector
γ
∈
R
2
determined by solving the macroscopic
specimen level problem. The respective deformation of the RVE is characterised by a scalar transverse displacement
field
u
(
x
)
∈
R
with the shear strain vector
γ
(
x
)
=
∇
u
(
x
)
,
(2)
where
∇
denotes the gradient operator and
γ
(
x
)
∈
R
2
. The displacement field
u
(
x
)
∈
R
consists of an a
ffi
ne component
due to the applied
γ
and a fluctuating component
v
(
x
) so that
u
(
x
)
=
γ
·
x
+
v
(
x
)
,
(3)
which implies the strain decomposition
γ
(
x
)
=
γ
+
∇
v
(
x
)
.
(4)
The fluctuating displacement
v
(
x
)
∈
R
must satisfy the periodicity condition
v
(
x
0
,
x
1
)
=
v
(
x
0
+
L
,
x
1
)
=
v
(
x
0
,
x
1
+
L
)
.
(5)
The decomposition (4) and the periodicity condition (5) ensure that the applied
γ
is indeed the average strain
1
L
2
Z
L
0
Z
L
0
γ
d
x
0
d
x
1
=
1
L
2
Z
L
0
Z
L
0
γ
+
∇
v
(
x
)
d
x
0
d
x
1
=
γ
.
(6)
4
The stress field vector
σ
(
x
)
∈
R
2
of the micro-structure level satisfies the equilibrium equation
∇·
σ
(
x
)
=
0
,
(7)
and the constitutive equation
σ
(
x
)
=
μ
(
x
)
γ
(
x
)
=
μ
(
x
)
γ
+
∇
v
(
x
)
.
(8)
Hence, the boundary value problem for micro-structure can be summarised as
∇·
(
μ
(
x
)
∇
v
(
x
)
)
+
γ
·∇
μ
(
x
)
=
0
.
(9)
To ensure the periodicity of the displacement field
v
(
x
) the Dirichlet boundary conditions must be chosen such
tat
v
(
x
0
,
0)
=
v
(
x
0
,
L
) and
v
(0
,
x
1
)
=
v
(
L
,
x
1
).
It is not possible to solve the boundary value problem (11) using a Fourier-based approach because of the non-
constant
μ
(
x
). Therefore, we first introduce a constant reference shear modulus
μ
0
and rewrite the constitutive equation
as (8) as
σ
(
x
)
=
(
μ
(
x
)
−
μ
0
)
γ
(
x
)
+
μ
0
γ
(
x
)
=
τ
(
x
)
+
μ
0
γ
(
x
)
,
(10)
where
τ
(
x
) is referred to as the polarisation stress. Subsequently, we use the equilibrium (7) to define the fixed point
iteration
μ
0
∇·∇
v
(
s
+
1)
(
x
)
+
∇·
τ
(
s
)
(
x
)
=
0
.
(11)
The polarisation stress
τ
(
s
)
at iteration step
s
depends on the known displacement
v
(
s
)
and the applied strain
γ
.
2.2. Periodic solutions
In preparation for the Fourier discretisation of the incremental RVE problem, we consider a polarisation stress
vector consisting of a single wave with a period
L
, (spatial) frequency vector
ξ
=
(
ξ
0
ξ
1
)
T
with
ξ
0
=
ξ
1
=
2
π/
L
and
a complex amplitude
ˆ
τ
∈
C
2
, i.e.,
τ
(
x
)
=
ˆ
τ
(
ξ
)
e
i
ξ
·
x
,
(12)
where
i
2
=
−
1 and
ξ
·
x
=
ξ
0
x
0
+
ξ
1
x
1
. The corresponding solution will be a single wave with the same frequency
vector
ξ
but a yet unknown amplitude ˆ
v
(
ξ
)
∈
C
2
:
v
(
x
)
=
ˆ
v
(
ξ
)
e
i
ξ
·
x
.
(13)
Note that the components of
τ
(
x
) and
v
(
x
) can have di
ff
erent phases given that the amplitudes
ˆ
τ
and ˆ
v
(
ξ
) are complex
valued. Introducing the expressions (12) and (13) into (11), while ignoring the iteration counter
s
, yields the amplitude
of the solution,
−
μ
0
(
ξ
·
ξ
)ˆ
v
(
ξ
)
+
i
ξ
·
ˆ
τ
(
ξ
)
=
0
⇒
ˆ
v
(
ξ
)
=
1
μ
0
i
ξ
·
ˆ
τ
(
ξ
)
ξ
·
ξ
.
(14)
Therefore, the solution of the RVE problem is a wave given by
v
(
x
)
=
1
μ
0
i
ξ
·
ˆ
τ
(
ξ
)
ξ
·
ξ
e
i
ξ
·
x
.
(15)
Di
ff
erentiating the solution vector yields according to (2) the strain
γ
(
x
)
=
−
1
μ
0
ξ
ξ
·
ˆ
τ
(
ξ
)
ξ
·
ξ
e
i
ξ
·
x
=
ˆ
Γ
(
ξ
)
·
ˆ
τ
(
ξ
)
e
i
ξ
·
x
,
(16)
5
where
Γ
(
σ
)
∈
R
2
.
2.3. Fourier discretisation
We approximate on the bounded RVE domain
□
=
(0
,
L
)
2
⊂
R
2
periodic functions with band-limited interpola-
tion, also referred to as Whittaker-Shannon interpolation [43]. The band-limited interpolation of the solution field is
defined as
v
(
x
)
≈
v
h
(
x
)
=
1
N
N
−
1
X
k
0
=
0
N
−
1
X
k
1
=
0
ˆ
v
k
0
k
1
e
i
ξ
k
0
k
1
·
x
=
1
N
N
−
1
X
k
0
=
0
N
−
1
X
k
1
=
0
ˆ
v
k
e
i
ξ
k
·
x
,
(17)
with the multi-index
k
=
(
k
0
,
k
1
) and the frequency vector
ξ
k
=
(
ξ
0
,
k
0
ξ
1
,
k
1
)
T
; hence
ξ
k
·
x
=
ξ
0
,
k
0
x
0
+
ξ
1
,
k
1
x
1
. As
will be explained shortly, the multi-index
k
can be identified as grid point labels of the RVE domain discretisation.
The components of the frequency vector for a specific
k
are given by
ξ
0
,
k
0
=
2
π
r
(
k
0
)
L
, ξ
1
,
k
1
=
2
π
r
(
k
1
)
L
.
(18)
Here and elsewhere in the paper
N
≥
2 is an even integer.
N
is an integer because
v
(
x
) is required to be periodic. The
function
r
(
l
) is introduced to relabel the frequency components as
r
(
k
0
)
=
k
0
0
≤
k
0
<
N
/
2
k
0
−
N
N
/
2
≤
k
0
<
N
;
(19)
see also [43, Ch. 3] and [9, Ch. 2].
To determine the amplitudes ˆ
v
k
0
k
1
from the function values
v
(
x
), we introduce a discretisation consisting of
N
×
N
cells of size
h
×
h
, i.e.
h
=
L
/
N
, and the grid point coordinates
x
k
≡
x
k
0
k
1
=
L
N
k
0
k
1
!
=
h
k
0
k
1
!
,
k
0
=
0
, ...,
N
−
1
,
k
1
=
0
, ...,
N
−
1
.
(20)
We denote the function values at the grid points with
v
k
=
v
(
x
k
). According to (17), the function values at the grid
points are given by
v
h
k
0
k
1
=
1
N
N
−
1
X
j
0
=
0
N
−
1
X
j
1
=
0
ˆ
v
j
0
j
1
e
i
ξ
0
,
j
0
k
0
h
+
ξ
1
,
j
1
k
1
h
=
1
N
N
−
1
X
j
0
=
0
N
−
1
X
j
1
=
0
ˆ
v
j
0
j
1
e
i
2
π
N
(
r
(
j
0
)
k
0
+
r
(
j
1
)
k
1
)
.
(21)
It is easy to show that this equation represents the inverse DFT of ˆ
v
k
0
k
1
, i.e.,
v
h
k
0
k
1
=
1
N
N
−
1
X
j
0
=
0
N
−
1
X
j
1
=
0
ˆ
v
j
0
j
1
e
i
2
π
N
(
j
0
·
k
0
+
j
1
·
k
1
)
.
(22)
The inverse of this mapping, i.e. the DFT of
v
h
jk
, takes the form
ˆ
v
j
0
j
1
−
1
N
N
−
1
X
k
0
=
0
N
−
1
X
k
1
=
0
v
h
k
0
k
1
e
−
i
2
π
N
(
j
0
·
k
0
+
j
1
·
k
1
)
.
(23)
As will be detailed in Section 4.5, the DFT and its inverse can be very e
ffi
ciently computed on a quantum computer
using the QFT algorithm.
Clearly, all periodic fields appearing in the RVE problem (11) can be approximated using band-limited inter-
polation. The band-limited approximation of a periodic field consists of a linear combination, or superposition, of
waves with
N
2
di
ff
erent frequencies. The RVE solution for each wave component is the same as the single-wave
6
Algorithm 1
Fourier-based iterative solution of the RVE problem on
□
=
(0
,
L
)
2
⊂
R
2
.
Initialization:
γ
(
s
=
0)
k
≡
γ
(
s
=
0)
k
0
k
1
=
̄
γ
σ
(
s
=
0)
k
≡
σ
(
s
=
0)
k
0
k
1
=
μ
(
x
k
)
γ
(0)
k
∀
x
k
≡
x
k
0
k
1
∈
□
Iteration:
γ
(
s
)
k
and
σ
(
s
)
k
at every grid point
k
=
(
k
0
,
k
1
) are
x
k
known
(a)
τ
(
s
)
k
=
σ
(
s
)
k
−
μ
0
γ
(
s
)
k
=
μ
(
x
k
)
−
μ
0
γ
(
s
)
k
(b)
ˆ
τ
(
s
)
j
=
DFT(
τ
(
s
)
k
)
(c)
Convergence test
(d)
ˆ
γ
(
s
+
1)
j
=
−
ˆ
Γ
j
·
ˆ
τ
(
s
)
j
if
j
0
,
N
/
2 and
j
1
,
N
/
2
√
N
̄
γ
if
j
0
=
j
1
=
N
/
2
(e)
γ
(
s
+
1)
k
=
DFT
−
1
ˆ
γ
(
s
+
1)
j
(f)
σ
(
s
+
1)
k
=
μ
(
x
k
)
γ
(
s
+
1)
k
(g)
s
←
s
+
1
solution (24) derived in the previous section. The entire solution is obtained as the superpositon of the solutions of
the
N
2
frequencies, i.e.,
v
h
(
x
)
=
1
μ
0
N
−
1
X
k
0
=
0
N
−
1
X
k
1
=
0
i
ξ
k
·
ˆ
τ
k
ξ
k
·
ξ
k
e
i
ξ
k
·
x
.
(24)
Finally, the sketched solution approach can be used for solving the homogenisation boundary value problem prob-
lem (11) with a non-homogenous shear modulus as detailed in Algorithm 1.
3. Essentials of quantum computing
In this Section we provide a summary of the foundations of the quantum information processing covering aspects
of quantum mechanics and computing. For a more comprehensive review we refer to textbooks [1, 25, 35, 46] and
tutorial paper [2].
3.1. Notation and definitions
We use in this paper both the Dirac notation from quantum mechanics, also known as bra-ket notation, and the
matrix notation familiar from linear algebra. As can be glanced from Table 1 the two notations widely mirror each
other.
3.2. Quantum systems
In quantum computing data is encoded via the state of a quantum system consisting of one or more qubits, i.e.
quantum particles, with two di
ff
erent distinct states. In physical terms, the two states of a qubit can be realised, e.g.,
as the polarisation of a photon or two energy levels of an electron. In contrast, the two states of a classical particle,
like a coin, are its head and tail states.
3.2.1. One-qubit systems
The state
|
q
⟩∈
C
2
of a single qubit is expressed as the
superposition
, or linear combination, of two states abstractly
labelled as
{|
0
⟩
,
|
1
⟩}
in Dirac notation or
{
e
0
=
(1 0)
T
,
e
1
=
(0 1)
T
}
in matrix notation, i.e.,
|
q
⟩
=
q
0
|
0
⟩
+
q
1
|
1
⟩
=
q
0
1
0
!
+
q
1
0
1
!
=
q
0
q
1
!
,
(25)
7
Matrix notation
Dirac notation
Examples
/
Notes
Scalar
z
∈
C
z
∈
C
Complex conjugate of
z
z
∗
∈
C
z
∗
∈
C
(1
+
i
)
∗
=
(1
−
i
)
Modulus of
z
|
z
|∈
R
|
z
|∈
R
|
z
|
=
√
z
∗
z
=
√
zz
∗
Vector (or, a ket)
q
∈
C
N
|
q
⟩∈
C
N
Components:
q
j
j
=
{
0
,
1
,
N
−
1
}
Dual vector (or, the bra) of
q
q
†
∈
C
N
⟨
q
|∈
C
N
q
†
=
(
q
T
)
∗
Inner product between
q
and
r
q
·
r
⟨
q
|
r
⟩
q
·
r
=
q
†
r
Kronecker product
q
⊗
r
∈
C
N
×
N
|
q
⟩⊗|
r
⟩∈
C
N
×
N
|
q
⟩⊗|
r
⟩≡|
q
⟩|
r
⟩≡|
qr
⟩
Matrix
A
∈
C
N
×
N
A
∈
C
N
×
N
Components:
A
jk
j
,
k
=
{
0
,
1
,
N
−
1
}
Hermitian conjugate of
A
A
†
∈
C
N
×
N
A
†
∈
C
N
×
N
A
†
=
(
A
T
)
∗
=
(
A
∗
)
T
Inner product between
q
and
Ar
q
†
Ar
⟨
q
|
A
|
r
⟩
⟨
q
|
A
|
r
⟩
∗
=
⟨
r
|
A
|
q
⟩
Standard basis vector
(or, the computational basis)
e
0
,
e
1
, ...,
e
N
−
1
|
0
⟩
,
|
1
⟩
, ...,
|
N
−
1
⟩
e
0
=
(1 0
...
0)
T
e
1
=
(0 1
...
0)
T
Table 1:
Summary of the definitions and notation used in this paper.
where
q
0
,
q
1
∈
C
are two coe
ffi
cients called
amplitudes
. For comparison, the same state
|
p
⟩
expressed in matrix
notation reads
q
=
q
0
e
0
+
q
1
e
1
=
q
0
1
0
!
+
q
1
0
1
!
=
q
0
q
1
!
.
(26)
The kets
|
0
⟩
and
|
1
⟩
, or
e
0
and
e
1
, are two basis vectors which are referred to as the
computational basis
.
The state vector
|
q
⟩
expressed in a di
ff
erent orthonormal basis (spanning the same Hilbert space
C
2
) will have
di
ff
erent coe
ffi
cients. Assuming that the measuring device can measure the two states
{|
0
⟩
,
|
1
⟩}
, the qubit will be
found either in state
|
0
⟩
or
|
1
⟩
when observed. In quantum mechanics terminology, the state
|
q
⟩
will
collapse
either
into state
|
0
⟩
or
|
1
⟩
. According to the postulates of quantum mechanics, specifically the
Born rule
, the probability to
observe
|
0
⟩
is
p
(
|
0
⟩
)
=
|⟨
q
|
0
⟩|
2
=
|
q
∗
0
⟨
0
|
0
⟩
+
q
∗
1
⟨
1
|
0
⟩|
2
=
|
q
∗
0
|
2
=
|
q
0
|
2
.
(27)
Note that
⟨
q
|
=
q
∗
0
⟨
0
|
+
q
∗
1
⟨
1
|
according to Table 1. Similarly, the probability to observe
|
1
⟩
is
p
(
|
1
⟩
)
=
|
q
1
|
2
. The
two probabilities must satisfy
|
q
1
|
2
+
|
q
2
|
2
=
1. Once the qubit has been observed, i.e. the state has collapsed, it will
maintain its observed state and repeated measurements will yield the same result.
As will be detailed in Section 3.4, we note that the two states
|
0
⟩
and
|
1
⟩
are a property of the measuring
device rather than the quantum system. For instance, a measuring device that can measure only the orthogonal
states
{|
r
⟩
,
|
r
⊥
⟩}
will find the qubit in one these two states. The respective probabilities are determined by replac-
ing
|
0
⟩
with
|
r
⟩
or
|
r
⊥
⟩
in (27). Hence, the representation of the intrinsic qubit state
|
q
⟩
in a specific basis is a matter of
choice by the observer.
3.2.2. Multi-qubit systems
To begin with, we consider a two-qubit system (
n
=
2) with the state vector
|
q
⟩ ∈
C
2
n
. The elements of the
respective 2
n
dimensional basis are given by the Kronecker product of the basis states
{|
0
⟩
,
|
1
⟩}
for each of the qubits,
8
i.e.,
{|
0
⟩⊗|
0
⟩
,
|
0
⟩⊗|
1
⟩
,
|
0
⟩⊗|
1
⟩
,
|
1
⟩⊗|
1
⟩}
.
(28)
These four basis states are often abbreviated as
|
0
⟩⊗|
0
⟩≡|
0
⟩|
0
⟩≡|
00
⟩
,
|
0
⟩⊗|
1
⟩≡|
0
⟩|
1
⟩≡|
01
⟩
,
|
1
⟩⊗|
0
⟩≡|
1
⟩|
0
⟩≡|
10
⟩
,
|
1
⟩⊗|
1
⟩≡|
1
⟩|
1
⟩≡|
11
⟩
.
(29)
Converting the four binary numbers 00, 01, 10 and 11 to the decimals 0, 1, 2 and 3, respectively, yields an alternative
labelling for the states
|
0
⟩≡|
0
⟩⊗|
0
⟩
,
|
1
⟩≡|
0
⟩⊗|
1
⟩
,
|
2
⟩≡|
1
⟩⊗|
0
⟩
,
|
3
⟩≡|
1
⟩⊗|
1
⟩
.
(30)
We obtain after evaluating the Kronecker products
|
0
⟩
=
1
1
0
!
0
1
0
!
=
1
0
0
0
,
|
1
⟩
=
1
0
1
!
0
0
1
!
=
0
1
0
0
,
|
2
⟩
=
0
1
0
!
1
1
0
!
=
0
0
1
0
,
|
3
⟩
=
1
0
1
!
0
0
1
!
=
0
0
0
1
.
(31)
Using these basis vectors, the state
|
q
⟩∈
C
4
of a two-qubit system is given by
|
q
⟩
=
3
X
k
=
0
q
k
|
k
⟩
=
q
0
q
1
q
2
q
3
,
(32)
with the coe
ffi
cients
q
k
∈
C
. The coe
ffi
cients
q
k
must be normalised as the probability to observe the qubit in state
|
k
⟩
is given by
p
(
|
k
⟩
)
=
|
q
k
|
2
.
It bears emphasis that the Kronecker product of two one-qubit states is di
ff
erent from the two-qubit state (32). The
Kronecker product of two one-qubit states
|
r
⟩
and
|
s
⟩
yields the state
|
r
⟩⊗|
s
⟩
=
(
r
0
|
0
⟩
+
r
1
|
1
⟩
)
⊗
(
s
0
|
0
⟩
+
s
1
|
1
⟩
)
=
r
0
s
0
r
0
s
1
r
1
s
0
r
1
s
1
.
(33)
The Kronecker product of two one-qubit states cannot express every valid quantum state such as the state
|
q
⟩
=
1
√
2
|
0
⟩⊗|
0
⟩
+
1
√
2
|
1
⟩⊗|
1
⟩
=
1
/
√
2
0
0
1
/
√
2
,
(34)
which requires
r
0
s
0
=
r
1
s
1
=
1
/
√
2, but at the same time
r
0
s
1
=
0 and
r
1
s
0
=
0. The states that cannot be repre-
sented as the Kronecker product of one-qubit states are referred to as
entangled states
. The non-entangled states are
the
separable states
or
product states
.
Similar to the two-qubit case the state of
n
qubits is given by
|
q
⟩
=
2
n
−
1
X
k
=
0
q
k
|
k
⟩
=
q
0
q
1
.
.
.
q
2
n
−
1
,
(35)
9
where
q
k
∈
C
. The index
k
is frequently expressed as a binary
k
=
k
0
2
n
−
1
+
k
1
2
n
−
2
+
...
+
k
n
−
2
2
1
+
k
n
−
1
2
0
≡
k
0
k
1
...
k
n
−
1
k
n
,
(36)
so that (35) can be written as
|
q
⟩
=
2
n
−
1
X
k
=
0
q
k
|
k
⟩
=
1
X
k
0
=
0
1
X
k
1
=
0
...
1
X
k
n
−
2
=
0
1
X
k
n
−
1
=
0
q
k
0
k
1
...
k
n
−
2
k
n
−
1
|
k
0
k
1
...
k
n
−
2
k
n
−
1
⟩
.
(37)
Moreover, similar to two qubit states each of the states
|
k
⟩
are obtained as the Kronecker products of single qubit
states which becomes evident when writing
|
k
0
k
1
...
k
n
−
2
k
n
−
1
⟩≡|
k
0
⟩|
k
1
⟩
...
|
k
n
−
2
⟩|
k
n
−
1
⟩≡|
k
0
⟩⊗|
k
1
⟩⊗
...
⊗|
k
n
−
2
⟩⊗|
k
n
−
1
⟩
.
(38)
The inevitability of entangled states is even more apparent in case of
n
>
2. Each separate qubit has two coe
ffi
-
cients so that a separable state with
n
qubits can have only up to 2
n
distinct coe
ffi
cients, in contrast an entangled state
can have up to 2
n
distinct coe
ffi
cients. Without going into details, we note that the entanglement property of quantum
systems is in addition to their superposition property fundamentally di
ff
erent from classical systems such as a system
with
n
binary coins with the states head and tail [24].
3.3. Quantum gates and circuits
At the most abstract level, a quantum computer maps a state
|
q
⟩
to a new state
U
|
q
⟩
for a given unitary matrix
U
.
The coe
ffi
cients of the state
|
q
⟩
are the input and the coe
ffi
cients of
U
|
q
⟩
are the output. The unitarity require-
ment,
U
†
=
U
−
1
, is dictated by quantum mechanics and ensures that the mapped state remains normalised. In the
circuit model
of quantum computing, the unitary matrix
U
is composed of a sequence of smaller elementary unitary
matrices acting only one or a few qubits at a time. This approach is possible because the product of unitary matrices is
also unitary. The elementary unitary matrices correspond in the
quantum circuit
to
gates
so that we refer to elementary
matrices interchangeably as gates. This section provides a summary of the mostly widely used gates and discusses
how they are combined to quantum circuits implementing the unitary transformation
U
.
3.3.1. One-qubit gates
The three most common one-qubit gates are the Pauli gates
X
=
0 1
1 0
!
,
Y
=
0
i
−
i
0
!
,
Z
=
1
0
0
−
1
!
,
(39)
and the unitary gate
I
=
1
√
2
1 0
0 1
!
.
(40)
Proposition 1.
Any unitary matrix U
∈
C
2
×
2
, or one-qubit gate, can be expressed as the linear combination of the
four unitary matrices, or gates,
{
I
,
X
,
Y
,
Z
}
.
The Pauli gates are Hermitian and involutory (self inverse). As an example, the
X
gate applied twice to a one-qubit
state yields, owing to the involutory property,
X
q
0
q
1
!
=
q
1
q
0
!
;
X
q
1
q
0
!
=
q
0
q
1
!
.
(41)
When exponentiated the Pauli matrices yield the three rotation gates
R
X
(
θ
)
=
e
−
i
θ
X
/
2
=
,
R
Y
(
θ
)
=
e
−
i
θ
Y
/
2
,
R
Z
(
θ
)
=
e
−
i
θ
Z
/
2
,
(42)
10
which evaluate to
R
X
(
θ
)
=
cos
θ
2
−
i
sin
θ
2
−
i
sin
θ
2
cos
θ
2
!
,
R
Y
(
θ
)
=
cos
θ
2
−
sin
θ
2
sin
θ
2
cos
θ
2
!
,
R
Z
(
θ
)
=
e
−
i
θ/
2
0
0
e
i
θ/
2
!
.
(43)
Proposition 2.
The exponential e
i
θ
A
of a Hermitian matrix A
=
A
†
is a unitary matrix and is equal to
e
i
θ
A
=
I
cos(
θ
)
+
iA
sin(
θ
)
.
(44)
Other widely used one-qubit gates include the Hadamard and the phase gates,
H
=
1
√
2
1
1
1
−
1
!
,
P
(
θ
)
=
1
0
0
e
i
θ
!
,
(45)
respectively.
3.3.2. Multi-qubit gates
We first consider gates defined as the Kronecker products of one-qubit gates. To this end, note that the Kronecker
product of two or more unitary matrices is a unitary as well. By way of example, consider the two-qubit gate
X
⊗
Y
=
0 1
1 0
!
⊗
0
i
−
i
0
!
=
0
0
i
−
i
0
!
1
0
i
−
i
0
!
1
0
i
−
i
0
!
0
0
i
−
i
0
!
=
0 0
0
i
0 0
−
i
0
0
i
0 0
−
i
0
0 0
.
(46)
If this gate is applied to a non-entangled product state
|
r
⟩⊗|
s
⟩
it is equivalent to applying first
X
to
|
r
⟩
and
Y
to
|
s
⟩
and
then taking their Kronecker product, i.e.,
(
X
⊗
Y
)(
|
r
⟩⊗|
s
⟩
)
=
(
X
|
r
⟩
)
⊗
(
Y
|
s
⟩
)
.
(47)
Hence, starting with a product multi-qubit state applying only single qubit gates the state will remain a non-entangled
product state.
To achieve entanglement a controlled-not or
CNOT
is required. The
CNOT
gate is defined as
CNOT
=
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
.
(48)
In studying the action of the
CNOT
gate, or any other gate for that matter, on a state
|
q
⟩
=
3
X
k
=
0
q
k
|
k
⟩
=
1
X
k
0
=
0
1
X
k
1
=
0
q
k
0
k
1
|
k
0
k
1
⟩
,
(49)
it is su
ffi
cient to focus on its action on a single basis elements
|
k
⟩
=
|
k
0
k
1
⟩
. This is possible because of the linearity of
quantum transformations. According (48), the
CNOT
gate maps the four basis elements as follows
CNOT
:
|
0
⟩⊗|
0
⟩7→|
0
⟩⊗|
0
⟩
;
|
0
⟩⊗|
1
⟩7→|
0
⟩⊗|
1
⟩
;
|
1
⟩⊗|
0
⟩7→|
1
⟩⊗|
1
⟩
;
|
1
⟩⊗|
1
⟩7→|
1
⟩⊗|
0
⟩
.
(50)
Here, the left qubit
k
0
is the
control
and the right qubit
k
1
is the
target
. Only when the control qubit
k
1
is in state
|
1
⟩
the target qubit
k
0
is flipped else its state is maintained.
11
|
k
0
⟩
=
|
0
⟩
I
|
k
1
⟩
=
|
0
⟩
X
(a)
|
k
0
⟩
=
|
0
⟩
|
k
1
⟩
=
|
1
⟩
X
(b)
Figure 1:
A basic quantum circuit with two qubits
k
0
and
k
1
. As indicated in (b) the identity gate
I
is usually omitted in circuit diagrams so that
circuits (a) and (b) are equivalent. The states of both qubits are initialised with
|
k
0
⟩
=
|
0
⟩
and
|
k
1
⟩
=
|
0
⟩
so that
|
q
⟩
=
|
k
0
⟩⊗|
k
1
⟩
=
|
0
⟩⊗|
0
⟩
which is
abbreviated as
|
q
⟩
=
|
00
⟩
. The output of the circuit is (
I
⊗
X
)(
|
0
⟩⊗|
0
⟩
)
=
I
|
0
⟩⊗
X
|
0
⟩
=
|
0
⟩⊗|
1
⟩
.
k
0
:
•
k
1
:
(a)
|
k
0
⟩
=
|
0
⟩
H
•
|
k
1
⟩
=
|
1
⟩
(b)
Figure 2:
Quantum circuits with two qubits
k
0
and
k
1
. The circuit (a) depicts the
CNOT
gate where
k
0
is the control and
k
1
the target wires. The
respective unitary matrix is given in (48). The state of the target
k
1
is only flipped only when the state of the control is
k
0
=
1 else it is maintained.
The output of the circuit (b) is the entangled state
1
√
2
(
|
0
⟩⊗|
0
⟩
+
|
1
⟩⊗|
1
⟩
)
=
1
√
2
(
|
00
⟩
+
|
11
⟩
)
=
1
√
2
(
|
0
⟩
+
|
3
⟩
).
In passing, we note that
CNOT
is referred as a controlled Pauli X gate given that
CNOT
=
|
0
⟩⟨
0
|⊗
I
+
|
1
⟩⟨
1
|⊗
X
=
1 0
0 0
!
⊗
1 0
0 1
!
+
0 0
0 1
!
⊗
0 1
1 0
!
.
(51)
It goes without saying that
CNOT
is like any other quantum gate a unitary. To obtain the controlled two-qubit versions
of other single-qubit gates it is su
ffi
cient to replace
X
above with the respective single qubit gate.
3.3.3. Quantum circuits
As stated earlier, quantum computation can be summarised as the mapping of a multi qubit state
|
q
⟩ ∈
C
2
n
into
the state
U
|
q
⟩ ∈
C
2
n
for the purpose of doing some desired computation. The construction of the unitary matrix
U
∈
C
2
n
×
2
n
out of one-qubit and multi-qubit gates is commonly visualised using
circuit diagrams
[18]. We should
bear in that
Proposition 3.
The product U
1
U
2
of two unitary matrices U
1
and U
2
is again a unitary.
Proposition 4.
The Kronecker product U
1
⊗
U
2
of two unitary matrices U
1
and U
2
is again a unitary.
In the circuit diagrams depicted in Figures 1 and 2 each line is referred to as a
wire
and represents a qubit. The circuit
is read from left to the right and shows the sequence of applied single and two-qubit gates. There is no joining or
splitting of wires which would violate the unitarity requirement for
U
. As illustrated in Figure 1 the identity gates
are usually omitted in the diagrams. In comparing and interpreting circuit diagrams note that there are two di
ff
erent
common qubit labelings, see Section 3.2.2.
In the basic circuit depicted in Figure 1 the computation starts with two qubits
k
0
and
k
1
both in the state
|
0
⟩
. The
corresponding state vector is
|
q
⟩
=
|
k
0
⟩⊗|
k
1
⟩
=
|
0
⟩⊗|
0
⟩
=
|
0
⟩⊗|
0
⟩
=
1
0
0
0
(52)
12
Next, we apply to the qubit
k
1
the Pauli
X
gate and to the qubit
k
0
the identity gate
I
. The resulting state is given by
|
q
⟩
=
(
I
⊗
X
)(
|
k
0
⟩⊗|
k
1
⟩
)
=
I
|
0
⟩⊗
X
|
0
⟩
=
1
0
!
⊗
0 1
1 0
!
1
0
!
=
0
1
0
0
.
(53)
Notice that
U
=
I
⊗
X
is the unitary for entire circuit.
The entangled state given in equation (34) can be obtained with the circuit depicted in Figure 2b. The sequence of
the mappings is applied as follows:
(
H
⊗
I
) :
|
0
⟩⊗|
0
⟩7→
1
√
2
(
|
0
⟩
+
|
1
⟩
)
⊗|
0
⟩
,
CNOT
:
1
√
2
(
|
0
⟩
+
|
1
⟩
)
⊗|
0
⟩7→
1
√
2
(
|
0
⟩⊗|
0
⟩
+
|
1
⟩⊗|
1
⟩
)
.
(54)
For the
CNOT
the left qubit (
k
1
) is the control qubit and the right (
k
0
) is the target qubit. The target qubit state is
flipped when the control qubit is in state
|
1
⟩
. This can be also more formally explained obtain the definition (51) of
the
CNOT
and noting the orthonormality of the states
|
0
⟩
and
|
1
⟩
.
3.4. Measurement
As mentioned before, in quantum systems the outcome of a measurement is random and measurement has an irre-
versible e
ff
ect on the state of a system. When a quantum system with the state vector
|
q
⟩∈
C
2
n
−
1
, i.e.
|
q
⟩
=
P
2
n
−
1
k
=
0
q
k
|
k
⟩
,
is measured we will find it in one of its 2
n
−
1
possible states. According to the Born rule, the probability of observing
the system in the specific state
|
k
∗
⟩
is
p
(
|
k
∗
⟩
)
=
|
q
k
∗
|
2
. The measurement process collapses the quantum state so
that after measurement the state vector becomes
|
q
⟩
=
|
k
∗
⟩
. Consequently, we can infer the absolute values of the
coe
ffi
cients
{|
q
0
|
2
,
|
q
1
|
2
,...,
|
q
2
n
−
1
|
2
}
only by considering the statistics of several quantum computations with the same
circuit.
Clearly, a state vector
|
q
⟩
can be expressed in di
ff
erent basis so that the possible outcomes of a measurement
depend on the specific basis imposed by the measurement apparatus. This realisation leads to the notion of projective
measurement.
Proposition 5.
A complete set of orthogonal projectors P
j
has the properties
P
j
P
j
=
I and P
j
P
k
=
δ
jk
and can be,
for instance, obtained from an orthonormal basis
{|
r
0
⟩
, ...,
|
r
2
n
−
1
⟩}
according to the definition
P
j
=
|
r
j
⟩⟨
r
j
|
.
(55)
In projective measurement the probability of observing the system in state
j
is given by
p
(
j
)
=
∥
P
j
|
q
⟩∥
=
⟨
q
|
P
j
|
q
⟩
.
(56)
Note that the probabilities for all 2
n
−
1
states add up to one as desired. Furthermore, during the measurement the
system collapses to the state
P
j
|
q
⟩
∥
P
j
||
q
⟩∥
=
P
j
|
q
⟩
p
p
(
j
)
.
(57)
Projective measurement can be used to derive the rules for partial measurement. For instance, in a two qubit
system the two projectors
P
0
=
I
⊗|
0
⟩⟨
0
|
,
P
1
=
I
⊗|
1
⟩⟨
1
|
,
(58)
form a complete set. They measure the probability of finding the right qubit in the state
|
0
⟩
or
|
1
⟩
, respectively. Hence,
13
applying
P
1
to a quantum state
|
q
⟩
=
1
√
2
(
|
1
⟩|
0
⟩
+
|
1
⟩|
1
⟩
) yields the probability
p
(0)
=
⟨
q
|
P
0
|
q
⟩
=
1
2
,
(59)
and the state colapses to
P
0
|
q
⟩
p
p
(0)
=
√
2
P
0
|
q
⟩
=
|
1
⟩|
0
⟩
.
(60)
3.5. Quantum algorithm complexity
The complexity of a quantum algorithm can be measured by three major ways: the number of universal quantum
gates, the depth of the quantum circuit, and the number of queries of an oracle (black box) model. In this work, we aim
to make all of our quantum algorithms explicit with no refence to oracle black box. We define the complexity of our
quantum algorithm by the number of quantum gates present in our quantum circuit. For all cases studied in this work,
we shall transpile our quantum circuits with a universal set of quantum gates made of the two-qubit Controlled-Not
(or
CNOT
) gate, and the one-qubit rotation gate (or
U
3
gate). We further assume the ideal scenario where we ignore
the error of fundamental quantum gates, and subsequently the cost for error correction.
4. Quantum computing algorithms
In this Section we provide a summary of quantum algorithms and circuits needed in our quantum computational
scheme. We also make comments on the computational complexity of these quantum algorithms.
4.1. Multi-controlled operation
One fundamental operation in scientific computing involves conditional commands for making decisions. In
classical computing, the ”if-then” structure is commonly used to handle such conditions. In the realm of quantum
computing, the equivalent of this conditional structure can be realized through multi-controlled operations.
As previously discussed in Section 3.3.2, the controlled-Not (
CNOT
) gate serves as a prototype circuit for such
operations. As elaborated in that section, it is possible to create a general controlled unitary circuit, denoted as the
controlled-
U
(
CU
) gate, by replacing the (
NOT
) gate with an arbitrary single-qubit rotation gate (
U
). Mathematically,
the
CU
gate is represented as:
CU
=
|
0
⟩⟨
0
|⊗
I
+
|
1
⟩⟨
1
|⊗
U
.
(61)
It is evident that the
CU
gate is an operator that maps the state
|
c
⟩|
t
⟩
to
|
c
⟩
U
|
t
⟩
. In simpler terms, this operation can be
described as follows: ”If the control qubit is
|
c
=
1
⟩
, then apply the operator
|
U
⟩
to the target qubit
|
t
⟩
.”
Generalizing the concept of the
CU
gate leads to the multi-controlled rotation gate, which performs the mapping:
|
c
0
c
1
...
c
n
⟩|
t
⟩7→|
c
0
c
1
...
c
n
⟩
U
|
t
⟩
,
(62)
where the rotation
U
is applied only if all the control qubits are set to
|
c
0
c
1
...
c
n
⟩
=
|
11
...
1
⟩
. In our work, we adopt the
”V-chain” approach proposed by Nelson and Chuang[1] for multi-controlled operations.
To illustrate, we provide an example quantum circuit with 3 control qubits in Figure 3, employing the V-chain
architecture shown in Figure 3 (b). In the computational basis
|
c
0
c
1
c
2
⟩
, the first To
ff
oli gate (i.e., the controlled
CNOT
gate) transforms the state of the first ancilla qubit into
|
a
0
=
c
0
·
c
1
⟩
, and the second To
ff
oli gate updates
the state of the second ancilla qubit to
|
a
1
=
c
0
·
c
1
·
c
2
⟩
. A controlled-
U
gate is subsequently applied if
|
a
1
⟩
=
1,
indicating that this operation occurs only when all control qubits are in the state
|
1
⟩
. The circuit is then un-computed
by re-applying the To
ff
oli gates to ensure reversibility.
Complexity
A general Multi-controlled operation with
n
control qubits requires
n
−
1 ancilla qubits and 2
n
−
2
To
ff
oli gates. We note that To
ff
oli gates can be realized by the universal gate set defined in 3.5, with 10
U
gate and
14