Representation of binary classification trees with binary features by quantum circuits

Raoul Heese1, Patricia Bickert1, and Astrid Elisa Niederle2

1Fraunhofer ITWM, 67663 Kaiserslautern, Germany
2BASF SE, 67063 Ludwigshafen, Germany

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

Abstract

We propose a quantum representation of binary classification trees with binary features based on a probabilistic approach. By using the quantum computer as a processor for probability distributions, a probabilistic traversal of the decision tree can be realized via measurements of a quantum circuit. We describe how tree inductions and the prediction of class labels of query data can be integrated into this framework. An on-demand sampling method enables predictions with a constant number of classical memory slots, independent of the tree depth. We experimentally study our approach using both a quantum computing simulator and actual IBM quantum hardware. To our knowledge, this is the first realization of a decision tree classifier on a quantum device.

Decision trees are well-known predictive models commonly used in data mining and machine learning for a wide area of applications. We propose a quantum representation of binary decision tree classifiers by loading a classical decision tree into a quantum circuit. This approach allows us to train quantum decision trees and use them to make memory-efficient predictions. We experimentally study our approach using both a quantum computing simulator and actual IBM quantum hardware.

► BibTeX data

► References

[1] S.B. Kotsiantis ``Decision trees: a recent overview'' Artif Intell Rev 39, 261-283 (2013).
https:/​/​doi.org/​10.1007/​s10462-011-9272-4

[2] O.Z. Maimonand L. Rokach ``Data Mining With Decision Trees: Theory And Applications'' World Scientific Publishing Company (2014).

[3] L. Breiman ``Classification and Regression Trees'' CRC Press (2017).

[4] Laurent Hyafiland Ronald L. Rivest ``Constructing optimal binary decision trees is NP-complete'' Information Processing Letters 5, 15–17 (1976).
https:/​/​doi.org/​10.1016/​0020-0190(76)90095-8

[5] Dimitris Bertsimasand Jack Dunn ``Optimal classification trees'' Machine Learning 106, 1039–1082 (2017).
https:/​/​doi.org/​10.1007/​s10994-017-5633-9

[6] Arman Zharmagambetov, Suryabhan Singh Hada, Miguel Á. Carreira-Perpiñán, and Magzhan Gabidolla, ``An Experimental Comparison of Old and New Decision Tree Algorithms'' (2020).
arXiv:1911.03054

[7] J.R. Quinlan ``Induction of decision trees'' Machine Learning 1, 81–706 (1986).
https:/​/​doi.org/​10.1007/​BF00116251

[8] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd, ``Quantum machine learning'' Nature 549, 195–202 (2017).
https:/​/​doi.org/​10.1038/​nature23474

[9] Edward Farhiand Sam Gutmann ``Quantum computation and decision trees'' Phys. Rev. A 58, 915–928 (1998).
https:/​/​doi.org/​10.1103/​PhysRevA.58.915

[10] Songfeng Luand Samuel L. Braunstein ``Quantum decision tree classifier'' Quantum Information Processing 13, 757–770 (2014).
https:/​/​doi.org/​10.1007/​s11128-013-0687-5

[11] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, ``An introduction to quantum machine learning'' Contemporary Physics 56, 172–185 (2015).
https:/​/​doi.org/​10.1080/​00107514.2014.964942

[12] Kamil Khadiev, Ilnaz Mannapov, and Liliya Safina, ``The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0'' (2019).
arXiv:1907.06840

[13] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, ``Quantum Random Access Memory'' Physical Review Letters 100 (2008).
https:/​/​doi.org/​10.1103/​physrevlett.100.160501

[14] Iordanis Kerenidisand Anupam Prakash ``Quantum Recommendation Systems'' (2016).
arXiv:1603.08675

[15] Howard Barnum, M Saks, and M Szegedy, ``Quantum Decision Trees and Semidefinite Programming'' (2001).
https:/​/​www.osti.gov/​biblio/​975874

[16] Harry Buhrmanand Ronald de Wolf ``Complexity measures and decision tree complexity: a survey'' Theoretical Computer Science 288, 21–43 (2002) Complexity and Logic.
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[17] Yaoyun Shi ``Entropy lower bounds for quantum decision tree complexity'' Information Processing Letters 81, 23–27 (2002).
https:/​/​doi.org/​10.1016/​S0020-0190(01)00191-0

