1 Introduction

A conception of solving problems with use of k Nearest Neighbor (kNN) algorithm was created in fifties of the previous century [2] and it is still very popular and develops constantly. In addition, the concept of Support Vector Machine (SVM) for problems of classification is a known solution, which actual version was presented in 1995 [1]. As researchers working on some aspects of quantum computing, we were inspired by kNN and SVM methods to apply the idea of pattern recognition in quantum circuits [4, 6, 14, 16].

We refer to [9, 12, 13], where it was shown that it is possible to build a quantum circuit which works as a classifier. The basic idea was prepared to be utilized in the field of image processing [8, 17, 18]. The kNN and SVM were constructed with visible inspiration flowing out of methods used in artificial neural networks: the data describing the patterns are enclosed in learning and testing sets, and the circuit obtains the learning set and is able to recognize if a tested element fits to the pattern emerging from the learning set. An aim of this article is to verify a thesis if quantum circuits based on kNN and SVM methods are able to recognize Hermitian and non-Hermitian matrices.

This work is an extended version of conference ACIIDS 2017 paper: [15]—in that article, we simulated a quantum circuit based on kNN algorithm which role was to classify the Hermitian and non-Hermitian matrices. This article is organized as follows: in Sect. 2, we present some basic definitions helpful in understanding the main idea of this work. Section 3 is dedicated to the detailed description of the quantum circuit for kNN method and Sect. 4 contains the construction of quantum solution for SVM. In Sect. 5, the results of computational experiments were analysed. A summary and conclusions are presented in Sect. 6.

2 Quantum computing—basic definitions

To explain the analysed matter, we need to introduce a few definitions corresponding to quantum information processing [5]. First, notion concerns a quantum bit—so-called qubit which is a normalized vector in a two-dimensional Hilbert space \(\mathcal {H}_2\).

Two orthogonal qubits constitute a computational basis. Of course, we can imagine the infinite number of such paired qubits. One of the most known basis is so-called standard basis. This basis is created by qubits:

$$\begin{aligned} \vert 0 \rangle = \left[ \begin{array}{l} 1\\ 0\\ \end{array} \right] , \vert 1 \rangle = \left[ \begin{array}{l} 0\\ 1\\ \end{array} \right] . \end{aligned}$$
(1)

where the form \(\vert \cdot \rangle \) is a Dirac notation. The difference between classical bit and qubit is that qubit may be a "mixture" of orthogonal vectors. This phenomenon is called superposition. Hence, the state of quantum bit \(\vert \psi \rangle \) we can present as

$$\begin{aligned} \vert \psi \rangle = \alpha _{0} \vert 0 \rangle + \alpha _{1} \vert 1 \rangle \text {, where } \vert \alpha _{0}\vert ^2 + \vert \alpha _{1}\vert ^2 = 1. \end{aligned}$$
(2)

The coefficients \(\alpha _{0}\) and \(\alpha _{1}\) are complex numbers and they are termed amplitudes. A character of quantum state is non-deterministic. The probability that the state \(\vert \psi \rangle \) equals \(\vert 0 \rangle \) is \(\vert \alpha _{0}\vert ^2\) and, adequately, the probability that the state \(\vert \psi \rangle \) is \(\vert 1 \rangle \) is expressed by value \(\vert \alpha _{1}\vert ^2\). Of course, it is also possible that one of the amplitudes equals to 0 and the other to 1 (in this case state \(\vert \psi \rangle \) is one of basic states).

If we need more than one quantum bit to perform any calculations, we can use a quantum register which is a system of qubits, joined by a tensor product (denoted by symbol \(\otimes \)) in a mathematical sense. For example, the state \(\vert \phi \rangle \) of 3-qubit register containing qubits \(\vert 0 \rangle , \vert 1 \rangle \) and \(\vert 1 \rangle \) is

$$\begin{aligned} \vert \phi \rangle = \vert 0 \rangle \otimes \vert 1 \rangle \otimes \vert 1 \rangle = \left[ \begin{array}{l} 1\\ 0\\ \end{array} \right] \otimes \left[ \begin{array}{l} 0\\ 1\\ \end{array} \right] \otimes \left[ \begin{array}{l} 0\\ 1\\ \end{array} \right] . \end{aligned}$$
(3)

