OptiPauli: An algorithm to find a near-optimal Pauli Feature Map for Quantum Support Vector Classifiers
Annika Daspal · 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) · 2022
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.