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 diference 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 eficiency 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 eficiency 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.
While building a quantum computer is still a daunting engineering challenge, it already has a long list of areas to be efective [ 1, 2]:
• data modeling (weather forecast, chemical modeling); • 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: quantum 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.
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 dificult 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.
A quantum computer operates with minimal information units - qubits. A qubit can be represented as a unit vector of a 2-dimensional complex space:
1 |0⟩ = √ |0⟩ + √ |1⟩ = 2 2 [︃ √1 ]︃ 2 √2 | ⟩ = |0⟩ + |1⟩, ,
∈ C √︀| |2 + | |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⟩ = [︃0]︃ 1
And also other values that represent the probability of occurrence of zero or one. Such
probabilities are called probability amplitudes. In example (
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:
the following condition has to be met:
(
To measure the state of a system with one qubit of information, one must first choose an orthonormal basis:
|⟩, |⟩ : ⟨|⟩ = 0, ‖‖ = ‖‖ = 1, 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
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 (
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 (
|⟩ = |⟩ ⊗ | ⟩ = ⎢⎢ ⎣1 × ⎡ 0 ×
1 ︂[ 0]︂ ⎤
⎡00⎤ ︂[ 01]︂ ⎥⎥⎦ = ⎢⎢⎣1010⎥⎦⎥ 11
If two qubits are in a superposition state, the system will transition to one of four states
during measurement:
(
| |2 + | |2 + | |2 + | |2 = 1
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 (
All operators performed on the state vector must be unitary. That is, for the operator , its adjoint operator must be equal to the inverse:
Another property of unitary operators is that when they are applied, the scalar product of vectors (the angle between them) has preserved:
∀, ∈ |⟨ |⟩|⟨ | ⟩| = |⟨ ⟩|
In addition to this, the length of the vector has also preserved:
We can also write the wave function from (
∀ ‖ |⟩ ‖=‖ |⟩ ‖ | ⟩ = (cos 2 |0⟩ + sin 2 |1⟩) where is global phase, is local phase. The global phase does not afect 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. (11) (12) (13) (14) (15) (16) (17)
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 : 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: | ⟩ = 2 | ⟩ = ∀ 360 × 2
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 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: • obtaining a superposition by applying the -bit operation ⊗ on the second register: | 0⟩ = |0⟩⊗ | ⟩; • creates a supervised CU statement that applies only if the control bit is |1⟩. Based on (15): 2 | ⟩ = 2− 1 | ⟩ = 2− 1 2 | ⟩ = ... = 2 2 .
Now it is necessary to apply controlled operations 2− 1 in the range 0 ≤ ≤ − 1 : | 2⟩ = 212 (|0⟩ + 2 2− 1 + |1⟩) ⊗ ... ⊗ (|0⟩ + 2 21 + |1⟩)⊗ ⊗ (|0⟩ + 2 20 + |1⟩) ⊗ | ⟩ = 1 2∑−︁1 2 |⟩) ⊗ | ⟩ 2 2 =0 where is an integer representation of -bit numbers. • perform inverse Fourier transform: | 3⟩ = 212 2∑=−︁01 2 |⟩) ⊗ | ⟩ →− − 1 21 ∑=︁0 ∑=︁0 − 22 (− 2 )|⟩ ⊗ | ⟩ 2− 1 2− 1 • measure the system and get the answer in the auxiliary register:
| 4⟩ = |2 ⟩ ⊗ | ⟩ = + ⌈log 2 + 1 ⌉ (18) (19) (20) (21) (22) (23) (24)
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:
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. 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:
To get a matrix form solution, it is necessary to find the inverse matrix − 1: |⟩ = |⟩
− 1 |⟩ = − 1|⟩ = ∑︁ − 1 | ⟩ =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
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 efective 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 component) of the vector |⟩. • we put = 2 • loading the vector |⟩ through a transformation of the form |0⟩ ↦→ |⟩ • application of Quantum Phase Evaluation (QPE):
The quantum state of the register, expressed in its own basis :
− 1 = = ∑︁ |⟩⟨|
=0 where | ⟩ – is -bit binary representation of . (25) (26) (27) (28) (29) • adding an auxiliary qubit and applying rotation under the condition | ⟩ 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: • measurement of the auxiliary qubit on a computational basis. If the result is 1, then the register is following after measurement: − 1 ∑︁ |0⟩ | ⟩ =0 ︃( √︃
2 1 − 2 |0⟩ + |1⟩ ︃( √︃
1 ∑︀=− 01 | |2/| |2 )︃ ∑− ︁1 |0⟩ | ⟩ =0 )︃ )︃ (30) (31) (32) • applying the observable to calculate () = ⟨| |⟩.
The following parameters afect 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.
The computational complexity for the conjugate vector method is ( log 1/). The HHL algorithm has a computational complexity of (22− 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) (35) 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: ∑︁ | ⟩⟨ | ⊗ | ˜ ⟩⟨˜ |
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 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:
The QSVM method allows you to speed up the calculation of the dot produc→t− × . 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:
Matrix consists of scalar products of the kernel matrix of the training sample: [︃ ]︃ →− = − 1 [︃ 0 ]︃ →− [︃0
]︃ 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 poin→t− 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 ).
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 (36) (37) (38) (39) 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 shufled 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 diferent 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 difer much from the runtime on the simulator.
From the results obtained earlier, we can conclude that quantum devices are not eficient 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.
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 not negate the importance of research in this area. When the stable quantum computer is invented with suficient 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.