Usually, we omit the symbols \(\otimes \), so the above state may be also denoted as \(\vert \phi \rangle = \vert 011 \rangle \).

In case of any n-qubit state \(\vert \varphi \rangle \), its form can be expressed as a superposition of basic states:

$$\begin{aligned} \vert \varphi \rangle= & {} \alpha _{0} \vert 00\ldots 000 \rangle + \alpha _{1} \vert 00\ldots 001 \rangle \nonumber \\&+ \alpha _{2} \vert 00\ldots 010 \rangle + \ldots + \alpha _{(2^{n}-1)} \vert 11\ldots 111 \rangle \end{aligned}$$
(4)

where the normalization condition must be fulfilled:

$$\begin{aligned} \sum _{i=0}^{2^{n}-1}\vert \alpha _{i}\vert ^2 = 1, \;\;\; \alpha _{i} \in \mathbb {C}. \end{aligned}$$
(5)

To perform the calculations on quantum states, we use quantum gates. Quantum gates have to preserve a quantum state—that means the performed operation preserves the state’s normalization condition—so they have to be unitary operators to ensure this feature.

The gate which is very useful in many algorithms is a Hadamard gate H. Let \(\vert x \rangle \) be a n-qubit state as in example Eq. (3), but with labeled qubits:

$$\begin{aligned} \vert x \rangle = \vert x_{0} \rangle \otimes \vert x_{1} \rangle \otimes \dots \otimes \vert x_{n-2} \rangle \otimes \vert x_{n-1} \rangle . \end{aligned}$$
(6)

The impact of Hadamard gate on state \(\vert x \rangle \) is

$$\begin{aligned} H\vert x \rangle= & {} H( \vert x_{0} \rangle \otimes \vert x_{1} \rangle \otimes \dots \otimes \vert x_{n-2} \rangle \otimes \vert x_{n-1} \rangle )\nonumber \\= & {} H\vert x_{0} \rangle \otimes H\vert x_{1} \rangle \otimes \dots \otimes H\vert x_{n-2} \rangle \otimes H\vert x_{n-1} \rangle \nonumber \\= & {} \bigotimes \nolimits _{i=0}^{n-1} H\vert x_{i} \rangle = \frac{1}{\sqrt{2^n}} \left[ \bigotimes \nolimits _{i=0}^{n-1} \big ( \vert 0 \rangle + (-1)^{x_i} \vert 1 \rangle \big ) \right] .\nonumber \\ \end{aligned}$$
(7)

As we can see the Hadamard gate makes all absolute values of state’s amplitudes even (equal to \(\frac{1}{\sqrt{2^n}}\)), so it causes the phenomenon of superposition in a quantum register.

It is important to remember that quantum gates, in contrast to classical ones, always have the same number of inputs and outputs. It is so because they were designed as reversible operators the matrix form of quantum gate is unitary and Hermitian.

Another basic gate is an exclusive-or (XOR) gate, called also a controlled negation (CNOT) gate. This gate has two entries and, naturally, two outputs. The operation XOR is realized on the second qubit (the first qubit remains unchanged):

$$\begin{aligned} XOR\vert 00 \rangle= & {} \vert 00 \rangle , \;\;\; XOR\vert 01 \rangle = \vert 01 \rangle ,\nonumber \\ XOR\vert 10 \rangle= & {} \vert 11 \rangle , \;\;\; XOR\vert 11 \rangle = \vert 10 \rangle . \end{aligned}$$
(8)

The matrix form of this gate is

$$\begin{aligned} XOR = \left[ \begin{array}{llll} 1 &{} \quad 0 &{} \quad 0 &{} \quad 0\\ 0 &{} \quad 1 &{} \quad 0 &{} \quad 0\\ 0 &{} \quad 0 &{} \quad 0 &{} \quad 1\\ 0 &{} \quad 0 &{} \quad 1 &{} \quad 0\\ \end{array} \right] . \end{aligned}$$
(9)

3 The k nearest neighbors algorithm

In this work, we would like to use a quantum circuit to check if some matrices are Hermitian or not. The approach presented in this section is based on the k Nearest Neighbors (kNN) algorithm for pattern classification [9]. As an example, we chose the matrices which are binary and unitary, sized \(4 \times 4\) as in Fig. 1. In this case, all analysed matrices are column (or row, interchangeably) permutations of identity matrix \(I_{4 \times 4}\). Let us remind that a matrix U is Hermitian when it is equal to its conjugate transpose:

$$\begin{aligned} U=U^\dagger . \end{aligned}$$
(10)

Because the analysed set of matrices does not contain any matrices with complex elements, it would be some simplification to say that a Hermitian matrix is just equal to its transpose what can be observed in Fig. 1.

Fig. 1
figure 1

Set of all binary and unitary matrices sized \(4 \times 4\), divided into Hermitian and non-Hermitian matrices. The bigger dots stand for 1 and the smaller dots for 0

Full size image

The quantum circuit to perform a Hermitian matrices’ recognition is shown in Fig. 2. Although in this work, we only test a circuit for matrices sized \(4 \times 4\), the presented circuit is universal in terms of matrix dimensions.

Fig. 2
figure 2

Quantum circuit classifying Hermitian and non-Hermitian matrices

Full size image

To describe the matrices, we use 16-element binary series which are built of matrix elements row by row:

$$\begin{aligned} \left[ \begin{array}{llll} 1 &{} \quad 0 &{} \quad 0 &{} \quad 0\\ 0 &{} \quad 0 &{} \quad 1 &{} \quad 0\\ 0 &{} \quad 0 &{} \quad 0 &{} \quad 1\\ 0 &{} \quad 1 &{} \quad 0 &{} \quad 0\\ \end{array} \right] \rightarrow 1000|0010|0001|0100 \rightarrow 1000001000010100. \end{aligned}$$
(11)

In carried out computational experiment matrices \(4 \times 4\) were taken into account, so the number of quantum circuit’s (Fig. 2) inputs/outputs is 33. In general, if the matrices are sized \(k \times k\), the number of inputs/outputs is \(2k^2+1\). The first \(k^2\) inputs serve to enter the succeeding elements of testing set. The next \(k^2\) inputs serve to constitute a learning set. There is also one ancilla input on which the Hadamard operation is performed.

First, we would like to describe a block labeled Op.Learn.Set. Its role in the circuit is to accumulate the elements of learning set. The learning set contains binary series describing Hermitian matrices. We can roughly call these series permutative—the number of ones is similar (e.g., for unitary matrices is always equal to 4), but they occupy other positions in series. It means that the block Op.Learn.Set is a subsystem built of gates XOR and H, because the XOR gates ensure the permutations and H gates allow to accumulate some different series in qubits of quantum register.

The block Op.Test.Set is also constructed of XOR and H gates, but it differs from the subsystem Op.Learn.Set. This block contains only one element of testing set, representing Hermitian or non-Hermitian matrix, in each computational experiment. It means that, in case of unitary matrices \(4 \times 4\), we have to perform 24 experiments, always with different block Op.Test.Set.

Summarizing this part of the circuit, we have the initial quantum state entering the system:

$$\begin{aligned} \vert \psi _0 \rangle = \vert 0 \rangle ^{\otimes 2k^2+1}. \end{aligned}$$
(12)

Then, the first \(k^2\) qubits will be affected by the block Op.Test.Set and successive \(k^2\) qubits by the block Op.Learn.Set to produce the superposition of elements from a learning set:

$$\begin{aligned} \frac{1}{\sqrt{L}} \sum _{p=1}^{L}\vert l_{1}^{p}, \dots , l_{k^2}^{p} \rangle , \end{aligned}$$
(13)

where L denotes the number of elements in learning set and l represents the successive qubits.

The first \(k^2\) qubits describe an element from a testing set. It means that after the operations caused by blocks Op.Learn.Set, Op.Test.Set and Hadamard gate on ancilla qubit the system’s state is

$$\begin{aligned} \vert \psi _1 \rangle= & {} \vert t_{1}, \dots , t_{k^2} \rangle \otimes \frac{1}{\sqrt{L}} \left( \sum _{p=1}^{L}\vert l_{1}^{p}, \dots , l_{k^2}^{p} \rangle \right) \nonumber \\&\quad \otimes \frac{1}{\sqrt{2}}(\vert 0 \rangle + \vert 1 \rangle ) \end{aligned}$$
(14)

where t stands for the qubits of element from the testing set.

