Parametric Probabilistic Quantum Memory

2020·arXiv

Abstract

1. Introduction

Quantum Computing is a computational paradigm that has been harvesting increasing attention for decades now. Several quantum algorithms have time advantages over their best known classical counterparts [1, 2, 3, 4]. The current advances in quantum hardware are bringing us to the era of Noisy Intermediate-Scale Quantum (NISQ) computers [5]. The quest for quantum supremacy is the search for an efficient solution of a task in a quantum computer that current classical computers are not able to efficiently solve. Some authors argue that given the current state of the art, we will achieve quantum supremacy in the next few years [6]. One of the approaches to achieve this supremacy and to expand the potential applications of quantum computers is through quantum machine learning [7].

Machine learning (ML) [8] aims at developing automated ways for computers to learn a specific task from a given set of data samples. ML has several applications in image classification [9], NP-hard problems [10] and others. Some of the limitations of ML are the lack of algorithms to select an ML method and to avoid local minimums.

Quantum machine learning investigates the use of quantum computing concepts to build quantum-enhanced machine learning models able to outperform the classical ones [7]. For instance, quantum computing can be used to efficiently convert a nonlinearly separable dataset into a linearly separable one by exploiting the exponential size of quantum spaces [11] and to select neural networks architectures without dependence of weights initialization [12, 13]. Quantum machine learning proposes speedups of some algorithms used in machine learning such as reinforcement learning [14] and systems of linear equations [15].

There are several works proposing quantum machine learning models such as a quantum generalization of a neural network [16], a quantum distance-based classifier [17], and quantum associative memories [18, 19, 20, 21]. In [20, 21] is introduced a Probabilistic Quantum Memory (PQM) that computes the Hamming distance from an n-bits input pattern to k n-bits patterns with computational cost linear in the number of bits, O(n).

However, the PQM [20] (and quantum associative memories in general) has received criticism from various authors. The memory state is lost in every execution of the retrieval algorithm when the memory state is measured. Memory collapse is considered to be the main limitation of this memory [22] as argued in [23] since the O(m) cost to reload m patterns in the memory using its storage algorithm jeopardizes the PQM advantages. Another author [24] claims that the probabilistic quantum memory cannot be considered as a complete model. However, in [4] we show a PQM application in which a single execution of the retrieval algorithm is sufficient to evaluate, probabilistically, the artificial neural networks architectures without the need for weights initialization. We used the PQM as a data structure to store and train artificial neural networks in superposition and to devise a quantum algorithm able to evaluate and select neural network architectures.

The objective of this work is to improve the PQM model in pattern classification tasks extending the model described in [25]. To accomplish this aim, we propose two approaches:

1. We introduce the Parametric PQM (P-PQM), where the parameter allows the PQM to compute a weighted Hamming distance and adapt the model to the given training dataset.

2. We also propose a hybrid classical-quantum version of the PQM retrieval algorithm suitable for NISQ computers.

The remainder of this work is structured as follows. Section 2 gives the concepts of quantum computing to make this work self-contained. Section 3 describes related works and the probabilistic quantum memory, and Section 4 presents a quantum weightless classifier and one of its limitations. Section 5 and Section 6 show the main contributions of this work. In Section 5, we describe the proposed parametric probabilistic quantum memory and present simulated experiments to evaluate a weightless neural network based on the P-PQM. In Section 6, we present a modification of the PQM that allows its implementation in a NISQ computer. Finally, in Section 7 we draw some conclusions and list some possible further works.

2. Quantum Computing

Quantum computing is a field that is receiving increasing attention due to its current advances [5]. It is a field that uses concepts and results from quantum mechanics and computing theory. A quantum computer is a computational device capable of representing and manipulating information at the quantum level to perform computational tasks [26]. In quantum computing, the quantum bit (qubit) represents the basic unit of information, representing a two-level quantum system. Analogously to the behavior of a subatomic particle, the qubit can be in more than one basis state at a given time. Eq. (1) describes one qubit in superposition (linear combination), where and are orthonormal vectors (basis), and are the probabilistic amplitudes (complex numbers) associated with the states and , and + = 1.

basis, where

Quantum gates are used to modify the state of a quantum system.

In the computational basis, a gate is represented by a unitary matrix and carries out a reversible operation

on the quantum state. The Pauli gates are examples of quantum operators. They are defined by the matrices below.

The Hadamard gate H (Eq. (2)) can create a state superposition; where ) and ).

