=Paper= {{Paper |id=Vol-3077/paper06 |storemode=property |title=Classification problem solving using quantum machine learning mechanisms |pdfUrl=https://ceur-ws.org/Vol-3077/paper06.pdf |volume=Vol-3077 |authors=Alina O. Savchuk,Nonna N. Shapovalova }} ==Classification problem solving using quantum machine learning mechanisms== https://ceur-ws.org/Vol-3077/paper06.pdf

Classification problem solving using quantum
machine learning mechanisms
Alina O. Savchuk1 , Nonna N. Shapovalova1
1
Kryvyi Rih National University, 11 Vitalii Matusevych Str., Kryvyi Rih, 50027, Ukraine

Abstract
Due to the similarity of the computational and probabilistic nature of quantum computing and machine
learning, the idea arose to optimize the learning process using quantum methods. There are both
fundamentally new algorithms, such as HHL, and quantum-improved ones: QPCA, QSVM. In this article,
we will look at the QSVM algorithm step by step, starting from the basics described in section 2 and
gradually delving into the composition of the algorithm. Thus, after the basics, we will consider the
quantum phase estimation, which is part of the HHL algorithm, and then the QSVM algorithm, the
component of which is the HHL. We also will consider the QPCA algorithm, which can be applied before
the QSVM algorithm to reduce the dimension of the data sample. In this way, we explore the fundamental
difference between classical algorithms and their quantum counterparts. We also implement the QSVM
method in practice and compare the obtained practical results with theory. As a result, we obtained high
quality of accuracy (100 %) compared to the classical SVM (83 %) on a data sample of dimension 72.
However, we found out that the learning time on a quantum device is far from ideal (it can reach 5 min for
a sample of this size). The study aims to theoretically argue or disprove the hypothesis about the efficiency
of quantum computing for machine learning algorithms. The object of research is the programming
of quantum computers. The research subject is the study of quantum computing mechanisms for the
implementation of machine learning problems. The research result is a software module that allows
evaluating the efficiency of the classification task on a quantum computer. It also can be used to compare
the results obtained from classical and quantum devices. Research methods: theoretical analysis of
the foundations of quantum computing: principles of superposition and entanglement, linear algebra,
probability theory over complex numbers; building a model of one qubit and multi-qubit system; research
of quantum machine learning algorithms’ work principles and their complexity; empirical comparison
of quantum machine learning methods with their classical counterparts.

Keywords
quantum machine learning, classification problem, HHL algorithm, quantum principal component
analysis, quantum support vector machine

1. Introduction
While building a quantum computer is still a daunting engineering challenge, it already has a
long list of areas to be effective [1, 2]:

• data modeling (weather forecast, chemical modeling);
CS&SE@SW 2021: 4th Workshop for Young Scientists in Computer Science & Software Engineering, December 18, 2021,
Kryvyi Rih, Ukraine
" stereoalina@gmail.com (A. O. Savchuk); shapovalovann09@gmail.com (N. N. Shapovalova)
~ http://mpz.knu.edu.ua/pro-kafedru/vikladachi/shapovalova-n-n (N. N. Shapovalova)
0000-0003-4335-3714 (A. O. Savchuk); 0000-0001-9146-1205 (N. N. Shapovalova)
© 2022 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)

160
• creation of drugs (search for new formulas for drugs by studying the spatial structure of
protein compounds, diagnostics, and testing of various types of diseases);
• logistics (combinatorial traveling salesman problem);
• search optimization (Google uses quantum technologies to refine search results, taking
into account more important ones);
• data security (quantum protocols for encryption and data transmission);
• military engineering (improving the accuracy of radar weapons);
• machine learning (more accurate solutions and faster learning algorithms).

Therefore, the field of quantum computing have met with increasing interest. Governments
of countries such as China, the USA, Germany, Switzerland, Russia, and others are investing in
quantum computing technologies development to take a leading position in the quantum race.
Private companies, including Google, IBM, Microsoft, Intel, Amazon, are not lagging behind.
The number of qubits plays an influential role in quantum superiority achievement, but no
less important, one might even say, the decisive factor is the “quantum volume” – a metric that
determines the power of a quantum computer in conjunction with the level of computational
errors. Today, Honeywell is the leader in these indicators, setting a record of 64 units of quantum
volume [3].
However, quantum computers may be useless without appropriate scientific knowledge about
their proper use. In this regard, the IBM company has a policy of encouraging interest in
research in this area, providing hardware (IBM Q) and software (Qiskit) tools on a costless basis
[4]. These tools allow anyone to conduct experiments on real-life quantum installations of the
order of 1 to 5 qubits, with a quantum volume from 1 to 32 units.
There are the following technologies for constructing qubits, implemented in practice: quan-
tum dots (Intel), superconducting elements (D-Wave, Google, IBM), vacuum traps (IonQ, AQT,
Honeywell), vacancies in the diamond lattice (Quantum Diamond Technologies) [5]. The most
popular approach is to build qubits on superconducting elements.
The biggest challenge for building any quantum computer is the problem of overcoming
decoherence. Decoherence is the process of destroying the coherence of a coupled qubits
system. This phenomenon is created by thermodynamic processes when interacting with the
environment. Decoherence disrupts the communication of the system of qubits and destroys
their quantum properties, which negates the advantage of a quantum computer over a classical
one. This problem is usually solved by combining more physical qubits into a single logical one.
This technique is called quantum error correction. Quantum error correction is well developed
in theory but not achievable in practice because the noise level of physical qubits is still too
high.
There are such fundamental problems associated with the possibility of applying quantum
machine learning algorithms [6, 7, 8]:

• input problem;
• output problem;
• problem of calculation;
• the problem of comparative analysis.

161
Quantum computers are known to provide exponential acceleration in some cases. But data
input and output operations are carried out by transferring information from the classical world
to the quantum one and vice versa. These operations can be quite time-consuming and, most
importantly, can completely negate the benefits of exponential problem solving. The data entry
problem can be solved by creating a quantum equivalent memory (QRAM). This problem is
another significant engineering problem.
The calculation problem is related to input and output problems. It is impossible to know in
advance how many gates a quantum computer will need when working with classical devices.
Although quantum computers can solve big tasks better than classical computers, it is still
unknown how big a problem must be to gain a quantum advantage.
The problem with the comparative analysis is that it is sometimes difficult to argue that the
quantum algorithm is better than all the known classical ones. This claim requires extensive
comparative testing with modern heuristic methods. Establishing lower bounds for quantum
algorithms would partially solve this problem.
Thus, it is necessary to develop software for quantum machine learning considering all the
described technical and algorithmic problems.

2. Quantum computing basics
A quantum computer operates with minimal information units - qubits. A qubit can be repre-
sented as a unit vector of a 2-dimensional complex space:

|𝜑⟩ ∈ 𝐻, ‖ 𝜑 ‖= 1, 𝑑𝑖𝑚 𝐻 = 2. (1)
Here |𝜑⟩ is a column vector, 𝐻 is a Hilbert space. A qubit can be 0 and 1, just like a bit:
[︃ ]︃ [︃ ]︃
1 0
|𝑞0 ⟩ = |0⟩ = , |𝑞0 ⟩ = |1⟩ = (2)
0 1

And also other values that represent the probability of occurrence of zero or one. Such
probabilities are called probability amplitudes. In example (3) the qubit |𝑞0 ⟩ can take the value
of either 0 or 1 (the probability of meeting this or that event is 12 ). In this case, they say that the
qubit is in superposition.
[︃ 1 ]︃
1 𝑖 √
|𝑞0 ⟩ = √ |0⟩ + √ |1⟩ = 𝑖2 (3)
2 2 √
2

The sum of the probabilities should always be equal to one. For complex numbers, this means
that the vector must be normalized. That is, for the vector:

|𝜓⟩ = 𝛼|0⟩ + 𝛽|1⟩, 𝛼, 𝛽 ∈ C (4)
the following condition has to be met:

(5)
√︀
|𝛼|2 + |𝛽|2 = 1

162
To measure the state of a system with one qubit of information, one must first choose an
orthonormal basis:

|𝑥⟩, |𝑦⟩ : ⟨𝑥|𝑦⟩ = 0, ‖𝑥‖ = ‖𝑦‖ = 1, (6)
and then take measurements on this basis. Thus, the state |𝑥⟩ encountering probability when
measuring the state |𝜓⟩ equal to the square of the modulus of the scalar product of the row
vector ⟨𝑥| and the column vector |𝜓⟩:

𝑝(|𝑥⟩) = |⟨𝑥|𝜓⟩|2 (7)
After measurement, the system from the state |𝜓⟩ can pass into the state |𝑥⟩ or the state |𝑦⟩
and does not change it after repeated measurement. Therefore, we can say that the measurement
process converts quantum information into classical information. That is why measurements
are most often at the very end of the algorithm.
Usually, we make measurements in the computational basis |0⟩, |1⟩. However, we can make
measurements in other bases. For example, measuring the qubit from (3) in the Hadamard basis
|+⟩, |−⟩, we obtain |⟨+|𝑞0 ⟩|2 = 0 and |⟨−|𝑞0 ⟩|2 = 1.
The state of a system consisting of more than one qubit can be represented as the tensor
product of qubits. For example, the system state consisting of qubits |𝑎⟩ and |𝑏⟩ is described
in (8). Thus, a system of 𝑛 qubits is a vector with dimension 2𝑛 . In this case, the number 𝑚,
encoded by a vector in its pure form, reflects the state of the system, where the string 𝑚 + 1
takes the value 1.
⎡ [︂ ]︂⎤ ⎡ ⎤
𝑏0 𝑎0 𝑏0
⎢𝑎0 × 𝑏1 ⎥ ⎢𝑎0 𝑏1 ⎥
|𝑎𝑏⟩ = |𝑎⟩ ⊗ |𝑏⟩ = ⎢ [︂ ]︂⎥ = ⎢ ⎥ (8)
⎣ 𝑏0 ⎦ ⎣𝑎1 𝑏0 ⎦
𝑎1 ×
𝑏1 𝑎1 𝑏1
If two qubits are in a superposition state, the system will transition to one of four states
during measurement:

(𝛼|0⟩ + 𝛽|1⟩)(𝛾|0⟩ + 𝛿|1⟩) = 𝛼𝛾|00⟩ + 𝛼𝛿|01⟩ + 𝛽𝛾|10⟩ + 𝛽𝛿|11⟩ (9)
In this case, the sum of the squares of all possible states is equal to 1:

|𝛼𝛾|2 + |𝛼𝛿|2 + |𝛽𝛾|2 + |𝛽𝛿|2 = 1 (10)
However, not all multi-qubit systems can be decomposed into the tensor product of several
separate states. For example, for the Bell state √12 (|00⟩ + |11⟩), the measurement of the first
qubit will result in the instantaneous measurement of the second: it will no longer be in a
superposition state. If the measurement of one qubit leads to the measurement of the second,
the state of such qubits is called entangled.
Based on formula (9), the system qubits independence can be verified by the equality of the
product of the external and internal coefficients of the system. Thus, if equality is not met (as
shown in (11)), then the system is confusing:

163
𝛼𝛾 × 𝛽𝛿 ̸= 𝛼𝛿 × 𝛽𝛾 (11)
All operators performed on the state vector must be unitary. That is, for the operator 𝑈 , its
adjoint operator must be equal to the inverse:

𝑈 𝑈 * = 𝑈 *𝑈 = 𝐼 (12)
Another property of unitary operators is that when they are applied, the scalar product of
vectors (the angle between them) has preserved:

∀𝜑, 𝜓 ∈ 𝐻|⟨𝑈 |𝜑⟩|⟨𝑈 |𝜓⟩| = |⟨𝜑𝜓⟩| (13)
In addition to this, the length of the vector has also preserved:

∀𝜑 ‖ 𝑈 |𝜑⟩ ‖=‖ |𝜑⟩ ‖ (14)
We can also write the wave function from (5) in the following form:

𝜃 𝜃
|𝜓⟩ = 𝑒𝑖𝛾 (cos |0⟩ + 𝑒𝑖𝜑 sin |1⟩) (15)
2 2
where 𝑒𝑖𝛾 is global phase, 𝑒𝑖𝜑 is local phase. The global phase does not affect the calculation
results because it is not observable.
Each operator has a finite set of eigenvalues and eigenphases. Eigenstate is a state that
is immune to some operations. After applying the operator for such a state, the probability
amplitude and the local phase will not change, but the global phase will change.Eigenphase is
the global phase acquired by the eigenvalue. The global phase carries information about the
applied operator. We can obtain this information by using a phase estimation.

3. Quantum phase estimation
Quantum phase estimation (QPE) is one of the commonly used building blocks of quantum
machine learning algorithms. This algorithm helps to extract unobservable information from
the global phase 𝜃 of the quantum operator 𝑈 :

𝑈 |𝜓⟩ = 𝑒2𝜋𝑖𝜃 |𝜓⟩ (16)
where |𝜓⟩− is an eigenvector and |𝑒2𝜋𝑖𝜃 − is an eigenvalue.
As we can see from (16), each eigenphase 𝜃𝑗 is associated with eigenstate 𝑢𝑗 . Worth noticing
the eigenphase 𝜃𝑗 is a fraction of 360° in the output quantum register. Looking ahead, the value
of the output register 𝑅 with size 𝑚 will take the value:

𝑅 = ∀𝜃𝑗 360 × 2𝑚 (17)
The QPE algorithm writes the eigenphase of the 𝑈 operator in the Hadamard basis. Then,
using inverse QFT, we convert the value from the Hadamard basis to the computational basis.
In other words, using the QPE algorithm, information is converted from the global phase to

164
its own one. Then the information is decoded to produce the result with a READ operation.
Algorithm description:

• system initialization where |𝜓⟩ has stored in one register and the value 2𝑛 𝜃 in another
register:
|𝜓0 ⟩ = |0⟩⊗𝑛 |𝜓⟩; (18)
• obtaining a superposition by applying the 𝑛-bit operation 𝐻 ⊗𝑛 on the second register:
1 ⊗𝑛
|𝜓1 ⟩ = 𝑛 (|0⟩ + |1⟩) |𝜓⟩; (19)
22
• creates a supervised CU statement that applies only if the control bit is |1⟩. Based on (15):
𝑗 𝑗−1 𝑗−1 𝑗
𝑈 2 |𝜓⟩ = 𝑈 2 |𝜓⟩ = 𝑈 2 𝑒2𝜋𝑖𝜃 |𝜓⟩ = ... = 𝑒2𝜋𝑖2 𝜃 . (20)
𝑗−1
Now it is necessary to apply controlled operations 𝐶𝑈 2 in the range 0 ≤ 𝑗 ≤ 𝑛 − 1 :

1 2𝜋𝑖𝜃2𝑛−1 1
|𝜓2 ⟩ = 𝑛 (|0⟩ + 𝑒 + |1⟩) ⊗ ... ⊗ (|0⟩ + 𝑒2𝜋𝑖𝜃2 + |1⟩)⊗
22
2𝑛 −1 (21)
2𝜋𝑖𝜃20 1 ∑︁ 2𝜋𝑖𝜃𝑘
⊗(|0⟩ + 𝑒 + |1⟩) ⊗ |𝜓⟩ = 𝑛 𝑒 |𝑘⟩) ⊗ |𝜓⟩
2 2 𝑘=0