[18] Salman Beigiand Leila Taghavi ``Quantum Speedup Based on Classical Decision Trees'' Quantum 4, 241 (2020).
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[19] Cristian S. Calude, Michael J. Dinneen, Monica Dumitrescu, and Karl Svozil, ``Experimental evidence of quantum randomness incomputability'' Physical Review A 82 (2010).
https:/​/​doi.org/​10.1103/​physreva.82.022102

[20] Johannes Koflerand Anton Zeilinger ``Quantum Information and Randomness'' European Review 18, 469–480 (2010).
https:/​/​doi.org/​10.1017/​s1062798710000268

[21] Sourabh Katoch, Sumit Singh Chauhan, and Vijay Kumar, ``A review on genetic algorithm: past, present, and future'' Multimedia Tools and Applications 80, 8091–8126 (2021).
https:/​/​doi.org/​10.1007/​s11042-020-10139-6

[22] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang, ``Quantum inference on Bayesian networks'' Phys. Rev. A 89, 062315 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.89.062315

[23] Sima E. Borujeni, Nam H. Nguyen, Saideep Nannapaneni, Elizabeth C. Behrman, and James E. Steck, ``Experimental evaluation of quantum Bayesian networks on IBM QX hardware'' 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) 372–378 (2020).
https:/​/​doi.org/​10.1109/​QCE49297.2020.00053

[24] Michael de Oliveiraand Luis Soares Barbosa ``Quantum Bayesian Decision-Making'' Foundations of Science (2021).
https:/​/​doi.org/​10.1007/​s10699-021-09781-6

[25] S. Akers ``Binary Decision Diagrams'' IEEE Transactions on Computers 27, 509–516 (1978).
https:/​/​doi.org/​10.1109/​TC.1978.1675141

[26] Foster Provostand Pedro Domingos ``Tree Induction for Probability-Based Ranking'' Machine Learning 52, 199–215 (2003).
https:/​/​doi.org/​10.1023/​A:1024099825458

[27] Melanie Mitchell ``An Introduction to Genetic Algorithms'' MIT Press, Cambridge (1999).

[28] Alvaro H. C. Correia, Robert Peharz, and Cassio de Campos, ``Joints in Random Forests'' (2020).
arXiv:2006.14937

[29] M. A. Nielsenand I. L. Chuang ``Quantum Computation and Quantum Information: 10th Anniversary Edition'' Cambridge University Press (2010).

[30] Lov Groverand Terry Rudolph ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002).
arXiv:0208112

[31] Maris Ozols, Martin Roetteler, and Jérémie Roland, ``Quantum rejection sampling'' Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS'12 (2012).
https:/​/​doi.org/​10.1145/​2090236.2090261

[32] Maria Schuldand Francesco Petruccione ``Supervised Learning with Quantum Computers'' Springer International Publishing (2018).

[33] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa, ``Transformation of Quantum States Using Uniformly Controlled Rotations'' Quantum Info. Comput. 5, 467–473 (2005).

[34] V.V. Shende, S.S. Bullock, and I.L. Markov, ``Synthesis of quantum-logic circuits'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
https:/​/​doi.org/​10.1109/​tcad.2005.855930

[35] Martin Pleschand Časlav Brukner ``Quantum-state preparation with universal gate decompositions'' Physical Review A 83 (2011).
https:/​/​doi.org/​10.1103/​physreva.83.032302

[36] Yuval R. Sanders, Guang Hao Low, Artur Scherer, and Dominic W. Berry, ``Black-Box Quantum State Preparation without Arithmetic'' Physical Review Letters 122 (2019).
https:/​/​doi.org/​10.1103/​physrevlett.122.020502

[37] Johannes Bausch ``Fast Black-Box Quantum State Preparation'' (2021).
arXiv:2009.10709

[38] Pierre-Luc Dallaire-Demersand Nathan Killoran ``Quantum generative adversarial networks'' Physical Review A 98 (2018).
https:/​/​doi.org/​10.1103/​physreva.98.012324

[39] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini, ``Parameterized quantum circuits as machine learning models'' Quantum Science and Technology 4, 043001 (2019).
https:/​/​doi.org/​10.1088/​2058-9565/​ab4eb5

[40] Ling Hu, Shu-Hao Wu, Weizhou Cai, Yuwei Ma, Xianghao Mu, Yuan Xu, Haiyan Wang, Yipu Song, Dong-Ling Deng, Chang-Ling Zou, and Luyan Sun, ``Quantum generative adversarial learning in a superconducting quantum circuit'' Science Advances 5 (2019).
https:/​/​doi.org/​10.1126/​sciadv.aav2761