Controlled gates operate on a target qubit depending on the state of another qubit used as control. The CNOT gate is the controlled version of the X gate and flips target qubit if the control qubit is in the state . Eq. (3) describes the CNOT gate.

An important characteristic of quantum systems is the need to measure for extracting information from a quantum state. After a measurement, the system collapses to one of its superposed basis states. Given the quantum state described in Eq. (4), the probability of finding after a measurement is and the state will collapse to .

Due to the capacity of dealing with states in superposition and other incorporated quantum effects (such as entanglement), quantum computers provide an alternative way of computing, which presumably could be used to solve problems in a way that presumably has no counterpart in classical computing [1].

3. Related works

The first model of Quantum Associative Memory (QAM) was proposed in [18] and used a variation of Grover’s algorithm. The main idea of QAM is to store patterns in superposition, allowing to store 2patterns using n qubits. The use of Grover’s algorithm is one limitation of the first QAM that searches for exact patterns and not similar patterns. The QAM performs a search for exact patterns and not similar patterns, and the required number of quantum operators limit the use of QAM in NISQ computers. A Probabilistic Quantum Memory (PQM) was proposed in [20]. The retrieval algorithm of the PQM is not based on Grover’s algorithm and searches for similar patterns instead of performing an exact search. However, the retrieval algorithm is probabilistic and depends on the distribution of patterns stored in the memory.

Quantum associative memories have been used to perform classification tasks in several works [27, 17, 23, 4, 28, 29, 30]. In [29] Grover’s algorithm and a quantum associative memory based on it are used to perform classification tasks in a toy dataset representing orange and apples with 3-qubit patterns. In [23] the PQM is used to classify digits from the MNIST dataset, the PQM accuracy on the test set is only 50%. An evaluation of the PQM in benchmark classification datasets was performed in [25]. One limitation of the PQM is the lack of parameters to adjust the model to a dataset [25, 23].

3.1. Probabilistic Quantum Memories

In this section, we present the quantum memory model used to build a weightless network classifier. The Probabilistic Quantum Memory (PQM) [20, 21] is a content-addressable quantum memory. It outputs the probability of a given input pattern being stored in the memory by calculating the Hamming distance between the input pattern and all the patterns stored in the memory. It is a probabilistic model designed to recognize incomplete or noisy information. Despite being an associative model, the PQM possess a highly scalable storage capability, being able to store all the possible 2binary patterns of n bits. The following subsections explain the PQM storage and retrieval algorithms.

3.1.1. The Storage algorithm

The storage algorithm receives a dataset with r patterns each with n bits, uses three quantum registers and follows Algorithm 1 to produce state described in Eq. (5).

Before being processed and stored on the memory, every pattern must be initialized in an input register . The memory itself is separated from the input patterns which have not yet been processed and resides in the register . After the end of the storage algorithm, the register will be in the state refers to the memory quantum register during the construction of the uniform superposition and is the resulting memory state. The last quantum register used is an auxiliary two-qubit register , , which is used to keep tabs on which patterns are already stored and which still need to be processed and written. The algorithm initial stateusing the three registers is shown in Eq. (6).

Algorithm 1 describes the storage algorithm receiving as input a dataset with r n-bit patterns. Step 1 initializes the quantum registers with the quantum state . The second qubit in indicates whether a pattern has been already stored or not. In this case, a in the second qubit of , , indicates that the pattern has not been stored yet.

The for loop in line 2 is repeated for each pattern in data. Step 1 initializes the quantum register with a pattern from data. Step 4 uses n 2CNOT operations to make a copy of the n bits from the pattern in to the respective register flagged by . The 2CNOT operation is equivalent to a Toffoli gate that flips the target bit if the two control bits are in state .

Step 5 applies CNOT operations to registers and followed by an X operation to . This step fills with 1s all the bits in the memory register which are equal to the respective bits in register ; this is true only for the pattern which is being currently processed.

Line 6 uses the nCNOT operation, which is a generalization of the CNOT gate for n bits. The operation is controlled by all the bits of and is applied to the first bit of . Thus, if the first bit of is flipped.

Step 7 adds the input pattern to the memory register with uniform amplitudes. This is done by applying the gate, shown below:

The remaining steps apply the inverse operations to return the memory to its initial state and prepare it to receive the next pattern. The algorithm runs until all the patterns have been processed and stored on .

3.1.2. The Retrieval Algorithm