where 𝑘 is an integer representation of 𝑛-bit numbers.
• perform inverse Fourier transform:

𝑛
2 −1 2 −1 2 −1 𝑛 𝑛
1 ∑︁ 2𝜋𝑖𝜃𝑘 𝑄𝐹 𝑇𝑛−1 1 ∑︁ ∑︁ − 2𝜋𝑖𝑘 (𝑥−2𝑛 𝜃)
|𝜓3 ⟩ = 𝑛 𝑒 |𝑘⟩) ⊗ |𝜓⟩ −→ 𝑛 𝑒 2𝑛 |𝑥⟩ ⊗ |𝜓⟩ (22)
2 2 𝑘=0 2
𝑥=0 𝑘=0

• measure the system and get the answer in the auxiliary register:

|𝜓4 ⟩ = |2𝑛 𝜃⟩ ⊗ |𝜓⟩ (23)

Thus, you can get reliable information about the global phase if 2𝑛 𝜃 is an integer. Otherwise,
reliable information will be received with a probability of about 40%. We can improve this
probability by increasing the number of qubits. If you need to get your eigenphase by 𝑝 bits of
accuracy and the probability does not exceed 𝑒, you can determine the number of qubits 𝑚 in
the following way:
1
𝑚 = 𝑝 + ⌈log 2 + ⌉ (24)
𝜀
The considered algorithm is irreplaceable for some QML algorithms. For example, the HHL
algorithm uses QPE to obtain critical information about the matrix to be inverted.

