OptiPauli: An algorithm to find a near-optimal Pauli Feature Map for Quantum Support Vector Classifiers
Annika Daspal
Quantum Support Vector Classifiers have been gaining traction in solving classification problems as it enables efficient kernel estimation and potential improvement in accuracy. To estimate the kernel matrices, a quantum kernel needs a Pauli Feature Map which encodes the classical data into the quantum state space. For a given dataset and dimension, we can have an exorbitant number of Pauli Feature Maps. Hence, finding a Pauli Feature Map that maximizes model accuracy is a research challenge. To address this optimization problem, we propose an algorithm that finds a near-optimal Pauli Feature Map by solving several sub-problems with varying numbers of decision variables and their constraints. Each sub-problem aims to find the Pauli Feature Map that maximizes the model accuracy. We use genetic algorithm to solve each sub-problem, and then select the best out of all the near-optimal Pauli Feature Maps. Instead of formulating a single optimization problem, we use this divide-and-conquer approach (of breaking down the problem into multiple sub-problems) to reduce the overall search space. To evaluate the efficiency of our algorithm, we compare it against solving each sub-problem through exhaustive approach. The latter yields the optimal Pauli Feature Map by exploring the full state space. For the scikit-learn Breast Cancer dataset with dimension 5, our algorithm converges to the optimal Pauli Feature Map in about 804 seconds which is over 4 times faster than the exhaustive approach.
IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•4 citations