The retrieval algorithm computes the Hamming distance between the input and all the patterns superposed in the memory quantum state. It probabilistically indicates the chance of a given input pattern being in the memory based on the results of its distance distribution to the stored patterns in superposition. If the input pattern is very distant from the patterns stored in the memory, one will obtain as a result with a significant probability. Otherwise, would be obtained. Since the memory state is in a superposition, the retrieval algorithm can calculate the distances from input to all the patterns at once.

The PQM retrieval algorithm is described in Algorithm 2. It uses three quantum registers: and . The pattern size gives the size of the first two registers and is a single qubit register. Step 1 of the algorithm loads the input pattern into the first register. The second register is the memory that contains all the stored patterns and is a control qubit initialized with a uniform superposition of and . The quantum state after the first step of the algorithm can be seen in Eq. (7), where r is the number of stored patterns.

Step 2 sets the jth qubit in memory register to , if the jth bit of input and memory are equal; and set to , if they differ. If a pattern stored in the memory is identical to the input pattern, step 2 will set its memory state to , where n is the pattern size. In step 3, the operators U (described in Eq. (8)) and controlled are applied to the memory registers.

Step 3 is responsible for computing the Hamming distance between the input pattern s and the patterns in the memory. It computes the number of 0s in the memory register (the qubits that differ between memory and input). When is , step 3 calculates the number of 0s in the memory state with a positive sign and with a negative sign when is .

Step 4 reverts the memory register to its original state by computing the inverse of step 2. Step 5 measures the quantum register . An input pattern similar to the stored patterns increases the probability of measuring = 0, and an input that is very distant to the stored patterns increases the probability of measuring = 1. The measurement probabilities can be seen in Eq. (9), where r is the number of stored patterns and ) denotes the Hamming distance between input and the kth stored pattern.

4. The Quantum Weightless Classiﬁer

The Quantum Weightless Neural Network Classifier [31] (QWC) is composed of Probabilistic Quantum Memories acting as the network neurons. The model is devised by using an array of PQM instances capable of distance-based classification. Each PQM instance, by itself, works as a single class classifier, being responsible for the classification of just one of the classes in the dataset. The model does not demand any training in the sense that the neurons do not have to be iteratively adjusted to learn from the training patterns. The model classification algorithm and the necessary setup are detailed below.

4.1. The Setup Algorithm

The Quantum Weightless Classifier requires an initial setup algorithm in order to perform classification tasks. For a given dataset with n classes, the model has n PQMs acting as neurons. The training samples must be divided and grouped by class. For each group, a new PQM is created and used to store all the samples belonging to that group, making in total n PQM instances, one for each class.

The setup algorithm consists in storing the training samples on their respective PQM. The n PQMs together define a single classifier. Algorithm 3 describes the setup process. Once all the training samples are correctly stored, the model can perform the classification task by calling the PQM retrieval algorithm.

4.2. The Classification Algorithm

After the initialization described in Algorithm 3, the next module is the classification algorithm shown in Algorithm 4. In order to classify a new sample, the Quantum Weightless Classifier must present it to all the PQM neurons which constitute its network. Each PQM neuron performs its retrieval algorithm using the presented sample as input. Since each PQM holds the patterns of a specific class, each output will be the probability of the sample having similar features to the patterns of that specific class. Let X be a random value corresponding to the number of 1s in the probabilistic quantum memory output, the PQM neuron which outputs the smallest expected value, E(X), is assumed to be the one that correctly classifies the sample.

Table 1: Memory configurations

4.3. QWC Numeric Example

In this section, we present a numerical example of the PQM classifier evaluation. We show one limitation of the QWC with an artificial data set. Assume the memory configuration in Table 1, and that the algorithm evaluates the input pattern 0111010101. Patterns of memory in Table 1 have Hamming distance j to the input pattern .

The dataset has two classes and and 10-bit patterns. We suppose that . To evaluate the classifier, we need to run the PQM retrieval algorithm for memories and with input to obtain the probability of input pattern to be in each memory. So, we begin the algorithm obtaining the initial state in each memory:

If we denote ) as the Hamming distance between the input pattern and every stored pattern , then ) = 1 and ) = 3, = 1 . . . 4. After step 3 of Algorithm 2 we obtain the state.

Applying the step 4 of Algorithm 2, we obtain:

The next step measures the control qubit . Therefore, we must verify the probability amplitudes of or . If only one memory returns 0, the pattern is classified as a member of the class ) = 9755 and ) = 79389. The recognition probability of the input pattern being recognized as a pattern of memory or is high for both memories, and then the model can perform a wrong classification.