[41] Christa Zoufal, Aurélien Lucchi, and Stefan Woerner, ``Quantum Generative Adversarial Networks for learning and loading random distributions'' npj Quantum Information 5, 103 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0223-2

[42] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter, ``Elementary gates for quantum computation'' Physical Review A 52, 3457–3467 (1995).
https:/​/​doi.org/​10.1103/​physreva.52.3457

[43] Israel F. Araujo, Daniel K. Park, Francesco Petruccione, and Adenilton J. da Silva, ``A divide-and-conquer algorithm for quantum state preparation'' Scientific Reports 11, 6329 (2021).
https:/​/​doi.org/​10.1038/​s41598-021-85474-1

[44] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang, ``Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis'' (2021).
arXiv:2108.06150

[45] Xiao-Ming Zhang, Man-Hong Yung, and Xiao Yuan, ``Low-depth Quantum State Preparation'' (2021).
arXiv:2102.07533

[46] Ji Liu, Luciano Bello, and Huiyang Zhou, ``Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits'' (2020).
arXiv:2012.07711

[47] Laxmidhar Biswal, Debjyoti Bhattacharjee, Anupam Chattopadhyay, and Hafizur Rahaman, ``Techniques for fault-tolerant decomposition of a multicontrolled Toffoli gate'' Physical Review A 100 (2019).
https:/​/​doi.org/​10.1103/​physreva.100.062326

[48] Mehdi Saeediand Massoud Pedram ``Linear-depth quantum circuits forn-qubit Toffoli gates with no ancilla'' Physical Review A 87 (2013).
https:/​/​doi.org/​10.1103/​physreva.87.062318

[49] Manabendra Nath Bera, Antonio Acín, Marek Kuś, Morgan W Mitchell, and Maciej Lewenstein, ``Randomness in quantum mechanics: philosophy, physics and technology'' Reports on Progress in Physics 80, 124001 (2017).
https:/​/​doi.org/​10.1088/​1361-6633/​aa8731

[50] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles, ``Variational Quantum Algorithms'' (2020).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9
arXiv:2012.09265

[51] W. Zhai, P. Kelly, and W.-B. Gong, ``Genetic algorithms with noisy fitness'' Mathematical and Computer Modelling 23, 131–142 (1996).
https:/​/​doi.org/​10.1016/​0895-7177(96)00068-4

[52] Donald A. Sofge ``Toward a Framework for Quantum Evolutionary Computation'' 2006 IEEE Conference on Cybernetics and Intelligent Systems 1–6 (2006).
https:/​/​doi.org/​10.1109/​ICCIS.2006.252360

[53] Gexiang Zhang ``Quantum-inspired evolutionary algorithms: a survey and empirical study'' Journal of Heuristics 17, 303–351 (2011).
https:/​/​doi.org/​10.1007/​s10732-010-9136-0

[54] Rafael Lahoz-Beltra ``Quantum Genetic Algorithms for Computer Scientists'' Computers 5 (2016).
https:/​/​doi.org/​10.3390/​computers5040024

[55] Harper R. Grimsley, Sophia E. Economou, Edwin Barnes, and Nicholas J. Mayhall, ``An adaptive variational algorithm for exact molecular simulations on a quantum computer'' Nature Communications 10, 3007 (2019).
https:/​/​doi.org/​10.1038/​s41467-019-10988-2

[56] Arthur G. Rattew, Shaohan Hu, Marco Pistoia, Richard Chen, and Steve Wood, ``A Domain-agnostic, Noise-resistant, Hardware-efficient Evolutionary Variational Quantum Eigensolver'' (2020).
arXiv:1910.09694

[57] L. Franken, B. Georgiev, S. Muecke, M. Wolter, N. Piatkowski, and C. Bauckhage, ``Gradient-free quantum optimization on NISQ devices'' (2021).
arXiv:2012.13453

[58] Andrew Arrasmith, M. Cerezo, Piotr Czarnik, Lukasz Cincio, and Patrick J. Coles, ``Effect of barren plateaus on gradient-free optimization'' (2020).
https:/​/​doi.org/​10.22331/​q-2021-10-05-558
arXiv:2011.12245

[59] David W. Aha ``Tic-Tac-Toe Endgame Data Set'' (1991) accessed June 2021.
https:/​/​archive.ics.uci.edu/​ml/​datasets/​Tic-Tac-Toe+Endgame

[60] Dheeru Duaand Casey Graff ``UCI Machine Learning Repository'' (2017).
http:/​/​archive.ics.uci.edu/​ml