165
4. Quantum machine learning algorithms
Systems of linear equations (SLE) in machine learning are the foundation of many algorithms.
In general, a system of 𝑛 equations is written as follows:

𝐴|𝑥⟩ = |𝑏⟩ (25)

To get a matrix form solution, it is necessary to find the inverse matrix 𝐴−1 :
𝑁
∑︁−1
|𝑥⟩ = 𝐴 −1
|𝑏⟩ = 𝜆−1
𝑗 𝑏𝑗 |𝑢𝑗 ⟩ (26)
𝑗=0

where |𝑢𝑗 ⟩ is the 𝑗 𝑡ℎ eigenvector of 𝐴 and 𝜆𝑗 id eigenvalue.
Among the traditional algorithms for finding the solution vector 𝑥, the nonlinear conjugate
gradient method can be distinguished as the most optimal algorithm. Matrix 𝐴. in this case,
must be valid and meet the condition:

𝐴 = 𝐴𝑇 > 0 (27)

The HHL algorithm is used to solve SLN on a quantum computer. Since only unitary operators
can be used in quantum algorithms, the matrix 𝐴 must be Hermitian.
The HHL algorithm (figure 1) is effective in such cases:
• if one uses it as a structural element of a quantum machine learning algorithm;
• when it’s necessary to check the equality of vectors |𝑥⟩ and |𝑦⟩;
• when one needs to find some derivative characteristic (sum, average, frequency compo-
nent) of the vector |𝑥⟩.
Figure 1 shows an example of a quantum circuit that implements the HHL algorithm. Here are
three quantum registers, initialized to |0⟩. The 𝑛𝑙 register stores the binary representation of the
eigenvalues of 𝐴. The rest of the registers are used as service registers for storing intermediate
calculations.
A step-by-step description of the algorithm [9]:
• we put 𝑁 = 2𝑛𝑏
• loading the vector |𝑏⟩ through a transformation of the form |0⟩𝑛𝑏 ↦→ |𝑏⟩𝑛𝑏
• application of Quantum Phase Evaluation (QPE):
𝑁
∑︁−1
𝑈 = 𝑒𝑖𝐴𝑡 = 𝑒𝑖𝜆𝑗 𝑡|𝑢𝑗 ⟩⟨𝑢𝑖 | (28)
𝑗=0