The next block serves to calculate the Hamming distance between one test series and elements of learning set. The Hamming distance is a measure expressing the difference between two series. It tells how many elements, occupying the same positions, differ from each other. The block Ham.Dist.Calculation uses the XOR operations on every couple of qubits \((t_i,l_i^p)\) and saves their results as d in the part of register which previously contained elements of a learning set:

$$\begin{aligned} XOR(t_i,l_i^p)=(t_i,d_i^p), \;\;\; i=1, \dots ,k^2. \end{aligned}$$
(15)

After this operation, the system’s state is

$$\begin{aligned}&\vert \psi _2 \rangle = \vert t_{1}, \dots , t_{k^2} \rangle \otimes \frac{1}{\sqrt{L}} \left( \sum _{p=1}^{L}\vert d_{1}^{p}, \dots , d_{k^2}^{p} \rangle \right) \nonumber \\&\otimes \frac{1}{\sqrt{2}}(\vert 0 \rangle + \vert 1 \rangle ).\nonumber \\ \end{aligned}$$
(16)

If the differences are already computed, then they must be summed to obtain the Hamming distance. The block Quantum Summing stands for the operation U:

$$\begin{aligned} U=\mathrm{e}^{-\mathbf {i}\frac{\pi }{2k^2}\hat{H}}, \;\;\; \hat{H}=I_{{k^2} \times {k^2}} \otimes \left[ \begin{array}{ll} 1 &{} 0\\ 0 &{} 0\\ \end{array} \right] ^{\otimes k^2} \otimes \left[ \begin{array}{ll} 1 &{} 0\\ 0 &{} -1\\ \end{array} \right] , \end{aligned}$$
(17)

where \(\mathbf {i}\) represents the imaginary unit. This results with the state \(\vert \psi _3 \rangle \):

$$\begin{aligned} \vert \psi _3 \rangle= & {} \frac{1}{\sqrt{2L}} \sum \nolimits _{p=1}^{L}\nonumber \\&\left( \mathrm{e}^{\mathbf {i}\frac{\pi }{2k^2}d(t,l^p)} \vert t_{1}, \dots , t_{k^2} \rangle \otimes \vert d_{1}^{p}, \dots , d_{k^2}^{p} \rangle \otimes \vert 0 \rangle + \right. \nonumber \\&\ \left. +\,\mathrm{e}^{-\mathbf {i}\frac{\pi }{2k^2}d(t,l^p)} \vert t_{1}, \dots , t_{k^2} \rangle \otimes \vert d_{1}^{p}, \dots , d_{k^2}^{p} \rangle \otimes \vert 1 \rangle \right) .\nonumber \\ \end{aligned}$$
(18)

The last step is designed to reverse the Hadamard operation on the last qubit (of course with use of reversible H gate). That will allow to measure the last qubit in the standard basis and obtain \(\vert 0 \rangle \) or \(\vert 1 \rangle \) with sufficiently high probability. The final state of the whole system is

$$\begin{aligned} \vert \psi _4 \rangle= & {} \frac{1}{\sqrt{L}} \sum \nolimits _{p=1}^{L}\nonumber \\&\left( \cos \left( \frac{\pi }{2k^2}d(t,l^p) \right) \vert t_{1}, \dots , t_{k^2} \rangle \otimes \vert d_{1}^{p}, \dots , d_{k^2}^{p} \rangle \otimes \vert 0 \rangle + \right. \nonumber \\&\left. + \sin \left( \frac{\pi }{2k^2}d(t,l^p) \right) \vert t_{1}, \dots , t_{k^2} \rangle \otimes \vert d_{1}^{p}, \dots , d_{k^2}^{p} \rangle \otimes \vert 1 \rangle \right) .\nonumber \\ \end{aligned}$$
(19)

Now, the measurement needs to be done only on the last ancilla qubit. If the result is \(\vert 0 \rangle \) that means the tested matrix is close to the pattern described in the learning set (is Hermitian), and if the result is \(\vert 1 \rangle \), the matrix should not be Hermitian.