A PQM classifier [31, 23] is not a good classifier in this situation. If we increase the size of andand if the input pattern have a Hamming distance of 1 and 3 for all stored patterns in and , respectively, the probability ) and ) will tend to 1 and the algorithm would indicate that is in both classes. In the next section, we propose a parametric PQM that allows adjusting the model to a dataset.

5. Parametric Quantum Weightless Classiﬁer

The PQM retrieval algorithm output is a function of the Hamming distances between the input and the stored patterns. This distance is not reliable for all datasets, as we have seen in the previous section. When patterns are close to patterns from another class, there is a high probability of misclassification. In order to improve the memory output probabilities, we propose a modified version of the PQM. We show how, for all memory size , that it is possible to add a parameter t, with 0 1, to the calculation of the probability in such a way that the distance between ) and ) will be sufficient to assure a greater probability to perform a correct classification. The idea is that given ), where and are Hamming distances between all patterns stored in and , respectively, we can add a parameter t in the calculation of the probabilities and obtain values for (0, 1) that increase the distance between the probabilities ) and ). We want to make the probability

considerably close to 1, while the probability

stays considerably close to zero. A Parametric Probabilistic Quantum Memory (P-PQM) operates as the PQM, but with the addition of a scale parameter in the retrieval algorithm. We replace the U operator used in the PQM with the operator described below, where t is a free parameter. Note that for t = 1 the P-PQM is equivalent to the PQM.

We define the Parametric Quantum Weightless Classifier (P-QWC), as the QWC classifier with a parametric retrieval algorithm. In the next section, we revisit the example of the previous section to verify the effectiveness of the parametric approach.

5.1. Numeric Example revisited

Taking the example in Section 4.3 as into account, we can apply the parameter from , hence:

Applying step 4 of Algorithm 2, where n = 10, we have:

Figure 1: Graph of f(t) with maximum points.

We look for a value of t which improves the probability of to be recognized in memory and not

recognized in .

As ) = cosand ) = cos

Let f(t) be the function described in Eq. (11), where the first term is the one with the shortest Hamming distance to the input.

Any value of t that maximizes f(t) is a parameter that makes the pattern recognition more reliable. It is sufficient to analyze the derivative of f(t) to maximize f. By looking ath the maximum of f we can get infinite values for t that maximize the function, these values are those that give us the most significant distances between the probabilities. Below we will give some values of t that maximizes f(t). Values of t where f assumes minimum values lead to the classification of the input pattern by the memory with the greatest Hamming distance. The graph of f(t) is presented in Fig. 1.

We can obtain these values of t by calculating the derivative of f. For our numeric example, we obtain , or

With n = 1, we get values 044, 017, and 0268. Now let us calculate the probabilities for each value of t.

i. ) = cos

i. ) = cos079.

Note that in all cases the distance between the memories is considerably large, giving us greater confidence that the input pattern is recognized by the memory since the Hamming distance associated with it is the smallest.

Table 2: Datasets characteristics

We have just shown that it is possible to obtain a parameter to improve the capabilities of the PQM classifier. Even in the case where the probabilities are very close and with a high value of n, the P-QWC can solve the cases where the QWC may not be efficient. Therefore, the P-QWC classifier provides a significant improvement over the QWC. In the next section, we use benchmark datasets to compare the QWC with the proposed P-QWC.

5.2. Experiments

We present in this section the experiments conducted on a conventional computer with a reduced classical version of Algorithm 2. To simulate the Probabilistic Quantum Memory classically we followed the description of its output probability described in Eq. (9). Once the PQM classical representation is obtained, the QWC can be evaluated by following the setup and the classification algorithms described in Section 4. The same algorithm applies to the P-QWC model, with the only modification being the addition of a parameter to the Hamming distance calculation step.

To perform the experiments, we used categorical and numerical datasets from the UCI Machine Learning Repository [32]. Table 2 presents the description of the selected datasets. All datasets were preprocessed to binarize feature values and deal with any missing values. Datasets containing real numerical values were not considered. We replaced missing values by the value with the highest number of occurrences for the corresponding feature.

Following Algorithm 3, we stored the training samples in specific PQMs according to the classes they belong to. Then, we follow Algorithm 4. The model classification accuracy was evaluated by passing the patterns in the test set as input to each of the PQMs. The class of the PQM which outputs the lowest expected value was set as the evaluated pattern class. This algorithm was repeatedly applied to each of the evaluated datasets. For the P-QWC, model we optimized and selected the parameters which achieved the best test set accuracy for each P-PQM in the classifier. We tested 15 parameter values in the range (0, 1] for each P-PQM. In a quantum computer, it would be necessary to perform several runs to estimate the best value of t. In this simulated experiment, we performed only one run and analyzed the output state to determine t.