The quantum state of the register, expressed in its own basis 𝐴:
𝑁
∑︁−1
𝑏𝑗 |𝜆𝑗 ⟩𝑛𝑙 |𝑢𝑗 ⟩𝑛𝑏 (29)
𝑗=0

where |𝜆𝑗 ⟩𝑛𝑙 – is 𝑛𝑙 -bit binary representation of 𝜆𝑗 .

where 𝐶 – is a normalization constant and, as expressed in the current form above, should
be less than the smallest eigenvalue 𝜆𝑚𝑖𝑛 in magnitude |𝐶| < 𝜆𝑚𝑖𝑛 ;
• applying the QPE † operation. In this case, ignoring QPE errors will be displayed in the
following form:
𝑁 −1
(︃√︃ )︃
∑︁ 𝐶2 𝐶
𝑏𝑗 |0⟩𝑛𝑙 |𝑢𝑗 ⟩𝑛𝑏 1 − 2 |0⟩ + |1⟩ (31)
𝜆𝑗 𝜆𝑗
𝑗=0

• measurement of the auxiliary qubit on a computational basis. If the result is 1, then the
register is following after measurement:
(︃√︃ )︃ 𝑁 −1
1 ∑︁ 𝑏𝑗
∑︀𝑁 −1 |0⟩𝑛𝑙 |𝑢𝑗 ⟩𝑛𝑏 (32)
2
𝑗=0 |𝑏𝑗 | /|𝜆𝑗 |
2 𝜆𝑗
𝑗=0