It should be emphasized that the quantum implementation of kNN method has a lower computational complexity in comparison with kNN method running on a classical computer. The first difference is connected with the phase of learning—in the classical approach, the complexity is affected by the number and length of series included in the learning set, while in quantum system, only the length \(k^2\) of learning series influences its complexity. The second advantage of quantum approach in the field of complexity is an ability to compare a tested element with all elements from learning set simultaneously (a phenomenon of quantum parallelism takes place during the calculation of Hamming distances). Finally, the complexity of quantum kNN is: \(O(k^2+Hc)\), where Hc stands for the complexity of Hamiltonian (17) simulation. The simulation of Hamiltonian [3] may realized with no greater complexity than \(O( td \Vert H \Vert _\mathrm{max} + \frac{\log (1/ \epsilon )}{\log \log (1/ \epsilon )})\), where t is a interval of time, d is a sparse of Hamiltonian, \(\Vert H \Vert _\mathrm{max}\) is a value of Hamiltonian’s maximal element, and \(\epsilon \) stands for accuracy.

4 Support vector machine

Support Vector Machine (SVM) is a method used in a field of supervised learning. Let us assume that we have a learning set containing vectors from two different classes: \(C_1\) and \(C_2\). The SVM’s goal is to find a hyperplane \(g(\mathbf {x})\):

$$\begin{aligned} g(\mathbf {x})=\mathbf {w}^T\mathbf {x}+w_0 \end{aligned}$$
(20)

separating vectors from \(C_1\) and \(C_2\):

$$\begin{aligned} g(\mathbf {x})\ge & {} 1, \quad \forall _{\mathbf {x}} \in C_1 \nonumber \\ g(\mathbf {x})\le & {} -1, \quad \forall _{\mathbf {x}} \in C_2 \end{aligned}$$
(21)

In addition, the hyperplane must be calculated in a way maximizing the margin z, which is a distance between a hyperplane and objects from \(C_1\) and \(C_2\):

$$\begin{aligned} z=\frac{\vert g(\mathbf {x}) \vert }{\Vert \mathbf {w} \Vert }=\frac{1}{\Vert \mathbf {w} \Vert } \end{aligned}$$
(22)

That means an aim is to minimize \(\Vert \mathbf {w} \Vert \). This task may be formulated as finding a solution of Lagrange function \(L(\mathbf {\lambda })\) using Karush–Kuhn–Tucker conditions:

$$\begin{aligned} L({\varvec{\lambda }})=\sum _{i=1}^M g_i(\mathbf {x})\lambda _i - \frac{1}{2} \sum _{i,j=1}^M \lambda _i K_{i,j} \lambda _j \end{aligned}$$
(23)

under constraints:

$$\begin{aligned} \sum _{i=1}^M \lambda _i = 0 \quad \text {and}\quad g_i(\mathbf {x})\lambda _i \ge 0, \end{aligned}$$
(24)

where M is a number of training examples, vector \(\lambda \) stands for the Lagrange multipliers and K is a kernel matrix \(K_{i,j}=\mathbf {x}_i^T \cdot \mathbf {x}_j\). Then, the machine should be able to classify the unknown vectors according to (21).

The computational complexity of SVM is polynomial and depends on the dimensions of classified vectors and the number of elements in the training set. Of course, using the quantum version of this method, the complexity may be reduced to logarithmic. The speedup is achieved utilizing a quantum circuit to calculate in parallel the inner products of the vectors. Then, the SVM training is converted to an approximate least-squares problem which may be solved by the quantum matrix inversion algorithm with \(O(\kappa ^2 \log X)\), where \(\kappa \) stands for a condition number of a X-equation system [7, 9,10,11].

Fig. 3
figure 3

Scheme of quantum circuit implementing the SVM method

Full size image

The process of quantum calculations may be shown as in Fig. 3 according to [18]. The presented circuit has \((N+2)\) inputs/outputs, where N is a number of elements in classified vectors. Solving (23) leads to a least-square approximation of calculating matrix \(F_{M+1 \times M+1}\), because the SVM parameters are determined by

$$\begin{aligned} (w_0, {\varvec{\lambda }}^T)^T=F^{-1}(0, g(\mathbf {x})^T)^T, \end{aligned}$$
(25)

so the first block performs the matrix F inversion to calculate the hyperplane \(g(\mathbf {x})\), but it also accumulates the values of training set, because for matrix F, it is possible to calculate its eigenvectors \(| u_j \rangle \) and corresponding eigenvalues \(\alpha _j\) (\(j=1,...,(M+1)\)). On the first N qubits of the computational register phase estimation generates the state storing training data. After the operation performed by the block MatrixInversion, we will obtain the state:

$$\begin{aligned} | w_0,{\varvec{\lambda }} \rangle =\frac{1}{\sqrt{C}}\left( w_0| 0 \rangle + \sum _{i=1}^M \lambda _i | i \rangle \right) \end{aligned}$$
(26)

where

$$\begin{aligned} C=w_0^2 + \sum _{i=1}^M \lambda _i^2. \end{aligned}$$
(27)

The training data Oracle causes that all eigenvectors \(| \hat{u} \rangle \) of matrix F:

$$\begin{aligned} | \hat{u} \rangle = \frac{1}{\sqrt{N_{\hat{u}}}} \left( w_0 | 0 \rangle | 0 \rangle + \sum _{i=1}^M \lambda _i \vert \mathbf {x}_i \vert | i \rangle | \mathbf {x}_i \rangle \right) \end{aligned}$$
(28)

where

$$\begin{aligned} N_{\hat{u}}=w_0^2 + \sum _{i=1}^M \lambda _i^2 \vert \mathbf {x}_i \vert ^2. \end{aligned}$$
(29)

The last block is to calculate the probability telling if an arbitrary vector \(| \mathbf {t} \rangle \) from the training set may be classified to \(C_1\) or \(C_2\):

$$\begin{aligned} | \mathbf {t} \rangle = \frac{1}{\sqrt{N_{\mathbf {t}}}} \left( | 0 \rangle | 0 \rangle + \sum _{i=1}^M \vert \mathbf {t} \vert | i \rangle | \mathbf {t} \rangle \right) \end{aligned}$$
(30)

with

$$\begin{aligned} N_{\mathbf {t}}= M \vert \mathbf {t} \vert ^2 + 1. \end{aligned}$$
(31)

The final state of the system is

$$\begin{aligned} | \psi \rangle =\frac{1}{\sqrt{2}} \left( | \hat{u} \rangle | 0 \rangle + | \mathbf {t} \rangle | 1 \rangle \right) \end{aligned}$$
(32)

and the measurement on the last qubit has to be performed. If the obtained value is \(| 1 \rangle \), it means that the vector \(| \mathbf {t} \rangle \) belongs to the class \(C_1\), and if the value of the last qubit is \(| 0 \rangle \), then the vector belongs to \(C_2\).

Table 1 Results of pattern recognition for quantum versions of kNN and SVM methods
Full size table

5 Results of the experiments

We conducted a computational experiments to examine if a quantum system is able to recognize the pattern of Hermitian and non-Hermitian matrices sized \(4 \times 4\). The calculations for kNN were based on Eq. (19) and the calculations for SVM on (28) and (30). The results presented in this section were delivered by a script written in Python programming language.

The first experiments were conducted on sets of unitary matrices described as 16-element binary series as in (11). The results of these computations are presented in Table 1 (the numbers were rounded to four decimal places). For kNN method, the learning set contains the Hermitian matrices. As we can see the Hermitian matrices were recognized with a quite high probability. The problem is that also the non-Hermitian matrices were recognized as patterns similar to patterns in learning set—the kNN method uses the Hamming distance to distinguish between series and all used series contain 4 elements equal to one and 12 elements equal to zero, so probably, the series were treated as similar by the utilized method.

For the SVM method, we assume that Hermitian matrices belong to the class \(C_1\) and non-Hermitian to \(C_2\). The algorithm for SVM was implemented to point the class with value P: if \(P > 0.5\) the matrix belongs to \(C_1\) and if \(P < 0.5\)–\(C_2\). In comparison with the SVM method allowed to obtain better results. However, there are 2 Hermitian and 3 non-Hermitian matrices with \(P=0.5000\), so the method was not able to classify these matrices unambiguously.

To improve the pattern recognition, we propose to label the matrices and run the calculations using labels. The labels should be constructed as feature vectors in a way increasing the Hamming distances between Hermitian and non-Hermitian matrices.

Table 2 Results of pattern recognition for quantum versions of kNN and SVM methods
Full size table
Fig. 4
figure 4

Discrimination line for values of probability for the kNN method when matrices are encoded with feature vectors

Full size image

