Generative Data Intelligence

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

Date:

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.

Abstract

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:/​/​doi.org/​10.48550/​arXiv.1411.4028.
https:/​/​doi.org/​10.48550/​arXiv.1411.4028
arXiv:1411.402

[2] N. Moll et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3, 2017. DOI: https:/​/​doi.org/​10.1088/​2058-9565/​aab822.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2020-04-20-256.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2021-06-17-479.
https:/​/​doi.org/​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:/​/​doi.org/​10.1109/​QCE49297.2020.00017.
https:/​/​doi.org/​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:/​/​doi.org/​10.1140/​epjqt/​s40507-022-00123-4.
https:/​/​doi.org/​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:/​/​doi.org/​10.1088/​2058-9565/​ac3e54.
https:/​/​doi.org/​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:/​/​doi.org/​10.1145/​3477495.3531755.
https:/​/​doi.org/​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:/​/​doi.org/​10.1038/​ncomms5213.
https:/​/​doi.org/​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:/​/​doi.org/​10.1038/​s41534-019-0187-2.
https:/​/​doi.org/​10.1038/​s41534-019-0187-2

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

[12] J. Gacon, C. Zoufal, G. Carleo, and S. Woerner. Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information. Quantum, 5, 2021. DOI: https:/​/​doi.org/​10.22331/​q-2021-10-20-567.
https:/​/​doi.org/​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:/​/​doi.org/​10.1016/​S0004-3702(97)00063-5.
https:/​/​doi.org/​10.1016/​S0004-3702(97)00063-5

[14] M. Kuhn, K. Johnson, et al. Applied predictive modeling, volume 26. Springer, 2013. DOI: https:/​/​doi.org/​10.1007/​978-1-4614-6849-3.
https:/​/​doi.org/​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:/​/​doi.org/​10.1023/​A:1012487302797.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2203.13261.
https:/​/​doi.org/​10.48550/​arXiv.2203.13261
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:/​/​1qbit.com/​whitepaper/​optimal-feature-selection-in-credit-scoring-classification-using-quantum-annealer/​.
https:/​/​1qbit.com/​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:/​/​doi.org/​10.2307/​2282952.
https:/​/​doi.org/​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:/​/​doi.org/​10.1088/​2058-9565/​abdbc9.
https:/​/​doi.org/​10.1088/​2058-9565/​abdbc9

[20] N. Yamamoto. On the natural gradient for variational quantum eigensolver. arXiv preprint – arXiv:1909.05074, 2019. DOI: https:/​/​doi.org/​10.48550/​arXiv.1909.05074.
https:/​/​doi.org/​10.48550/​arXiv.1909.05074
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:/​/​doi.org/​10.48550/​arXiv.2106.05807.
https:/​/​doi.org/​10.48550/​arXiv.2106.05807
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:/​/​doi.org/​10.1007/​s10955-020-02682-1.
https:/​/​doi.org/​10.1007/​s10955-020-02682-1

[23] J. Stokes, J. Izaac, N. Killoran, and G. Carleo. Quantum Natural Gradient. Quantum, 4, 2020. DOI: https:/​/​doi.org/​10.22331/​q-2020-05-25-269.
https:/​/​doi.org/​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:/​/​dx.doi.org/​10.1109/​ICASSP.1998.675489.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2108.00022.
https:/​/​doi.org/​10.48550/​arXiv.2108.00022
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:/​/​doi.org/​10.1103/​PhysRevLett.72.3439.
https:/​/​doi.org/​10.1103/​PhysRevLett.72.3439

[27] J. J. Meyer. Fisher information in noisy intermediate-scale quantum applications. Quantum, 5:539, 2021. DOI: https:/​/​doi.org/​10.22331/​q-2021-09-09-539.
https:/​/​doi.org/​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:/​/​doi.org/​10.1109/​9.119632.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevA.103.012405.
https:/​/​doi.org/​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:/​/​doi.org/​10.1109/​CDC.1997.657661.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.1201.0490.
https:/​/​doi.org/​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:/​/​doi.org/​10.1186/​s40537-020-00305-w.
https:/​/​doi.org/​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:/​/​doi.org/​10.1098/​rspl.1895.0041.
https:/​/​doi.org/​10.1098/​rspl.1895.0041

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

[35] G. Vidal. Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett., 91(14), 2003. DOI: https:/​/​doi.org/​10.1103/​PhysRevLett.91.147902.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.1008.3477.
https:/​/​doi.org/​10.48550/​arXiv.1008.3477

[37] H. Abraham et al. Qiskit: An open-source framework for quantum computing, 2019. DOI: https:/​/​doi.org/​10.5281/​zenodo.2562110.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1103/​PhysRevX.8.031012

[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:/​/​dx.doi.org/​10.1038/​s41467-018-07090-4.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.119.180509.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.127.200505.
https:/​/​doi.org/​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:/​/​doi.org/​10.1145/​3205651.3208227.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.1605.05775.
https:/​/​doi.org/​10.48550/​arXiv.1605.05775
arXiv:1605.05775

[44] A. Novikov, M. Trofimov, and I. Oseledets. Exponential Machines. arXiv preprint – arXiv:1605.03795, 2017. DOI: https:/​/​doi.org/​10.48550/​arXiv.1605.03795.
https:/​/​doi.org/​10.48550/​arXiv.1605.03795
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:/​/​doi.org/​10.1103/​PhysRevX.10.041038. Publisher: American Physical Society.
https:/​/​doi.org/​10.1103/​PhysRevX.10.041038

[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:/​/​doi.org/​10.1038/​s41467-021-27045-6.
https:/​/​doi.org/​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:/​/​doi.org/​10.1088/​2058-9565/​aaea94.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevResearch.3.033002.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevX.12.011047.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2108.02792.
https:/​/​doi.org/​10.48550/​arXiv.2108.02792
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:/​/​doi.org/​10.48550/​arXiv.2110.00507.
https:/​/​doi.org/​10.48550/​arXiv.2110.00507
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:/​/​doi.org/​10.1038/​s41467-021-21728-w.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevA.72.032325.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2019-12-09-214.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2208.13673.
https:/​/​doi.org/​10.48550/​arXiv.2208.13673
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:/​/​doi.org/​10.48550/​arXiv.2205.06217.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2010.15968.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.128.180505.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.126.190501.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevResearch.3.033090.
https:/​/​doi.org/​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:/​/​doi.org/​10.1007/​s10878-014-9734-0.
https:/​/​doi.org/​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] Kaito Wada, Rudy Raymond, Yuki Sato, and Hiroshi C. Watanabe, “Full optimization of a single-qubit gate on the generalized sequential quantum optimizer”, arXiv:2209.08535, (2022).

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-01-26 17:23:57). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-01-26 17:23:51: Could not fetch cited-by data for 10.22331/q-2023-01-26-909 from Crossref. This is normal if the DOI was registered recently.

spot_img

Latest Intelligence

spot_img

Chat with us

Hi there! How can I help you?