Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection

Christa Zoufal1, Ryan V. Mishmash2, Nitin Sharma3, Niraj Kumar3, Aashish Sheshadri3, Amol Deshmukh4, Noelle Ibrahim4, Julien Gacon5,6, and Stefan Woerner5

1IBM Quantum, IBM Research Europe – Zurich
2IBM Quantum, Almaden Research Center – Almaden
3PayPal – San Jose
4IBM Quantum, Thomas J. Watson Research Center – Yorktown Heights
5IBM Quantum, IBM Research – Zurich
6Institute of Physics, École Polytechnique Fédérale de Lausanne (EPFL)

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We introduce a variational quantum algorithm to solve unconstrained black box binary optimization problems, i.e., problems in which the objective function is given as black box. This is in contrast to the typical setting of quantum algorithms for optimization where a classical objective function is provided as a given Quadratic Unconstrained Binary Optimization problem and mapped to a sum of Pauli operators. Furthermore, we provide theoretical justification for our method based on convergence guarantees of quantum imaginary time evolution.

To investigate the performance of our algorithm and its potential advantages, we tackle a challenging real-world optimization problem: $\textit{feature selection}$. This refers to the problem of selecting a subset of relevant features to use for constructing a predictive model such as fraud detection. Optimal feature selection---when formulated in terms of a generic loss function---offers little structure on which to build classical heuristics, thus resulting primarily in ‘greedy methods’. This leaves room for (near-term) quantum algorithms to be competitive to classical state-of-the-art approaches. We apply our quantum-optimization-based feature selection algorithm, termed VarQFS, to build a predictive model for a credit risk data set with $20$ and $59$ input features (qubits) and train the model using quantum hardware and tensor-network-based numerical simulations, respectively. We show that the quantum method produces competitive and in certain aspects even better performance compared to traditional feature selection techniques used in today's industry.

► BibTeX data

► References

[1] E. Farhi, J. Goldstone, and S. Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint - arXiv:1411.402, 2014. DOI: https:/​/​​10.48550/​arXiv.1411.4028.

[2] N. Moll et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3, 2017. DOI: https:/​/​​10.1088/​2058-9565/​aab822.

[3] P. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner. Improving variational quantum optimization using CVaR. Quantum, 4:256, 2020. DOI: https:/​/​​10.22331/​q-2020-04-20-256.

[4] D. J. Egger, J. Mareček, and S. Woerner. Warm-starting quantum optimization. Quantum, 5, 2021. DOI: https:/​/​​10.22331/​q-2021-06-17-479.

[5] J. Gacon, C. Zoufal, and S. Woerner. Quantum-enhanced simulation-based optimization. 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 2020. DOI: https:/​/​​10.1109/​QCE49297.2020.00017.

[6] D. Amaro, M. Rosenkranz, N. Fitzpatrick, K. Hirano, and M. Fiorentini. A case study of variational quantum algorithms for a job shop scheduling problem. EPJ Quantum Technology, 9(1):5, 2022. DOI: https:/​/​​10.1140/​epjqt/​s40507-022-00123-4.

[7] D. Amaro, C. Modica, M. Rosenkranz, M. Fiorentini, M. Benedetti, and M. Lubasch. Filtering variational quantum algorithms for combinatorial optimization. Quantum Science and Technology, 7(1):015021, 2022. DOI: https:/​/​​10.1088/​2058-9565/​ac3e54.

[8] M. F. Dacrema, F. Moroni, R. Nembrini, N. Ferro, G. Faggioli, and P. Cremonesi. Towards feature selection for ranking and classification exploiting quantum annealers. Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022. DOI: https:/​/​​10.1145/​3477495.3531755.

[9] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1), 2014. DOI: https:/​/​​10.1038/​ncomms5213.

[10] S. McArdle, T. Jones, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan. Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information, 5(1), 2019. DOI: https:/​/​​10.1038/​s41534-019-0187-2.

[11] D. Dua and C. Graff. UCI machine learning repository, 2017. Available online: http:/​/​​ml/​machine-learning-databases/​statlog/​german/​

[12] J. Gacon, C. Zoufal, G. Carleo, and S. Woerner. Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information. Quantum, 5, 2021. DOI: https:/​/​​10.22331/​q-2021-10-20-567.

[13] A. L. Blum and P. Langley. Selection of relevant features and examples in machine learning. Artificial Intelligence, 97(1), 1997. DOI: https:/​/​​10.1016/​S0004-3702(97)00063-5.