5.3. Results

We verified that the P-QWC model performed better than the QWC over all the datasets. The parameter influence on the SPECT Heart dataset performance can be seen in Fig. 2. The curve shows the performance obtained by using the same parameter value for all P-PQMs constituting the classifier. Considering the original PQM performance is equivalent to P-PQM with parameter 1.0, a considerable increase in classification performance was observed through parameter variation and even better accuracies are possible by choosing different parameters for each P-PQM.

Table 3 describes the results obtained with the experimental setup described in Section 5.2. The accuracy of the QWC and P-QWC models can be compared against the results obtained using the k-nearest neighbors algorithm (KNN). The accuracy values shown are the average obtained from 10-fold cross-validation. Standard deviations are included between parentheses. We choose KNN as a baseline comparison because

Figure 2: Parameter impact on SPECT Heart dataset

it is also based on a measurement of distance. The KNN model was set to use uniform weights for all its points and the k nearest neighbors value was optimized, and selected from values between 1 and 50.

A nonparametric statistical test was employed to perform an appropriate comparison of the models. We used the Wilcoxon paired signed-rank test [33] with = 0.05 to verify whether there exist significant differences between the compared classifiers performances over the chosen datasets. Statistically significant results between the P-QWC and KNN models are marked in bold, significant results in the comparison between the QWC and P-QWC models are italicized. KNN and P-QWC are statistically equivalent in Balance scale, Breast cancer, SPECT Heart, Tic-tac-toe and Zoo datasets. KNN has better accuracy on Mushroom and Voting records datasets. P-QWC performed better on Lymphography dataset and also surpassed the QWC model in the SPECT Heart, Tic-tac-toe and Zoo datasets. In comparison with QWC, P-QWC has better accuracy in all datasets with statistically significant results in datasets SPECT Heart, Tic-tac-toe and Zoo.

The P-QWC has a performance equivalent to KNN in five out of the eight tested datasets and outperforms it in one dataset. The main advantage of the P-QWC is its memory requirements and the ability to receive inputs in superposition. While a RAM node memory grows exponentially with input size [34], the QWC memory size grows linearly. This memory advantage enables us to implement new kinds of weightless neural networks architectures [31].

6. PQM for NISQ computers

In this section, we first discuss why implementing the memory as proposed in [20] would not be feasible on noisy small-scale quantum computers. Then, we propose a hybrid classical/quantum protocol implementation, optimized for devices with a reduced number of qubits. We performed an experiment on a small-scale quantum computer as a proof of concept that the modified retrieval algorithm will work on NISQ computers.

Table 3: 10-fold cross-validation average accuracy per dataset

6.1. Quantum-only implementation viability analysis

The PQM retrieval algorithm calculates the distance of all the stored patterns to the input and outputs with probability proportional to the given input pattern being close to patterns in the memory. For patterns with n bits, three quantum registers are needed for the quantum circuit: an input quantum register , a memory quantum register , both with n qubits; and a controlled quantum register with at least one qubit. The retrieval algorithm can be described in 5 steps. There are 2n CNOT and NOT operations; n U and controlled operations; one Hadamard operator; and no operations involving more than two qubits. Operators U and are not included in the set of gates available on the quantum device but can be constructed as a three gate composition. Thus, the significant issues with a quantum-only implementation are the memory scalability and the number of operations needed. A quantum memory used to store n-bit patterns will require 2n + 2 qubits, for the storage algorithm; and 2n + 1, for the retrieval algorithm. As the number of qubits is a limited resource on such small devices, the qubits requirement becomes a prohibiting issue. Furthermore, the high number of quantum operators results in too much noise being added to the output. These two issues make a quantum-only implementation on NISQ computers impractical. Therefore, due to the discussed limitations, we devised quantum-classical storage and retrieving algorithms to implement the PQM.

6.2. Hybrid quantum-classical implementation method

In the probabilistic quantum memory retrieval algorithm, the quantum register input always remains in a classical state. This fact and the hybrid classical/quantum architecture used in the actual quantum computers allows the removal of the input quantum register from Algorithm 2.

