Quantum Machine Learning Overview
Quantum Machine Learning Overview
1
College of Computing and Data Science, Nanyang Technological University,
639798, Singapore
2
Centre for Quantum Technologies, National University of Singapore, 117543,
Singapore
3
Hon Hai Research Institute, Taipei, 114, Taiwan
†
duyuxuan123@[Link]
↿
[Link]@[Link]
⊥
cqtfpr@[Link]
‡
[Link]@[Link]
∗
Equal contributions
ii
Abstract
iii
iv
Contents
Preface ix
1 Introduction 1
1.1 A First Glimpse of Quantum Machine Learning . . . . . . . . 3
1.1.1 Quantum computers . . . . . . . . . . . . . . . . . . . 3
1.1.2 Different measures of quantum advantages . . . . . . . 7
1.1.3 Explored tasks in quantum machine learning . . . . . 9
1.2 Progress of Quantum Machine Learning . . . . . . . . . . . . 11
1.2.1 Progress of quantum computers . . . . . . . . . . . . . 11
1.2.2 Progress of quantum machine learning under FTQC . 13
1.2.3 Progress of quantum machine learning under NISQ . . 15
1.2.4 A brief review of quantum machine learning . . . . . . 18
1.3 Organization of This Tutorial . . . . . . . . . . . . . . . . . . 19
v
vi CONTENTS
6 Conclusion 205
ix
x Preface
the community.
To overcome this challenge, we have written this tutorial to deliver a
comprehensive introduction to the latest developments in QML, specifically
designed for readers with expertise in machine learning. Whether you are
an AI researcher, a machine learning practitioner, or a computer science
student, this resource will equip you with a solid foundation in the principles
and techniques of QML. By bridging the gap between classical ML and
quantum computing, this tutorial could serve as a useful resource for those
looking to engage with quantum machine learning and explore the forefront
of AI in the quantum era.
The Authors
Feb, 2025
Chapter 1
Introduction
1
2 CHAPTER 1. INTRODUCTION
The three key elements in the above interpretation are: quantum proces-
sors, specified tasks, and advantages. In what follows, let us elucidate the
specific meaning of each of these terms, providing the necessary foundation
for a deeper understanding of the mechanisms and potential of QML.
Classical Computation
Input (Algorithm) Output
7 Bits
0111001 [Digital Logic Circuits]
Input
0000000 Quantum Computation
7 Qubits 0000001 (Algorithm) Output
…. [Quantum Circuits]
1111111
• Bits versus Qubits. A classical bit is a binary unit that takes on a value
of either 0 or 1. In contrast, a quantum bit, or qubit, can exist in a
superposition of both 0 and 1 simultaneously, represented by a two-
dimensional vector where the entries correspond to the probabilities of
the qubit being in each state.
Furthermore, while classical bits follow the Cartesian product rule,
qubits adhere to the tensor product rule. This distinction implies that
an N -qubit system is described by a 2N -dimensional vector, allowing
quantum systems to encode information exponentially with N —far
surpassing the capacity of classical bits. Table 1.2 summarizes the
mathematical expressions of classical and quantum bits.
Remark
Note that quantum volume is not the unique metric for evaluating the
performance of quantum computers. There are several other metrics
that assess the power of quantum processors from different perspec-
tives. For instance, Circuit Layer Operations Per Second (CLOPS)
(Wack et al., 2021) measures the computing speed of quantum com-
puters, reflecting the feasibility of running practical calculations that
involve a large number of quantum circuits. Additionally, effective
quantum volume (Kechedzhi et al., 2024) provides a more nuanced
comparison between noisy quantum processors and classical comput-
ers, considering factors such as error rates and noise levels. These
metrics, among others, offer a more comprehensive understanding of
the strengths and limitations of quantum computers across various
applications.
Remark
(Difference of sample complexity in classical and quantum ML). In
classical ML, sample complexity typically refers to the number of
training examples required for a model to generalize effectively, such
as the number of labeled images needed to train an image classi-
fier. In quantum ML, however, sample complexity can take on varied
meanings depending on the context, as shown below.
Q for C C for Q
Classifier (supervised learning) (unsupervised learning)
Discriminative Generative
learning learning Q for Q C for C (reinforcement learning)
Applications
Remark
The primary focus of this tutorial is on the QC and QQ sectors. For
more details on CQ, interested readers can refer to (Schuld et al.,
2015; Dunjko and Briegel, 2018; Carleo et al., 2019).
Photon 1M qubits
PsiQuantum
known for their high coherence times, precise control over individual qubits,
and full connectivity of all qubits (Bruzewicz et al., 2019). Moreover, Ry-
dberg atom systems enable flexible qubit connectivity through highly con-
trollable interactions (Morgado and Whitlock, 2021). Besides these archi-
tectures, integrated photonic quantum computers are emerging as promising
alternatives for robust and scalable quantum computation.
Despite recent advances, today’s quantum computers remain highly sen-
sitive to environmental noise and prone to quantum decoherence, lacking
the stability needed for fault-tolerant operation. This results in qubits,
quantum gates, and quantum measurements that are inherently imperfect,
introducing errors that can lead to incorrect outputs. To capture this stage
in quantum computing, John Preskill coined the term “noisy intermediate-
scale quantum” (NISQ) era (Preskill, 2018), which describes the current
generation of quantum processors. These processors feature up to thou-
sands of qubits, but their capabilities are restricted with error-prone gates
and limited coherence times.
In the NISQ era, notable achievements have been made alongside new
challenges. Industrial and academic teams, such as those at Google and
USTC, have demonstrated quantum advantages on specific sampling tasks,
where the noisy quantum computers they fabricated outperform classical
computers in computational efficiency (Arute et al., 2019; Wu et al., 2021).
However, most quantum algorithms that theoretically offer substantial run-
time speedups depend on fault-tolerant, error-free quantum systems—capabilities
1.2. PROGRESS OF QUANTUM MACHINE LEARNING 13
Remark
However, there are several critical caveats of the HHL-based QML
algorithms. First, the assumption of efficiently preparing the quan-
tum states corresponding to classical data runtime is very strong and
may be impractical in the dense setting. Second, the obtained result
x is still in the quantum form |x⟩. Note
√ that extracting one entry of
|x⟩ into the classical form requires O( N ) runtime, which collapses
the claimed exponential speedups. The above two issues amount to
the read-in and read-out bottlenecks in QML (Aaronson, 2015). The
1.2. PROGRESS OF QUANTUM MACHINE LEARNING 15
last caveat is that the employed strong quantum input model such as
quantum random access memory (QRAM) (Giovannetti et al., 2008)
leads to an inconclusive comparison. Through exploiting a classical
analog of QRAM as the input model, there exist efficient classical al-
gorithms to solve recommendation systems in poly-logarithmic time
in the size of input data.
As shown in Figure 1.4, the mechanisms of QNNs and deep neural net-
works (DNNs) are almost the same, whereas the only difference is the way
of implementing the trainable model. This difference gives the potential of
quantum learning models to solve complex problems beyond the reach of
classical neural networks, opening new frontiers in many fields. Roughly
speaking, research in QNNs and quantum kernel methods has primarily fo-
cused on three key areas: (I) quantum learning models and applications, (II)
the adaptation of advanced AI topics to QML, and (III) theoretical foun-
dations of quantum learning models. A brief overview of each category is
provided below.
(I) Quantum learning models and applications. This category
16 CHAPTER 1. INTRODUCTION
…
Data
Encoder
(dataset) (dataset)
Figure 1.4: Mechanisms of DNNs and QNNs. Both DNNs and QNNs
follow an iterative approach. At each iteration, they take input data, pro-
cess it through multiple layers, and produce an output prediction. The key
difference between DNNs and QNNs is the way of implementing their learn-
ing models.
Remark
It is important to note that QNNs and quantum kernel methods can
also be considered FTQC algorithms when executed on fully fault-
tolerant quantum computers. The reason these algorithms are dis-
cussed in the context of NISQ devices is their flexibility and robust-
ness, making them well-suited to the limitations of current quantum
hardware.
more flexible and can be executed on both NISQ and FTQC devices, depend-
ing on the available resources.
As quantum hardware continues to progress, the development of QML
algorithms must evolve in tandem. A promising direction is to integrate
FTQC algorithms with QNNs and quantum kernel methods, creating new
QML algorithms that can be run on current quantum processors while of-
fering enhanced quantum advantages across various tasks.
Basics of Quantum
Computing
21
22 CHAPTER 2. BASICS OF QUANTUM COMPUTING
where ⟨0| ≡ e⊤ ⊤
0 ≡ [1, 0], ⟨1| ≡ e1 ≡ [0, 1], and the symbol ‘⊤’ denotes the
transpose operation.
The physical interpretation of coefficients {ai } is probability amplitudes.
Namely, when we intend to extract information from the qubit state |a⟩ into
the classical form, quantum measurements are applied to this state, where
2.1. FROM CLASSICAL BITS TO QUANTUM BITS 23
the probability of sampling the basis |0⟩ (|1⟩) is |a1 |2 (|a2 |2 ). Recall that
the classical bit only permits the deterministic status with ‘0’ or ‘1’, while
the qubit state in Eqn. (2.2) is the superposition of the two status ‘|0⟩’ and
‘|1⟩’.
Remark
The quantum superposition leads to a distinct power between quan-
tum and classical computation, where the former can accomplish cer-
tain tasks with provable advantages.
Two-qubit state. The two qubits obey the tensor product rule, i.e.,
y1 x1 y1
x1 y x1 y2 x1 y2
⊗ 1 =
= , (2.4)
x2 y2 y1 x2 y1
x2
y2 y2 y2
which differs from the classical bits yielding the Cartesian product rule.
For instance, let the first qubit follow Eqn. (2.2) and the second qubit
state be |b⟩ = b1 |0⟩ + b2 |1⟩ with |b1 |2 + |b2 |2 = 1. The two-qubit state
formed by |a⟩ and |b⟩ is defined as
|a⟩ ⊗ |b⟩ = a1 b1 |0⟩ ⊗ |0⟩ + a1 b2 |0⟩ ⊗ |1⟩ + a2 b1 |1⟩ ⊗ |0⟩ + a2 b2 |1⟩ ⊗ |1⟩ ∈ C4 ,
1
(2.5)
0
where the computational basis follows |0⟩⊗|0⟩ ≡ 00 , |0⟩⊗|1⟩ ≡ 10 , |1⟩⊗
0 0 0 0
P2 P2
|0⟩ ≡ 1 , |1⟩ ⊗ |1⟩ ≡ 0 , and the coefficients satisfy i=1 j=1 |ai bj |2 =
0 0
0 1
1.
Remark
For ease of notations, the state |a⟩ ⊗ |b⟩ can be simplified as |ab⟩,
|a, b⟩, or |a⟩ |b⟩. We will interchangeably use these notations through-
out the tutorial.
Remark
In quantum computing, a basis state |i⟩ refers to a computational
basis state in the Hilbert space of a quantum system. For an N -
qubit system, the computational basis states are represented as |i⟩ ∈
{|0 · · · 0⟩ , |0 · · · 1⟩ , ..., |1 · · · 1⟩}, where i is the binary representation
of the state index. These states form an orthonormal basis of the
2N -dimensional Hilbert space, satisfying
A key property of the entangled states (e.g., Bell states and GHZ states) is
that measuring one qubit determines the outcome of measuring the other
qubit, reflecting their strong quantum correlation.
N N
where ρi = |ψi ⟩ ⟨ψi | ∈ C2 ×2 is the outer product of the pure state |ψi ⟩.
The outer product of two vectors |u⟩ , |v⟩ ∈ Cn is expressed as
u1 u1 v1∗ u1 v2∗ · · · u1 vn∗
u2
u2 v1∗ u2 v2∗ · · · u2 vn∗
∗ ∗ ∗
|u⟩ ⟨v| = . v1 v2 · · · vn = . .. .. .. , (2.13)
.. .. . . .
un un v1∗ un v2∗ · · · un vn∗
where ui and vi∗ are the element of |u⟩ and the conjugate transpose ⟨v|,
respectively.
From the perspective of computer science, the density operator ρ is just
a positive semi-definite matrix with trace-preserving, i.e., 0 ⪯ ρ and Tr(ρ) =
1.
2.1. FROM CLASSICAL BITS TO QUANTUM BITS 27
1. A is Hermitian: A = A†
2. For any nonzero vector |v⟩ ∈ Cn , ⟨v| A |v⟩ ≥ 0, where ⟨v| A |v⟩ repre-
sents the quadratic form of A with respect to |v⟩.
P (i) (i)
where pi ≥ 0, i pi = 1, and ρA and ρB are density operators on HA and
HB , respectively. If ρ can be written in this form, it is called separable.
Logic gates
Logic gates are the basic components of a digital circuit. They take binary
inputs, represented as 0 or 1, and produce a binary output based on a
predefined logical operation. The most common logic gates include:
1. NOT Gate: This gate inverts the input bit, i.e., it produces 1 if the
input is 0, and vice versa. Its truth table is shown in Table 2.1;
Quantum gate
Recall that the computational toolkit for classical computers is logic gates,
e.g., NOT, AND, OR, and XOR, which are applied to the single bit or mul-
tiple bits to accomplish computation. Similarly, the computational toolkit
for quantum computers (or quantum circuits) is quantum gate, which op-
erates on qubits introduced in Chapter 2.1.2 to complete the computation.
In the following, we will introduce both single-qubit and multi-qubit gates.
Single-qubit gates. Single-qubit gates control the evolution of the single-
qubit state |a⟩. Due to the law of quantum mechanics, the evolved state
should satisfy the normalization constraint. The implication of this con-
straint is that the evolution must be a unitary operation. Concretely, de-
noted U ∈ C2×2 as a linear operator and the evolved state as
1
32 CHAPTER 2. BASICS OF QUANTUM COMPUTING
The evolution from |a⟩ to |â⟩ can be visualized using a quantum circuit
diagram, as illustrated in Figure 2.2. The wire in the circuit represents a
qubit, which evolves from the initial state |a⟩ on the left to the final state
|â⟩ on the right. Gates are applied sequentially from left to right along the
wire.
Remark
The circuit model serves as a foundational framework for describing
quantum computation due to its intuitive and modular nature, mak-
ing it accessible for researchers and practitioners transitioning from
classical to quantum computing. First, the circuit model provides a
standardized graphical language to represent complex quantum algo-
rithms, enabling clear visualization of the computational flow and in-
teractions among qubits. Second, the modularity of the circuit model
allows quantum operations to be easily decomposed into a pre-defined
gate set, ensuring compatibility across different quantum hardware
architectures.
Remark
In the view of computer science, the quantum (logic) gates in Figure
2.1 are well-designed matrices with the following properties. First,
all quantum gates are unitary (e.g., X X† = I2 ). Second, X, Y, Z,
H gates have the fixed form with size 2 × 2; CNOT, CZ, and SWAP
gates have the fixed form with size 4×4. Third, RX(θ), RY(θ), RZ(θ)
gates are matrices controlled by a single variable θ.
2.2. FROM DIGITAL LOGICAL CIRCUIT TO QUANTUM CIRCUIT MODEL33
0⟩ X |1⟩
|0⟩ H
1
0⟩ X |1⟩ √ (|000⟩ + |111⟩)
|0⟩ 2
0⟩ X |1⟩ |0⟩
U
U
Figure 2.3: The decomposition of the multi-qubit circuit U in the
case of N = 3.
Remark
The CNOT gate plays a pivotal role in quantum computing due to
its unique ability to generate entangled states, such as the Bell states
and GHZ states presented in Examples 2.1&2.3. Besides, the CNOT
gate is one of the most commonly implemented gates on quantum
34 CHAPTER 2. BASICS OF QUANTUM COMPUTING
A universal quantum gate set. While many single and multi-qubit gates
exist, it is sufficient to use a universal set of gates to construct any unitary
operation. As proved in Chapter 4.5.2 of Ref. (Nielsen and Chuang, 2011),
any unitary operator U in Eqn. (2.18) can be decomposed into the single-
qubit and two-qubit gates with a certain arrangement.
Fact 2.8 (Solovay-Kitaev theorem, (Dawson and Nielsen, 2005)). Suppose
we are given a fixed universal gate set G, which generates a dense group
SU(d). Then any unitary operator U ∈ SU(d) can be approximated to an
arbitrary precision ϵ > 0 by a finite sequence of gates from G. Formally,
there exists a decomposition such that
L
Y
U− Gl ≤ ϵ, Gl ∈ G, L ∈ N, (2.20)
l=1 op
where ∥·∥op is the operator norm which is the largest singular value of a
matrix, and L is the required number of gates that scales as:
L = O(logc (1/ϵ)), (2.21)
with c ≈ 4.
A commonly used universal gate set includes single-qubit rotations RX(θ),
RY(θ), RZ(θ), and two-qubit gates such as the CNOT gate. As illustrated
in Figure 1.1, any ideal quantum computation can be represented by a uni-
tary operator. This universal gate set provides a practical and foundational
toolkit for implementing arbitrary quantum algorithms.
Quantum channels
Analogous to the unitary operation describing the evolution of quantum
states in the closed system, the quantum channel formalizes the evolution
of quantum states in the open system. Refer to the textbook (Wilde, 2011)
for more details.
Mathematically, every quantum channel N (·) can be treated as a linear,
completely positive, and trace-preserving map (CPTP map).
Definition 2.9 (CPTP map). Denote L(H) as the space of square linear
operators acting on the Hilbert space H. We say N (·) is a CPTP map if the
following conditions are satisfied:
2.2. FROM DIGITAL LOGICAL CIRCUIT TO QUANTUM CIRCUIT MODEL35
sider a single-qubit pure state ρ = |0⟩ ⟨0| with the density matrix
1 0
ρ = |0⟩ ⟨0| = . (2.24)
0 0
When the depolarizing channel Np acts on this state, the output is given
by
p
1 0 p 1 0 1− 2 0
Np (ρ) = (1 − p) + = p . (2.25)
0 0 2 0 1 0 2
Therefore, the purity is inferred as:
p2
Tr(Np2 (ρ)) = 1 − p + . (2.26)
2
When p = 0, the state remains pure and unchanged. When 0 < p ≤ 1,
the state becomes a mixture of states |0⟩ and |1⟩ with Tr(Np2 (ρ)) < 1.
When p = 1, the state evolves into the maximally mixed state.
The second type is the Pauli channel, which serves as a dominant noise
source in many computing architectures and as a practical model for ana-
lyzing error correction (Flammia and Wallman, 2020).
When the Pauli channel Np⃗ acts on this state, the output is given by
1 0 0 0 0 0 1 0
Np⃗ (ρ) = pI + pX + pY + pZ (2.29)
0 0 0 1 0 1 0 0
pI + pZ 0
= . (2.30)
0 pX + pY
Let us analyze three special cases for the probability vector p⃗ = (pI , pX , pY , pZ ):
• Case 3: For other values of p⃗, the effect of the Pauli channel
on the pure state |0⟩ can be interpreted as a combination of the
depolarizing channel and the bit-flip channel.
where PN = {I, X, Y, Z}⊗N denotes the set of all tensor products of the N
single-qubit PauliPoperators, and pP is the probability of applying the Pauli
operator P with P ∈PN pP = 1.
38 CHAPTER 2. BASICS OF QUANTUM COMPUTING
Remark
The multi-qubit Pauli channel considers the existence of correlated
Pauli noise on different qubits. If each qubit only experiences in-
dependent single-qubit Pauli noise, the multi-qubit channel can be
written as the tensor product of sing-qubit Pauli channels:
Np⃗ (ρ) = ⊗N
i=1 Np
⃗i (ρ), (2.34)
where Np⃗i is the single-qubit Pauli channel acting on the i-th qubit
with probabilities p⃗i = (pI , pX , pY , pZ ).
Remark
According to the Choi-Kraus decomposition, the unitary operator is
a special case of a quantum channel. Specifically, when d = 1, the
quantum channel reduces to:
where TrE (·) denotes the partial trace over the ancillary Hilbert space HE ,
and the dimension of HE depends on the rank of the Kraus representation
2.2. FROM DIGITAL LOGICAL CIRCUIT TO QUANTUM CIRCUIT MODEL39
of N .
The translation between the unitary operation and the quantum channels
described by Theorem 2.15 can be visually explained, as shown in Figure 2.4.
In this diagram, the first wire corresponds to the original input state ρ,
while the second wire represents the initial state |φ⟩ of the environment.
To determine the output of the quantum channel N applied to ρ, an N -
induced unitary operation U is performed on the combined system, followed
by a partial trace over the environment to discard its information.
ρ N (ρ)
U
|φ⟩ Trace over HE
Quantum measurements
In addition to quantum gates and quantum channels that manipulate quan-
tum states, another special operation in quantum circuits is measurement.
40 CHAPTER 2. BASICS OF QUANTUM COMPUTING
|ai
U
input state
1
The quantum measurements can be categorized into two types, i.e., pro-
jective measurements and positive operator-valued measures (Preskill, 1999;
Nielsen and Chuang, 2011).
The projective measurement, which is also called the von Neumann
P mea-
surement, is formally described by the Hermitian operator A = i λi |vi ⟩ ⟨vi |,
where {λi } and {|vi ⟩} refer to the eigenvalues and eigenvectors of A, re-
spectively. Supported by the Born rule (Nielsen and Chuang, 2011), when
N N
the measurement operator A ∈ C2 ×2 is applied to an N -qubit state
N
|Φ⟩ ∈ C2 , the probability of measuring any one of the eigenvalues in {λi }
is
Pr(λi ) = | ⟨vi |Φ⟩ |2 . (2.38)
Define Πi = |vi ⟩ ⟨vi | as the i-th projective operator. The complete set of
projective operators {Πi } has the following properties
X
1)Πi Πj = δij ; 2)Π†i = Π; 3)Π2i = Π; 4) Πi = I2N . (2.40)
i
Remark
Here we address the accessible information through quantum mea-
surements in the ideal and practical settings. For ease of discussion,
suppose that the computation result corresponds to the probabil-
ity amplitude a1 in the single-qubit state |a⟩ = a1 |0⟩ + a2 |1⟩ in
Eqn. (2.2). To extract a1 from the quantum state into the classi-
cal form, we apply the projective operator Π1 = |0⟩ ⟨0| to this state.
Due to the law of quantum mechanics, after each measurement, the
state is collapsed and the measured outcome Vi can be viewed as a
binary random variable with the Bernoulli distribution Ber(ai ), i.e.,
Pr(Vi = 1) = a1 and Pr(Vi = 0) = 1 − a1 . Through applying the
measurement Πi to K copies of the state |a⟩, P the obtained statistics,
K
i.e., the sample mean, is denoted by ā1 = i=1 Vi /K. The large
number theorem indicates ā1 = a1 when K → ∞. However, only
the finite number of measurements K is allowed in practice and thus
results in an estimation error.
Basis encoding
Basis encoding is a basic method for processing classical data that can be
represented in binary form. Given a classical binary vector x = (x0 , . . . , xi , . . . , xN −1 ) ∈
{0, 1}N , this encoding technique maps the vector directly into a quantum
computational basis state as follows:
|ψ⟩ = |x0 , . . . , xN −1 ⟩ . (2.44)
In this process, N qubits are required to represent a binary vector of length
N . To prepare the corresponding quantum state |ψ⟩, an X gate is applied
to each qubit where the corresponding bit value is 1. The overall quantum
state preparation can be expressed as:
N
O −1
|ψ⟩ = X xi |0⟩⊗N ,
i=0
2.3. QUANTUM READ-IN AND READ-OUT PROTOCOLS 43
where |0⟩⊗N represents an initial state of all qubits set to |0⟩, and X xi means
applying the X gate to the i-th qubit only if xi = 1.
|0⟩ X |1⟩
|0⟩ X |1⟩
|0⟩ |0⟩
Figure 2.6: Example of basis encoding for the integer 6.
Amplitude encoding
Amplitude encoding is a technique that maps classical data into the ampli-
N
tudes of a quantum state. Given a vector x = (x0 , . . . , xi , . . . , x2N −1 ) ∈ C2
containing complex values, we first apply L2 normalization to obtain a nor-
malized vector
x
x̂ = , (2.45)
∥x∥2
where ∥x∥2 is the Euclidean norm. This ensures that the normalized vec-
PN
tor x̂ satisfies 2i=0−1 |x̂i |2 = 1. The corresponding quantum state is then
expressed as
N −1
2X
|ψ⟩ = x̂i |i⟩ (2.46)
i=0
Angle encoding
Basis encoding and amplitude encoding are fundamental techniques for map-
ping classical data to quantum states, but each comes with distinct resource
costs. Basis encoding requires a number of qubits equal to the dimension-
ality of the binary representation of classical data and necessitates minimal
gate operations for state preparation. In contrast, amplitude encoding is
highly compact in terms of qubits, using only the logarithmic of the data
dimensionality, but it involves a significant gate complexity.
To address this limitation, an alternative is angle encoding. The core idea
of angle encoding is to embed classical data into a quantum state through
rotation angles.
Given a real-valued vector x = (x0 , . . . , xi , . . . , xN −1 ) ∈ RN , the en-
coded quantum state can be represented as:
N
O −1 N
O −1 x
⊗N i
|ψ⟩ = Rσ (xi ) |0⟩ = exp −i σ |0⟩⊗N , (2.47)
2
i=0 i=0
Remark
1
|D⟩ = √ (|0⟩a |10⟩d + |1⟩a |11⟩d ). (2.49)
2
The corresponding quantum circuit for implementing this state is
shown in Fig. 2.7.
|0⟩a H X X
|0⟩d
|0⟩d
Figure 2.7: Example of QRAM encoding for the dataset D = {2, 3}.
⃗ = (AT A)−1 AT p.
ρ (2.52)
Remark
The Pauli basis consists of four Hermitian matrics I, X, Y and Z
introduced in Figure 2.1. These operators form a complete basis for
the space of 2 × 2 complex matrices. For N -qubit systems, the tensor
products of these single-qubit operators span the space of 2N × 2N
48 CHAPTER 2. BASICS OF QUANTUM COMPUTING
complex matrix. This makes the Pauli basis essential for representing
quantum states, observables, and their transformations.
Remark
A common challenge across all quantum state tomography (QST)
methods, including linear inversion and MLE, is the exponential com-
putational cost with respect to the number of qubits. Specifically,
the number of parameters to reconstruct grows exponentially with
the system size, making QST methods feasible only for small-qubit
systems in practice. This limitation underscores the need for scal-
able approaches to quantum state characterization in larger quantum
systems.
current partial read-out protocols can be categorized into three classes, i.e.,
sampling, expectation value estimation, and shadow tomography.
Sampling. Sampling involves repeatedly measuring the quantum state in the
computational basis to estimate the probability distribution over bit-strings.
Given a state |ψ⟩, the probability of observing a specific computational basis
|i⟩ is given by
Pr(i) = |⟨ψ|i⟩|2 . (2.57)
The empirical frequency of each outcome from repeated measurements pro-
vides an estimate of Pr(i). Sampling is particularly useful in the following
applications
4 N
X
O= αi Pi , Pi ∈ {I2 , X, Y, Z}⊗N , αi ∈ R. (2.58)
i=1
50 CHAPTER 2. BASICS OF QUANTUM COMPUTING
4N 4N
X X
⟨O⟩ = αi Tr(ρPi ) ≡ αi ⟨Pi ⟩ . (2.60)
i=1 i=1
M
1 X
⟨P̂i ⟩ = rj . (2.61)
M
j=1
The expectation
P value of the observable O is therefore statistically estimated
by ⟨Ô⟩ = K−1
i=0 αi ⟨P̂i ⟩.
2.3. QUANTUM READ-IN AND READ-OUT PROTOCOLS 51
Remark
A key step in the process is to measure the quantum system in the ba-
sis of the eigenstates of Pi . If Pi is diagonal in the computational basis
(e.g., a tensor product of Pauli-Z operators), we can directly measure
the state without additional operations. Otherwise (e.g., for Pauli-X
or Pauli-Y operators), we need to apply a unitary transformation to
rotate the quantum state into the desired basis. Specifically, when
measuring in the Pauli-X basis (i.e., |+⟩ and |−⟩), a Hadamard gate
H is applied to the state ρ, i.e.,
ρ′ = HρH. (2.62)
ρ′ = S † HρHS. (2.63)
a
|0⟩ 0
UA A|ψ⟩
|ψ⟩ ∥A|ψ⟩∥
Here, ∥ · ∥ represents the spectral norm, i.e., the largest singular value of the
matrix.
Fact 2.21. (Block encoding via the linear combination of unitaries (LCU)
method, Gilyén et al. (2019)). Suppose that A can be written in the form
X
A= αk Uk , (2.65)
k
where {αk } are real numbers and Uk are some easily prepared unitaries such
as Pauli strings. Then, the LCU method allows us to have the access to two
54 CHAPTER 2. BASICS OF QUANTUM COMPUTING
unitaries, i.e.,
X
USEL = |k⟩⟨k| ⊗ Uk , (2.66)
k
1 X√
UPREP : |0⟩ → p αk |k⟩ , (2.67)
∥⃗
α ∥1 k
where α⃗ = (α1 , α2 , . . . ).
†
After simple mathematical analysis, one can obtain U = (UPREP ⊗
I2N )USEL (UPREP ⊗ I2N ) is a (∥⃗α∥1 , m, 0)-block-encoding of A. Here, I2N
is the identity operator of N -qubit size and ∥ · ∥1 denotes the ℓ1 norm of a
given vector.
Similar to the definition of block encoding, we can also define the state
preparation encoding.
Definition 2.22 (State preparation encoding Guo et al. (2024a)). We say
a unitary Uψ is an (α, a, ϵ)-state-encoding of an N -qubit quantum state |ψ⟩
if
∥|ψ⟩ − α(⟨0a | ⊗ I)Uψ |0a+N ⟩∥∞ ≤ ϵ, (2.68)
where ∥ · ∥∞ denotes the infinity norm of the given vector.
More straightforwardly, the (α, a, ϵ)-state-encoding Uψ prepares the state
1 p
Uψ |0⟩ |0⟩ = |0⟩ |ψ ′ ⟩ + 1 − α2 |1⟩ |bad⟩ ,
α
′
where ∥|ψ ⟩ − |ψ⟩∥∞ ≤ ϵ and |bad⟩ is an arbitrary quantum state. One can
further prepare the state |ψ ′ ⟩ by using O(α) times of amplitude amplification
(Brassard et al., 2002). The state preparation encoding can be understood
as a specific case of the block encoding, i.e., it is the block encoding of a
N
C2 ×1 matrix.
FactP 2.24 (Linear combination of block encoding, Gilyén et al. (2019)). Let
A = k xk Ak be an s-qubit operator with β ≥ ∥⃗x∥1 and ε1 > 0, where ⃗x is
the vector of coefficients. Suppose we have access to
X
PL |0⟩ = ck |k⟩ , (2.69)
k
X
PR |0⟩ = dk |k⟩ , (2.70)
k
!
X X
W = |k⟩⟨k| ⊗ Uk + Is − |k⟩⟨k| ⊗Ia ⊗ Ib , (2.71)
k k
P ∗
where − xk | ≤ ε1 and Uk is an (α, a, ε2 )-block-encoding of Ak .
k |βck dk
Then we can implement an (αβ, a + b, αε1 + βε2 )-block-encoding of A by
using one time of W, PL , and PR .
These results can be verified via direct computation. Another arithmetic
rule broadly employed in quantum machine learning is the Hadamard prod-
uct, a.k.a, the element-wise product. The following lemma exhibits how to
achieve this operation via the block encoding framework.
Lemma 2.25 (Hadamard product of the block encoding unitaries, Guo et al.
N N
(2024a)). With N ∈ N, consider two matrices A, B ∈ C2 ×2 , and assume
that we have an (α, a, δ)-encoding UA of matrix A and (β, b, ϵ)-encoding UB
of matrix B, then we can construct an (αβ, a + b + N, αϵ + βδ)-encoding of
matrix A ◦ B corresponding to the Hadamard product of A and B.
Proof sketch of Lemma 2.25. For simplicity, we only consider the perfect
case, i.e., no errors. Refer to Ref. (Guo et al., 2024a) for the proof details
under the more general cases.
The intuition for achieving the Hadamard product is that all the needed
elements can be found in the tensor product, i.e.,
(⟨0a+b | ⊗ I22N )(I2b ⊗ UA ⊗ I2N )(I2a ⊗ UB ⊗ I2N )(|0a+b ⟩ ⊗ I22N ) (2.72)
A⊗B
= .
αβ
To this end, the question is reduced to finding proper permutation uni-
taries that can shift the required elementsPto the correct positions to achieve
d−1
the Hadamard product. Denote P ′ = i=0 |i⟩⟨i| ⊗ |0⟩⟨i|. As proved by
Zhao et al. (2021), the tensor product of A and B can be reformulated to
the Hadamard product via P , i.e.,
P ′ (A ⊗ B)P ′† = (A ◦ B) ⊗ |0⟩⟨0|.
56 CHAPTER 2. BASICS OF QUANTUM COMPUTING
Pd−1
However, P ′ is not a unitary. Instead, we consider P = i,j=0 |i⟩⟨i| ⊗
|i ⊕ j⟩⟨j|, which can be easily constructed by using N CNOT gates, i.e.,
one CNOT gate between each pair of qubits consisting of one qubit from
the first register and the corresponding qubit from the second register. By
direct computation, we have
Proof sketch of Lemma 2.27. This can be achieved by finding a good poly-
nomial approximation for the function 1/x. One can not find such a poly-
nomial on the whole interval [−1, 1], however, such a polynomial exists on
the interval [−1, −δ] ∪ [δ, 1] for some δ > 0.
Basis encoding
PennyLane provides built-in support for basis encoding through its ‘Ba-
sisEmbedding’ function. Below is the Python code demonstrating the basis
encoding for the integer 6.
1 import pennylane as qml
2
3 dev = qml . device ( " default . qubit " , range (3) )
4 @qml . qnode ( dev )
5 def circuit ( x ) :
6 qml . BasisEmbedding (x , range (3) )
7 return qml . state ()
8
9 # Call the function
10 circuit (6)
Amplitude encoding
PennyLane offers built-in support for amplitude encoding via the ‘Ampli-
tudeEmbedding’ function. Below is a Python example demonstrating am-
plitude encoding for a randomly generated complex vector.
1 import pennylane as qml
2 import numpy as np
3
4 # Number of qubits
5 n_qubits = 8
6
2.5. CODE DEMONSTRATION 59
Angle encoding
PennyLane provides built-in support for angle encoding via the ‘AngleEm-
bedding’ function. Below is a Python example demonstrating angle encoding
for a randomly generated real vector.
1 import pennylane as qml
2 import numpy as np
3
4 # Number of qubits
5 n_qubits = 8
6
7 # Define a quantum device with 8 qubits
8 dev = qml . device ( " default . qubit " , wires = n_qubits )
9
10 @qml . qnode ( dev )
11 def circuit ( x ) :
12 qml . AngleEmbedding ( features =x , wires = range ( n_qubits ) ,
rotation = " X " )
13 return qml . state ()
14
15 # Generate a random real vector of length n_qubits
16 x = np . random . uniform (0 , np . pi , ( n_qubits ) )
17
60 CHAPTER 2. BASICS OF QUANTUM COMPUTING
computer (Liu et al., 2021a; Childs et al., 2021; An et al., 2021; Jin et al.,
2022; Shang et al., 2024). This remains an active research field. Quantum
eigenvalue processing, proposed by (Low and Su, 2024), focuses on matri-
ces with real spectra and Jordan forms, in which they prepare the Faber
history state to achieve efficient eigenvalue transformation over the complex
plane. (An et al., 2023, 2024) shows that simulating a general class of non-
unitary dynamics can be achieved by the linear combination of Hamiltonian
simulation (LCHS).
Another approach is to broaden the range of functions that can be im-
plemented by quantum linear algebra. Quantum phase processing, proposed
by (Wang et al., 2023b), can directly apply arbitrary trigonometric trans-
formations to eigenphases of a unitary operator. Similar results have been
independently obtained by Motlagh and Wiebe (2024). In addition, Rossi
and Chuang (2022) investigates how to implement multivariate functions.
For the application, a representative example is the multivariate state prepa-
ration achieved by (Mori et al., 2024), enabling the amplitude encoding of
classical multivariate data.
In Chapter 2.4, we introduce the concept of diagonal block encoding,
which can convert a state preparation unitary into a block encoding. As the
efficient construction of block encodings is a prerequisite for achieving end-
to-end quantum advantage, an important research direction is to investigate
which types of matrices can be efficiently prepared. By leveraging state-
of-the-art techniques in quantum state preparation (Zhang et al., 2022a;
Sun et al., 2023) and the linear combination of unitaries (Childs and Wiebe,
2012), it is possible to efficiently construct block encodings for certain classes
of matrices (Guseynov and Liu, 2024; Guseynov et al., 2024). Additionally,
explicit constructions have been explored for specific types of sparse matrices
(Camps et al., 2023).
66 CHAPTER 2. BASICS OF QUANTUM COMPUTING
Chapter 3
67
68 CHAPTER 3. QUANTUM KERNEL METHODS
could enable the detection of patterns that are difficult or impractical for
classical models to capture. By leveraging quantum circuits, we can poten-
tially access new regions of the feature space, leading to improved pattern
recognition capabilities and, consequently, better learning performance.
These insights motivate the development of quantum kernel meth-
ods, where both the hidden feature map and the kernel function are im-
plemented on a quantum computer. By harnessing the unique properties
of quantum mechanics, such as superposition and entanglement, quantum
kernel methods have the potential to surpass their classical counterparts in
specific machine learning tasks, particularly those involving highly complex
or subtle patterns. This could result in more powerful models with enhanced
generalization capabilities.
In this chapter, we provide a step-by-step explanation of the transition
from classical kernel machines to quantum kernel machines in Chapter 3.1
and Chapter 3.2. Moreover, we discuss the theoretical foundation of quan-
tum kernel machines in Chapter 3.3 from the aspects of expressivity and
generalization of quantum kernel machines. Finally, we demonstrate simple
yet illustrative code implementations on MNIST dataset.
Figure 3.1: Various distributions of data points. The left and middle
panels show the cases where data points can and cannot be separated by a
straight line. The right panel shows that the kernel function could map the
linearly inseparable data points into the high dimensional linearly separable
data points.
separates different classes of data. When the data is linearly separable, this
boundary can be represented as a straight line (in 2D), a plane (in 3D), or
a hyperplane (in higher dimensions), as illustrated in Figure 3.1(a). Math-
ematically, given an input space X ⊂ Rd with d ≥ 1 and a target or output
space Y = {+1, −1}, we consider a training dataset D = {(x(i) , y (i) )}ni=1 ∈
(X × Y)n where each data point x(i) ∈ X is associated with a label y (i) ∈ Y.
For the dataset to be linearly separable, there must exist a vector w ∈ Rd
and a bias term b ∈ R such that
where w⊤ x(i) represents the inner product of vectors w and x(i) . This
means that a hyperplane defined by (w, b) can perfectly separate the two
classes.
However, in real-world scenarios, data is often not linearly separable, as
shown in Figure 3.1(b). The decision boundary required to separate classes
may be curved or highly complex. Traditional linear models struggle with
such non-linear data because they are inherently limited to creating only
linear decision boundaries. This limitation highlights the need for more
flexible approaches.
To address the challenge of non-linear data, one effective strategy is to
transform the input data into a higher-dimensional space where the data
may become linearly separable. This transformation is known as feature
mapping, denoted by
ϕ : x → ϕ(x) ∈ RD , (3.2)
where the original input space X is mapped to a higher-dimensional feature
space RD with D ≥ d. The idea is that, in this higher-dimensional space,
complex patterns in the original data can be more easily identified using
linear models.
However, explicitly computing the feature map ϕ(x) in Eqn. (3.2) can be
computationally expensive, especially if the feature space is high-dimensional
or even infinite-dimensional. Fortunately, many machine learning algorithms
for tasks like classification or regression depend primarily on the inner prod-
uct between data points, which will be explained in Chapter 3.1.2. In the
feature space, this inner product is given by ⟨ϕ(x(i) ), ϕ(x(j) )⟩.
Remark
b.
Here, we see that the feature mapping, which comprises all second-order
terms, takes the form as
√ √
ϕ(x) = [x21 , · · · , x2d , 2x1 x2 , · · · , 2xd xd−1 ]⊤ . (3.5)
Notably, directly computing the kernel function (x⊤ z)2 for a large d is much
more efficient than explicitly calculating the feature map ϕ(x) and then
taking the inner product ϕ(x)⊤ ϕ(z). Specifically, using the kernel function
only requires O(d) time, since it involves computing the dot product in the
original input space Rd . In contrast, if we were to explicitly compute the
3.1. CLASSICAL KERNEL MACHINES 71
transformed feature vectors ϕ(x) and their inner product, the time com-
plexity could increase to O(D), where D is the dimensionality of the feature
space after mapping. For this example of a polynomial kernel with degree
2, D can grow to O(d2 ). This demonstrates the computational efficiency of
using the kernel trick.
Remark
Throughout this manuscript, we use the notations O and Ω to repre-
sent the asymptotic upper and lower bounds, respectively, on the
growth rate of a term, ignoring constant factors and lower-order
terms.
1 X ⊤ 2 λ
n
L(w) = w ϕ(x(i) ) − y (i) + w⊤ w, (3.6)
2 2
i=1
∂L(w) X ⊤
n
= w ϕ(x(i) ) − y (i) ϕ(x(i) ) + λw = 0, (3.7)
∂w
i=1
From this, we see that the solution for w can be expressed as a linear
combination of the training data’s feature vectors
n n
1X ⊤ X
w=− (w ϕ(x(i) ) − y (i) )ϕ(x(i) ) = a(i) ϕ(x(i) ) := Φ⊤ a, (3.8)
λ
i=1 i=1
72 CHAPTER 3. QUANTUM KERNEL METHODS
where Φ = [ϕ(x(1) ), · · · , ϕ(x(n) )]⊤ is the design matrix, whose i-th row is
given by ϕ(x(i) )⊤ . Here, the coefficients a(i) are functions of w, defined as
1
a(i) = − (w⊤ ϕ(x(i) ) − y (i) ). (3.9)
λ
Thus, instead of directly optimizing w, we can reformulate the problem in
terms of the parameter vector a, giving rise to a dual representation. By sub-
stituting w = Φ⊤ a into the original objective function L(w) in Eqn. (3.6),
we obtain
1 1 λ
L(a) = a⊤ ΦΦ⊤ ΦΦ⊤ a − a⊤ ΦΦ⊤ y + y ⊤ y + a⊤ ΦΦ⊤ y, (3.10)
2 2 2
where y = (y (1) , · · · , y (n) )⊤ denotes the vector representation of n training
labels. We define the kernel matrix K = ΦΦ⊤ , where each element is given
by
Kij = ϕ(x(i) )⊤ ϕ(x(j) ) = k(x(i) , x(j) ), (3.11)
using kernel function k(x, x′ ) defined by Eqn. (3.3). The objective function
in terms of a simplifies to
1 1 λ
L(a) = a⊤ K 2 a − a⊤ Ky + y ⊤ y + a⊤ Ky, (3.12)
2 2 2
Setting the gradient of L(a) with respect to a to zero give us
not seem advantageous when n > d, the true benefit of the dual formulation
lies in its ability to leverage the kernel trick. By expressing the solution
in terms of the kernel function, we avoid the explicit computation of the
feature vectors ϕ(x). This allows us to implicitly utilize feature spaces of
very high, or even infinite, dimensionality, enabling the model to capture
complex, non-linear relationships in the data without the associated com-
putational cost.
Remark
We standardize the notation used throughout this chapter to help
readers follow the content more easily. The kernel function is rep-
resented by the lowercase letter k, or with subscripts kQ and kC .
The kernel matrix is denoted by the capital letter K, or with sub-
scripts KQ and KC . Additionally, we use the bold lowercase letter
k(x) to represent the vector of kernel values, where each element
is given by kj (x) = k(x(j) , x), corresponding to the training points
x(j) ∈ {x(1) , . . . , x(n) }.
with ai > 0 if and only if for any square-integrable function c, the following
condition holds: Z Z
c(x)c(x′ )k(x, x′ )dxdx′ ≥ 0. (3.17)
X X
Example 3.4 (Gaussian kernels). The Gaussian kernel (or Radial Ba-
sis Function, RBF) is one of the most widely used kernels, defined as
′ ′ ∥x − x′ ∥
∀x, x ∈ R , k(x, x ) = exp −
d
, (3.20)
2σ 2
Remark
Support Vector Machines (SVMs) are a well-known algorithm that
heavily relies on kernel methods and are primarily used for classi-
fication tasks. The objective of an SVM is to identify the optimal
hyperplane that separates data points from different classes with the
maximum margin. The margin is defined as the distance between
the hyperplane and the closest data points from each class, known as
support vectors. SVMs can be applied to both linear and non-linear
76 CHAPTER 3. QUANTUM KERNEL METHODS
⋯
⋯
𝑥 (𝑗) |0⟩
|0⟩
⋯ 𝑈(𝑥 (𝑖) ) 𝑈 † (𝑥 (𝑗) )
|𝜓(𝑥 (𝑖) )⟩ |0⟩
|0⟩
|0⟩ 𝑈(𝑥) ⋯ |𝜓(𝑥 (𝑗) )⟩
|0⟩
Quantum feature space ℋ Quantum kernel
ϕ : X → F,
ϕ(x) = |ϕ(x)⟩ ⟨ϕ(x)| = ρ(x), (3.22)
kQ : X × X → R,
2
kQ (x, x′ ) = Tr(ρ(x)ρ(x′ )) = ⟨ϕ(x)|ϕ(x′ )⟩ . (3.23)
To justify the term ‘kernel’, we need to show that the quantum kernel is
indeed a positive definite function. A quantum kernel can be expressed as
the product of a complex-valued kernel k̂Q (x, x′ ) = ⟨ϕ(x)|ϕ(x′ )⟩ ∈ C and
78 CHAPTER 3. QUANTUM KERNEL METHODS
its complex conjugate k̂Q (x, x′ )∗ = ⟨ϕ(x)|ϕ(x′ )⟩∗ = ⟨ϕ(x′ )|ϕ(x)⟩. Since the
product of two kernels is known to be a valid kernel, it suffices to show that
k̂Q (x, x′ ) is a valid complex-valued kernel and satisfies positive definiteness.
For any x(i) ∈ X , i = 1, · · · , n, and any coefficients ci ∈ C, we have
X X
ci c∗j k̂Q (x(i) , x(j) ) = ci c∗j ⟨ϕ(x(i) )|ϕ(x(j) )⟩
i,j i,j
!
X X
= ci ⟨ϕ(x(i) )| c∗j |ϕ(x(j) )⟩
i j
2
X
= c∗i |ϕ(x(i) )⟩ ≥ 0. (3.24)
i
(a) (b)
|0⟩ H H
Figure 3.3: Two methods for computing the inner product of the
kernel. (a) Loschmidt echo test. (b) Swap test.
Remark
The efficiency discussed here refers to the computational time within
the respective classical or quantum frameworks. Specifically,
where ∥x∥2 is the Euclidean norm. The related quantum kernel is given
by
k(x, x′ ) = | ⟨x|x′ ⟩ |2 = |⟨x, x′ ⟩|2 . (3.29)
Proof sketch of Theorem 3.12. The assumption that the generator G is di-
agonal could be made without loss of generality because one can diagonalize
Hermitian operators as G = V e−ixi Σ V † with
e−ixi λ1 0 ··· 0
0 e−ixi λ2 ··· 0
e−ixi Σ =
···
,
(3.35)
···
0 ··· 0 e−ixi λm
k(x, x′ )
= ⟨ϕ(x′ )|ϕ(x)⟩
′ ′ 2
†
= ⟨0| W1† (e−ix1 Σ )† · · · (e−ixd Σ )† Wd+1 Wd+1 e−ixd Σ · · · e−ix1 Σ W1 |0⟩
′ ′ 2
= ⟨0| W1† (e−ix1 Σ )† · · · (e−ixd Σ )† e−ixd Σ · · · e−ix1 Σ W1 |0⟩
m
X m
X ′ ′
= e−i(λj1 x1 −λk1 x1 +···+λjd xd −λkd xd )
j1 ,··· ,jd =1 k1 ,··· ,kd =1
2
(1k ) (k k ) ∗ (j j ) (j 1)
× W1 1 · · · Wd d−1 d Wd d d−1 · · · W1 1
2
XX
x′ )
= e−i(Λj x−Λk (ωk )∗ ωj
j k
XXXX ′
= e−i(Λj −Λl )x ei(Λk −Λh )x (ωk ωh )∗ ωj ωl , (3.36)
j k h l
(ab)
Here, the scalars Wi refer to the element ⟨a| Wi |b⟩ of the unitary operator
Wi , the bold multi-index j summarizes the set (j1 , · · · , jd ) and Λj is a vector
containing the eigenvalues selected by the multi-index (and similarly for
k, h, l ).
3.2. QUANTUM KERNEL MACHINES 85
The frequency set Ω contains all vectors {Λj − Λl } with Λj = (λj1 , · · · , λjd )
and λj1 , · · · , λjd ∈ [1, · · · , m].
We summarize the various strategies for the construction of quantum
feature mappings and quantum kernels in Table 3.2.
Table 3.2: Overview of typical data encoding strategies and their quantum
kernels. The input domain is assumed to be the x = (x1 , · · · , xd ) ∈ X ⊂ Rd .
Encoding Qubits Dimension Quantum Kernel k(x, x′ )
Basis encoding d 2d δx,x′
Amplitude encoding ⌈log2 (d)⌉ d |x† x′ |2
Qd
Angel encoding d 2d | cos(xk − x′k )|2
Pk=1 −isx itx′
General angle encoding d 2d s,t∈Ω e e cst
Remark
After obtaining the quantum kernel matrix KQ for a given training
dataset {(x(i) , y (i) )}ni=1 , we can use it to perform regression or classi-
fication tasks in a manner similar to the classical kernel methods. In
particular, as discussed in Chapter 3.1.2, consider the linear regression
model given by
1 X ⊤ 2 λ
n
L(w) = w · ϕQ (x(i) ) − y (i) + w⊤ · w, (3.38)
2 2
i=1
𝜽(𝟎) ℋ
ℋ𝑄
Target function
𝜽∗ ⋯
𝜽∗
𝜽(𝑻) Optimization path
1| < ε. These additional factors, explained below, do not impede the uni-
versality of the theorem.
Moreover, the statement that Eqn. (3.40) holds for almost all x, x′ ∈ X
stems from measure theory. It signifies that the inequality is valid “except
on sets of measure zero,” or equivalently “with probability 1.” In other
words, while adversarial instances of x, x′ ∈ X may exist for which the
inequality does not hold, such instances are so sparse that the probability of
encountering them when sampling from the relevant probability distribution
is zero.
Last, Theorem 3.13 establishes that any kernel function can be approx-
imated as a quantum kernel up to a multiplicative and an additive factor
using a finite number of qubits.
Before presenting the proof of this theorem, let us first introduce Algo-
rithm 1, which maps classical vectors to quantum states. These quantum
states can then be used to evaluate Euclidean inner products as quantum
kernels. Then, we demonstrate Lemma 3.14 and Lemma 3.15, which sep-
arately formalize the correctness and runtime complexity of Algorithm 1,
as well as establish the relationship between the Euclidean inner product
of encoded real vectors and the Hilbert-Schmidt inner product of the corre-
sponding quantum states.
Proof of Lemma 3.14. The proof begins by expanding the state as follows
P4N −1 N −1
4X N −1
4X
I + i=1 ri Pi 1
N
= N |ri |I + ri Pi , (3.42)
2 2
i=1 i=1
N
where the first equality follows that ∥r∥1 = 1 and r ∈ R4 −1 . Rewriting
the above equation using sign(ri ) yields
P4N −1 N −1
4X N −1
4X
I + i=1 ri Pi 1
N
= N |ri |I + |ri |sign(ri )Pi
2 2
i=1 i=1
4N −1
1 X
= |ri |(I + sign(ri )Pi ) ⪰ 0. (3.43)
2N
i=1
P
Here, it is used that i |ri | = ∥r∥1 = 1 and I±Pi ≥ 0 for all Pauli operators
Pi . Notice that efficiently preparing I + Pi can be achieved by rotating each
qubit’s |0⟩ basis state to the corresponding Pauli basis and flipping the
necessary qubits individually. Since this state is a convex combination of
quantum states, it can be efficiently prepared by mixing, when the number
of terms is polynomial.
Proof of Lemma 3.15. The proof utilizes the following principles: (1) The
trace is linear, and the trace of a tensor product equals the product of traces.
(2) All Pauli words are traceless except for the identity, and each Pauli
operator is its own inverse. Hence, the product of distinct Pauli operators
is also traceless.
90 CHAPTER 3. QUANTUM KERNEL METHODS
Lemma 3.15 clarifies the origin of the extra factors in Theorem 3.13. In
particular, the 2N multiplicative factor is unproblematic, as N ≤ O(log(d))
and the methods are designed to scale polynomially with d. Moreover, the
quantum state ρr is generally mixed but can be efficiently prepared. The
mapping is injective but not surjective.
With these results in place, we now present the proof of Theorem 3.13.
Proof of Theorem 3.13. The proof follows from a corollary of Mercer’s theo-
rem and the universality of quantum computing. First, by a direct corollary
of the Mercer’s Theorem (i.e., Fact 3.1) which states that an arbitrary kernel
k admits a uniformly convergent expansion of the form in Eqn. (3.16), it is
ensured that there exists a finite-dimensional feature map Φm : X → Rm
such that
k(x, x′ ) − ⟨Φm (x), Φm (x′ )⟩ < ε. (3.48)
Without loss of generality, it is assumed that ∥Φm (x)∥ = 1 for all x ∈ X .
The quantum state ρΦm can then be prepared, which requires ⌈log4 (m + 1)⌉
qubits. By preparing two such states—one for Φm (x) and one for Φm (x′ )—
their inner product can be computed as the Hilbert-Schmidt inner product
of the quantum states, as shown in Lemma 3.15. This leads to
⟨Φm (x), Φm (x′ )⟩ = 2N Tr ρΦm (x) ρΦm (x′ ) − 1. (3.49)
3.3. THEORETICAL FOUNDATIONS OF QUANTUM KERNEL MACHINES91
For reference, it is noted that Tr ρΦm (x) ρΦm (x′ ) can be computed using
the SWAP test to an additive precision determined by the number of mea-
surement shots. This allows us to approximate the result efficiently to any
desired polynomial additive precision. Consequently, it follows that
k(x, x′ ) − 2N Tr ρΦm (x) ρΦm (x′ ) + 1 < ε, (3.50)
for almost all x, x′ ∈ X . This completes the proof.
We remark that Theorem 3.13 does not aim to demonstrate any quan-
tum advantage but rather establishes the ultimate expressivity of quantum
kernels. The theorem guarantees the existence of a quantum kernel us-
ing a finite number of qubits but does not address how quickly the num-
ber of required qubits grows with increasing computational complexity of
the kernel function k or with decreasing approximation error ε > 0. The
number of qubits N will depend on certain properties of the kernel k and
the approximation error ε. For instance, if the required number of qubits
scales exponentially with these parameters, Theorem 3.13 would have lim-
ited practical utility. Similarly, the time required to find such a quantum
kernel approximation-independent of the memory and runtime requirements
for preparing the feature vectors and computing their inner product—must
also be considered.
Remark
Although Theorem 3.13 establishes that all kernel functions can be
realized as quantum kernels, there may still exist kernel functions
that cannot be realized efficiently as quantum kernels. This observa-
tion requires us to identify quantum kernels that can be computed
efficiently on quantum computers, i.e., in polynomial time.
where y = [y (1) , ..., y (n) ]⊤ refers to the vector of labels and K ∈ Rn×n is the
kernel matrix, and the second equality follows that Φ = [ϕ(x(1) ), · · · , ϕ(x(n) )]† .
Moreover, the norm of the optimal parameters has a simple form for the case
of λ → 0, i.e.,
∥w∗ ∥22 = y ⊤ K −1 y. (3.54)
We now expose the prediction error of these learning models, i.e.,
In the context of learning theory, the upper bound of the expected pre-
diction error defined in Eqn. (3.55) (a.k.a, expected risk) is achieved
by separately analyzing the upper bounds of the training error (a.k.a,
empirical risk) and the generalization error, i.e.,
n n
1X 1X
Ex∼D ϵw∗ (x) = ϵw∗ (x(i) ) + Ex∼D ϵw∗ (x) − ϵw∗ (x(i) ) .
n n
i=1 i=1
| {z } | {z }
Training error Generalization error
(3.56)
This decomposition stems from the fact that data distribution D is
inaccessible in most scenarios.
Moreover, combining with the expression for the optimal w∗ given in Eqn. (3.53),
we can obtain the upper bound of training error in terms of the kernel matrix
K and hyper-parameter λ, i.e.,
n
r
1X λ2 y ⊤ (K + λIn )−2 y
ϵw∗ (x(i) ) ≤ . (3.58)
n n
i=1
We can see that when λ = 0 and K are invertible, the training error is zero.
However, the hyper-parameter is usually set as λ > 0 in practice.
• Generalization error. The derivation of generalization error is more com-
plicated than training error, which involves a basic theorem in statistic and
learning theory as presented below.
Fact 3.16 (Theorem 3.3, Mohri (2018)). Let G be a family of function map-
pings from a set Z to [0, 1]. Then for any δ > 0, with probability at least 1−δ
94 CHAPTER 3. QUANTUM KERNEL METHODS
n
" n
# r
1X 1 X log(2/δ)
Ez g(z) ≤ g(z (i) ) + 2Eσ sup σi g(z (i) ) + 3 , (3.59)
n g∈G n 2n
i=1 i=1
For kernel functions defined in Eqn. (3.55), the set Z refers to the space
of input vector with z (i) = x(i) drawn from some input distribution. Each
function g would be equal to ϵw /α for some w, where ϵw is defined in
Eqn. (3.55) and α is a normalization factor such that the range of ϵw /α is
[0, 1]. Without loss of generality, we assume that α = 1. For any specific
parameter w, consider the special case of G with setting Gw = {ϵv | ∀ ∥v∥ ≤
∥w∥}. Then we have the upper bound of generalization error for the optimal
parameter,
n
1X
Ex ϵ
w∗ (x) − ϵw∗ (x(i) )
n
i=1
" n
# r
1 X log(2∥w∗ ∥/δ)
≤2Eσ sup σi ϵv (x(i) ) + 3 . (3.60)
∥v∥≤∥w∗ ∥ n i=1
2n
where the first inequality follows that ϵv (x(i) ) is Lipschitz continuous with
respect to (w∗ )† · ϕ(x(i) ) with Lipschitz constant 1, the second inequality
follows direct algebra operation. For the detailed simplification processes,
refer to Lemma 1 of Huang et al. (2021a).
In conjunction with Eqn. (3.60), Eqn. (3.61), and the expression of the
optimal parameter w∗ given in Eqn. (3.53), we can reach the final upper
3.3. THEORETICAL FOUNDATIONS OF QUANTUM KERNEL MACHINES95
Remark
The upper bound of the prediction error for kernel methods defined
in Eqn. (3.55) refers to
r
λ2 y ⊤ (K + λIn )−2 y
Ex∼D ϵw∗ (x) ≤ O +
| {zn }
Training error
r r !
y ⊤ (K + λIn )−1 K(K + λIn )−1 y log(1/δ)
+ , (3.63)
| n {z n }
Generalization error
where K is a specific kernel related to the learning models, y =
[y (1) , · · · , y (n) ] refers to the label vector of n training data. For the
special case of λ = 0, the training error is zero, and the prediction
error reduce to the generalization error with a simple form
r r !
y ⊤ K −1 y log(1/δ)
Ex∼D ϵw∗ (x) ≤ O + . (3.64)
n n
We remark that the derived upper bound of the prediction error ap-
plies to both classical and quantum kernels, as we have not imposed any
restrictions on the kernel matrix K during the derivation.
sK (y) = y ⊤ K −1 y, (3.65)
From the second condition, we can see that the potential advantage for
the quantum kernel KQ to predict better than a classical kernel KC depends
on the largest possible separation between sQ (y) and sC (y) for a dataset.
Huang et al. (2021a) define a geometry metric, namely asymmetric ge-
ometric difference, to characterize this separation for a fixed training
dataset, which is given by
r
p p
gCQ = g(KC ||KQ ) = KQ (KC−1 ) KQ , (3.66)
∞
3.3. THEORETICAL FOUNDATIONS OF QUANTUM KERNEL MACHINES97
We now elucidate how to explicitly construct such a data set to enable the
maximal separation between the model complexity of quantum kernels and
classical kernels, as indicated by the geometry test in Figure 3.5. To separate
between quantum and classical models related to kernel matrix KQ and KC ,
we consider that the ratio between sC and sQ is as large as possible for a
particular choice of targets y (1) , · · · , y (n) . This could be achieved by solving
the optimization problem
sC y ⊤ K −1 y
minn = minn ⊤ C−1 , (3.67)
y∈R sQ y∈R y KQ y
This approach allows the quantum kernel estimation to use the same number
of qubits required for the quantum feature mapping of the classical vector
x.
Next, we provide an example demonstrating the workflow of applying
quantum kernels for classification tasks on the MNIST dataset, with step-
by-step code implementation.
perplexity =30)
6 label2name = {
7 0: ’3 ’ ,
8 1: ’6 ’
9 }
10 mnist_tsne = tsne . fit_transform ( X )
11 for label in np . unique ( labels ) :
12 indices = labels == label
13 plt . scatter ( mnist_tsne [ indices , 0] , mnist_tsne [
indices , 1] , cmap = ’ coolwarm ’ , s =20 , label = f ’
Number ␣ { label2name [ label ]} ’)
14
15 # Add labels and legend
16 plt . title ( "t - SNE ␣ Visualization ␣ of ␣ Two ␣ Classes ␣ (3 ␣ and ␣
6) " )
17 plt . xlabel ( "t - SNE ␣ Dimension ␣ 1 " )
18 plt . ylabel ( "t - SNE ␣ Dimension ␣ 2 " )
19 plt . legend ()
20
21 plt . tight_layout ()
22 plt . show ()
23
0
20
40
60
80
75 50 25 0 25 50 75 100
t-SNE Dimension 1
3 for a in A :
4 row = []
5 for b in B :
6 row . append ( kernel (a , b , n_qubit ) )
7 mat . append ( row )
8 return np . array ( mat )
Next, we visualize the quantum kernel matrix to gain insight into its
structure.
1 def visualize_kernel (X , y , n_sample ) :
2 X_vis = []
3 for label in np . unique ( y ) :
4 index = y == label
5 X_vis . append ( X [ index ][: n_sample ])
6
7 X_vis = np . concatenate ( X_vis , axis =0)
8 n _sa mp le _p er _c la ss = len ( X_vis ) // 2
9
10 sim_mat = kernel_mat ( X_vis , X_vis )
11 np . save ( ’ code / chapter_4_kernel / sim_mat . npy ’ , sim_mat )
12
13 import matplotlib . pyplot as plt
14 plt . imshow ( sim_mat , cmap = ’ viridis ’ , interpolation = ’
nearest ’)
15
34
35 plt . tight_layout ()
36 plt . show ()
37
38 visualize_kernel ( X_train , y_train , 10)
3-9
Similarity
3-10
6-1
6-2
6-3 0.4
6-4
6-5
6-6
6-7 0.2
6-8
6-9
6-10
3-1
3-2
3-3
3-4
3-5
3-6
3-7
3-8
3-9
3-10
6-1
6-2
6-3
6-4
6-5
6-6
6-7
6-8
6-9
6-10
Sample Index
0.98
0.97
Accuracy
0.96
0.95
0.94
categorized into three key areas: kernel design, theoretical findings, and
applications. Specifically, the advances in kernel design focus on addressing
challenges such as vanishing similarity and kernel concentration by exploring
innovative frameworks. Theoretical studies delve into the limitations and
capabilities of quantum kernels, examining factors such as generalization
error bounds, noise resilience, and their capacity to demonstrate quantum
advantage. Finally, applications of quantum kernels showcase their potential
across diverse domains. In the rest of this section, we separately review the
existing developments within each of these three branches.
Classical neural networks (LeCun et al., 2015) are the foundation of modern
artificial intelligence technologies and have achieved widespread success in
fields such as computer vision (Voulodimos et al., 2018) and natural lan-
guage processing (Otter et al., 2020). However, despite these achievements,
classical neural networks face significant challenges, including excessively
large model sizes and the corresponding high computational costs (Hoff-
mann et al., 2022), especially in terms of energy consumption (de Vries,
2023). These limitations result from their dependence on classical computa-
tional resources, which are becoming increasingly unsustainable as models
grow in complexity.
Quantum neural networks (QNNs) (Jeswal and Chakraverty, 2019) offer
a promising solution by enhancing neural networks with the computational
potential of quantum circuits (Liu et al., 2024a). In QNNs, classical input
data is encoded into quantum states, and quantum gates with trainable pa-
rameters process these states in ways that classical systems cannot easily
replicate. This computational regime leverages quantum mechanics to ex-
plore new forms of pattern recognition and problem-solving that go beyond
classical methods. Thus, QNNs have the potential to outperform classical
neural networks in specific learning tasks (Huang et al., 2022), where the
advantages in processing and learning can be explored.
Despite these promising features, there are challenges in realizing the
full potential of QNNs, such as quantum noise (Peters et al., 2021) and the
requirement for scalable quantum hardware (Acharya et al., 2024). Nonethe-
less, ongoing advancements in quantum hardware and algorithm design
promise QNNs to address the inefficiencies of classical models, especially
in areas such as quantum many-body physics (Gardas et al., 2018) and
113
114 CHAPTER 4. QUANTUM NEURAL NETWORKS
4.1.1 Perceptron
The perceptron model, first introduced by (McCulloch and Pitts, 1943), is
widely regarded as a foundational structure in artificial neural networks, in-
4.1. CLASSICAL NEURAL NETWORKS 115
z = w⊤ x, (4.1)
where w⊤ is the transpose of the weight vector and z is the output of the
weighted layer. A non-linear activation function is then applied to produce
the output neuron ŷ. For the standard perceptron model, the sign function
is typically used as the activation function:
(
1, if z ≥ 0,
ŷ = f (z) = (4.2)
−1, if z < 0.
The perceptron learns from input data by iteratively adjusting its train-
able parameters w. In particular, let D = {(x(a) , y (a) )}na=1 be the training
dataset, where x(a) represents the input features of the a-th example, and
116 CHAPTER 4. QUANTUM NEURAL NETWORKS
y (a) ∈ {−1, 1} denotes the corresponding label. When the perceptron out-
puts a prediction ŷ (s) , the parameters are updated accordingly, i.e.,
The training process is repeated iteratively until the error reaches a prede-
fined threshold.
Perceptrons can perfectly classify linearly separable data with a finite
number of mistakes, as stated in Theorem 4.1.
w∗ ⊤ w(t) − w∗ ⊤ w(t − 1)
= y (s,t) − ŷ (s,t) w∗ ⊤ x(s,t)
= 2y (s,t) w∗ ⊤ x(s,t) ≥ 2γ, (4.4)
where Eqn. (4.4) is derived by noticing the sample (x(s,t) , y (s,t) ) is misclas-
sified with ŷ (s,t) ̸= y (s,t) and y (s,t) , ŷ (s,t) ∈ {−1, 1}. By considering the
initialization w(0) = 0, the norm of the parameter after the t-th step can
be bounded by
where Eqn. (4.5) is follows from the condition ∥w∗ ∥ = 1. Eqn. (4.7) is
4.1. CLASSICAL NEURAL NETWORKS 117
where Eqn. (4.8) follows from the weight update rule in Eqn. (4.3). Eqn. (4.9)
is derived by noticing that y (s,t) ̸= ŷ (s,t) and y (s,t) , ŷ (s,t) ∈ {−1, 1}. Eqn. (4.10)
follows from the condition ∥x(i) ∥ = 1 for all samples. Eqn. (4.11) is derived
by noticing that the sample (x(s,t) , y (s,t) ) is misclassified by the perceptron
with the parameter w(t − 1), i.e.
1
t≤ . (4.13)
γ2
where σ represents the non-linear activation function, and W (ℓ) and b(ℓ)
denotes trainable weight and the bias term, respectively. Similar to the no-
tation z in the perceptron in Chapter 4.1.1, z (a,ℓ+1) denotes the output of
the linear sum in the ℓ + 1-th layer, which is expressed in a more gener-
alized vector form. Therefore, the parameter for the weighted linear sum
is represented in matrix form as W (ℓ) . Various methodologies have been
proposed for implementing non-linear activations, with some common ap-
proaches summarized in Table 4.1.
4.1. CLASSICAL NEURAL NETWORKS 119
∂L(a)
= ŷ (a) − y (a) ,
∂ ŷ (a)
∂L(a) ∂ ŷ (a) ∂L(a) h
(a)
i (a)
(a) (a)⊤ ∂L
= = diag ŷ − ŷ ŷ ,
∂x(a,3) ∂x(a,3) ∂ ŷ (a) ∂ ŷ (a)
∂L(a) ∂x(a,3) ∂L(a) h i (a)
(a,3) (a,3) ∂L
= = diag 1 − z ⊙ z ,
∂z (a,3) ∂z (a,3) ∂x(a,3) ∂x(a,3)
where 1 denotes the vector (1, 1, · · · , 1)⊤ , and ⊙ denotes the element-wise
multiplication (Hadamard product). For convenience, we omit the dimen-
sion of 1 here, which has the same dimension with z (a,3) . Next, the gradient
with respect to the hidden layer can be obtained using the chain rule:
The gradient with respect to the parameters for the input layer is derived
4.1. CLASSICAL NEURAL NETWORKS 121
similarly:
Remark
MLPs involve a large number of parameters due to their fully con-
nected multilayer architecture. This high parameter count enables
MLPs to possess considerable representational power, allowing them
to model complex data distributions. However, the excessive capac-
ity to fit the training data often leads to overfitting (Caruana et al.,
2000), where the MLP captures noise and irrelevant patterns instead
of generalizable features. As a result, MLPs tend to perform poorly
on unseen data, especially when the training set is limited or noisy. To
mitigate this issue, advanced techniques such as dropout (Srivastava
et al., 2014), weight decay (Krogh and Hertz, 1991), and attention
mechanisms (Vaswani, 2017) have been proposed to reduce overfit-
122 CHAPTER 4. QUANTUM NEURAL NETWORKS
d−1 N N
!
1 X O |0⟩ + |1⟩ O
|ϕ0 ⟩ = √ |x⟩ = √ = H |0⟩.
d x=0 n=1
2 n=1
q
2: Let m = ⌊ π4 d
M − 12 ⌋. Apply the following operation:
m
|ϕm ⟩ = H⊗N U0 H⊗N Uf |ϕ0 ⟩.
q
d
O( M (log d + Tf )), where d is the size of the dataset, M is the size of the
solution set, and Tf denotes the time complexity of implementing the oracle
Uf .
Remark
The Grover search achieves a quadratic speed-up in the query com-
plexity of the oracle Uf . It provides a quantum advantage in the
runtime only√if the time complexity of the oracle Uf , denoted as Tf ,
is less than d.
Similarly, the superposition of the states outside the solution set is given by
1 X
|other⟩ = √ |x⟩.
2N − M x|f (x)=0
αk = ⟨target|ϕk ⟩
= ⟨target|H ⊗N U0 H ⊗N Uf |ϕk−1 ⟩
= ⟨target|(2|ϕ0 ⟩⟨ϕ0 | − I)Uf (αk−1 |target⟩ + βk−1 |other⟩)
= ⟨target|(2|ϕ0 ⟩⟨ϕ0 | − I)(−αk−1 |target⟩ + βk−1 |other⟩)
= 1 − 2α02 αk−1 + 2α0 β0 βk−1 ,
βk = ⟨other|ϕk ⟩
= ⟨other|(2|ϕ0 ⟩⟨ϕ0 | − I)(−αk−1 |target⟩ + βk−1 |other⟩)
= 2β02 − 1 βk−1 − 2α0 β0 αk−1 .
q
N
Let the angle θ = arccos 2 2−MN , then by induction, it can be shown that
Example 4.4. For the sample (x(i) , y (i) ) = ([0, 0, 1, 0], 1), the corre-
sponding quantum state is |z (i) ⟩ = |00101⟩, where the last qubit encodes
the label (with “0” for the label “−1”), and the remaining qubits repre-
sent the data vector. When x(i) is a float vector, a similar bit sequence
can be obtained by concatenating the binary representations of the ele-
ments in x(i) .
where f : (w, z (i) ) → {0, 1}. The function outputs 1 if the current percep-
tron model with weight w misclassifies the training sample z (j) ; otherwise,
it outputs 0. Furthermore, we define
Fw = U † (I ⊗ Fw
′
)U, (4.18)
which is used as the oracle Uf in the Grover search. The online quantum
perceptron procedure is given in Algorithm 3. The query complexity of the
online quantum perceptron is provided in Theorem 4.5.
Theorem 4.5 (Online quantum perceptron (Kapoor et al., 2016)). Consider
a training dataset that consists of unit vectors {x(1) , · · · , x(d) } and labels
{y (1) , · · · , y (d) } with a margin γ, Denote by nquant the number of queries to
Fw needed to learn the weight w, such that the training dataset is perfectly
classified with probability at least 1 − ϵ, then
√ !
d 1
nquant ∈ O log 2 .
γ2 γ ϵ
126 CHAPTER 4. QUANTUM NEURAL NETWORKS
For the classical case where the training vectors are uniformly sampled from
the training dataset, the number of queries to fw is bounded by
d 1
Ω(d) ∋ nclass ∈ O 2 log 2 .
γ γ ϵ
Proof of Theorem 4.5. The main idea of the quantum perceptron model in
Algorithm 3 is to replace the procedure of finding the misclassified sample
in classical perceptrons with the Grover search. Due to convergence result
for perceptrons in Theorem 4.1, h = 1, · · · , ⌈ γ12 ⌉ iterations of Steps (3-13)
suffice to update the weight w towards the case of perfect classification.
Therefore, Theorem 4.5 is the direct consequence of the following lemmas
and Theorem 4.1. The query complexity of classical perceptrons has the
lower bound Ω(d), since the model needs to go through the entire dataset
in the worst case.
Lemma 4.6. Given only uniform sampling access to the training dataset,
there exists a classical perceptron that either finds a misclassified sample to
update the weight w or concludes that no such example exists with probability
1 − ϵγ 2 , using O(d log(1/ϵγ 2 )) queries to fw .
Lemma 4.7. The procedure of Steps 3-13 in Algorithm 3 either finds a mis-
classified sample to update the weight w√or concludes that no such example
exists with probability 1 − ϵγ 2 , using O( d log(1/ϵγ 2 )) queries to Fw .
q
Proof of Lemma 4.7. For convenience, denote θa := arccos d−d d , where d0
0
|0⟩
|0⟩
Udata (ρin ) V (θ)
|0⟩
|0⟩
Figure 4.4: Illustration of a QNN. The input state ρin is prepared using
the operation Udata , followed by a variational quantum circuit (VQC) V (θ)
and the measurement operation.
2024; Gao et al., 2024), researchers have devoted considerable effort to devel-
oping and implementing quantum machine learning algorithms optimized for
current and near-term quantum devices (Wang and Liu, 2024). Compared to
fault-tolerant quantum computers, these devices face three primary limita-
tions: quantum noise, limited coherence time, and circuit connectivity con-
straints. Regarding quantum noise, state-of-the-art devices have single-qubit
gate error rates of 10−4 ∼ 10−3 and two-qubit gate error rates of approxi-
mately 10−3 ∼ 10−2 (AbuGhanem, 2024; Gao et al., 2024). The coherence
time is around 102 µs (Acharya et al., 2024; AbuGhanem, 2024; Gao et al.,
2024), primarily limited by decoherence in noisy quantum channels. Regard-
ing circuit connectivity, most superconducting quantum processors employ
architectures that exhibit two-dimensional connectivity patterns and their
variants (Acharya et al., 2024; AbuGhanem, 2024; Gao et al., 2024). Gate
operations between non-adjacent qubits must be executed through interme-
diate relay operations, leading to additional error accumulation. To address
these inherent limitations, the quantum neural network (QNN) framework
has been proposed. Specifically, these QNNs are designed to perform mean-
ingful computations on near-term quantum devices.
Uent Uent
where the function f follows the Eqn. (4.21) and the one-hot vector e(j) has
the same dimension with θ with the j-th element being 1.
!
1
Y j−1
Y
ρ′in = Wj Gi (θi )Wi ρin Wi† Gi (θi )† Wj† ,
i=j−1 i=1
!
L
Y j
Y
O′ = Wi† Gi (θi )† O Gi (θi )Wi .
i=j i=L
where a simple feature map can be constructed via angle encoding, as in-
troduced in Chapter 2.3.1,
N
O N
O
(i)
Uϕ (x ) = RY(x(i)
n ) = exp(−iY x(i)
n /2). (4.24)
n=1 n=1
Denote by O and V (θ) the quantum observable and the VQC, respectively.
The prediction function of the QNN is given by
In the binary classification task, the QNN learns by training the param-
eter θ to minimize the distance between the label y (i) and the prediction
4.3. NEAR-TERM QUANTUM NEURAL NETWORKS 135
ŷ (i) (θ). Specifically, the mean square error (MSE) is used as the loss func-
tion:
1 X (i) 2
n
X n
∗ (i) (i)
θ = argminL(θ), where L(θ) = ℓ(θ, x , y ) = ŷ (θ) − y (i) .
2
i=1 i=1
(4.26)
The gradient of the loss in Eqn. (4.26) can be calculated via the chain rule,
i.e.,
Xn
∇θ L(θ) = ŷ (i) (θ) − y (i) ∇θ ŷ (i) (θ), (4.27)
i=1
where the gradient of the prediction ŷ (i) can be obtained by using the
parameter-shift rule in Theorem 4.9. Consequently, a variety of gradient-
based optimization algorithms, such as stochastic gradient descent (Amari,
1993), Adagrad (Duchi et al., 2011), and Adam (Kingma, 2014), can be
employed to train QNNs.
Remark
The QNN binary classification framework can be naturally extended
to multi-label classification using the one-vs-all strategy. Specifi-
cally, we train k QNN binary classifiers for k classes, with each clas-
sifier distinguishing a specific class from the others.
Remark
The QNN classification framework presented in this section can be
extended to quantum regression learning by incorporating continuous
labels.
Let γ and θ denote the parameters of the discriminator D and the generator
G, respectively. The optimization problem for the quantum patch GAN can
be formulated as:
min max L(Dγ (Gθ (z)), Dγ (x)) := E[log Dγ (x)] + E[log(1 − Dγ (Gθ (z)))].
θ γ x z
(4.33)
|0⟩
Index
Register
|0⟩
|0⟩
Ancillary
Uz
for G |0⟩
UG (θ)
|0⟩
Sample
Register
|0⟩
UD (γ)
|0⟩
Ancillary
for D |0⟩
Figure 4.8: The main structure of the quantum batch GAN. The
figure illustrates the process of generation and training using fake data.
The oracle Uz for encoding latent vectors, the quantum generator UG (θ),
and the quantum discriminator UD (γ) are applied sequentially to the initial
state |0⟩⊗N . Both UG and UD share the same hardware-efficient structure as
shown in Figure 4.7. In the case of real data, the operations Uz and UG (θ)
are replaced by the oracle Ux .
The qubits in the feature register are further partitioned into three parts:
ND qubits for generating quantum samples, NAG qubits for implementing
non-linear operations in the generator Gθ , and NAD qubits for implement-
ing non-linear operations in the discriminator Dγ . For a batch with size
|Bk | = 2NI , two oracles are used to encode the information of latent vectors
and training samples:
U 1 X
z
|0⟩I ⊗ |0⟩F −−→ |i⟩I ⊗ |z (i) ⟩F , (4.34)
2NI
i
U 1 X
x
|0⟩I ⊗ |0⟩F −−→ |i⟩I ⊗ |x(i) ⟩F . (4.35)
2NI
i
4.3. NEAR-TERM QUANTUM NEURAL NETWORKS 139
Remark
For data with M features, state preparation for amplitude encoding
in Ux requires Õ(2NI M ) multi-controlled quantum gates, which is in-
feasible for current quantum devices. This challenge can be addressed
by employing pre-trained shallow circuit approximations of the given
oracle (Benedetti et al., 2019a).
After the encoding stage, a PQC UG (θ) and the corresponding partial
measurement are employed as the quantum generator. Thus, the generated
state corresponding to |Bk | fake samples is obtained as follows:
1 X
|i⟩I ⊗ |z (i) ⟩F
2NI
i
UG (θ) 1 X
−−−−→ |i⟩I ⊗ UG (θ) ⊗ I2NAD |z (i) ⟩F := |ψ(z)⟩
2NI
i
ΠAG
I2NI ⊗ ΠAG ⊗ I2ND +NAD |ψ(z)⟩
−−−→ h i := |Gθ (z)⟩,
Tr I2NI ⊗ ΠAG ⊗ I2ND +NAD |ψ(z)⟩⟨ψ(z)|
Gθ (z (i) ) = Pr(J = 0|I = i), · · · , Pr(J = 2ND − 1|I = i) , (4.36)
where
the case of the real state, the state evolution proceeds as follows:
1 X
|i⟩I ⊗ |x(i) ⟩F
2NI
i
UD (γ) 1 X
−−−−→ N |i⟩I ⊗ I2NAG ⊗ UD (γ)|x(i) ⟩F := |ψ(x)⟩
2 I
i
ΠA I N −NAD ⊗ ΠAG |ψ(x)⟩
−−−D
→ h 2 i := |Dγ (x)⟩,
Tr I2N −NAD ⊗ ΠAG |ψ(x)⟩⟨ψ(x)|
𝛁ℒ ℋ
𝜽(𝟎) Grad info
𝝐 Target function
Optimal Optimal ⋯
𝜽∗
𝜽∗
𝜽(𝑻) Optimization path
While expressivity and generalization ability are crucial for both quan-
tum kernels and QNNs, trainability emerges as an additional consideration
for QNNs due to the introduction of trainable parameters in quantum cir-
cuits. This leads to fundamentally different optimization challenges, where
many existing results from classical ML models no longer apply. Specifi-
cally, trainability refers to a model’s ability to efficiently converge to a good
solution during training, directly influencing the computational cost of train-
ing. In Chapter 4.4.2, we will introduce a well-known challenge in training
QNNs, referred to as the barren plateau problem, where gradients vanish
exponentially as the system size increases, making optimization intractable.
Additionally, we will discuss various strategies to address this issue, offering
practical insights into enhancing the trainability of QNNs.
142 CHAPTER 4. QUANTUM NEURAL NETWORKS
where ℓ(·, ·) refers to the per-sample loss predefined by the learner. Unfortu-
nately, the inaccessible distribution P forbids us to assess the expected risk
directly. In practice, A alternatively learns an empirical hypothesis hθ̂ ∈ H,
as the global minimizer of the (regularized) loss function
n
1X
L(θ, D) = ℓ(hθ (x(i) ), y (i) ) + R(θ), (4.39)
n
i=1
where RGene (hθ̂ ) = R(hθ̂ ) − RERM (hθ̂ ) refers to the generalization error. In
this regard, achieving a small prediction error requires the learning model
to achieve both a small training error and a small generalization error.
4.4. THEORETICAL FOUNDATIONS OF QUANTUM NEURAL NETWORKS143
An overview
Before moving to analyze the training error (ERM) and generalization error
of QNNs rigorously, we first delve into better understanding the meaning of
expressivity and generalization ability of the learning models with the ERM
framework and try to give an intuition about the necessitates and benefits
of exploring such theoretical aspects of QNNs as a special learning model.
In particular, the expressivity could be directly understood as the size
of the hypothesis space H = {hθ : θ ∈ Θ} related to the learning model.
Intuitively, the achievable smallest empirical risk is determined by the ex-
pressivity of learning models. Specifically, a learning model with low ex-
pressivity may not fit the training data with complex patterns, e.g., the
hypothesis space of linear model H = {hθ = θ · x} cannot fit the nonlinear
data {x(i) , (x(i) )2 } perfectly.
In general, the cardinality of the hypothesis space is infinity, as the pa-
rameters θ are continuous. This makes it hard to compare the expressivity
of different learning models. An alternative measure is model complexity,
which measures the richness of the hypothesis space through the structural
factors of the specific learning models, such as the number of parameters,
depth, or architectural design. Remarkably, model complexity is measur-
able and bounded. In this tutorial, we will employ the covering number to
measure the model complexity of QNNs later.
The generalization capability of learning models is directly measured by
the generalization error RGene in Eqn. (4.41). A good generalization ability
means that the learning model predicts well on unseen data as well as on
the training data. In this regard, a small generalization error with a small
training error implicates a small prediction error, as a small generalization
error guarantees that the prediction performance is as well as the training
performance.
In statistical learning theory, it has been well-established that a bias-
variance trade-off governs the interplay between model complexity and gen-
eralization performance for any learning model, highlighting the delicate
balance required for a model to generalize well to unseen data. The rela-
tionship is often depicted by a U-shaped curve, as shown in Figure 4.10.
This curve suggests that there exists an optimal level of model complexity
for improving the generalization ability of any learning model. When under
the point related to optimal expressivity, increasing model complexity im-
proves performance on training data and enhances generalization. However,
beyond a certain point, higher complexity leads to overfitting, resulting in
poor generalization on test data. For QNNs, identifying this optimal level
144 CHAPTER 4. QUANTUM NEURAL NETWORKS
Underfitting Overfitting
Best fit
Error
Model Complexity
of complexity is crucial for achieving the best balance between training per-
formance and generalization.
Expressivity of QNNs
In this chapter, we analyze the generalization error of QNNs through a spe-
cific measure of model complexity: the covering number. By leveraging this
measure, we aim to understand better and characterize the generalization
performance of QNNs.
To elucidate the specific definition of the covering number, we first re-
N N
view the general structures of QNNs. Define ρ ∈ C2 ×2 as the N -qubit
N N
input quantum states, O ∈ C2 ×2 as the quantum observable, U (θ) =
QN g N
l=1 ul (θ) ∈ U(2 ) as the applied ansatz, where θ ∈ Θ are the trainable
parameters living in the parameter space Θ, ul (θ) ∈ U(2k ) refers to the
l-th quantum gate operated with at most k-qubits with k ≤ N , and U(2N )
stands for the unitary group in dimension 2N . In general, U (θ) is formed by
Ngt trainable gates and Ng − Ngt fixed gates, e.g., Θ ⊂ [0, 2π)Ngt . Under the
above definitions, the explicit form of the output of QNN under the ideal
scenarios is
h(θ, O, ρ) := Tr U (θ)† OU (θ)ρ . (4.42)
Given the training data set D = {(ρ(i) , y (i) )}ni=1 and loss function L(θ, D)
defined in Eqn. (4.39), QNN is optimized to find a good approximation
h∗ (θ, O, ρ) = arg minh(θ,O,ρ)∈H L(θ, D) that can well approximate the target
concept, where H refers to the hypothesis space of QNNs with
n o
H = Tr U (θ)† OU (θ)ρ θ ∈ Θ . (4.43)
4.4. THEORETICAL FOUNDATIONS OF QUANTUM NEURAL NETWORKS145
gates Ngt , the number of qubits k the gates acting on, and the type of the
quantum observable O. In the end, we first look at a simpler hypothesis
space consisting of the operator group
n o
Hcirc := U (θ)† OU (θ) θ ∈ Θ , (4.44)
Fact 4.11. Let (H1 , d1 ) and (H2 , d2 ) be two metric spaces satisfying f :
H1 → H2 be bi-Lipschitz such that
where the left inequality requires ϵ ≤ cl cu /2 with cu being the upper bound
of the distance between any two points in H1 , namely, d1 (x, z) ≤ cu for
x, z ∈ H1 .
Fact 4.11 indicates that we can derive the covering number of the metric
space (H, d) by analyzing the covering number of the metric space (Hcirc , dcirc )
and the Lipschitz constants of the mapping between H and Hcirc . Intuitively,
a quantum circuit consisting of a large number of multi-qubit parameterized
gates leads to a complicated QNN with a large model complexity. These in-
tuitions are formalized into Theorem 4.13. Specifically, the result of the cov-
ering number of the metric space (Hcirc , dcirc ) is encapsulated in Lemma 4.12.
Lemma 4.12. Suppose that the employed N -qubit quantum circuit contain-
ing in total Ng gates with Ng > N , each gate ui (θ) acting on most k qubits,
and Ngt ≤ Ng gates in U (θ) are trainable. The ϵ-covering number for the
operator group Hcirc in Eqn. (4.44) with respect to the operator-norm dis-
tance obeys
2k
7Ngt ∥O∥ 2 Ngt
N (Hcirc , ϵ, ∥ · ∥) ≤ , (4.47)
ϵ
where ∥O∥ denotes the operator norm of O.
4.4. THEORETICAL FOUNDATIONS OF QUANTUM NEURAL NETWORKS147
Proof of Lemma 4.12. To measure the covering number the operator group
of Hcirc = {U (θ)† OU (θ) θ ∈ Θ}, one could first consider a fixed ϵ-covering
S for the set N (U (2k ), ϵ, ∥ · ∥) of all possible gates and define the set
Y Y
S̃ := ui (θi ) uj ui (θi ) ∈ S , (4.48)
i∈{Ngt } j∈{Ng −Ngt }
where ui (θi ) and uj specify the trainable and fixed quantum gates in the
employed quantum circuit, respectively. Note that for any circuit U (θ) =
QNg
i=1 ui (θi ), one can always find a Uϵ (θ) ∈ S̃ where each ui (θi ) of trainable
gates is replaced with the nearest element in the covering set S, and the
discrepancy ∥U (θ)† OU (θ) − Uϵ (θ)† OUϵ (θ)∥ satisfies
∥U (θ)† OU (θ) − Uϵ (θ)† OUϵ (θ)∥
≤∥U − Uϵ ∥∥O∥
≤Ngt ∥O∥ϵ, (4.49)
where the first inequality uses the triangle inequality, and the second in-
equality follows from ∥U − Uϵ ∥ ≤ Ngt ϵ.
Therefore, by Definition 4.10, S̃ forms an Ngt ∥O∥ϵ-covering set for Hcirc .
An upper bound for the group S, as established by Barthel and Lu (2018,
22k
Lemma 1), gives |S| ≤ 7ϵ . Since there are |S|Ngt combinations for the
22k Ngt
gates in S̃, it follows that |S̃| ≤ 7ϵ and the covering number for Hcirc
satisfies 22k Ngt
7
N (Hcirc , Ngt ∥O∥ϵ, ∥ · ∥) ≤ . (4.50)
ϵ
An equivalent representation of the above inequality is
2k
7Ngt ∥O∥ 2 Ngt
N (Hcirc , ϵ, ∥ · ∥) ≤ . (4.51)
ϵ
With the established covering number of operator group Hcirc , one could
directly analyze the covering number of the hypothesis space H related to
QNNs, which is encapsulated in the following theorem.
Theorem 4.13. For 0 < ϵ < 1/10, the covering number of the hypothesis
space H in Eqn. (4.43) yields
2k
7Ngt ∥O∥ 2 Ngt
N (H, ϵ, | · |) ≤ , (4.52)
ϵ
148 CHAPTER 4. QUANTUM NEURAL NETWORKS
where the first equality comes from the explicit form of the hypothesis, the
first inequality uses the Cauchy-Schwartz inequality, and the last inequality
employs Tr(ρ) = 1 and
Theorem 4.13 indicates that the most decisive factor, which controls the
complexity of H, is the employed quantum gates in U (θ). This claim is
k
ensured by the fact that the term 22 Ngt exponentially scales the complexity
N (H, ϵ, | · |). Meanwhile, the qubits count N and the operator norm ∥O∥
polynomially scale the complexity of N (H, ϵ, |·|). These observations suggest
a succinct and direct way to compare the expressivity of QNNs with different
quantum circuits. Moreover, the dependence of the expressivity of QNNs on
the type of quantum gates (denoted by the term k) demonstrated that the
expressivity of QNNs depends on the structure information of ansatz such
as the location of different quantum gates and the types of the employed
quantum gates. The expressivity measured by the covering number could
provide practical guidance for designing the circuit structure of QNNs.
where H|S denotes the set of vectors formed by the hypothesis with n ex-
amples in the dataset S. In this regard, the generalization error bound in
Eqn. (4.57) could be obtained by combining the Eqn. (4.58) and Eqn. (4.59)
with direct but tedious calculations, which is omitted here. For details of the
calculations, please refer to the proof of Theorem 2 in Du et al. (2022c).
The assumption used in this analysis is quite mild, as the loss functions
in QNNs are generally Lipschitz continuous and can be bounded above by
a constant C. This property has been broadly employed to understand the
capability of QNNs. The results obtained have three key implications. First,
the generalization bound exhibits an exponential dependence on the term k
and a sublinear dependence on the number of trainable quantum gates Ngt .
This observation reflects the quantum version of Occam’s razor (Haussler
and Warmuth, 1987), where the parsimony of the output hypothesis implies
greater predictive power. Second, increasing the number of training exam-
ples n improves the generalization bound. This suggests that incorporating
more training data is essential for optimizing complex quantum circuits.
Lastly, the sublinear dependence on Ngt may limit the ability to accurately
assess the generalization performance of overparameterized QNNs (Larocca
et al., 2023). Together, these implications provide valuable insights for de-
signing more powerful QNNs.
Fact 4.15 ( Cerezo et al. (2021b)). Let {Wy }y∈Y ⊂ U(d) form a unitary
2-design, and let A, B, C, D : Hw → Hw be arbitrary linear operator. Then
1 X Tr[A] Tr[B]
Tr[Wy AWy† B] = , (4.62)
|Y | d
y∈Y
1 X
Tr[Wy AWy† B] Tr[Wy CWy† D]
|Y |
y∈Y
1
= (Tr[AC] Tr[BD] + Tr[A] Tr[B] Tr[C] Tr[D])
d2 − 1
1
− 2
(Tr[A] Tr[C] Tr[BD] + Tr[AC] Tr[B] Tr[D]), (4.63)
d(d − 1)
1 X
Tr[Wy AWy† BWy CWy† D]
|Y |
y∈Y
1
= 2 (Tr[A] Tr[C] Tr[BD] + Tr[AC] Tr[B] Tr[D])
d −1
1
− (Tr[AC] Tr[BD] + Tr[A] Tr[B] Tr[C] Tr[D]). (4.64)
d(d2 − 1)
Fact 4.15 can be derived from Facts C.4 and C.5 in Appendix C, which
provides a more detailed discussion of unitary designs, potentially of inde-
pendent interest. By applying Fact 4.15, it can be shown that QNNs with
quantum circuits forming 2-designs exhibit barren plateau loss landscapes.
Theorem 4.16 (Adapted from McClean et al. (2018)). Q Consider the loss
function given in Eqn. (4.60), where the QNN V (θ) = L j=1 Vj (θj )Wj with
fixed gate Wj and variational gate Vj (θj ) = exp(−iθj Hj /2). Suppose all
hermitian matrices {Hj } are traceless. For a integer k ∈ [1, L], denote
152 CHAPTER 4. QUANTUM NEURAL NETWORKS
Q QL
U− = k−1j=1 Vj (θj )Wj and U+ = j=k+1 Vj (θj )Wj . Then, if both U− and
U+ form 2-designs, there is
∂f ∂f 1
E = 0, Var ≈ 3N +1 Tr O2 Tr ρ2 Tr Hj2 . (4.65)
∂θk ∂θk 2
h i
f = Tr OV ρV †
h i
= Tr OU− Vk Wk U+ ρU+† Wk† Vk† U−†
h i
† † † †
= Tr U− OU− Vk Wk U+ ρU+ Wk Vk
= Tr O′ exp(−iθk Hk /2)ρ′ exp(iθk Hk /2) ,
where O′ := U−† OU− and ρ′ := Wk U+ ρU+† Wk† . Thus, the gradient could be
calculated as
∂f i h h ii
= Tr O′ Vk ρ′ Vk† , Hk .
∂θk 2
∂f i h h ii
E = E Tr O′ Vk ρ′ Vk† , Hk
U+ ,U− ∂θk 2
i h † h ii
= E Tr U− OU− Vk ρ′ Vk† , Hk
U+ ,U− 2
i hh ii
= E N +1 Tr[O] Tr Vk ρ′ Vk† , Hk (4.66)
U+ 2
= 0, (4.67)
where Eqn. (4.66) follows from Eqn. (4.62), and Eqn. (4.67) is derived by
noticing Tr[[A, B]] = Tr[AB − BA] = 0. Therefore, the variance of the
4.4. THEORETICAL FOUNDATIONS OF QUANTUM NEURAL NETWORKS153
2
∂f ∂f
Var = E
U+ ,U− ∂θk U+ ,U− ∂θk
1 h h ii2
= − EU+ ,U− Tr U−† OU− Vk ρ′ Vk† , Hk
4 h
1 2 i2
′ †
= − E Tr O Tr Vk ρ Vk , Hk
4 × (22N − 1) U+
h i2
1 2 ′ †
+ N +2 2N E Tr[O] Tr Vk ρ V k , Hk (4.68)
2 (2 − 1) U+
h i2
1 2 ′ †
= − Tr O E Tr Vk ρ Vk , Hk , (4.69)
4 × (22N − 1) U+
where Eqn. (4.68) follows from Eqn. (4.63), and Eqn. (4.69) follows from
Tr[O] = 0. Further, it can be shown that
h i2
′ †
E Tr Vk ρ Vk , Hk
U+
2 2
′ † ′ † 2
= 2 E Tr Vk ρ Vk Hk − 2 E Tr Vk ρ Vk (Hk )
U+ U+
2
† † †
= 2 E Tr Vk Wk U+ ρU+ Wk Vk Hk
U+
2
† † † 2
−2 E Tr Vk Wk U+ ρU+ Wk Vk (Hk )
U+
2 2 2
2
= Tr[ρ] Tr[Hk ] + Tr ρ Tr[Hk ]2
22N − 1
2 2 2
− N 2N Tr ρ Tr Hk + Tr[ρ]2 Tr[Hk ]2
2 (2 − 1)
2
− N Tr Hk2 Tr ρ2 (4.70)
2
2N +1
≈ − 2N Tr Hk2 Tr ρ2 , (4.71)
2 −1
where Eqn. (4.70) follows from Eqn. (4.62) and Eqn. (4.64). Eqn. (4.71)
is derived by ignoring minor terms and using Tr[Hk ] = 0. Combining
154 CHAPTER 4. QUANTUM NEURAL NETWORKS
Remark
The influence of barren plateau can be categorized into three folds.
Since the barren plateau could seriously affect the trainability of scaled
QNNs and raise concerns about the utility of QNNs for achieving quan-
tum advantages, researchers have been focused on developing techniques
to address this problem. Existing efforts including specific architecture de-
sign (Cerezo et al., 2021b; Pesah et al., 2021; Zhang et al., 2021b), parameter
initialization schemes (Grant et al., 2019; Zhang et al., 2022b), and advanced
training protocols (Skolik et al., 2021; Haug and Kim, 2021). Here we briefly
introduce two related results with theoretical guarantees.
Fact 4.17 (Shallow hardware-efficient circuits are BP-free, informal ver-
sion adapted from Cerezo et al. (2021b)). Suppose the observable has a local
form in the Pauli basis decomposition. For QNNs employing N -qubit shal-
low hardware-efficient circuits with logarithmic depths, the variance of the
4.5. CODE DEMONSTRATION 155
19
20 return X_train , y_train , X_test , y_test
21 X_train , y_train , X_test , y_test = load_wine ()
0
t-SNE Dimension 2
6
1 0 1 2 3
t-SNE Dimension 1
0 Rot Rot
1 Rot Rot
2 Rot Rot
3 Rot Rot
4 Rot Rot
5 Rot Rot
AngleEmbedding
6 Rot Rot
7 Rot Rot
8 Rot Rot
9 Rot Rot
10 Rot Rot
11 Rot Rot
12 Rot Rot
15 # compute cost
16 cost_train . append ( cost ( param , circuit , X_train ,
y_train ) )
17 cost_test . append ( cost ( param , circuit , X_test , y_test )
)
18
19 # compute accuracy
162 CHAPTER 4. QUANTUM NEURAL NETWORKS
20 pred_train = []
21 for j in range ( len ( X_train ) ) :
22 pred_train . append ( circuit ( param , x = X_train [ j ]) )
23 acc_train . append ( accuracy ( np . array ( pred_train ) ,
y_train ) )
24
25 pred_test = []
26 for j in range ( len ( X_test ) ) :
27 pred_test . append ( circuit ( param , x = X_test [ j ]) )
28 acc_test . append ( accuracy ( np . array ( pred_test ) , y_test )
)
After training the QNN, the training and test cost, as well as the accu-
racy over epochs, can be visualized using the following code.
0.8
1.2
1.0 0.6
Accuracy
Cost
0.8
0.4
0.6
0.2
Training Accuracy
0.4 Test Accuracy
0 10 20 30 40 50 0 10 20 30 40 50
Epochs Epochs
Label: 0 Label: 1 Label: 2 Label: 3 Label: 4 Label: 5 Label: 6 Label: 7 Label: 8 Label: 9
11 nn . Dropout () ,
12 nn . Linear (256 , 128) ,
13 nn . ReLU () ,
14 nn . Dropout () ,
15 nn . Linear (128 , 1) ,
16 nn . Sigmoid ()
17 )
18
19 def forward ( self , img ) :
20 return self . model ( img )
Step 4: Training the quantum patch GAN. With the dataset and
models ready, we initialize the quantum generator, classical discriminator,
and their optimizers.
1 # Hyperparameters
2 torch . manual_seed (0)
168 CHAPTER 4. QUANTUM NEURAL NETWORKS
3 image_width = 8
4 image_height = 8
5 n_generator = 4
6 n_qubit_d = int ( np . log2 (( image_width * image_height ) //
n_generator ) )
7 n_qubit_a = 1
8 n_qubit = n_qubit_d + n_qubit_a
9 n_layer = 6
10
11 # Quantum device
12 dev = qml . device ( " lightning . qubit " , wires = n_qubit )
13 qnode_generator = qml . QNode ( QuantumGenerator , dev )
14
15 # Initialize generator and discriminator
16 discriminator = C l a s s i c a l D i s c r i m i n a t o r ([ image_height ,
image_width ])
17 discriminator . train ()
18 generator = P a t c h Q u a n t u m G e n e r a t o r ( qnode_generator ,
n_generator , n_qubit , n_qubit_a , n_layer )
19 generator . train ()
20
21 # Optimizers
22 lr_generator = 0.3
23 lr_discriminator = 1e -2
24 opt _discr iminat or = optim . SGD ( discriminator . parameters () ,
lr = lr_discriminator )
25 opt_generator = optim . SGD ( generator . parameters () , lr =
lr_generator )
26
27 # Construct dataset and dataloader
28 batch_size = 4
29 dataset = OptdigitsData ( ’ code / chapter5_qnn / data / optdigits
. tra ’ , label =5)
30 dataloader = DataLoader ( dataset , batch_size = batch_size ,
shuffle = True , drop_last = True )
31
32 # Loss function
33 loss_fn = nn . BCELoss ()
34 labels_real = torch . ones ( batch_size , dtype = torch . float )
35 labels_fake = torch . zeros ( batch_size , dtype = torch . float )
36
37 # Testing setup
38 n_test = 10
39 z_test = torch . rand ( n_test , n_qubit ) * math . pi
4.5. CODE DEMONSTRATION 169
The GAN training process involves alternating updates for the discrimi-
nator and the generator. The discriminator is trained to distinguish between
real and fake images, while the generator learns to create images that can
successfully deceive the discriminator. To track the generator’s progress
during training, the generated images are saved at the end of each epoch.
1 n_epoch = 10
2 record = {}
3 for i in range ( n_epoch ) :
4 for data , _ in dataloader :
5
6 zs = torch . rand ( batch_size , n_qubit ) * math . pi
7 image_fake = generator ( zs )
8
1 n _ e p o c h s _ t o _ v i s u a l i z e = len ( record ) // 2
2 n_ im ag es _p er _e po ch = 10
3
4 fig , axes = plt . subplots ( n_epochs_to_visualize ,
n_images_per_epoch , figsize =( n_images_per_epoch ,
n_epochs_to_visualize ))
5
6 # Iterate through the recorded epochs and visualize
generated images
7 for epoch_idx , ( epoch , data ) in enumerate ( record . items () )
:
8 if epoch_idx % 2 == 1:
9 continue
10 images = np . array ( data [ ’ image_generated ’ ])
11
12 for img_idx in range ( n_ im ag es _p er _ep oc h ) :
13 ax = axes [ epoch_idx // 2 , img_idx ]
14 ax . imshow ( images [ img_idx ] , cmap = ’ gray ’)
15 ax . axis ( ’ off ’)
16
17 # Add epoch information to the title of each row
18 if img_idx == 0:
19 ax . set_title ( f " Epoch ␣ { epoch } " , fontsize =10)
20
21 plt . tight_layout ()
22 plt . show ()
4.6. BIBLIOGRAPHIC REMARKS 171
Epoch 0
Epoch 2
Epoch 4
Epoch 6
Epoch 8
Model designs
In the realm of quantum discriminative models, researchers have developed
various quantum neural architectures. In general, variational quantum clas-
sifiers (Havlı́ček et al., 2019; Mitarai et al., 2018) could employ parame-
terized quantum circuits for classification tasks. Subsequently, quantum
convolutional neural networks (Cong et al., 2019) are designed for process-
ing structured data. Hybrid quantum-classical architectures (Arthur et al.,
2022) are proposed to combine quantum layers with classical neural net-
works. Other notable works include the development of quantum versions of
popular classical architectures like recurrent neural networks (Bausch, 2020)
and attention mechanisms (Shi et al., 2024). Finally, Pérez-Salinas et al.
(2020); Fan and Situ (2022) have explored quantum re-uploading strategies
for encoding classical data, achieving QML models with more expressive
feature maps.
In addition to manually designed architectures, various lightening strate-
gies have been explored to enhance the efficiency of quantum neural net-
works. For example, quantum architecture search methods have been de-
veloped by (Du et al., 2022a; Zhang et al., 2022c; Linghu et al., 2024) to
automatically discover optimal quantum circuit designs with reduced gate
complexity. Sim et al. (2021); Wang et al. (2022b) introduced quantum prun-
ing techniques that systematically identify and remove redundant quantum
gates while preserving the performance. In the realm of knowledge dis-
tillation, researchers have demonstrated how to transfer knowledge from
the teacher model given as quantum (Alam et al., 2023) or classical (Li
et al., 2024) neural networks to more compact quantum circuit architec-
tures that are more robust against quantum noises. These optimization
approaches have collectively contributed to improving the practical perfor-
mance of QNNs on real quantum devices, particularly in the NISQ era.
Theoretical foundations
To gain a deeper understanding of the potential advantages and limitations
of QNNs, a crucial research topic is analyzing their learnability. More con-
cisely, the learnability is determined by the interplay of three key aspects:
4.6. BIBLIOGRAPHIC REMARKS 173
Applications
Model designs
Researchers have developed various QNN architectures tailored for gener-
ative tasks. Quantum circuit Born machines (QCBMs) (Benedetti et al.,
2019a) are one of the pioneering models, utilizing parameterized quantum
circuits to generate discrete probability distributions. Quantum generative
adversarial networks (Lloyd and Weedbrook, 2018) extend the adversarial
framework to the quantum domain, where quantum generators and discrim-
inators compete to learn complex distributions. Quantum Boltzmann ma-
chines (Amin et al., 2018) are another notable model, employing quantum
devices to prepare Boltzmann distributions for estimating target discrete
distributions. Additionally, quantum autoencoders (Romero et al., 2017)
have been proposed for tasks like quantum state compression and recon-
struction, offering potential advantages in quantum information processing.
Recently, quantum diffusion models (Zhang et al., 2024b; Kölle et al., 2024)
have been proposed for generating quantum state ensembles or classical im-
ages. These models showcase the versatility of QNNs in addressing diverse
generative tasks.
Theoretical foundations
The theoretical understanding of generative quantum neural networks has
advanced in several directions. Similar to QNNs for discriminative tasks,
quantum generative models like QCBMs face the barren plateau issue with
additional mechanisms from the Kullbach-Leibler (KL) divergence loss func-
tion (Rudolph et al., 2024). In parallel, QCBMs are more efficient in the
data-limited regime than the other classical generative models (Hibat-Allah
et al., 2024). Besides, Gao et al. (2018) proved the existence of quantum
generative model that is more capable of representing probability distri-
butions compared with classical generative models, which has exponential
speedup in learning and inference. Similarly, Gao et al. (2022) proved the
separation in expressive power between a class of widely used generative
models, known as Bayesian networks, and its minimal quantum-inspired ex-
tension. Du et al. (2022d) analyzed the generalization bounds of QCBMs
and QGANs under the maximum mean discrepancy loss.
Applications
Generative QNNs have shown potential in various practical applications. In
finance, they have been used to model complex financial data distributions
and generate synthetic financial datasets, demonstrating better performance
4.6. BIBLIOGRAPHIC REMARKS 177
than classical models in certain scenarios (Alcazar et al., 2020; Zhu et al.,
2022). In the domain of quantum physics, quantum generative models have
been applied for quantum state tomography and quantum simulation, aid-
ing in the understanding of quantum systems (Benedetti et al., 2019b). In
image generation, QGANs have been employed to produce high-quality im-
ages, showcasing their capability in handling complex visual data (Huang
et al., 2021b). Furthermore, quantum generative models have been explored
for drug discovery, where they can potentially accelerate the process by effi-
ciently exploring large chemical spaces (Li et al., 2021). These applications
highlight the broad potential of QNNs in generative tasks across different
domains.
178 CHAPTER 4. QUANTUM NEURAL NETWORKS
Chapter 5
Quantum Transformer
179
180 CHAPTER 5. QUANTUM TRANSFORMER
5.1.2 Self-attention
Self-attention is a core building block of the transformer architecture, which
captures intrinsic correlations among tokens. By allowing each token in a
sequence to attend to every other token, Transformer generates attention
matrices via the inner-product operations, encoding complex inter-token
relationships into a transformative vector representation, colloquially termed
“scaled dot-product attention”. The generated attention matrices highlight
how relevant each part of the input is to every other part. This allows
Transformers to handle contextual dependencies across a variety of data
structures.
The self-attention mechanism, as highlighted by the blue or red box
in Figure 5.1, involves three parameterized weight matrices: Wq , Wk ∈
Rdmodel ×dk and Wv ∈ Rdmodel ×dv .
Remark
Following conventions (Vaswani, 2017), we use the notation d to spec-
ify dmodel , dk , and dv in the rest of this chapter, i.e., d := dmodel =
dk = dv . This is a widely used setting in practice.
d d
1 X soft X
s̄j := ( (Gjk + Sjk ), . . . , jk + Sjk )) ∈ R ,
(Gsoft d
d
k=1 k=1
184 CHAPTER 5. QUANTUM TRANSFORMER
q P
1 d soft + S − s̄ ) )2 . The complete residual connec-
where ς := d k=1 ((Gj j j k
tion with the layer normalization LN(·, ·) can be expressed as
Gsoft
j + Sj − s̄j
LNγ,β (Gsoft
j , Sj ) = γ + β, (5.3)
ς
where γ and β denote the scale and bias parameters, respectively.
FFN(LN(zj , Sj )) = σ(LN(Gsoft
j , Sj )M1 + b1 )M2 + b2 , (5.4)
′ ′
where M1 ∈ Rd×d , M2 ∈ Rd ×d are linear transformation matrices, and b1 , b2
are vectors. In most practical cases, d′ = 4d. Here σ(x) is an activation
function, such as tanh(x) and ReLU(x) = max(0, x). Another activation
function that has been widely used in Transformers is the Gaussian Error
Linear Units function (GELU), i.e.,
1 x
GELU(x) = x · 1 + erf √ .
2 2
For the final output, i.e., to predict the next token, one can imple-
ment the softmax function to make the vector into a distribution
Pr(·|S1 , . . . , Sj−1 ), where the dimension is the size of the token dic-
tionary dtoken , and sample from this distribution.
ℓ
1X
L=− Pr(Sj |S1 , . . . , Sj−1 ), (5.6)
ℓ
j=1
where Pr(Sj |S1 , . . . , Sj−1 ) is the predicted probability of the correct Sj com-
ing out of the softmax layer, based on the previous tokens.
This process of training Transformers can be achieved by using Adam
optimizer (Kingma and Ba, 2015). Learning rate schedules, such as warm-up
followed by decay, can provide stable and effective convergence.
After optimization, we could use the trained Transformer for inference,
which refers to making predictions on new data. Given a new initial sequence
′
S ′ = {S1′ , . . . , Sj−1 }, we feed it to the trained Transformer and obtain the
′
distribution Pr(Sj′ |S1′ , . . . , Sj−1 ). Then we can use a decoding strategy (e.g.,
greedy decoding or sampling) to select the token based on the highest prob-
ability or a sampling approach.
Efficient inference is crucial for deploying models in real-world appli-
cations. Speed optimization techniques, such as quantization, reduce the
precision of weights and activations to accelerate inference with minimal
accuracy loss (Jacob et al., 2018). Pruning removes redundant weights or
attention heads to reduce the model size and computational cost (Han et al.,
2015). Batching and parallelism are also critical, with batched inference al-
lowing the processing of multiple inputs simultaneously and GPU or TPU
acceleration enabling parallel computations. Efficient attention at inference,
such as caching key and value tensors, reduces redundant computations in
autoregressive tasks like text generation (Shoeybi et al., 2019).
The inference cost is up to 10 times the training cost as large language
models (LLMs) are trained once and applied millions of times (McDonald
et al., 2022; Desislavov et al., 2023). For this reason, in the next section, we
explore how to harness quantum computing to address this issue, which is
crucial from both scientific and societal perspectives.
186 CHAPTER 5. QUANTUM TRANSFORMER
Remark
For simplicity and clarity, in the following, we consider the perfect
block encoding of input matrices without errors, i.e., ε = 0. As such,
we will not explicitly write the error term of the block encoding, and
use (α, a) instead of (α, a, 0). The output of the quantum transformer
is a quantum state corresponding to the probability distribution of
the next token. The complete single-layer structure is described in
Figure 5.2.
Under the above assumptions about access to the read-in protocols, the
following theorem indicates how to implement a single-head and single-block
transformer architecture in Eqn. (5.5) on the quantum computer.
d
X
Transformer(S, j)k |k⟩ , (5.8)
k=1
X d
M2 · (M1 · ) k |ki
k=1
Feed-Forward Network
Quantum residual connection with layer normalization for
the 𝑗-th token <latexit sha1_base64="C54unuoyOhuDss2m+vMy2PsmPT4=">AAACJHicbVA9SyRBEO3xvFPXu3PV0KRRDvbg2JsxUEEE4QINRBRvVdhZh57emrWdnp6hu0ZcxvklRib+FRMDPzAwMfJnXHC9uwZ+PSh4/V4VXfXCTAqDrvvgDH0a/vxlZHSsMv712/eJ6uTUrklzzaHBU5nq/ZAZkEJBAwVK2M80sCSUsBfGf3r+3jFoI1L1F7sZtBLWUSISnKGVguqyb/IkKOIVrzxoUx/hBIuNzbK2dlAMHiaNsCyDo190Jzj6GcT0lMa+ZqojIajOuXW3D/qeeM9kbvV3+G/t6YxuBdVbv53yPAGFXDJjmp6bYatgGgWXUFb83EDGeMw60LRUsQRMq+gfWdIfVmnTKNW2FNK++nKiYIkx3SS0nQnDQ/PW64kfec0co6VWIVSWIyg++CjKJcWU9hKjbaGBo+xawrgWdlfKD5lmHG2uFRuC9/bk92R3vu4t1Be2bRo1MsAomSGzpEY8skhWyTrZIg3CyTm5JNfkxrlwrpw7537QOuQ8z0yTV3Ae/wM5TajJ</latexit>
Xd
Layer Norm LN(Gsoft
j , Sj )k |ki
k=1
Block Encoding
Block encoding of the input matrices
" # " # " # "
<latexit sha1_base64="xJizW/lvUxlTt70q/Zo7Q+r/hGk=">AAAC3nicnZJBaxNBFMdnV2vbtWqqRy+DwVKKrLu2tB4LXgQvLZq0kA3x7eQlGTozu8y8bRuWHLx4UEqv/Vze/CDenaRBtBEKfTDMn/97P+bNm8lLJR0lyc8gvHd/6cHyymr0cO3R4yeN9adtV1RWYEsUqrDHOThU0mCLJCk8Li2CzhUe5SfvpvmjU7ROFuYTjUvsahgaOZACyFu9xq/MosEzUWgNpl9nYC2MHVkkMZrUabw9ibIch9LUuQay8nwSfXydgSpHwDf4VpZFW9M9ytDTf0peLUCHd4E+3AVq3w7FvUYziZNZ8EWRzkWTzeOg1/iR9QtRaTQkFDjXSZOSujVYkkKhn1HlsARxAkPseGlAo+vWs+eZ8Jfe6fNBYf0yxGfu30QN2rmxzn2l73Dkbuam5v9ynYoGb7u1NGVFaMT1QYNKcSr49K15X1oUpMZegLDS98rFCCwI8j8i8kNIb155UbTfxOluvHu409zfnI9jhT1nL9gmS9ke22fv2QFrMRF0gi/Bt+B7+Dn8Gl6El9elYTBnnrF/Irz6DaNh3uA=</latexit>
#
S/↵ ⇤ Q/↵ ⇤ K/↵ ⇤ V /↵ ⇤
, , , .
Input sequence Weight matrices ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤ ⇤
Wq , Wk , Wv 2 Rd⇥d
<latexit sha1_base64="fFKNJu8fRJYkhs8SafCmd5s3XAU=">AAACDnicbVC7TsMwFHXKo6XlUWBksagqdUBVwlAYK1gYC6IPqQmR4zitVccJtlOpivoFMPArLAwgxMrMxm8wM+A+Bmg50pWOzrlX997jxYxKZZqfRmZldW09m9vIFza3tneKu3stGSUCkyaOWCQ6HpKEUU6aiipGOrEgKPQYaXuD84nfHhIhacSv1SgmToh6nAYUI6Ult1huu7dHbXega2hTDu0Qqb7npVfjm9S3FQ2JhP7YLZbMqjkFXCbWnJTqha+zbOH+u+EWP2w/wklIuMIMSdm1zFg5KRKKYkbGeTuRJEZ4gHqkqylHeo+TTt8Zw7JWfBhEQhdXcKr+nkhRKOUo9HTn5Fq56E3E/7xuooJTJ6U8ThTheLYoSBhUEZxkA30qCFZspAnCgupbIe4jgbDSCeZ1CNbiy8ukdVy1atXapU6jAmbIgQNwCCrAAiegDi5AAzQBBnfgETyDF+PBeDJejbdZa8aYz+yDPzDefwAVYp8S</latexit>
<latexit sha1_base64="8CBtkLGuEFB1brlPUmdPFf2FYsY=">AAACBHicbVC7TsMwFHXKq5RXgbGLRYXUqUoYChNUYmFC5dGH1ITKcZzWquNEtoNURR1Y+BUWBhBi5QfY2Nj6BSz8AE7bAVqOdKWjc+7Vvfe4EaNSmeankVlYXFpeya7m1tY3Nrfy2zsNGcYCkzoOWShaLpKEUU7qiipGWpEgKHAZabr909Rv3hIhaciv1SAiToC6nPoUI6WlTr5wZVMO7QCpnusml8Ob5NxWNCASesNOvmiWzTHgPLGmpHgy+hp9vx83a538h+2FOA4IV5ghKduWGSknQUJRzMgwZ8eSRAj3UZe0NeVI73GS8RNDuK8VD/qh0MUVHKu/JxIUSDkIXN2ZXitnvVT8z2vHyj9yEsqjWBGOJ4v8mEEVwjQR6FFBsGIDTRAWVN8KcQ8JhJXOLadDsGZfnieNg7JVKVcuzGK1BCbIggLYAyVggUNQBWegBuoAgzvwAJ7As3FvPBovxuukNWNMZ3bBHxhvP7d0nUY=</latexit>
N ⇥d
S2R
0 0
<latexit sha1_base64="NMDQE8ww6vmGdJj1DX5d3rFZ6CA=">AAACVHicbVDLSsNAFJ2mvp9Vl24GRXQhJelCXYpu3AgqVoWmhslkooOTmTBzI5YQ3PgTLt35BX6GSx/fogsnrYi1XrhwOPdczr0nTAU34LrvFac6NDwyOjY+MTk1PTNbm5s/MSrTlDWpEkqfhcQwwSVrAgfBzlLNSBIKdhpe7Zbz02umDVfyGDopayfkQvKYUwKWCmo7+4GHfS6xnxC4DMP8qDjPo1XsA0+YwVGxjveDxqDiR7BaBLVlt+52Cw8C7xssb1dXbp/u7x4OgtqHHymaJUwCFcSYluem0M6JBk4FKyb8zLCU0CtywVoWSmKN2nn31wKvWCbCsdK2JeAu+3sjJ4kxnSS0yvJe83dWkv/NWhnEW+2cyzQDJmnPKM4EBoXL4HDENaMgOhYQqrm9FdNLogkFG2+fy01s2b438tIOlBKmTMv7m80gOGnUvY36xqGNbQ31agwtoiW0hjy0ibbRHjpATUTRI3pGr+it8lL5dKrOcE/qVL53FlBfOTNfT5m4bg==</latexit>
M1 2 Rd ⇥d , M2 2 Rd⇥d
j ∈ [ℓ], one can construct a block encoding of a matrix G such that Gj⋆ =
Gsoft
j := (softmax QK ⊤ /α0 V )j⋆ .
Remark
For quantum self-attention, we make a slight change by setting the
scaling factor α0 = αs2 αw2 for the following reasons. The first is that
√
the usual setting α0 = 1/ d is chosen somehow in a heuristic sense,
and there are already some classical works considering different scal-
ing coefficients which may even achieve better performance (Yang
et al., 2022; Ma et al., 2024). The second, which is more impor-
tant, is that the quantum input assumption using the block encoding
format naturally contains the normalization factor α which plays a
similar role to the scaling factor. Therefore, for the quantum case in
the context of our work, it suffices to use α directly.
- For the matrix QK ⊤ , we first use Fact 2.23 to construct the (αq , aq )-
encoding UQ and (αk , ak )-encoding UK with Q = Wq S and K = Wk S,
respectively. Then, we use Fact 2.23 again to construct the (α0 , a0 )-
encoding UQK ⊤ of QK ⊤ , where α0 = αs2 αw2 and a = 2a + 2a . Note
0 s w
†
that for a real matrix M and its block encoding unitary UM , UM is
the block encoding of M .⊤
Step II. Once the unitary UQK ⊤ is prepared, we move to implement the
quantum algorithm corresponding to the softmax function, i.e., softmax(QK ⊤ /α0 ).
Note that the softmax function relies on the exponential function, which is
generally resource-intensive to implement on quantum computers. To cir-
cumvent this bottleneck, the quantum Transformer uses polynomial func-
tions to approximate the softmax function, as supported by the following
fact.
Fact 5.4. For x ∈ [−1, 1], the function f (x) := ex can be approximated with
error bound ϵ with an O(log(1/ϵ))-degree polynomial function.
Remark
The notation exp ◦(A) indicates that the exponential operation is ap-
plied elementwise to each entry of the matrix A, rather than repre-
senting a matrix exponential.
Moreover, the element-wise functions mean that functions are imple-
mented on each matrix element.
Pr j
Moreover, for a polynomial function gr (x) = j=0 cj x with constant
term c0 , one can construct a (C ′ , b)-encoding of gr ◦ (A/α), where C ′ =
rc0 + C.
Supported by the above lemma, we can complete Step II (i.e., the quan-
tum softmax for self-attention), as shown in the following theorem.
Theorem 5.6 (Quantum softmax for self-attention, informal). Given an
(α, a)-encoding UA of a matrix A ∈ Rℓ×ℓ , a positive integer d, and an index
j ∈ [ℓ], one can prepare a state-encoding of
Xℓ q ℓ A
1 X
|Aj ⟩ := softmax(A/α)jk |k⟩ = p exp ◦ |k⟩ ,
Zj k=1 2α jk
k=1
Pℓ
where Zj = k=1 exp ◦(A/α)jk .
A
Proof sketch of Theorem 5.6. We first construct the block encoding of exp ◦( 2α ).
Note that Taylor expansion of exp(x) contains a constant term 1. This can
be achieved with lemma 5.5 and fact 5.4. Here, since we are only focusing
on the j-th row, instead of taking linear combination with the matrix whose
elements are all 1, we take sum with the matrix whose j-th row elements
are all 1 and else
√ are 0. This enables us to have a better dependency on ℓ,
i.e., from ℓ to ℓ. For index j ∈ [ℓ], let Uj : |0⟩ → |j⟩. One can achieve this
by changing Eqn. (5.12) to the following,
√
X ℓ
|j⟩⟨k| = (Uj H ⊗N − Uj I2N − 2 |0N ⟩ ⟨0N | H ⊗N ). (5.13)
2
k
Following the same steps in lemma 5.5, one can achieve the construction.
There are two error terms in this step. Denote Uf ◦(A) as the constructed
block encoding unitary. By lemma 5.5 and some additional calculation,
A
one can show that Uf ◦(A) is a block-encoding of exp ◦( 2α ). Note that
A A ⊤ †
exp ◦( 2α )jk = exp ◦( 2α )kj . With unitary Uf ◦(A) (I ⊗ Uj ) and amplitude
amplification, one can prepare a state-encoding of the target state
1 X
ℓ A
|Aj ⟩ := p exp ◦ |k⟩ , (5.14)
Zj k=1 2α jk
5.2. FAULT-TOLERANT QUANTUM TRANSFORMER 193
P
where Zj = ℓk=1 exp ◦(A/α)jk is the normalization factor of softmax func-
tion for the j-th row.
Step III. Finally, we implement the matrix multiplication with V . This can
be easily achieved by using Fact 2.23, with Uf†(QK ⊤ ) and UV . Consequently,
we obtain an encoded quantum state analogous to
ℓ
X
(softmax(QK ⊤ /α0 )V )jk |k⟩ . (5.15)
k
Combining the results of Steps I, II, and III, we are now ready to present
the proof of Theorem 5.3.
Proof of Theorem 5.3. In the first step, we construct the block encoding
of matrix QK ⊤ and V . Note that for a real matrix M and its block en-
†
coding unitary UM , UM is the block encoding of M ⊤ . By Fact 2.23, one
can construct an (α0 , a0 )-encoding UQK ⊤ of QK ⊤ , where α0 := αs2 αw 2 and
ℓ
X
(softmax(QK ⊤ /α0 )V )jk |k⟩ .
k
194 CHAPTER 5. QUANTUM TRANSFORMER
One may further achieve the multi-head self-attention case by using the
linear combination of unitaries.
Pd qP
1 soft d soft
where s̄j := d k=1 (Gjk + Sjk ) and ς := k=1 (Gjk + Sjk − s̄j )2 .
Note that H log d is a (1, 0, 0)-encoding of itself, and the first column of H log d
is √1d (1, . . . , 1)⊤ . By fact 2.23, one can multiply Gsoft + S with H log d to
√
construct a block encoding of an ℓ × d matrix, whose (j, 1)-element is ds̄i .
One can further move this element to (1, 1) by switching the first row with
the j-th row. By tensor product √ with the identity I of log d qubits, one can
construct a block encoding of ds̄i · I.
With Uj : |0⟩ → |j⟩, one can prepare the state
s P 2
d
X
† 1 k ψk
Ures (I ⊗ Uj ) |0⟩ |0⟩ = |0⟩ ψk |k⟩ + 1 − |1⟩ |bad⟩ .
αg + αs (αg + αs )2
k=1
(5.18)
and
1 1
P2 |0⟩ = q √ (|0⟩ − √d |1⟩), (5.20)
1 + 1/ d
one can construct a block encoding of diag(Gj1 +Sj1 − s̄j , . . . , Gjd +Sjd − s̄j ),
and we call it ULN . Then the unitary ULN (I ⊗ H log d ) is an state-encoding
of the state
d
1 X soft
(Gjk + Sjk − s̄j ) |k⟩ ,
ς
k=1
qP
d soft
where ς := k=1 (Gjk + Sjk − s̄j )2 .
1 X
d
|ϕ⟩ = M2 · GELU(M1 · ψ) |k⟩ , (5.21)
C k
k=1
where |⊥⟩e is an unnormalized orthogonal state. For the case d′ ≥ ℓ, this can
be achieved by padding ancilla qubits to the initial state. By fact 2.28, one
can construct a block encoding of the diagonal matrix diag((M1 ψ)1 , . . . , (M1 ψ)d′ ).
Note that the GELU function does not have a constant term, and is suit-
able to use the importance-weighted amplitude transformation as in Rat-
tew and Rebentrost (2023). Instead of directly implementing the GELU
function, we first implement the function f (x) = 21 (1 + erf( √x2 )). Note
that the value of |erf(x)| is upper bounded by 1. By fact 2.28 with func-
tion 14 (1 + erf(ααm √x2 )), one can construct a block encoding of matrix
diag(f (M1 ψ)1 , . . . , f (M1 ψ)d′ ).
Let the previously constructed block-encoding unitary be Uf (x) . We have
1 X
Uf (x) (I ⊗ UM1 )(I ⊗ Uψ ) |0⟩ |0⟩ = |0⟩ f′ ⟩ ,
GELU(M1 ψ)k |k⟩ + |⊥
2ααm
k
(5.23)
198 CHAPTER 5. QUANTUM TRANSFORMER
e ′′ ⟩ is an unnormalized orthogonal
where C is the normalization factor, and |⊥
state.
Remark
The quantum feedforward network discussed in this subsection is a
quantum implementation of the classical feedforward network under
the input assumption of block encoding, which is essentially different
from the quantum analog of neural networks introduced in chapter 4.
5.3.1 Overview
Having the quantum implementation of self-attention, residual connection,
layer normalization, and feed-forward networks, we are able to construct the
quantum transformer by combining these building blocks as in theorem 5.2.
We obtain this final complexity on the basis of the following consider-
ations: the single-head and single-block transformer architecture includes
one self-attention, one feed-forward network, and two residual connections
with layer normalization, as shown in Figure 5.2.
Starting from the input assumption as Assumption 5.1, for the index
j ∈ [ℓ], we first construct the block encoding of self-attention matrix, as de-
scribed in Section 5.2.1. This output can be directly the input of the quan-
tum residual connection and layer normalization, as Section 5.2.2, which
output is a state encoding. Remind the definition of state encoding as def-
inition 2.22. The state encoding can directly be used as the input of the
feed-forward network, as section 5.2.3. Finally, we put the output of the
feed-forward network, which is a state encoding, into the residual connec-
tion block. This is possible by noticing that state encoding is a specific
5.3. RUNTIME ANALYSIS WITH QUADRATIC SPEEDUPS 199
103
Frobenius Norm
102 101
100
102
102
101
Spectral Norm
102 100
101
101 102 101 102 101 102 103
Input Sequence Length N Input Sequence Length N Input Sequence Length N
Figure 5.3: Scaling of the spectral norm ∥S∥ and the Frobenius norm ∥S∥F
with ℓ for each model, displayed on logarithmic scales for both axes. For
√
reference, the line y ∝ x is also shown. We use tokens in MMLU dataset
and convert them to S.
(Wq , Wk , Wv ) for the large language models. The result can be seen in Fig-
ure 5.4. Many of the LLMs below a dimension d of 103 that we have checked
have substantially different norms. We observe that for larger models such
as Llama2-7b and Mistral-7b, which are close to the current state-of-the-art
open-source models, the norms do not change dramatically. Therefore, it is
reasonable to assume that the spectral
√ norm and the Frobenius norm of the
weight matrices are at most O( d) for advanced LLMs.
175 175 40
150 150
Frobenius Norm
125 125 30
100 100
75 75 20
50 50
10
25 25
0
1000 2000 3000 4000 1000 2000 3000 4000 1000 2000 3000 4000
30 10
40
25 8
Spectral Norm
30
20 6
15 20
4
10 10 2
5 0
1000 2000 3000 4000 1000 2000 3000 4000 1000 2000 3000 4000
Dimension of the weight matrix Wq Dimension of the weight matrix Wk Dimension of the weight matrix Wv
20 W_k = np . array (
21 [
22 [0.1 , 0.3 , 0.5 , 0.7] ,
23 [0.6 , 0.4 , 0.2 , 0.1] ,
24 [0.8 , 0.9 , 0.7 , 0.6] ,
25 [0.2 , 0.1 , 0.3 , 0.4] ,
26 ]
27 )
28
29 W_v = np . array (
30 [
31 [0.3 , 0.5 , 0.7 , 0.9] ,
32 [0.6 , 0.4 , 0.2 , 0.1] ,
33 [0.8 , 0.9 , 0.7 , 0.6] ,
34 [0.5 , 0.4 , 0.3 , 0.2] ,
35 ]
36 )
37
38 # Compute Query , Key , and Value matrices
39 Q = S @ W_q
40 K = S @ W_k
41 V = S @ W_v
4
5 def softmax ( x ) :
6 """ Compute softmax values for each set of scores in x
. """
7 return np . exp ( x ) / np . sum ( np . exp ( x ) , axis =1 , keepdims
= True )
8
9 atte ntion_ weight s = softmax ( attention_scores )
The final output captures how each word relates to every other word in the
sentence. In this case, “sleeps” pays most attention to “cat” (0.432), some
attention to “The” (0.346), and less attention to itself (0.222). Finally, we
use these scores to create a weighted sum of the values:
1 output = at tentio n_weig hts @ V
Conclusion
205
206 CHAPTER 6. CONCLUSION
Appendix A
Notations Summary
Notation Concept
a, b, aj , bj , α, β Scalars
x, y Vectors
W, A Matrices
R Real Euclidean space
C Complex Euclidean space
N The set of natural numbers
[a] The set of integers {1, 2, · · · , a}
E[·] Expectation value of a random variable
Var[·] Variance of a random variable
O Asymptotic upper bound notation
Ω Asymptotic lower bound notation
⊤ Transpose operation
a∗ complex conjugate of the number a
† Conjugate Transpose operation
|·⟩ ⟨·| Outer product operation
A⊙B element-wise multiplication (Hadamard product) of matrices
A and B
f ◦g composition of functions f and g
|0⟩ , |1⟩ , |ψ⟩ Pure quantum state in Dirac notation
N Number of qubits
|0N ⟩ , |0⟩⊗N Zero state with N -qubits
Id Identity matrix with the size d × d
ρ Quantum state in density matrix representation
H Hamiltonian
207
208 APPENDIX A. NOTATIONS SUMMARY
U, V Unitary operator
X, Y, Z Pauli operators
RX, RY, RZ Rotation gates along the x, y and z axes, respectively
CX, CZ Controlled-X gate and controlled-Z gate
E, N Quantum channel
O Observable
⟨O⟩ Expectation of observable O
∥·∥op Operator norm
n Number of training examples
D Dataset
Tr(Oρ) Expectation value of an observable O
U (θ) Parameterized quantum circuit
L(θ) Loss function
∇θ L(θ) Gradient of loss function L w.r.t parameters θ
Table A.1: Notations used in this work.
Appendix B
Concentration Inequality
Z ∞
EX = xp(x)dx. (B.1)
0
EX
P{X ≥ t} ≤ . (B.2)
t
209
210 APPENDIX B. CONCENTRATION INEQUALITY
Here, the parameter q can be chosen to optimize the upper bound in spe-
cific examples. Such moment bounds often provide sharp estimates for tail
probabilities. A related idea forms the basis of Chernoff’s bounding method.
In particular, by setting ϕ(x) = esx for some s > 0, we can derive a useful
upper bound for any random variable X and t > 0,
EesX
P{X ≥ t} = P{esX ≥ est } ≤ . (B.8)
est
In Chernoff’s method, the goal is to choose an appropriate s > 0 to minimize
the upper bound or make it as small as possible.
Now, we turn to concentration inequalities for sums of independent ran-
dom variables. Specifically, we aim to bound probabilities
P of deviations from
the mean, i.e., P{|Sn − ESn | ≥ t}, where Sn = ni=1 Xi , and X1 , · · · , Xn
are independent real-valued random variables.
By applying Chebyshev’s inequality to Sn , we obtain
Pn
Var(Sn ) Var(Xi )
P{|Sn − ESn | ≥ t} ≤ 2
= i=1 2 . (B.9)
t t
In terms of the sample mean, this can be rewritten as,
( n
)
1X σ2
P Xi − EXi ≥ ε ≤ 2 , (B.10)
n nε
i=1
Pn
where σ 2 = n1 i=1 Var(Xi ). Chernoff’s bounding method is particularly
useful for bounding tail probabilities of sums of independent random vari-
ables. By exploiting the independence property (i.e., the expected value
of a product of independent random variables equals the product of their
expected values), Chernoff’s bound can be expressed as
" n
!#
X
P{Sn − ESn ≥ t} ≤e−st E exp s (Xi − EXi )
i=1
n
Y
=e−st E[exp(s(Xi − EXi ))] (by independence).
i=1
(B.11)
Now, the challenge then becomes finding a good upper bound for the
moment generating function of the random variables Xi −EXi . For bounded
random variables, one of the most elegant results is Hoeffding’s inequality
Hoeffding (1994).
212 APPENDIX B. CONCENTRATION INEQUALITY
and
−2t2
P{Sn − ESn ≤ −t} ≤ exp Pn 2
, (B.14)
i=1 (bi − ai )
1. left-invariant, i.e. µ(U S) = µ(S) for any measurable set S ⊆ U(d) and
any unitary U ∈ U(d).
213
214 APPENDIX C. HAAR MEASURE AND UNITARY T-DESIGN
distribution shares the same t-th moment with the Haar measure is defined
as the unitary t-design.
Definition C.2 (Unitary 2-design). Let µ be the Haar measure on the space
U(d). Then, a finite set S forms a unitary t-design if and only if it fulfills
one of the following equivalent conditions:
1. Z
1 X ⊗t † ⊗t
U ⊗ (U ) = U ⊗t ⊗ (U † )⊗t dµ(U ).
|S| U (d)
U ∈S
Fact C.5 (Average over unitary 2-design (Puchala and Miszczak, 2017)).
Let S be a set of unitary 2-design on U(d) and µ be the corresponding Haar
measure. Then
Z
1 X ∗ ∗
Ui1 j1 Ui2 j2 Ui′ j ′ Ui′ j ′ = Ui1 j1 Ui2 j2 Ui∗′ j ′ Ui∗′ j ′ dµ(U )
|S| 1 1 2 2
U (d)
1 1 2 2
U ∈S
1
= 2 δ ′ δ ′ δ ′ δ ′ + δi1 i′2 δi2 i′1 δj1 j2′ δj2 j1′
d − 1 i 1 i1 i 2 i2 j1 j1 j2 j2
1
− δ ′ δ ′ δ ′ δ ′ + δ i1 i2 i2 i1 j1 j1 j2 j2 .
′ δ ′ δ ′ δ ′
d(d2 − 1) i1 i1 i2 i2 j1 j2 j2 j1
How big is a unitary t-design? Roy and Scott (2009) have proved that, for
instance, the size of unitary 1-design and unitary 2-design scale polynomially
to the dimension of the unitary space.
215
Fact C.6 (The size of a unitary 2-design (Roy and Scott, 2009)). A unitary
1-design on U(d) has no fewer than d2 elements. A unitary 2-design on U(d)
has no fewer than d4 − 2d2 + 2 elements.
Notes
1
Parameters are obtained from the Hugging Face website, which is an open-source
platform for machine learning models.
218 NOTES
Bibliography
219
220 BIBLIOGRAPHY
Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya
Safro, Marco Pistoia, and Yuri Alexeev. Quantum computing for finance.
Nature Reviews Physics, 5(8):450–465, 2023.
Andrew W Cross, Lev S Bishop, Sarah Sheldon, Paul D Nation, and Jay M
Gambetta. Validating quantum computers using randomized model cir-
cuits. Physical Review A, 100(3):032328, 2019.
Andrew Wack, Hanhee Paik, Ali Javadi-Abhari, Petar Jurcevic, Ismael Faro,
Jay M Gambetta, and Blake R Johnson. Quality, speed, and scale: three
key attributes to measure the performance of near-term quantum com-
puters. arXiv preprint arXiv:2110.14108, 2021.
Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van
Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel,
Kristan Temme, et al. Evidence for the utility of quantum computing
before fault tolerance. Nature, 618(7965):500–505, 2023.
Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to
quantum machine learning. Contemporary Physics, 56(2):172–185, 2015.
Vedran Dunjko and Hans J Briegel. Machine learning & artificial intelligence
in the quantum domain: a review of recent progress. Reports on Progress
in Physics, 81(7):074001, 2018.
Giuseppe Carleo, Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria
Schuld, Naftali Tishby, Leslie Vogt-Maranto, and Lenka Zdeborová. Ma-
chine learning and the physical sciences. Reviews of Modern Physics, 91
(4):045002, 2019.
Bin Cheng, Xiu-Hao Deng, Xiu Gu, Yu He, Guangchong Hu, Peihao Huang,
Jun Li, Ben-Chuan Lin, Dawei Lu, Yao Lu, et al. Noisy intermediate-scale
quantum computers. Frontiers of Physics, 18(2):21308, 2023.
He-Liang Huang, Dachao Wu, Daojin Fan, and Xiaobo Zhu. Superconduct-
ing quantum computing: a review. Science China Information Sciences,
63:1–32, 2020a.
Colin D Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M
Sage. Trapped-ion quantum computing: Progress and challenges. Applied
Physics Reviews, 6(2), 2019.
M Morgado and S Whitlock. Quantum simulation and computing with
rydberg-interacting qubits. AVS Quantum Science, 3(2), 2021.
John Preskill. Quantum computing in the nisq era and beyond. Quantum,
2:79, 2018.
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin,
Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao,
David A Buell, et al. Quantum supremacy using a programmable super-
conducting processor. Nature, 574(7779):505–510, 2019.
Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xi-
awei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al.
Strong quantum computational advantage using a superconducting quan-
tum processor. Physical review letters, 127(18):180501, 2021.
222 BIBLIOGRAPHY
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum
singular value transformation and beyond: exponential improvements for
quantum matrix arithmetics. In Proceedings of the 51st Annual ACM
SIGACT Symposium on Theory of Computing, STOC ’19. ACM, June
2019. doi: 10.1145/3313276.3316366. URL [Link]
1145/3313276.3316366.
Zherui Chen, Yuchen Lu, Hao Wang, Yizhou Liu, and Tongyang
Li. Quantum langevin dynamics for optimization. arXiv preprint
arXiv:2311.15587, 2023.
Junyu Liu, Minzhao Liu, Jin-Peng Liu, Ziyu Ye, Yunfei Wang, Yuri Alexeev,
Jens Eisert, and Liang Jiang. Towards provably efficient quantum algo-
rithms for large-scale machine-learning models. Nature Communications,
15(1):434, 2024a.
Scott Aaronson. Read the fine print. Nature Physics, 11(4):291–293, 2015.
Jinkai Tian, Xiaoyu Sun, Yuxuan Du, Shanshan Zhao, Qing Liu, Kaining
Zhang, Wei Yi, Wanrong Huang, Chaoyue Wang, Xingyao Wu, et al.
Recent advances for quantum neural networks in generative learning.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(10):
12321–12340, 2023.
Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao.
Quantum circuit architecture search for variational quantum algorithms.
npj Quantum Information, 8(1):62, 2022a.
James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo. Quantum
natural gradient. Quantum, 4:269, 2020.
Xinbiao Wang, Junyu Liu, Tongliang Liu, Yong Luo, Yuxuan Du, and
Dacheng Tao. Symmetric pruning in quantum neural networks. In The
Eleventh International Conference on Learning Representations, 2023a.
URL [Link]
224 BIBLIOGRAPHY
John Preskill. Lecture notes for physics 219: Quantum computation. Caltech
Lecture Notes, 7:1, 1999.
Bo Qi, Zhibo Hou, Li Li, Daoyi Dong, Guoyong Xiang, and Guangcan Guo.
Quantum state tomography via linear regression estimation. Scientific
reports, 3(1):3496, 2013.
Tak Hur, Israel F Araujo, and Daniel K Park. Neural quantum embedding:
Pushing the limits of quantum supervised learning. Physical Review A,
110(2):022411, 2024.
Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Kil-
loran. Quantum embeddings for machine learning. arXiv preprint
arXiv:2001.03622, 2020.
Minzhao Liu, Junyu Liu, Rui Liu, Henry Makhanov, Danylo Lykov, Anuj
Apte, and Yuri Alexeev. Embedding learning in hybrid quantum-classical
228 BIBLIOGRAPHY
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd. Quan-
tum singular-value decomposition of nonsparse low-rank matrices. Phys-
ical review A, 97(1):012327, 2018a.
Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao. Quantum
gram-schmidt processes and their application to efficient state readout
for quantum algorithms. Physical Review Research, 3(4):043095, 2021a.
Román Orús. Tensor networks for complex quantum systems. Nature Re-
views Physics, 1(9):538–550, 2019.
Haoxiang Wang, Maurice Weber, Josh Izaac, and Cedric Yen-Yu Lin. Pre-
dicting properties of quantum systems with conditional generative models.
arXiv preprint arXiv:2211.16943, 2022a.
BIBLIOGRAPHY 229
Liming Zhao, Naixu Guo, Ming-Xing Luo, and Patrick Rebentrost. Provable
learning of quantum states with graphical models, 2023. URL https:
//[Link]/abs/2309.09235.
Yang Qian, Yuxuan Du, and Dacheng Tao. Shuffle-qudio: accelerate dis-
tributed vqe with trainability enhancement and measurement reduction.
Quantum Machine Intelligence, 6(1):1–22, 2024.
Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao,
and Jiasu Wang. Quantum-accelerated multilevel Monte Carlo methods
for stochastic differential equations in mathematical finance. Quantum, 5:
481, June 2021. ISSN 2521-327X. doi: 10.22331/q-2021-06-24-481. URL
[Link]
Shi Jin, Nana Liu, and Yue Yu. Quantum simulation of partial differential
equations via schrodingerisation, 2022. URL [Link]
2212.13969.
Zhong-Xia Shang, Naixu Guo, Dong An, and Qi Zhao. Design nearly optimal
quantum algorithm for linear differential equations via lindbladians, 2024.
URL [Link]
Guang Hao Low and Yuan Su. Quantum eigenvalue processing, 2024. URL
[Link]
Dong An, Jin-Peng Liu, and Lin Lin. Linear combination of hamiltonian
simulation for nonunitary dynamics with optimal state preparation cost.
Phys. Rev. Lett., 131:150603, Oct 2023. doi: 10.1103/PhysRevLett.131.
150603. URL [Link]
150603.
Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying. Laplace transform
based quantum eigenvalue transformation via linear combination of hamil-
tonian simulation, 2024. URL [Link]
Youle Wang, Lei Zhang, Zhan Yu, and Xin Wang. Quantum phase process-
ing and its applications in estimating phase and entropies. Physical Review
A, 108(6), December 2023b. ISSN 2469-9934. doi: 10.1103/physreva.108.
062413. URL [Link]
Hitomi Mori, Kosuke Mitarai, and Keisuke Fujii. Efficient state preparation
for multivariate monte carlo simulation, 2024. URL [Link]
abs/2409.07336.
Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum State Prepa-
ration with Optimal Circuit Depth: Implementations and Applications.
Physical Review Letters, 129(23):230504, November 2022a. doi: 10.1103/
PhysRevLett.129.230504. URL [Link]
PhysRevLett.129.230504.
Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang.
Asymptotically Optimal Circuit Depth for Quantum State Preparation
and General Unitary Synthesis. IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, 42(10):3301–3314, October
2023. ISSN 1937-4151. doi: 10.1109/TCAD.2023.3244885. URL https:
//[Link]/document/10044235.
Nikita Guseynov and Nana Liu. Efficient explicit circuit for quantum
state preparation of piece-wise continuous functions, 2024. URL https:
//[Link]/abs/2411.01131.
Nikita Guseynov, Xiajie Huang, and Nana Liu. Explicit gate construction of
block-encoding for hamiltonians needed for simulating partial differential
equations, 2024. URL [Link]
Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quan-
tum circuits for block encodings of certain sparse matrices, 2023. URL
[Link]
Carsten Blank, Daniel K Park, June-Koo Kevin Rhee, and Francesco Petruc-
cione. Quantum classifier with tailored quantum kernel. npj Quantum
Information, 6(1):41, 2020.
232 BIBLIOGRAPHY
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne.
Journal of machine learning research, 9(11), 2008.
Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data en-
coding on the expressive power of variational quantum-machine-learning
models. Physical Review A, 103(3):032430, 2021.
Cong Lei, Yuxuan Du, Peng Mi, Jun Yu, and Tongliang Liu. Neural auto-
designer for enhanced quantum kernels. arXiv preprint arXiv:2401.11098,
2024.
Supanut Thanasilp, Samson Wang, Marco Cerezo, and Zoë Holmes. Ex-
ponential concentration and untrainability in quantum kernel methods.
arXiv preprint arXiv:2208.11060, 2022.
Yudai Suzuki, Hideaki Kawaguchi, and Naoki Yamamoto. Quantum fisher
kernel for mitigating the vanishing similarity issue. Quantum Science and
Technology, 2022.
Ruslan Shaydulin and Stefan M Wild. Importance of kernel bandwidth in
quantum machine learning. Physical Review A, 106(4):042407, 2022.
Abdulkadir Canatar, Evan Peters, Cengiz Pehlevan, Stefan M Wild, and
Ruslan Shaydulin. Bandwidth enables generalization in quantum kernel
models. arXiv preprint arXiv:2206.06686, 2022.
Maria Schuld. Supervised quantum machine learning models are kernel
methods. arXiv preprint arXiv:2101.11020, 2021.
Sofiene Jerbi, Lukas J Fiderer, Hendrik Poulsen Nautrup, Jonas M Kübler,
Hans J Briegel, and Vedran Dunjko. Quantum machine learning beyond
kernel methods. Nature Communications, 14(1):1–8, 2023.
Xinbiao Wang, Yuxuan Du, Yong Luo, and Dacheng Tao. Towards under-
standing the power of quantum kernels in the nisq era. Quantum, 5:531,
2021a.
Jonas Kübler, Simon Buchholz, and Bernhard Schölkopf. The inductive bias
of quantum kernels. Advances in Neural Information Processing Systems,
34:12661–12673, 2021.
Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert. On
the quantum versus classical learnability of discrete distributions. Quan-
tum, 5:417, 2021.
Daniel Beaulieu, Dylan Miracle, Anh Pham, and William Scherr. Quantum
kernel for image classification of real world manufacturing defects. arXiv
preprint arXiv:2212.08693, 2022.
Pablo Rodriguez-Grasa, Robert Farzan-Rodriguez, Gabriele Novelli, Yue
Ban, and Mikel Sanz. Satellite image classification with neural quantum
kernels. arXiv preprint arXiv:2409.20356, 2024.
Teresa Sancho-Lorente, Juan Román-Roche, and David Zueco. Quantum
kernels to learn the phases of quantum matter. Physical Review A, 105
(4):042432, 2022.
234 BIBLIOGRAPHY
Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan. Quantum phase
recognition via quantum kernel methods. Quantum, 7:981, 2023.
Nana Liu and Patrick Rebentrost. Quantum machine learning for quantum
anomaly detection. Physical Review A, 97(4):042315, 2018.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature,
521(7553):436–444, 2015.
Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li,
Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John
Preskill, et al. Quantum advantage in learning from experiments. Science,
376(6598):1182–1186, 2022.
Evan Peters, João Caldeira, Alan Ho, Stefan Leichenauer, Masoud Mohseni,
Hartmut Neven, Panagiotis Spentzouris, Doug Strain, and Gabriel N Per-
due. Machine learning of high dimensional data on a noisy quantum
processor. npj Quantum Information, 7(1):161, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL
[Link]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-
based learning applied to document recognition. Proceedings of the IEEE,
86(11):2278–2324, 1998.
Warren S McCulloch and Walter Pitts. A logical calculus of the ideas im-
manent in nervous activity. The bulletin of mathematical biophysics, 5:
115–133, 1943.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual
learning for image recognition. In Proceedings of the IEEE conference on
computer vision and pattern recognition, pages 770–778, 2016.
Anders Krogh and John Hertz. A simple weight decay can improve gener-
alization. Advances in neural information processing systems, 4, 1991.
BIBLIOGRAPHY 237
Dongxin Gao, Daojin Fan, Chen Zha, Jiahao Bei, Guoqing Cai, Jianbin Cai,
Sirui Cao, Xiangdong Zeng, Fusheng Chen, Jiang Chen, et al. Establishing
a new benchmark in quantum computational advantage with 105-qubit
zuchongzhi 3.0 processor. arXiv preprint arXiv:2412.11924, 2024.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient meth-
ods for online learning and stochastic optimization. Journal of machine
learning research, 12(7), 2011.
Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with
shallow circuits. Science, 362(6412):308–311, 2018.
Elton Yechao Zhu, Sonika Johri, Dave Bacon, Mert Esencan, Jungsang Kim,
Mark Muir, Nikhil Murgai, Jason Nguyen, Neal Pisenti, Adam Schouela,
et al. Generative quantum learning of joint probability distribution func-
tions. Physical Review Research, 4(4):043092, 2022.
238 BIBLIOGRAPHY
He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue
Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, et al. Experimental
quantum generative adversarial networks for image generation. Physical
Review Applied, 16(2):024051, 2021b.
Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao. Efficient measure
for the expressivity of variational quantum algorithms. Physical Review
Letters, 128(8):080506, 2022c.
Richard M Dudley. The sizes of compact subsets of hilbert space and conti-
nuity of gaussian processes. Journal of Functional Analysis, 1(3):290–330,
1967.
Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Ex-
act and approximate unitary 2-designs and their application to fidelity
estimation. Physical Review A—Atomic, Molecular, and Optical Physics,
80(1):012304, 2009.
BIBLIOGRAPHY 239
Aram W Harrow and Richard A Low. Random quantum circuits are approx-
imate 2-designs. Communications in Mathematical Physics, 291:257–302,
2009.
Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J
Coles. Cost function dependent barren plateaus in shallow parametrized
quantum circuits. Nature communications, 12(1):1791, 2021b.
Arthur Pesah, Marco Cerezo, Samson Wang, Tyler Volkoff, Andrew T Sorn-
borger, and Patrick J Coles. Absence of barren plateaus in quantum
convolutional neural networks. Physical Review X, 11(4):041011, 2021.
Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao. To-
ward trainability of deep quantum neural networks. arXiv preprint
arXiv:2112.15002, 2021b.
Kaining Zhang, Liu Liu, Min-Hsiu Hsieh, and Dacheng Tao. Escaping from
the barren plateau via gaussian initializations in deep variational quantum
circuits. Advances in Neural Information Processing Systems, 35:18612–
18627, 2022b.
Farid Ablayev, Marat Ablayev, Joshua Zhexue Huang, Kamil Khadiev, Nai-
lya Salikhova, and Dingming Wu. On quantum methods for machine
learning problems part ii: Quantum classification algorithms. Big Data
Mining and Analytics, 3(1):56–67, 2019.
Jinjing Shi, Ren-Xin Zhao, Wenxuan Wang, Shichao Zhang, and Xuelong
Li. Qsan: A near-term achievable quantum self-attention network. IEEE
Transactions on Neural Networks and Learning Systems, 2024.
Liangliang Fan and Haozhen Situ. Compact data encoding for data re-
uploading quantum classifier. Quantum Information Processing, 21(3):87,
2022.
Shi-Xin Zhang, Chang-Yu Hsieh, Shengyu Zhang, and Hong Yao. Differen-
tiable quantum architecture search. Quantum Science and Technology, 7
(4):045023, 2022c.
Kehuan Linghu, Yang Qian, Ruixia Wang, Meng-Jun Hu, Zhiyuan Li, Xue-
gang Li, Huikai Xu, Jingning Zhang, Teng Ma, Peng Zhao, et al. Quantum
circuit architecture search on a superconducting processor. Entropy, 26
(12):1025, 2024.
Xinbiao Wang, Junyu Liu, Tongliang Liu, Yong Luo, Yuxuan Du, and
Dacheng Tao. Symmetric pruning in quantum neural networks. arXiv
preprint arXiv:2208.14057, 2022b.
Mingze Li, Lei Fan, Aaron Cummings, Xinyue Zhang, Miao Pan, and Zhu
Han. Hybrid quantum classical machine learning with knowledge distil-
lation. In ICC 2024-IEEE International Conference on Communications,
pages 1139–1144. IEEE, 2024.
Zhan Yu, Hongshun Yao, Mujin Li, and Xin Wang. Power and limitations
of single-qubit native quantum neural networks. Advances in Neural In-
formation Processing Systems, 35:27810–27823, 2022a.
BIBLIOGRAPHY 241
Zoë Holmes, Kunal Sharma, Marco Cerezo, and Patrick J Coles. Connecting
ansatz expressibility to gradient magnitudes and barren plateaus. PRX
Quantum, 3(1):010313, 2022.
Zhan Yu, Qiuhao Chen, Yuling Jiao, Yinan Li, Xiliang Lu, Xin Wang, and
Jerry Zhijian Yang. Non-asymptotic approximation error bounds of pa-
rameterized quantum circuits. In The Thirty-eighth Annual Conference
on Neural Information Processing Systems, 2022b.
Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone,
Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in vari-
ational quantum algorithms. Nature communications, 12(1):6961, 2021b.
Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. Learning unitaries by
gradient descent. arXiv preprint arXiv:2001.11897, 2020.
Zhiqiang Xu, Xin Cao, and Xin Gao. Convergence analysis of gradient
descent for eigenvector computation. International Joint Conferences on
Artificial Intelligence, 2018.
Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao.
Learnability of quantum neural networks. PRX quantum, 2(4):040337,
2021b.
Jun Qi, Chao-Han Huck Yang, Pin-Yu Chen, and Min-Hsiu Hsieh. Theo-
retical error performance analysis for variational quantum circuit based
functional regression. npj Quantum Information, 9(1):4, 2023.
Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli,
and Stefan Woerner. The power of quantum neural networks. Nature
Computational Science, 1(6):403–409, 2021.
Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang.
Statistical complexity of quantum circuits. Physical Review A, 105(6):
062431, 2022.
Kaining Zhang, Junyu Liu, Liu Liu, Liang Jiang, Min-Hsiu Hsieh, and
Dacheng Tao. The curse of random quantum data. arXiv preprint
arXiv:2408.09937, 2024a.
Yuxuan Du, Yibo Yang, Dacheng Tao, and Min-Hsiu Hsieh. Problem-
dependent power of quantum neural networks on multiclass classification.
Physical Review Letters, 131(14):140601, 2023.
Kyle Poland, Kerstin Beer, and Tobias J Osborne. No free lunch for quantum
machine learning. arXiv preprint arXiv:2003.14103, 2020.
BIBLIOGRAPHY 243
Kunal Sharma, Marco Cerezo, Zoë Holmes, Lukasz Cincio, Andrew Sorn-
borger, and Patrick J Coles. Reformulation of the no-free-lunch theorem
for entangled datasets. Physical Review Letters, 128(7):070501, 2022.
Xinbiao Wang, Yuxuan Du, Zhuozhuo Tu, Yong Luo, Xiao Yuan, and
Dacheng Tao. Transition role of entangled data in quantum machine
learning. Nature Communications, 15(1):3716, 2024a.
Xinbiao Wang, Yuxuan Du, Kecheng Liu, Yong Luo, Bo Du, and Dacheng
Tao. Separable power of classical and quantum learning protocols through
the lens of no-free-lunch theorem. arXiv preprint arXiv:2405.07226,
2024b.
Eric R Anschuetz, Hong-Ye Hu, Jin-Long Huang, and Xun Gao. Inter-
pretable quantum advantage in neural sequence learning. PRX Quantum,
4(2):020338, 2023.
Pablo Bermejo, Paolo Braccia, Manuel S Rudolph, Zoë Holmes, Lukasz Cin-
cio, and M Cerezo. Quantum convolutional neural networks are (effec-
tively) classically simulable. arXiv preprint arXiv:2408.12739, 2024.
Seongwook Shin, Yong Siah Teo, and Hyunseok Jeong. Dequantizing quan-
tum machine learning models using tensor networks. Physical Review
Research, 6(2):023218, 2024.
Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and El-
ham Kashefi. Classically approximating variational quantum machine
learning with random fourier features. arXiv preprint arXiv:2210.13200,
2022.
Franz J Schreiber, Jens Eisert, and Johannes Jakob Meyer. Classical sur-
rogates for quantum learning models. Physical Review Letters, 131(10):
100803, 2023.
Yuxuan Du, Min-Hsiu Hsieh, and Dacheng Tao. Efficient learning for
linear properties of bounded-gate quantum circuits. arXiv preprint
arXiv:2408.12199, 2024.
Maxwell Henderson, Samriddhi Shakya, Shashindra Pradhan, and Tristan
Cook. Quanvolutional neural networks: powering image recognition with
quantum circuits. Quantum Machine Intelligence, 2(1):2, 2020.
HTS ALRikabi, Ibtisam A Aljazaery, Jaafar Sadiq Qateef, Abdul Hadi M
Alaidi, and M Roa’a. Face patterns analysis and recognition system based
on quantum neural network qnn. Int. J. Interac. Mob. Tech, 16(8):35–48,
2022.
Hongni Jin and Kenneth M Merz Jr. Integrating machine learning
and quantum circuits for proton affinity predictions. arXiv preprint
arXiv:2411.17856, 2024.
Jiwon Roh, Seunghyeon Oh, Donggyun Lee, Chonghyo Joo, Jinwoo Park,
Il Moon, Insoo Ro, and Junghwan Kim. Hybrid quantum neural network
model with catalyst experimental validation: Application for the dry re-
forming of methane. ACS Sustainable Chemistry & Engineering, 12(10):
4121–4131, 2024.
Yanan Li, Zhimin Wang, Rongbing Han, Shangshang Shi, Jiaxin Li, Ruimin
Shang, Haiyong Zheng, Guoqiang Zhong, and Yongjian Gu. Quantum
recurrent neural networks for sequential learning. Neural Networks, 166:
148–161, 2023a.
Nouhaila Innan, Abhishek Sawaika, Ashim Dhor, Siddhant Dutta, Sairupa
Thota, Husayn Gokal, Nandan Patel, Muhammad Al-Zafar Khan, Ioan-
nis Theodonis, and Mohamed Bennai. Financial fraud detection using
BIBLIOGRAPHY 245
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine trans-
lation of rare words with subword units. In Katrin Erk and Noah A. Smith,
editors, Proceedings of the 54th Annual Meeting of the Association for
Computational Linguistics (Volume 1: Long Papers), pages 1715–1725,
Berlin, Germany, August 2016. Association for Computational Linguis-
tics. doi: 10.18653/v1/P16-1162. URL [Link]
P16-1162.
Taku Kudo and John Richardson. SentencePiece: A simple and language in-
dependent subword tokenizer and detokenizer for neural text processing.
In Eduardo Blanco and Wei Lu, editors, Proceedings of the 2018 Con-
ference on Empirical Methods in Natural Language Processing: System
Demonstrations, pages 66–71, Brussels, Belgium, November 2018. Asso-
ciation for Computational Linguistics. doi: 10.18653/v1/D18-2012. URL
[Link]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual
learning for image recognition. arXiv:1512.03385, 2015.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normal-
ization, 2016. URL [Link]
BIBLIOGRAPHY 247
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Op-
timization. In Yoshua Bengio and Yann LeCun, editors, 3rd Interna-
tional Conference on Learning Representations, ICLR 2015, San Diego,
CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL
[Link]
Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights
and connections for efficient neural networks. In Advances in Neural In-
formation Processing Systems (NeurIPS), pages 1135–1143, 2015.
Joseph McDonald, Baolin Li, Nathan Frey, Devesh Tiwari, Vijay Gade-
pally, and Siddharth Samsi. Great power, great responsibility: Recom-
mendations for reducing energy for training language models. Findings
of the Association for Computational Linguistics: NAACL 2022, 2022.
doi: 10.18653/v1/[Link]-naacl.151. URL [Link]
18653/v1/[Link]-naacl.151.
Greg Yang, Edward J. Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu,
David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng
Gao. Tensor programs v: Tuning large neural networks via zero-shot
hyperparameter transfer. arXiv:2203.03466, 2022.
Shuming Ma, Hongyu Wang, Lingxiao Ma, Lei Wang, Wenhui Wang, Shao-
han Huang, Li Dong, Ruiping Wang, Jilong Xue, and Furu Wei. The era
248 BIBLIOGRAPHY
of 1-bit llms: All large language models are in 1.58 bits. arXiv:2402.17764,
2024.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika,
Dawn Song, and Jacob Steinhardt. Measuring massive multitask language
understanding. Proceedings of the International Conference on Learning
Representations (ICLR), 2021.
Guangxi Li, Xuanqiang Zhao, and Xin Wang. Quantum self-attention neural
networks for text classification, 2023b. URL [Link]
2205.05625.
Yeqi Gao, Zhao Song, Xin Yang, and Ruizhe Zhang. Fast quantum algorithm
for attention computation. 2023. URL [Link]
08045.
Chen-Yu Liu, Chao-Han Huck Yang, Min-Hsiu Hsieh, and Hsi-Sheng Goan.
A quantum circuit-based compression perspective for parameter-efficient
learning. 2024b. URL [Link]
BIBLIOGRAPHY 249
Siyi Yang, Naixu Guo, Miklos Santha, and Patrick Rebentrost. Quan-
tum Alphatron: quantum advantage for learning with kernels and
noise. Quantum, 7:1174, November 2023. ISSN 2521-327X.
doi: 10.22331/q-2023-11-08-1174. URL [Link]
q-2023-11-08-1174.
Chenyi Zhang and Tongyang Li. Comparisons are all you need for optimizing
smooth functions, 2024. URL [Link]
Hao Wang, Chenyi Zhang, and Tongyang Li. Near-optimal quantum algo-
rithm for minimizing the maximal loss, 2024c. URL [Link]
abs/2402.12745.
Yidong Liao and Chris Ferrie. Gpt on a quantum computer. 2024. URL
[Link]
Nikhil Khatri, Gabriel Matos, Luuk Coopmans, and Stephen Clark. Quixer:
A quantum transformer model. 2024. URL [Link]
2406.04305.
Gabriel Nagy. On the haar measure of the quantum su (n) group. Commu-
nications in mathematical physics, 153:217–217, 1993.
Aidan Roy and Andrew J Scott. Unitary designs and codes. Designs, codes
and cryptography, 53:13–31, 2009.
Quantum kernel machines offer potential solutions to the limitations of classical kernel methods by utilizing quantum circuits for feature mapping. This allows quantum kernels to explore exponentially larger feature spaces compared to classical kernels, potentially capturing complex patterns that classical methods might miss. Moreover, quantum kernels can be implemented on near-term quantum devices, making them a practical tool for leveraging quantum advantages in machine learning scenarios .
The No-Free-Lunch theorem, when applied to QNNs, implies that there is no universal quantum model that can outperform classical models across all datasets and tasks. However, it highlights that QNNs can be advantageous in specific scenarios, particularly when quantum properties, like entanglement, are beneficial. This underscores the idea that QNNs might not be superior across all applications but can offer particular advantages in niche domains where classical models are limited, emphasizing the need for task-specific considerations when selecting machine learning models .
Advancements in applications involving quantum entangled data, such as those demonstrating improved communication and reduced resource requirements in distributed learning frameworks, suggest potential growth areas for quantum machine learning. These include fields like cryptography, where secure quantum communication offers significant advantages, and complex data processing, where entanglement can enhance computational efficiency and security. The ability to harness quantum resources efficiently could open new research and application domains, fostering innovative solutions in data-intensive and security-sensitive sectors .
The Hadamard product operation within the block encoding framework is achieved by constructing encodings of two matrices A and B and applying the block encoding process to perform element-wise multiplication. Mathematically, for matrices A and B, with their respective block encodings, a permutation operation is used to align elements correctly, converting the tensor product to the Hadamard product. This process is enabled by the existence of permutation unitaries that shift necessary elements to compute the A ◦ B efficiently within quantum circuits .
Entanglement plays a crucial role in achieving quantum advantage by potentially reducing the communication requirements in non-local machine learning tasks and enabling quantum contextuality, which can yield polynomial advantages over classical models. Entangled states can process and store correlations unavailable to classical systems, thereby facilitating tasks where such correlations are beneficial, for instance, in entangled data scenarios which classical systems struggle to replicate effectively .
Block encoding addresses the challenge of representing non-unitary matrices in quantum computing by encoding a non-unitary matrix A into a unitary form. This is necessary because quantum gates are inherently unitary. By block encoding, we effectively create an (α, a, ε)-block encoding of A, where the unitary operation U allows for approximating A up to an error ε using the largest singular value representation. This technique permits the integration of non-unitary operations into quantum algorithms, facilitating tasks like solving linear equations on quantum systems .
Quantum neural networks possess a potentially higher expressivity than classical models because they can represent a broader class of functions, particularly those involving quantum phenomena, such as entanglement and superposition, which classical models cannot naturally encode. This increased expressivity implies that QNNs can capture complex, quantum-specific patterns and relationships that would be infeasible or require significant computational resources in classical approaches. As a result, QNNs might provide significant predictive advantages in domains where these quantum effects are prominent .
Differential privacy in quantum machine learning ensures that the addition or removal of a single training sample does not significantly affect the model's output, thus protecting individual data points from leakage. This quantum adaptation of differential privacy enhances data security given the non-trivial randomization processes inherent in quantum measurements, which can naturally obfuscate data-specific details. The application of differential privacy is crucial as it ensures that QML models remain robust against potential privacy violations inherent in classical and quantum attacks .
Quantum feature maps differ from classical feature maps in that they encode data into quantum states, which allows them to operate in exponentially large complex-valued vector spaces. This capability enables them to capture and process intricate patterns and correlations that would be challenging or infeasible for classical feature maps. The advantage for machine learning is significant potential improvements in pattern recognition and predictive accuracy, most notably in high-dimensional data scenarios that leverage the inherent parallelism and entanglement of quantum computing .
Quantum neural tangent kernels (QNTK) help to demonstrate the exponential convergence rate of over-parameterized QNNs. They provide a theoretical framework to explain the fast convergence towards optimal local minima in the optimization landscape. This is particularly beneficial in training scenarios where gradient-descent-based methods are employed, as QNTK aids in understanding the dynamics of weights during training, thereby supporting efficient training of QNNs .