• applying the observable 𝑀 to calculate 𝐹 (𝑥) = ⟨𝑥|𝑀 |𝑥⟩.

Figure 1: HHL algorithm schematic.

The following parameters affect the performance of the SLN solution: 𝑛 is the size of the SLN,
𝑘 is the condition number of the matrix 𝐴 𝑠 is the sparsity of the matrix 𝐴, 𝜀, is the accuracy of
the solution.

167
The computational complexity for the conjugate vector method is 𝑂(𝑛𝑠𝑘 log 1/𝜀). The HHL
algorithm has a computational complexity of 𝑂(𝑘 2 𝑠2 𝜀−1 log 𝑛), which provides exponential
acceleration depending on the size of the SLN 𝑛. However, one should remember that this
algorithm does not provide an exact solution. By analogy with numerical methods, HHL gives
an approximate solution with an accuracy 𝜀.
Principal component analysis (PCA) is used to filter out correlated features and dimensionality
reduction. We can achieve this by projecting the data point onto a new, lower-dimensional basis.
The vectors covering this basis are called principal components and are the eigenvectors of
the covariance matrix. The most costly action of PCA algorithm is considered to be the proper
decomposition of the covariance matrix 𝜎:
1
𝜎= 𝑋𝑇 𝑋 (33)
𝑛−1
where 𝑋 is an 𝑚 × 𝑛, 𝑚 is data points, 𝑛 is features. As with the HHL algorithm, the QPCA
algorithm should help us speed up the costly process of decomposing the covariance matrix.
The algorithm consists of two steps:
1) the QPCA algorithm requires reusable SWAP operations on 𝜌 ⊗ 𝜎 for representation of the
covariance matrix. The density operator is:
∑︁ ∑︁
𝜌= 𝜌𝑗 |𝜓𝑗 ⟩⟨𝜓𝑗 |, 𝜌𝑗 = 1 (34)
𝑗 𝑗