The main disadvantage of this approach is the need to recompile the circuit when the system receives an input, but as we show in [4] the PQM has applications with a fixed input. Here, we remove the input quantum register and keep it in a classical variable. All the control operators from the input register to memory register are removed from the circuit and replaced with an X operation applied to the jth memory bit only when the jth input bit is 1. We also remove the X gates from steps 2 and 4, as they would cancel with the X gates used to obtain . With these modifications, we can use the 5-qubit quantum computer to simulate a probabilistic quantum memory up to 4-bit patterns.

In this work, we used the Quantum Information Software Kit (QISKit) SDK [35] and run the circuit on the IBM Q Experience Tenerife 5-qubit quantum computer [36].

The memory retrieval algorithm operations are further simplified by breaking down complex quantum operations into classical-quantum equivalent algorithms. These algorithms are conditioned on the classical input and apply a smaller number of gates to achieve the same resulting state.

6.3. Experiments

The Tenerife 5-qubit quantum computer architecture does not have arbitrary qubits connections. All the possible connections in the Tenerife computer are defined by its architecture topology, which can be seen in Fig. 3.

Figure 3: IBM Q Experience “Tenerife” 5-qubit quantum computer topology

For this experiment, the PQM is tested with 2, 3 and 4 qubits memory size. We store different patterns on the PQM and run the retrieval algorithm using inputs with the same size as the memory patterns size. The PQMs are constructed by storing the control bit c on the quantum register labelled as Q3 on Tenerife’s topology. In this way, the necessary gates could be directly applied without swapping qubits. Table 4 describes the results after 8192 executions of the probabilistic quantum memory running on the Tenerife backend and the local QISKit simulator. The calculated expected values for each memory state are included as well.

We calculate the expected outputs, obtained through numerical evaluation; the real outputs, obtained from the Tenerife backend; and the simulation outputs from the QISKit simulator. We calculate the percentual Mean Squared Error (MSE) of the expected outputs and the outputs of the experiment on the Tenerife backend. In the first set of experiments, we use a PQM with memory size equal to one and present all possible binary inputs. With memory state and ), we obtain, respectively, MSE equal to 0.0058, 0.0059 and 0.0006. The resulting mean error was 0.0041.

In the second set of experiments, we use a 2-qubit PQM, we use all possible 2-bit strings as inputs. With memory states ) and , we obtain, respectively, MSE equal to 0.0072, 0.0027 and 0.0066. The resulting mean error was 0.0055.

In the third set of experiments, we use a 3-qubit PQM and all possible 3-bit strings as inputs. With memory states |000000010000100000001110111) and |111, we obtain, respectively, MSE equal to 0.0257, 0.0187, 0.0133, 0.023, 0.0218, and 0.026. The resulting mean error was 0.0214.

Finally, in the fourth set of experiments we use a 4-qubit PQM and all possible 4-bit strings as inputs. With memory states |000000000100100001001100101001101110), |111001111111) and |1111, we obtain, respectively, MSE equal to 0.0228, 0.0174, 0.0236, 0.0144, 0.0228, 0.0148, 0.0248, 0.0141, and 0.0226. The resulting mean error was 0.0197. Results for inputs 0000 and 1111 are displayed in Fig. 4.

Although the calculated outputs do not correspond precisely to the predicted outputs, the probability of obtaining from a measurement of the quantum register is still related to the distance between the input and the memory content. In all experiments, the estimate of can be used to verify if a pattern is close to the patterns in the memory.

The proposed simplified retrieval algorithm of the PQM was successfully implemented in the Tenerife architecture without swapping quantum bits. We conjecture that a quantum computer with planar architecture where n qubits are connected to a single qubit (to be used as a quantum register ) can be used to efficiently implement an n-qubits PQM in near term quantum computers.

Table 4: Probabilistic quantum memory retrieval algorithm for input executed on the Tenerife backend with 8192 executions. The results for 1, 2, 3, and 4-qubit PQM can be seen for different memory configurations. The table shows the real output obtained from the quantum device, the results from the local simulator, and the expected output probability calculated numerically. We denote by Ps the Pattern Size, and by the probabilities obtained from the Tenerife backend, the local QISKit simulator and the calculated expected output, respectively.

7. Conclusion

In this work, we proposed a parametric version of the PQM named P-PQM. We performed an empirical evaluation of a quantum weightless classifier and proposed a modification which achieved a considerable improvement in the classification capabilities of the model. The proposed parametric quantum model used as a classifier (P-QWC) performed better or equivalent to its unmodified version (QWC) in all datasets used in the experiments.