[61] ``Qiskit: An Open-source Framework for Quantum Computing'' (2019).
https:/​/​doi.org/​10.5281/​zenodo.2562110

[62] 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, 2825–2830 (2011).

[63] John Preskill ``Quantum Computing in the NISQ era and beyond'' Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[64] IBM ``IBM Quantum'' (2021).
https:/​/​quantum-computing.ibm.com

[65] Ryan LaRose ``Overview and Comparison of Gate Level Quantum Software Platforms'' Quantum 3, 130 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-25-130

[66] Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation, and Jay M. Gambetta, ``Validating quantum computers using randomized model circuits'' Physical Review A 100 (2019).
https:/​/​doi.org/​10.1103/​physreva.100.032328

[67] Leo Breiman ``Random Forests'' Machine Learning 45, 5–32 (2001).
https:/​/​doi.org/​10.1023/​A:1010933404324

[68] Chin-Yao Chang, Eric Jones, and Peter Graf, ``On Quantum Computing for Mixed-Integer Programming'' (2020).
arXiv:2010.07852

[69] Jin-Kao Kochenberger, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, and Yang Wang, ``The unconstrained binary quadratic programming problem: a survey'' Journal of Combinatorial Optimization 28, 58–81 (2014).
https:/​/​doi.org/​10.1007/​s10878-014-9734-0

[70] Ehsan Zahedinejadand Arman Zaribafiyan ``Combinatorial Optimization on Gate Model Quantum Computers: A Survey'' (2017).
arXiv:1708.05294

[71] C. E. Shannon ``A mathematical theory of communication'' The Bell System Technical Journal 27, 379–423 (1948).
https:/​/​doi.org/​10.1002/​j.1538-7305.1948.tb01338.x

[72] T.M. Coverand J.A. Thomas ``Elements of Information Theory'' Wiley (2012).

[73] Nisha Saini ``Review of Selection Methods in Genetic Algorithms'' International Journal of Engineering and Computer Science 6, 22261–22263 (2017).
http:/​/​www.ijecs.in/​index.php/​ijecs/​article/​view/​2562

[74] G. Cowan ``Statistics'' Oxford University Press (2020).
https:/​/​doi.org/​10.1093/​ptep/​ptaa104

[75] Jerzy Neyman ``A selection of early statistical papers'' University of California Press (1967).

[76] Niek J. Boumanand Serge Fehr ``Sampling in a Quantum Population, and Applications'' (2012).
arXiv:0907.4246

[77] Lawrence D. Brown, T. Tony Cai, and Anirban DasGupta, ``Interval Estimation for a Binomial Proportion'' Statistical Science 16, 101–133 (2001).
https:/​/​doi.org/​10.1214/​ss/​1009213286

[78] Abdullah Ash Saki, Mahabubul Alam, and Swaroop Ghosh, ``Study of Decoherence in Quantum Computers: A Circuit-Design Perspective'' (2019).
arXiv:1904.04323

[79] G. Lindblad ``On the generators of quantum dynamical semigroups'' Communications in Mathematical Physics 48, 119–130 (1976).
https:/​/​doi.org/​10.1007/​BF01608499

[80] B. M. Villegas-Martínez, F. Soto-Eguibar, and H. M. Moya-Cessa, ``Application of Perturbation Theory to a Master Equation'' Advances in Mathematical Physics 2016, 9265039 (2016).
https:/​/​doi.org/​10.1155/​2016/​9265039

[81] Kamil Khadievand Liliya Safina ``The Quantum Version of Random Forest Model for Binary Classification Problem'' YRID-2020: International Workshop on Data Mining and Knowledge Engineering 30–35 (2020).

[82] Maria Schuldand Francesco Petruccione ``Quantum ensembles of quantum classifiers'' Scientific Reports 8, 2772 (2018).
https:/​/​doi.org/​10.1038/​s41598-018-20403-3

[83] Zeke Xieand Issei Sato ``A Quantum-Inspired Ensemble Method and Quantum-Inspired Forest Regressors'' (2017).
arXiv:1711.08117

[84] Mohsen Shahhosseiniand Guiping Hu ``Improved Weighted Random Forest for Classification Problems'' Progress in Intelligent Decision Science 42–56 (2021).
https:/​/​doi.org/​10.1007/​978-3-030-66501-2_4

Cited by

[1] Weikang Li and Dong-Ling Deng, "Recent advances for quantum classifiers", Science China Physics, Mechanics, and Astronomy 65 2, 220301 (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-29 06:12:13). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-29 06:12:11).