where 𝜌𝑗 is the probability of encountering a mutually orthogonal state 𝜓𝑗 . This view
requires reusable SWAP operations;
2) phase estimation to determine the eigenvalues of 𝜎. The representation of 𝜎 in the density
operator 𝜌 form makes it possible to obtain the phase estimates of the eigenvector at the
output and the associated eigenvalue (variance value) in the output register. The principal
component with an eigenvalue and a vector is determined randomly but depends on the
magnitude of the variance. Most likely, it will be the component with the greatest variance.
Using 𝜌 as the initial state, we get the state with the highest rank value:
∑︁
𝑟𝑗 |𝜒𝑗 ⟩⟨𝜒𝑗 | ⊗ |𝑟˜𝑗 ⟩⟨𝑟˜𝑗 | (35)
𝑗

where 𝜒𝑗 – eigenvector of 𝜌 operator, ˜𝑟𝑗 – estimate of the corresponding eigenvalue 𝑟𝑗 .
This state will be decomposed into an eigenvector/eigenvalue pair. Then we can get the
mathematical expectation of an eigenvector with an eigenvalue 𝑟𝑗 using the measurement
operation ⟨𝜒𝑗 |𝑀 |𝜒𝑗 ⟩〉.
The traditional PCA algorithm has a computational complexity of 𝑂(𝑑), where 𝑑 is the
number of features. The quantum analogue of this method is performed in time 𝑂(𝑅 log 𝑑),
where 𝑅 is the smallest rank of the approximation of the covariance matrix. In this case, the
exponential acceleration by the quantum algorithm is achieved under the condition 𝑅 < 𝑑 [10].
Support vector machine allows you to find a hyperplane maximizing the distance between two

168
hyperplanes:
1 ∑︁ ∑︁ →
𝑎𝑖 −
𝑥 𝑖 × 𝑎𝑗 →
−
∑︁
𝑎 𝑗 𝑦𝑖 − 𝑥𝑗 (36)
2
𝑖 𝑖 𝑗

where 𝑥𝑖 is the 𝑖𝑡ℎ – point in the feature space, 𝑦𝑗 is the tagged class and 𝑎𝑗 – parameter of the
model. Thus, to find the optimal hyperplane, it is necessary to find →−𝑎 = [𝑎1 , ..., 𝑎𝑚 ]. Unlabeled
data can be classified by the formula:

𝑎𝑖 →
−
𝑥𝑖×→ −
∑︁
𝑠𝑖𝑔𝑛( 𝑥 − 𝑏) (37)
𝑖