We also presented a modification of the PQM to allow its implementation on Noisy Intermediate-Scale Quantum computers. As a proof of concept, the model was implemented in a small-scale quantum computer. We verified through experiments that a noisy version of the PQM can be implemented on a 5-qubit quantum computer.

There are several possible future works. We can adapt the model to use different distance functions, use different architectures for the quantum weightless classifier, investigate how to reduce noise on the P-PQM, and define an error cost function to update the parameter t as in a variational quantum circuit.

Code avaiability

All code used in this work can be made available upon reasonable request.

Figure 4: Results obtained from executing the retrieval algorithm of a 4-qubit PQM on the Tenerife backend and the QISKit local simulator, including the numerically calculated expected probabilities.

Acknowledgements

This work was supported by the Serrapilheira Institute (grant number Serra-1709-22626), CNPq Edital Universal (grants numbers 420319/2016-6 and 421849/2016-9 and FACEPE (grant number IBPG-1578-1.03/16). We acknowledge use of the IBM Q for this work. The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Q team.

References

[1] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41 (2) (1999) 303–332.

[2] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical review letters 79 (2) (1997) 325.

[3] P. Rebentrost, M. Mohseni, S. Lloyd, Quantum support vector machine for big data classification, Physical review letters 113 (13) (2014) 130503.

[4] P. G. dos Santos, R. S. Sousa, I. C. Araujo, A. J. da Silva, Quantum enhanced cross-validation for near-optimal neural networks architecture selection, International Journal of Quantum Information (2018) 1840005.

[5] J. Preskill, Quantum computing in the NISQ era and beyond, arXiv preprint arXiv:1801.00862 (2018).

[6] A. W. Harrow, A. Montanaro, Quantum computational supremacy, Nature 549 (7671) (2017) 203.

[7] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, S. Lloyd, Quantum machine learning, Nature 549 (7671) (2017) 195.

[8] T. Mitchell, Machine Learning, McGraw-Hill, 1997.

[9] C. Shi, C.-M. Pun, Adaptive multi-scale deep neural networks with perceptual loss for panchromatic and multispectral images classification, Information Sciences 490 (2019) 1 – 17.

[10] H. Zhang, Q. Zhang, L. Ma, Z. Zhang, Y. Liu, A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows, Information Sciences 490 (2019) 166 – 190.

[11] V. Havl´ıˇcek, A. D. C´orcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567 (7747) (2019) 209.

[12] A. J. da Silva, T. B. Ludermir, W. R. de Oliveira, Quantum perceptron over a field and neural network architecture selection in a quantum computer, Neural Networks 76 (2016) 55–64.

[13] A. Fawaz, P. Klein, S. Piat, S. Severini, P. Mountney, Training and meta-training binary neural networks with quantum computing, in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, ACM, 2019, pp. 1674–1681.

[14] V. Dunjko, J. M. Taylor, H. J. Briegel, Quantum-enhanced machine learning, Physical review letters 117 (13) (2016) 130501.

[15] A. W. Harrow, A. Hassidim, S. Lloyd, Quantum algorithm for linear systems of equations, Physical review letters 103 (15) (2009) 150502.

[16] K. H. Wan, O. Dahlsten, H. Kristj´ansson, R. Gardner, M. Kim, Quantum generalisation of feedforward neural networks, npj Quantum Information 3 (1) (2017) 36.

[17] M. Schuld, M. Fingerhuth, F. Petruccione, Implementing a distance-based classifier with a quantum interference circuit, EPL (Europhysics Letters) 119 (6) (2017) 60002.

[18] D. Ventura, T. Martinez, Quantum associative memory, Information Sciences 124 (1-4) (2000) 273–296.

[19] A. Ezhov, A. Nifanova, D. Ventura, Quantum associative memory with distributed queries, Information Sciences 128 (3-4) (2000) 271–293.

[20] C. A. Trugenberger, Probabilistic quantum memories, Physical Review Letters 87 (6) (2001) 067901.

[21] C. A. Trugenberger, Quantum pattern recognition, Quantum Information Processing 1 (6) (2002) 471–493.

[22] T. Brun, H. Klauck, A. Nayak, M. R¨otteler, C. Zalka, Comment on “probabilistic quantum memories”, Phys. Rev. Lett. 91 (2003) 209801. doi:10.1103/PhysRevLett.91.209801. URL https://link.aps.org/doi/10.1103/PhysRevLett.91.209801

[23] M. Schuld, I. Sinayskiy, F. Petruccione, Quantum computing for pattern classification, in: Pacific Rim International Conference on Artificial Intelligence, Springer, 2014, pp. 208–220.

[24] V. Dunjko, H. J. Briegel, Machine learning & artificial intelligence in the quantum domain: a review of recent progress, Reports on Progress in Physics 81 (7) (2018) 074001.

[25] P. G. dos Santos, R. S. Sousa, A. J. da Silva, A wnn model based on probabilistic quantum memories, in: European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning 2019 Proceedings, 2019, pp. 313–318.

[26] M. A. Nielsen, I. Chuang, Quantum computation and quantum information, AAPT, 2002.

[27] R. Zhou, Quantum competitive neural network, International Journal of Theoretical Physics 49 (1) (2010) 110.

[28] F. M. de Paula Neto, A. J. da Silva, W. R. de Oliveira, T. B. Ludermir, Quantum probabilistic associative memory architecture, Neurocomputing 351 (2019) 101–110.

[29] M. P. Singh, K. Radhey, V. Saraswat, S. Kumar, Classification of patterns representing apples and oranges in three-qubit system, Quantum Information Processing 16 (1) (2017) 16.

[30] J.-P. T. Njafa, S. N. Engo, Quantum associative memory with linear and non-linear algorithms for the diagnosis of some tropical diseases, Neural Networks 97 (2018) 1–10.

[31] A. Silva, W. de Oliveira, T. Ludermir, A weightless neural node based on a probabilistic quantum memory, in: 2010 Eleventh Brazilian Symposium on Neural Networks, IEEE, 2010, pp. 259–264.

[32] D. Dheeru, E. Karra Taniskidou, UCI machine learning repository (2017). URL http://archive.ics.uci.edu/ml

[33] J. Demˇsar, Statistical comparisons of classifiers over multiple data sets, Journal of Machine learning research 7 (Jan) (2006) 1–30.

[34] I. Aleksander, M. De Gregorio, F. M. G. Fran¸ca, P. M. V. Lima, H. Morton, A brief introduction to weightless neural systems., in: ESANN, Citeseer, 2009, pp. 299–305.

[35] G. Aleksandrowicz, T. Alexander, P. Barkoutsos, L. Bello, Y. Ben-Haim, D. Bucher, F. J. Cabrera-Hernndez, J. Carballo- Franquis, A. Chen, C.-F. Chen, J. M. Chow, A. D. Crcoles-Gonzales, A. J. Cross, A. Cross, J. Cruz-Benito, C. Culver, S. D. L. P. Gonzlez, E. D. L. Torre, D. Ding, E. Dumitrescu, I. Duran, P. Eendebak, M. Everitt, I. F. Sertage, A. Frisch, A. Fuhrer, J. Gambetta, B. G. Gago, J. Gomez-Mosquera, D. Greenberg, I. Hamamura, V. Havlicek, J. Hellmers, ukasz Herok, H. Horii, S. Hu, T. Imamichi, T. Itoko, A. Javadi-Abhari, N. Kanazawa, A. Karazeev, K. Krsulich, P. Liu, Y. Luh, Y. Maeng, M. Marques, F. J. Martn-Fernndez, D. T. McClure, D. McKay, S. Meesala, A. Mezzacapo, N. Moll, D. M. Rodrguez, G. Nannicini, P. Nation, P. Ollitrault, L. J. O’Riordan, H. Paik, J. Prez, A. Phan, M. Pistoia, V. Prutyanov, M. Reuter, J. Rice, A. R. Davila, R. H. P. Rudy, M. Ryu, N. Sathaye, C. Schnabel, E. Schoute, K. Setia, Y. Shi, A. Silva, Y. Siraichi, S. Sivarajah, J. A. Smolin, M. Soeken, H. Takahashi, I. Tavernelli, C. Taylor, P. Taylour, K. Trabing, M. Treinish, W. Turner, D. Vogt-Lee, C. Vuillot, J. A. Wildstrom, J. Wilson, E. Winston, C. Wood, S. Wood, S. Wrner, I. Y. Akhalwaya, C. Zoufal, Qiskit: An Open-source Framework for Quantum Computing (Jan. 2019). doi:10.5281/ zenodo.2562111. URL https://doi.org/10.5281/zenodo.2562111

[36] I. Q. team, IBM Q 5 Tenerife backend specification v1.3.0, https://ibm.biz/qiskit-tenerife, online; accessed 24-September-2018 (2018).

Designed for Accessibility and to further Open Science