[14] M. Kuhn, K. Johnson, et al. Applied predictive modeling, volume 26. Springer, 2013. DOI: https:/​/​​10.1007/​978-1-4614-6849-3.

[15] I. Guyon, J. Weston, S. Barnhill, and V. Vapnik. Gene selection for cancer classification using support vector machines. Machine learning, 46(1):389–422, 2002. DOI: https:/​/​​10.1023/​A:1012487302797.

[16] S. Mücke, R. Heese, S. Müller, M. Wolter, and N. Piatkowski. Quantum feature selection. arXiv preprint - arXiv:2203.13261, 2022. DOI: https:/​/​​10.48550/​arXiv.2203.13261.

[17] A. Milne, M. Rounds, and P. Goddard. Optimal feature selection in credit scoring and classification using a quantum annealer, 2017. Available online: https:/​/​​whitepaper/​optimal-feature-selection-in-credit-scoring-classification-using-quantum-annealer/​.

[18] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. DOI: https:/​/​​10.2307/​2282952.

[19] P. Huembeli and A. Dauphin. Characterizing the loss landscape of variational quantum circuits. Quantum Science and Technology, 6(2), 2021. DOI: https:/​/​​10.1088/​2058-9565/​abdbc9.

[20] N. Yamamoto. On the natural gradient for variational quantum eigensolver. arXiv preprint - arXiv:1909.05074, 2019. DOI: https:/​/​​10.48550/​arXiv.1909.05074.

[21] A. Lopatnikova and M.-N. Tran. Quantum Speedup of Natural Gradient for Variational Bayes. arXiv preprint - arXiv:2106.05807, 2021. DOI: https:/​/​​10.48550/​arXiv.2106.05807.

[22] S. Becker and W. Li. Quantum Statistical Learning via Quantum Wasserstein Natural Gradient. Journal of Statistical Physics, 182(1):7, 2021. DOI: https:/​/​​10.1007/​s10955-020-02682-1.

[23] J. Stokes, J. Izaac, N. Killoran, and G. Carleo. Quantum Natural Gradient. Quantum, 4, 2020. DOI: https:/​/​​10.22331/​q-2020-05-25-269.

[24] S. Amari and S. C. Douglas. Why natural gradient? In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181), volume 2, pages 1213–1216 vol.2, 1998. DOI: http:/​/​​10.1109/​ICASSP.1998.675489.

[25] C. Zoufal, D. Sutter, and S. Woerner. Error bounds for variational quantum time evolution. arXiv preprint - arXiv:2108.00022, 2021. DOI: https:/​/​​10.48550/​arXiv.2108.00022.

[26] S. L. Braunstein and C. M. Caves. Statistical distance and the geometry of quantum states. Phys. Rev. Lett., 72, 1994. DOI: https:/​/​​10.1103/​PhysRevLett.72.3439.

[27] J. J. Meyer. Fisher information in noisy intermediate-scale quantum applications. Quantum, 5:539, 2021. DOI: https:/​/​​10.22331/​q-2021-09-09-539.

[28] J. Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 37(3), 1992. DOI: https:/​/​​10.1109/​9.119632.

[29] A. Mari, T. R. Bromley, and N. Killoran. Estimating the gradient and higher-order derivatives on quantum hardware. Physical Review A, 103(1), 2021. DOI: https:/​/​​10.1103/​PhysRevA.103.012405.

[30] J. Spall. Accelerated second-order stochastic optimization using only function measurements. In Proceedings of the 36th IEEE Conference on Decision and Control, volume 2, 1997. DOI: https:/​/​​10.1109/​CDC.1997.657661.

[31] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12, 2011. DOI: https:/​/​​10.48550/​arXiv.1201.0490.

[32] J. T. Hancock and T. M. Khoshgoftaar. Survey on categorical data for neural networks. Journal of Big Data, 7(1):28, 2020. DOI: https:/​/​​10.1186/​s40537-020-00305-w.

[33] K. Pearson and F. Galton. Note on regression and inheritance in the case of two parents. Proceedings of the Royal Society of London, 58(347-352), 1895. DOI: https:/​/​​10.1098/​rspl.1895.0041.

[34] LightGBM. https:/​/​​en/​latest/​index.html. Accessed: 2021-09-02.

[35] G. Vidal. Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett., 91(14), 2003. DOI: https:/​/​​10.1103/​PhysRevLett.91.147902.