The QSVM method allows you to speed up the calculation of the dot product → −𝑥 𝑖 × 𝑥. This
product is also known as the kernel matrix 𝐾.
Let us rewrite the problem of finding the vector →
−
𝑎 in the LS-SVM form of a system of linear
equations to apply the HHL algorithm:
[︃ ]︃ [︃ ]︃
𝑏 0
→
− = 𝐹 −1 → − (38)
𝑎 𝑦

Matrix 𝐹 consists of scalar products of the kernel matrix 𝐾 of the training sample:
[︃ ]︃
0 𝑖𝑇
(39)
1 𝐾 + 𝛾1 𝐼

where 𝑖 is the unit vector, 𝐼 is the unit matrix, 𝛾 is the hyperparameter.
We use HHL to find 𝐹 −1 . At the same time, we pass the amplitude-encoded |→ −
𝑦 ⟩ = [0, →
−
𝑦]
classes’ vector to the input register of the phase estimation eigenstate. Moreover, we regard
|→
−
𝑦 ⟩ as a superposition of eigenstates of 𝐹 . As a consequence, |𝐹 −1 →
−𝑦 ⟩ exactly coincides with
→
−
the desired solution |𝑏, 𝑎 ⟩.
It remains us only to classify the data by obtaining a sign. If we store the superposition of
the training data amplitudes 𝑎𝑖 in one QRAM quantum register and the new data point → −𝑥 in
the other, we will be able to apply the SWAP test procedure. This procedure is constructed so
that the probability 𝑝 becomes 𝑝 < 0.5 for the +1 sign and 𝑝 ≥ 0.5 for the -1 sign. By repeating
the SWAP test, it is possible to estimate the value of the probability 𝑝 to the desired accuracy.
In the best case, the implementation of the SVM algorithm has a complexity of 𝑂(𝑝𝑜𝑙𝑦(𝑚, 𝑛)),
where 𝑚 is the amount of data used for training, and 𝑛 is the number of features. The quantum
analog of the SVM algorithm allows you to obtain a logarithmic acceleration of 𝑂(log 𝑚𝑛).

5. Research results
It was decided to use the QSVM algorithm using the Qiskit public library and the IBM Quantum
Experience cloud service to solve the assigned task. For comparison, the original classic SVM
algorithm and the Google Colaboratory cloud development environment were used. It was
significant to check the practical applicability of quantum machine learning algorithms. As
well as the existing algorithms’ ability to correctly perform the task of not only binary but

169
also multiple classifications have been checked. The dataset "ElectricalFaultDetection.csv" was
selected to detect electrical faults at various locations on the power line. This dataset has six
features and six classes. Since the maximum number of qubits in the free-for-all IBM machines
is five, only the first five features participated in the training. The number of data points in
this dataset is 7861. As it turned out, using all the data for training and testing would take at
least a couple of days on a quantum device (without waiting in the queue). For this reason,
we use a sample of shuffled data with a dimension of 72 for the quantum algorithm training.
However, we used all data to train the classical SVM. Each sample has been divided into 75 %
of the training data and 25 % of the test data. With the optimal selection of parameters, the
classical SVM algorithm has been trained in 2.64 s. with an accuracy of 73.25 %. Let us consider
in more detail the results obtained by execution on different quantum devices.
First, let’s look at why training on large data sets on today’s quantum devices is not desirable.
Figure 2 shows how long it takes a model to train in a quantum simulator. As we can see, the
time increases with the growth of the size of the training and test samples with a polymodal
rate. It makes sense since we are only simulating quantum behavior.
If you perform the same actions on the real quantum device, the time will grow less and less
with the growth of the sample according to the logarithmic law (figure 3). This result is in line
with theory, but if one pays attention, the execution time for a sample size of 72 reaches almost
5 minutes. The classical method only needs about 3 seconds. Of course, as the size of the qubit
increases, it will be possible to train the data in parallel, which will give a greater speedup.
However, one cannot ignore the fact that the need to run the same circuit many times, external
noise, and the time spent on error correction influence the total program execution time.
In terms of accuracy, it ranges from 61 % to 94 % on a training set of up to three data points.
For the training set with a dimension of four and higher, we got an accuracy of 100 %. The
accuracy of the classical SVM with the same training and test sample size was 83 %. Consider
now the time it took for the program to execute on various quantum devices: qasm_simulator
474 s, lima 481 s, quito 352 s and belem 347 s. As we see, the runtime on real quantum devices
ultimately does not differ much from the runtime on the simulator.
From the results obtained earlier, we can conclude that quantum devices are not efficient
for small datasets. However, QPU needs more qubits for large datasets and, of course, more
quantum volume. When QPUs achieve this condition, quantum computers can become an
indispensable assistant in machine learning.