The labels are 16-bit binary series to provide a unique label for every binary matrix sized \(4 \times 4\). The labels are ordered: the first label contains 16 zeros, next 16 labels contain 1 figure one and 15 zeros, subsequent series contain 2 ones, 3 ones, and so on until we obtain a series of 16 ones. In every group of labels with the same number of ones, the series are sorted ascending in the meaning of the binary number written in a series. Let us assign the matrices to labels: at the beginning, the set of series presenting matrices is sorted in the same way as labels; we extract all 1024 Hermitian matrices from the set of series and we assign them to the first 1024 labels; other non-Hermitian matrices we assign to remaining labels. This approach allows to decrease the number of ones in labels corresponding to Hermitian matrices and to increase the number of ones in labels corresponding to non-Hermitian matrices. Table 2 contains the results of learning using labels.

We can see that the kNN method still tends to classify all matrices as Hermitian, but it is possible to calculate a discrimination line (see Fig. 4) between values of \(P_{\vert 0 \rangle }\) for Hermitian and non-Hermitian matrices, because the lowest value of probability for Hermitian matrices is 0.8790 and the highest value of \(P_{\vert 0 \rangle }\) for non-Hermitian matrices is 0.8313. The same situation we can observe for the SVM method with a discrimination line (see Fig. 5) between values 0.5634 and 0.5452.

The last experiment was conducted with use of labels, but the learning and test sets were more numerous (28 Hermitian and 40 non-Hermitian matrices were used). The sets were enhanced with labels corresponding to non-unitary matrices. The results are presented in Table 3.

Increasing the number of elements in the learning set caused some improvement for kNN method—the lowest value of \(P_{\vert 0 \rangle }=0.8859\) for Hermitian matrices and the highest value of \(P_{\vert 0 \rangle }=0.8011\) for non-Hermitian matrices. However, this strategy did not improve the results for SVM method.

Of course, it should be emphasized that the presented approach with use of quantum versions of kNN and SVM has a probabilistic character. That implies the fact that the calculations have to be repeated to obtain the most accurate approximation of distribution shown in tables above. The probabilities of measuring \(| 0 \rangle \) or \(| 1 \rangle \) on the last qubit are different, so it allows to indicate the distance of analysed case from the learning set. In general, the computations illustrated by the quantum circuits should be performed \(O(P (1-P) \frac{1}{\varepsilon ^2})\) times to obtain probability P distribution with accuracy \(\varepsilon \).

Fig. 5
figure 5

Discrimination line for values of probability for the SVM method when matrices are encoded with feature vectors

Full size image
Table 3 Results of pattern recognition for quantum versions of kNN and SVM methods
Full size table

6 Summary

The computational experiments showed that the quantum circuits are able to distinguish between the pattern of Hermitian and non-Hermitian matrices.

In case of kNN, the way of encoding patterns is very important. The kNN method uses Hamming distance to distinguish between the matrices so using feature vectors to describe the recognized objects should comply the character of Hamming distance measure. The distances between objects from the same class should be as small as possible. On the other side, distances between objects belonging to other classes should be increased. In our experiments, we used the system of labels to describe the matrices. Hermitian matrices were described by vectors with the minimal needed number of ones and non-Hermitian matrices with maximal number of ones. In case of feature vectors for unitary Hermitian matrices, the number of ones is equal to 2 and for non-Hermitian matrices: 4 and 5. The pattern recognition was more efficient when the learning set was extended by non-unitary matrices. The conclusion is obvious: not only the number of ones is an important factor for Hamming distance, but also the position of figures in series and non-unitary matrices brought some diversity in this aspect (there may be Hermitian matrices with 0 to 4 figures equal to one and non-Hermitian with 4–16 figures equal to one). The similar results were presented in [9].

The SVM method was surprisingly efficient even for a small learning set and series generated directly from matrices as in (11). Utilizing the feature vectors allowed to introduce a clear discrimination line between the values of P pointing objects from the classes \(C_1\) and \(C_2\).

It should also be emphasized that the character of quantum computations is probabilistic and conducting more experiments would let to describe the obtained values with higher accuracy.

The further work on the idea of using quantum circuit as a classifier should develop in direction of deeper analysis of Hamiltonian \(\hat{H}\) used in (19)—especially to formulate the matrix U given there. The other issue is to simulate the behaviour of quantum circuit and check if the averaged results will overlap with calculated values of probability from Tables 1, 2, 3. Finally, looking for the system of describing matrices by feature vectors to increase pattern recognition would be also very interesting.