Recently, converting classical data into quantum information brought considerably potential applications in improving machine learning tasks. Particularly, a quantum feature map could provide a promising alternative kernel to enhance a Support Vector Classifier (SVC). While there are very few existing guiding principles to design a high performing feature map, a quantum circuit family called the Pauli feature map is arguably known to behave well. The family is characterized by the occurrence of Pauli gates on the quantum circuits, while it still has several tunable parameters whose optimal values are sensitive to the nature of the datasets. In this work, we present an automatic generation of such feature map using the Genetic Algorithm (GA), aiming to maximize the accuracy of the model while keeping the circuit as simple as possible. We applied the approach to both synthetic and real datasets. The resulting classification metrics and best circuits are discussed in comparison with several classical and quantum kernel baselines. In general, the GA-generated feature maps perform better than other baselines. Moreover, the results show that the evolutionary circuits tend to difer among various datasets, which signify the usability of this generic scheme to determine the best customized quantum feature map for a specific dataset.
The progress of quantum information technologies opens tation. An important area that can be benefited by quantum computation is artificial intelligence (AI), with main focus on machine learning algorithms[1, 2, 3]. Many cal machine learning models in the quantum computation framework. Several supervised classification models have quantum counterparts, for instances quantum
challenges of requiring a huge computational resource due to their need for a large amount of data and complex model architectures. In this context, quantum machine learning seeks to enhance the capabilities of machine (H. S. Sugiarto)
To build a quantum kernel is essentially to encode classical data ( ⃗) into a useful quantum information (| ( )⃗⟩ ) that can be processed meaningfully by a quantum computer. While this is notoriously dificult, a common approach is to design a specific quantum circuit known as the quantum feature map. The most common quantum ence and Management (QDSM’23), August 28 - September 1, 2023, generate an optimal quantum kernel for SVC. © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License feature map circuit for the quantum kernel SVM is to use Attribution 4.0 International (CC BY 4.0). the ZZ feature map[15]. This map contributes to some its ubiquitous applications in[25]. considerably good results[18, 19, 20]. However, there is Recently, genetic algorithms are also used to optimize no rigorous explanation of why such map is ideal for various quantum circuits for various purposes. The apthe domain-specific works, implying that there might plication of genetic algorithm to automatically generate be another better unexplored feature map option. In- a quantum feature map enhancing a SVC is first formustead of finding the optimal feature map of all possible lated in 2021[26]. In the following year, the same authors quantum circuits, we try to tackle a more modest opti- extend their method with some classical dimensionalmization problem: to find the best Pauli feature map for ity reduction strategies in order to accommodate more specific data (since ZZ feature map is a special case of complex datasets[27]. In their work, the evolutionary Pauli feature map family). Nevertheless, searching the op- design could freely choose the quantum gates structure timal Pauli feature map is also considerably challenging. as well as the entanglement scheme, whereas we rather Because, as the number of data features grows, the com- constrain our design so that the resulting circuit is albinatorial possibilities of Pauli feature maps also grow ways under the Pauli feature map family. Although our exponentially. Therefore, we need an eficient mecha- design seems to be less general, it is able to accommodate nism to find the optimal Pauli feature map for the data. any number of qubits. It also serves the main research
To find the optimal Pauli feature map, we propose a purpose with the best configuration, that is to undergenetic algorithm design with specific encoding that is stand the performance of quantum kernels within the compatible with Pauli feature map family. Genetic algo- underlying family of Pauli feature maps. rithm is a well-established meta-heuristic optimization Later on, many other developments and variations on for searching optimal solutions. This method is very ver- this topic emerges. Apart from the SVC, the genetic alsatile and can be adapted to various types of complex gorithm is also applicable for designing the best circuit problem, including quantum circuit optimization. configuration in the context of Parametric Quantum Cir
The objectives of this work are threefold: (i) to imple- cuit (PQC)[28]. Moreover, a comparison between the ment the genetic algorithm strategy for automatic gener- SVC enhanced by the evolutionary kernel and the variation of the best Pauli feature map for specific datasets, ational ansatz method is also explored[29]. Besides the (ii) to investigate whether customized forms of Pauli fea- genetic algorithm, several other methods to automatically ture map produce a better classifier than popular classical generate the quantum circuit to enhance a classification and quantum counterparts (iii) to understand if there is task also exist. In 2022, a Sequential Model-based Optia consistent pattern among best circuit configurations in mization (SMBO) using Parzen estimator to find the best varying natures of datasets. ansatz circuit is proposed [30]. In a very recent paper,
The rest of this paper is organized as follows. In Sec- a Bayesian approach to adaptively construct the feature tion 2, several related existing works are reviewed and map for preparing an SVM task is presented[31]. compared. Section 3 describes detailed explanation of our proposed method to generate the Pauli feature map using the evolutionary strategy. The datasets are described in 3. Methods Section 4 while the results and further discussions are presented in Section 5. Finally, Section 6 concludes the 3.1. Quantum Kernel Classification paper along with some future outlooks.
classify data based on labeled training examples. Labeled 2. Related Works training data consists of input data with associated output labels or categories, and the algorithm learns to identify This work is a part of an optimization problem in which patterns and relationships between the input data and the specific quantum circuit is optimized on the basis of their corresponding labels. Once trained, the algorithm several criteria. The specific meta-heuristic optimization can then be used to classify new unlabeled data into one frameworks that we employ is the genetic algorithm that of the predefined categories. mimics the natural selection process to obtain the fittest A nonlinear classifier is needed when the data is too individual within generations representing the best so- complex and cannot be separated by a linear boundary lution [21]. Genetic algorithms are used in extremely decision. One of the most common nonlinear classifier diverse areas of classical optimizations. To name some is a kernel SVM[14]. Kernel SVM is capable of separatinstances, it is applicable for path planning of a sensor- ing nonlinear data by mapping the original data using based robot[22], job scheduling[23], and image process- a complex function into a higher-dimensional feature ing[24]. In the field of machine learning, the genetic space to enable better linear separation between diferalgorithm is also commonly utilized to find the best neu- ent classes. Specifically, a nonlinear kernel term is inral network architecture, for example one could review serted into standard SVM prediction. The kernelized binary prediction for data test ⃗′ depends on the sign with data mapping: =1 of
∑ ( ⃗ , ⃗′) + , where and represent the trainable parameters, is the data label, and ( ⃗ , ⃗′) is the kernel between data training ⃗ and data test ⃗′.
In quantum kernel classification, the kernel function is implemented using a quantum circuit which is capable of transforming low dimensional classical data into high dimensional quantum states (i.e. Hilbert space), allowing for the exploration of quantum interactions between data points. These quantum feature maps can be tailored to capture specific patterns in the data, enhancing the classification performance. The key idea behind quantum kernel is to compute the inner product between pairs of quantum information eficiently. The inner products can be used to obtain the feature kernel, (,⃗ )⃗ = |⟨ ( )⃗ ∣ ( )⃗⟩ |2. By performing quantum inner product, the computational advantages of quantum computing such as exponential speedup can be acquired[18].
In traditional machine learning, feature maps are used to transform raw input data into a higher dimensional feature space. Similarly, quantum feature maps are used to transform classical data into a quantum state that can be processed by a quantum computer. In a quantum feature map, the input data is transformed using a quantum gates operation to produce a new quantum state vector that contains higher-order correlations between the original data points (| ( )⃗⟩ =
Φ( )⃗|0⟩⊗ ). The quantum feature maps are able to eficiently generate complex transformation that are computationally hard to construct using classical method. Moreover, the base quantum circuit operation can also be repeated multiple times to construct more complex feature maps.
Quantum feature maps have been shown to be
efective in a variety of machine learning tasks, and ongoing
research is exploring new types of quantum feature maps
and their applications in practical machine learning
problems[16, 18, 26]. ZZ feature map is the most common
proposed feature maps for kernel support vector machine
∈
( )⃗ = {∏( − ) if || > 1
(
represents the Pauli matrices and is a variable to adjust the magnitude of Pauli rotation gates.
type, and . These parameters are arguments on the
Pauli sequence represents the possible choices for . The number of repetitions represents how many times the
type represents the entanglement structure among qubits. In general, every qubit can be either entangled or not with other qubits in various diferent graph structure. To simplify the situation, we use only 4 possible schemes: full, circular, linear, and reverse linear. In full entanglement, all pairs of qubits are connected, while on all other schemes, only consecutive qubits are entangled. The diference is that in circular scheme, the last qubit is connected to the first one, while the other two schemes does not allow this. The distinction between the rest is that the entanglement of the reverse linear is in the opposite direction of that of the linear scheme. Originally, is continuous variables. However, in our scheme, is constrained into 16 possible values only: {ℓ ∶ ℓ = 1, … , 16}, to simplify the combinatorial search space. 16
In this context, the ZZ feature map is only a special case of Pauli feature maps with Pauli sequence [ , ] no repetition, full entanglement, and = 1 . This quantum gates configuration can also be associated with Ising interaction[15]. For 2 features (2 qubits), the Pauli expansion matrix of ZZ feature map can be written as: ()⃗
= exp ( 0 0 + 1 1 + ( − 0)( − 1) 0 1). (
that transform input data with features ⃗∈ quantum information in qubits | ( )⃗⟩ can be described
R
into as unitary operator below:
⊗ ⋯ ⊗ Φ()⃗ = ⏟⏟Φ⏟⏟(⏟)⃗⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟Φ⏟⏟(⏟)⃗⏟⏟⏟⏟⏟⏟
# repetitions Φ()⃗ represents the Pauli expansion matrix: formance[15]. ZZ feature map itself is a second order problem because of its simplicity and experimental per- (2 0) and exp( 1 1) = (2 1). Furthermore, the tensor product, exp(( − 0)( − 1) 0 1)is equivalent Φ()⃗ = exp ( ∑ ( )⃗ ∏ ) .
(
(2( − 0)( − 1))) ⋅ .
3.3. Genetic Algorithm
(
In particular, GA will automatically tune the quantum cir- the Pauli rotation factor. All these are represented using cuits configuration under the Pauli feature-maps family a 4-ary string of length 25 whose alphabet is taken from to achieve the best quantum kernel. Whereas, the SVC {0, 1, 2, 3}. The detailed explanation of the encoding is uses this kernel and internally optimises its parameters. provided in Figure 2. Note that the design of this Pauli
We provide an overview of the GA design with ( + ) feature map encoding is applicable for any number of strategy, summarized in Figure 1, as follows. Initially, the features that the map would receive. However, if the algorithm generates a population of random individuals number of features is < 4 , then the Pauli strings are of size , encoded by a 4-ary string each of which rep- restricted to have length of at most by manipulating resents a certain instance of the Pauli quantum feature the encoding rule for the string length control digits. map as a candidate for solution. For a certain number of We list down some examples to help the reader undergenerations, the algorithm performs the fitness values stand the genetic encoding as provided in Table 1. We computation as well as with certain probabilities, some put some additional remarks on the examples as follows. genetic operators to each individual to filter out the fittest The Pauli sequence of the first example is explained in individual representing the best solution for the optimiza- the example box of Figure 2. As the 0-th digit of the tion problem. The more fitness value of an individual has, second example is 0, it means that the Pauli sequence the more chance of survival it gains within generations. only has length 1 and thus the substring 6 7 … 20 would The genetic operators include the followings: selection not contribute anything to describe the feature map. The operator to perform exploitation while crossover and similar fashion also appears when the first digit of a block mutation operators to perform exploration. These oper- of Pauli string control has value less than 3. For instance, ators are applied in order to produce number of new consider the substring 16 17 … 20 in the first example ofsprings. These processes are repeated for a certain which controls the last Pauli string of the 4-length Pauli (fixed) number of generations that is chosen as a hyper- sequence. The value 16 = 1 tells that the Pauli string parameter of the GA. Finally, the fittest individual of the only has length 2 implying that the values of 19 and 20 last generation is taken to be the final solution and an play no role in describing the feature map. additional evaluation is performed using a predetermined testcase to obtain the overall score of GA solution. 3.3.2. Fitness Values 3.3.1. Genetic Encoding
ious deep and highly entangled circuits, some of them
might provide a considerably good quality of
classification performance. However, at certain point, an
extremely complex circuit would not be practical to deal
the Pauli sequence where the first digit 0 defines the length of the sequence and the next 5( 0 + 1)digits describes the ( 0 + 1)
Pauli strings in ( 0 + 1)blocks of 5-digit strings. (b) The last 4 digits of the encoding describe three other related parameters.
3.3.3. Genetic Operators
operators work. Under the scheme of -tournament
seare selected to join the tournament at which the one
having the greatest fitness value wins the tournament and
thus proceed to the next genetic operators. Particularly,
this work uses = 5 . Next, the parents selected by the
tournaments are randomly paired to undergo the 2-point
crossover scheme with some hyperparameter
probability. For the mutation, we use a slight modification of
the bitflip scheme: once a ’bit’ is decided to mutate, it
will randomly choose a new character from the 4-ary
alphabet uniformly.
(
4.1.1. Synthetic Dataset
4.1.2. Real Dataset
we perform the same benchmarking on several wellknown datasets commonly used to evaluate classification models. Table 2 provides some description of each dataset used in this works. All of these datasets are obtainable via OpenML Python Package[34].
In each group, the model is trained and tested to obtain two classification evaluation metrics: accuracy and f1score (macro-averaged). We include the f1-score since it represents the balance between the other two wellknown metric scores, precision, and recall. The average scores among those of the 4-fold groups will contribute to the fitness values computed during the genetic algorithm. By having the 4-fold scheme, the feature map obtained during the training phase would not overly suit to a very specific group of training set while behave very poorly on another group. Finally, once the best feature map is decided by the GA, we employ it to perform the last training using all the 80% train set. The overall evaluation score of the model is then determined by the last 20% test set which has not been seen at all by the model during the evolutionary training.
4.2. Data Preprocessing & Validation both synthetic and real datasets in order to review its efectiveness. All performance metrics presented in this To set up the training, we normalize the data instances section are the ones obtained on the test dataset whose and split them into 80% training set and 20% testing set. instances are not included during the training. To avoid the overfitting problem, we divide the training The GA hyperparameters used in this work are preset into 4 groups to perform the 4-fold cross-validation. sented in Table 3. These values are generally inherited from [26] while also experimentally fine-tuned. We remark that the relatively low number of generations chosen in this work is determined based on experiments, to avoid the GA to overfit the training data too much. This is because as the number of generation goes up, while the accuracy of the training set rises, at a certain point, the performance on the test set starts to worsen. The construction of the quantum circuit in this paper is implemented using the Qiskit framework[32] (IBM Python library for quantum computing) on classical computers.
As baselines, we pick three classical and four quantum kernels to assist a support vector machine model. The classical include the linear, polynomial, and radial based kernels. For the quantum kernel baselines, we use four circuits based on Pauli feature map families: the X, Y, Z, and ZZ feature maps. One can observe some instances of these circuits on small number of qubits in Figure 5. 5.2. Classification on Real Datasets We then compare their performances to the feature map automatically obtained by the genetic algorithm.
We present the classification results on the synthetic datasets in Table 4. The best metric score for each dataset are written in bold while the best scores among each baseline group are also emphasized in italic. The Pauli feature map circuits produced by the GA best individual for each dataset are provided in Figure 6. The detailed description of each feature map is accessible in Table 5.
While the blobs dataset seems not challenging enough to discriminate between the classical and quantum feaFor real datasets, the classification results can be reviewed in Table 6. Similarly, bold scores denote the overall best metric scores for each dataset while the italic represents the best among each baseline group. The Pauli feature map circuits encoded by the best individual of the GA for each dataset are presented in Figure 7 with each detailed description presented in Table 5.
From the metrics presented there, it is evident that the model enhanced by the GA-generated quantum feature maps generally works the best among all other baseline models. While on iris dataset, the best performance of each group of baselines is no worse than the GAgenerated one, on the other three datasets, the quantum
GA kernel properly dominates all the baseline kernels. noisy_circles noisy_moons noisy_circles
noisy_moons F1 blobs
We observe that the existence of categorical features pansion sub-circuit plays a considerable role to achieve on a dataset could give a significant discrimination be- a better score, for example in veteran dataset. tween the classical and quantum feature maps. On the all- From these results, apparently there is no definitive numerical-valued features such as blood and iris datasets, generic choice of Pauli sequence which could fit all types it seems that the quantum baselines do not significantly of dataset. There are better alternatives of Pauli sequence outperform the classical kernels while the one assisted combination rather than ZZ feature map. While at a by GA could slightly perform better. On the other hand, glance, the choice of Z expansion sub-circuit may seem when there are categorical features on the dataset, which to be ubiquitous on the best choice of many datasets, it are the Irish and Veteran datasets, the quantum-GA fea- is not an absolute fact. For example, the best circuit of ture maps give a significantly better result than all clas- the veteran dataset possesses no Z expansion sub-circuit sical baselines. In particular, the occurrence of the Y ex- at all. Hence, the automatic nature of this evolutionary design of feature map could provide a generic way to ob- computers environment when the technology is ready. tain the best circuit that suits the specific dataset without Finally, this scheme of evolutionary feature map genfalling into overfitting issue. Moreover, we can observe eration can also be applied in other quantum machine that all best circuits has no entanglement and also there learning optimizations. are diverse range of alpha and repetitions parameters.
This result is consistent with some other works [26, 39].
feature maps optimization for the quantum kernel classification using the evolutionary algorithm framework. In all choices of datasets, the evolutionary design has the best accuracy. In fact, the GA-quantum feature map tends to perform significantly better when the dataset has categorical features, which is not a natural habitat of the classical kernels. Overall, the best feature map obtained by the evolutionary algorithm tends not to converge into specific characteristics. This marks the significance of this method, which is able to find diverse designs of feature map customized to the nature of the dataset.
Several possible improvements are left for future works. Further investigation is needed on how the quantum kernel particularly tends to perform better in datasets with categorical features. Moreover, although currently the entanglement type is only encoded using 1 character among the 4-ary genetic code, some modifications may contribute significantly to the complexity of the circuit. For the next work, it is possible to refine the style of the entanglement into many other options so that the small changes of the digits would not lead to huge diference in circuit complexity. Furthermore, this scheme can also be implemented in real quantum
[8] I. Kerenidis, J. Landman, A. Luongo, A. Prakash, [24] M. Gong, Y.-H. Yang, Multi-resolution stereo matchq-means: A quantum algorithm for unsupervised ing using genetic algorithm, in: Proceedings IEEE machine learning, Advances in neural information Workshop on Stereo and Multi-Baseline Vision processing systems 32 (2019). (SMBV 2001), IEEE, 2001, pp. 21–29. [9] I. Cong, S. Choi, M. D. Lukin, Quantum convo- [25] H. Chiroma, S. Abdulkareem, A. Abubakar, T. Herlutional neural networks, Nat. Phys. 15 (2019) awan, Neural networks optimization through ge1273–1278. netic algorithm searches: a review, Appl. Math. Inf. [10] C. Zoufal, A. Lucchi, S. Woerner, Quantum genera- Sci 11 (2017) 1543–1564.
tive adversarial networks for learning and loading [26] S. Altares-López, A. Ribeiro, J. J. García-Ripoll, Aurandom distributions, npj Quantum Inf. 5 (2019) tomatic design of quantum feature maps, Quantum 103. Science and Technology 6 (2021) 045015. [11] M. Schuld, A. Bocharov, K. M. Svore, N. Wiebe, [27] S. Altares-López, J. J. García-Ripoll, A. Ribeiro, AuCircuit-centric quantum classifiers, Physical Re- toqml: Automatic generation and training of roview A 101 (2020) 032308. bust quantum-inspired classifiers by using genetic [12] K. Mitarai, M. Negoro, M. Kitagawa, K. Fujii, Quan- algorithms on grayscale images, arXiv preprint tum circuit learning, Phys. Rev. A 98 (2018) 032309. arXiv:2208.13246 (2022). [13] S. Theodoridis, K. Koutroumbas, Pattern recogni- [28] M. Incudini, F. Martini, A. Di Pierro, Structure tion, Elsevier, 2006. learning of quantum embeddings, arXiv preprint [14] C. Cortes, V. N. Vapnik, Support-vector networks, arXiv:2209.11144 (2022).
Machine Learning 20 (2004) 273–297. [29] B.-S. Chen, J.-L. Chern, Genetically auto[15] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Har- generated quantum feature maps, arXiv preprint row, A. Kandala, J. M. Chow, J. M. Gambetta, Su- arXiv:2207.11449 (2022). pervised learning with quantum-enhanced feature [30] N. Nguyen, K.-C. Chen, Quantum embedding spaces, Nature 567 (2019) 209–212. search for quantum machine learning, IEEE Ac[16] M. Schuld, N. Killoran, Quantum machine learning cess 10 (2022) 41444–41456.
in feature hilbert spaces, Physical review letters [31] E. Torabian, R. V. Krems, Compositional optimiza122 (2019) 040504. tion of quantum circuits for quantum kernels of [17] M. Schuld, Supervised quantum machine learn- support vector machines, Physical Review Research ing models are kernel methods, arXiv preprint 5 (2023) 013211.
arXiv:2101.11020 (2021). [32] Qiskit contributors, Qiskit: An open-source frame[18] Y. Suzuki, H. Yano, Q. Gao, S. Uno, T. Tanaka, work for quantum computing, 2023. doi:1 0 . 5 2 8 1 / M. Akiyama, N. Yamamoto, Analysis and synthesis z e n o d o . 2 5 7 3 5 0 5 . of feature map for kernel-based quantum classifier, [33] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Quantum Machine Intelligence 2 (2020) 1–9. B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, [19] J. Mancilla, C. Pere, A preprocessing perspective for R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, quantum machine learning classification advantage D. Cournapeau, M. Brucher, M. Perrot, E. Duchin finance using nisq algorithms, Entropy 24 (2022) esnay, Scikit-learn: Machine learning in Python, 1656. Mach Learn Res. 12 (2011) 2825–2830. [20] M. Grossi, N. Ibrahim, V. Radescu, R. Loredo, [34] M. Feurer, J. N. Van Rijn, A. Kadra, P. Gijsbers, K. Voigt, C. Von Altrock, A. Rudnik, Mixed N. Mallik, S. Ravi, A. Müller, J. Vanschoren, F. Hutquantum–classical method for fraud detection with ter, Openml-python: an extensible python api for quantum feature selection, IEEE Transactions on openml, Mach Learn Res. 22 (2021) 4573–4577.
Quantum Engineering 3 (2022) 1–12. [35] R. A. Fisher, The use of multiple measurements in [21] L. Davis, Handbook of genetic algorithms (1991). taxonomic problems, Ann. Eugen. 7 (1936) 179–188. [22] G. Yasuda, H. Takai, Sensor-based path planning [36] I.-C. Yeh, K.-J. Yang, T.-M. Ting, Knowledge discovand intelligent steering control of nonholonomic ery on rfm model using bernoulli sequence, Expert mobile robots, in: IECON’01. 27th Annual Confer- Systems with Applications 36 (2009) 5866–5871. ence of the IEEE Industrial Electronics Society (Cat. [37] V. Greaney, T. Kellaghan, Equality of Opportunity in No. 37243), volume 1, IEEE, 2001, pp. 317–322. Irish Schools: a longitudinal study of 500 students, [23] A. Madureira, C. Ramos, S. do Carmo Silva, A co- Educational Company, 1984. ordination mechanism for real world scheduling [38] J. D. Kalbfleisch, R. L. Prentice, The statistical analproblems using genetic algorithms, in: Proceedings ysis of failure time data, John Wiley & Sons, 2011. of the 2002 Congress on Evolutionary Computation. [39] A. Pérez-Salinas, A. Cervera-Lierta, E. Gil-Fuster, CEC’02 (Cat. No. 02TH8600), volume 1, IEEE, 2002, J. I. Latorre, Data re-uploading for a universal quanpp. 175–180. tum classifier, Quantum 4 (2020) 226.