6. Conclusion
In the problem studying process using a quantum computer to solve the classifying machine
learning problem from the theoretical side, the high advantage of quantum computing algorithms
over classical ones was substantiated. It was written a module that allows you to perform the
classification task on a classical and quantum device to check the current state of quantum
computing. This module enables performing the classification task on a classical and quantum
device. It has been proven that a quantum computing device can solve both binary and multiclass
classification tasks. Empirical research has shown that the current state of quantum computing
is far from quantum superiority in accelerating classical teaching methods. However, this does

170
Figure 2: Training of the model on the IBM quantum simulator.

not negate the importance of research in this area. When the stable quantum computer is
invented with sufficient computational resources to perform real-world tasks, the need for
theoretically based quantum algorithms will increase. Therefore, an important task is to build
fundamentally new algorithms for quantum machine learning. In the future, it is planned to
study the possibility of using quantum machine learning to increase the forecasting accuracy of
short-term time series.

171
Figure 3: Training of the model on the IBM quantum belem device.

References
[1] L. V. Lehka, S. V. Shokaliuk, Quantum programming is a promising direction of IT
development, CEUR Workshop Proceedings 2292 (2018) 76–82.
[2] S. O. Semerikov, A. M. Striuk, T. A. Vakaliuk, A. V. Morozov, Quantum information
technology on the Edge, CEUR Workshop Proceedings 2850 (2021) 1–15. URL: http:
//ceur-ws.org/Vol-2850/paper0.pdf.
[3] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin,
M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson, B. Neyenhuis, Demonstration

172
of the trapped-ion quantum CCD computer architecture, Nature 592 (2021) 209–213.
doi:10.1038/s41586-021-03318-4.
[4] L. V. Lehka, A. O. Bielinskyi, S. V. Shokaliuk, V. N. Soloviev, P. V. Merzlykin, Y. Y. Bo-
hunenko, Prospects of quantum informatics and the study of its basics in the school course,
in: S. Semerikov, V. Osadchyi, O. Kuzminska (Eds.), Proceedings of the Symposium on
Advances in Educational Technology, AET 2020, University of Educational Management,
SciTePress, Kyiv, 2022.
[5] R. V. Dushkin, Review of modern state of quantum technologies, Computer Research and
Modeling 10 (2018) 165–179. doi:10.20537/2076-7633-2018-10-2-165-179.
[6] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, S. Lloyd, Quantum machine
learning, Nature 549 (2017) 195–202. doi:10.1038/nature23474.
[7] P. V. Zahorodko, S. O. Semerikov, V. N. Soloviev, A. M. Striuk, M. I. Striuk, H. M. Shalatska,
Comparisons of performance between quantum-enhanced and classical machine learning
algorithms on the IBM Quantum Experience, Journal of Physics: Conference Series 1840
(2021) 012021. doi:10.1088/1742-6596/1840/1/012021.
[8] P. V. Zahorodko, Y. O. Modlo, O. O. Kalinichenko, T. V. Selivanova, S. O. Semerikov,
Quantum enhanced machine learning: An overview, CEUR Workshop Proceedings 2832
(2020) 94–103. URL: http://ceur-ws.org/Vol-2832/paper13.pdf.
[9] B. Duan, J. Yuan, C.-H. Yu, J. Huang, C.-Y. Hsieh, A survey on hhl algorithm: From
theory to application in quantum machine learning, Physics Letters A 384 (2020) 126595.
doi:10.1016/j.physleta.2020.126595.
[10] S. Lloyd, M. Mohseni, P. Rebentrost, Quantum principal component analysis, Nature
Physics 10 (2014) 631–633. doi:10.1038/nphys3029.

173