[36] U. Schollwöck. The density-matrix renormalization group in the age of matrix product states. Ann. Phys., 326(1):96–192, 2011. DOI: https:/​/​​10.48550/​arXiv.1008.3477.

[37] H. Abraham et al. Qiskit: An open-source framework for quantum computing, 2019. DOI: https:/​/​​10.5281/​zenodo.2562110.

[38] Z.-Y. Han, J. Wang, H. Fan, L. Wang, and P. Zhang. Unsupervised Generative Modeling Using Matrix Product States. Phys. Rev. X, 8(3):031012, 2018. DOI: 10.1103/​PhysRevX.8.031012. Publisher: American Physical Society.

[39] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1), 2018. DOI: http:/​/​​10.1038/​s41467-018-07090-4.

[40] K. Temme, S. Bravyi, and J. M. Gambetta. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett., 119, 2017. DOI: https:/​/​​10.1103/​PhysRevLett.119.180509.

[41] C. Piveteau, D. Sutter, S. Bravyi, J. M. Gambetta, and K. Temme. Error mitigation for universal gates on encoded qubits. Phys. Rev. Lett., 127:200505, 2021. DOI: https:/​/​​10.1103/​PhysRevLett.127.200505.

[42] S. Saito, S. Shirakawa, and Y. Akimoto. Embedded Feature Selection Using Probabilistic Model-Based Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '18, page 1922–1925, New York, NY, USA, 2018. Association for Computing Machinery. DOI: https:/​/​​10.1145/​3205651.3208227.

[43] E. M. Stoudenmire and D. J. Schwab. Supervised Learning with Quantum-Inspired Tensor Networks. arXiv preprint - arXiv:1605.05775, 2017. DOI: https:/​/​​10.48550/​arXiv.1605.05775.

[44] A. Novikov, M. Trofimov, and I. Oseledets. Exponential Machines. arXiv preprint - arXiv:1605.03795, 2017. DOI: https:/​/​​10.48550/​arXiv.1605.03795.

[45] Y. Zhou, E. M. Stoudenmire, and X. Waintal. What Limits the Simulation of Quantum Computers? Phys. Rev. X, 10(4):041038, 2020. DOI: https:/​/​​10.1103/​PhysRevX.10.041038. Publisher: American Physical Society.

[46] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles. Noise-Induced Barren Plateaus in Variational Quantum Algorithms. Nature Communications, 12(1):6961, 2021. DOI: https:/​/​​10.1038/​s41467-021-27045-6.

[47] W. Huggins, P. Patil, B. Mitchell, K. B. Whaley, and E. M. Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and Technology, 4(2):024001, 2019. DOI: https:/​/​​10.1088/​2058-9565/​aaea94.

[48] M. Foss-Feig, D. Hayes, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, J. M. Pino, and A. C. Potter. Holographic quantum algorithms for simulating correlated spin systems. Physical Review Research, 3(3):033002, 2021. DOI: https:/​/​​10.1103/​PhysRevResearch.3.033002.

[49] R. Haghshenas, J. Gray, A. C. Potter, and G. K.-L. Chan. Variational power of quantum circuit tensor networks. Phys. Rev. X, 12:011047, 2022. DOI: https:/​/​​10.1103/​PhysRevX.12.011047.

[50] L. Slattery and B. K. Clark. Quantum Circuits For Two-Dimensional Isometric Tensor Networks. arXiv preprint - arXiv:2108.02792, 2021. DOI: https:/​/​​10.48550/​arXiv.2108.02792.

[51] I. MacCormack, A. Galda, and A. L. Lyon. Simulating Large PEPs Tensor Networks on Small Quantum Devices. arXiv preprint - arXiv:2110.00507, 2021. DOI: https:/​/​​10.48550/​arXiv.2110.00507.

[52] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1), 2021. DOI: https:/​/​​10.1038/​s41467-021-21728-w.

[53] A. Hayashi, T. Hashimoto, and M. Horibe. Reexamination of optimal quantum state estimation of pure states. Physical Review A, 72(3), 2005. DOI: https:/​/​​10.1103/​PhysRevA.72.032325.

[54] E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti. An initialization strategy for addressing barren plateaus in parametrized quantum circuits. Quantum, 3, 2019. DOI: https:/​/​​10.22331/​q-2019-12-09-214.

[55] M. S. Rudolph, J. Miller, J. Chen, A. Acharya, and A. Perdomo-Ortiz. Synergy between quantum circuits and tensor networks: Short-cutting the race to practical quantum advantage. arXiv preprint - arXiv:2208.13673, 2022. DOI: https:/​/​​10.48550/​arXiv.2208.13673.

[56] J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert. Exploiting symmetry in variational quantum machine learning, 2022. DOI: https:/​/​​10.48550/​arXiv.2205.06217.

[57] C. Ortiz Marrero, M. Kieferová, and N. Wiebe. Entanglement-induced barren plateaus. PRX Quantum, 2:040316, 2021. DOI: https:/​/​​10.48550/​arXiv.2010.15968.

[58] K. Sharma, M. Cerezo, L. Cincio, and P. J. Coles. Trainability of dissipative perceptron-based quantum neural networks. Phys. Rev. Lett., 128:180505, 2022. DOI: https:/​/​​10.1103/​PhysRevLett.128.180505.

[59] Z. Holmes, A. Arrasmith, B. Yan, P. J. Coles, A. Albrecht, and A. T. Sornborger. Barren Plateaus Preclude Learning Scramblers. Physical Review Letters, 126(19), 2021. DOI: https:/​/​​10.1103/​PhysRevLett.126.190501.

[60] T. L. Patti, K. Najafi, X. Gao, and S. F. Yelin. Entanglement devised barren plateau mitigation. Physical Review Research, 3(3), 2021. DOI: https:/​/​​10.1103/​PhysRevResearch.3.033090.

[61] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28(1):58–81, 2014. DOI: https:/​/​​10.1007/​s10878-014-9734-0.

[62] I. I. Cplex. V12. 1: User’s Manual for CPLEX. International Business Machines Corporation, 46(53):157, 2009.

Cited by

[1] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 129 (2023) ISBN:979-8-3503-4323-6.

[2] Haiyan Wang, "A novel feature selection method based on quantum support vector machine", Physica Scripta 99 5, 056006 (2024).

[3] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner, and Giuseppe Carleo, "Variational quantum time evolution without the quantum geometric tensor", Physical Review Research 6 1, 013143 (2024).

[4] Giuseppe Scriva, Nikita Astrakhantsev, Sebastiano Pilati, and Guglielmo Mazzola, "Challenges of variational quantum optimization with measurement shot noise", Physical Review A 109 3, 032408 (2024).

[5] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).

[6] Katsuhiro Endo, Yuki Sato, Rudy Raymond, Kaito Wada, Naoki Yamamoto, and Hiroshi C. Watanabe, "Optimal parameter configurations for sequential optimization of the variational quantum eigensolver", Physical Review Research 5 4, 043136 (2023).

[7] Gerhard Hellstern, Vanessa Dehn, and Martin Zaefferer, "Quantum computer based feature selection in machine learning", IET Quantum Communication qtc2.12086 (2024).

[8] Mathias Schmid, Sarah Braun, Rudolf Sollacher, and Michael J. Hartmann, "Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers", arXiv:2401.16381, (2024).

[9] Yaswitha Gujju, Atsushi Matsuo, and Rudy Raymond, "Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications", arXiv:2307.00908, (2023).

[10] Alistair Letcher, Stefan Woerner, and Christa Zoufal, "Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits", arXiv:2309.12681, (2023).

[11] Kaito Wada, Rudy Raymond, Yuki Sato, and Hiroshi C. Watanabe, "Sequential optimal selection of a single-qubit gate and its relation to barren plateau in parameterized quantum circuits", arXiv:2209.08535, (2022).

[12] Monit Sharma, Hoong Chuin Lau, and Rudy Raymond, "Quantum-Enhanced Simulation-Based Optimization for Newsvendor Problems", arXiv:2403.17389, (2024).

[13] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner, "Stochastic Approximation of Variational Quantum Imaginary Time Evolution", arXiv:2305.07059, (2023).

[14] Kaito Wada, Kazuma Fukuchi, and Naoki Yamamoto, "Quantum-enhanced mean value estimation via adaptive measurement", arXiv:2210.15624, (2022).

[15] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler, and Stefan Woerner, "Provable bounds for noise-free expectation values computed from noisy samples", arXiv:2312.00733, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-19 03:59:33) and SAO/NASA ADS (last updated successfully 2024-04-19 03:59:34). The list may be incomplete as not all publishers provide suitable and complete citation data.