Representation of binary classification trees with binary features by quantum circuits

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.

arXiv comment43 pages, 20 figures, 3 tables

References in corpus (40)

• Scikit-learn: Machine Learning in Python
• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Elementary gates for quantum computation
• Variational Quantum Algorithms
• An introduction to quantum machine learning
• Quantum Computation and Decision Trees
• Parameterized quantum circuits as machine learning models
• An adaptive variational algorithm for exact molecular simulations on a quantum computer
• Quantum random access memory
• Validating quantum computers using randomized model circuits
• Synthesis of Quantum Logic Circuits
• Quantum generative adversarial networks
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Quantum-state preparation with universal gate decompositions
• Creating superpositions that correspond to efficiently integrable probability distributions
• Effect of barren plateaus on gradient-free optimization
• A divide-and-conquer algorithm for quantum state preparation
• Quantum generative adversarial learning in a superconducting quantum circuit
• Overview and Comparison of Gate Level Quantum Software Platforms
• Black-box quantum state preparation without arithmetic
• Randomness in Quantum Mechanics: Philosophy, Physics and Technology
• Quantum Inference on Bayesian Networks
• Experimental Evidence of Quantum Randomness Incomputability
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• A Domain-agnostic, Noise-resistant, Hardware-efficient Evolutionary Variational Quantum Eigensolver
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Improved Weighted Random Forest for Classification Problems
• Fast Black-Box Quantum State Preparation
• Quantum rejection sampling
• New techniques for fault-tolerant decomposition of Multi-Controlled Toffoli gate
• Quantum information and randomness
• Study of Decoherence in Quantum Computers: A Circuit-Design Perspective
• The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
• Quantum Circuit Evolution on NISQ Devices
• Quantum Speedup Based on Classical Decision Trees
• An Experimental Comparison of Old and New Decision Tree Algorithms
• Low-depth Quantum State Preparation
• Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits
• A Quantum-Inspired Ensemble Method and Quantum-Inspired Forest Regressors

Cited by in corpus (11)

• Recent advances for quantum classifiers
• Quantum Neural Network Classifiers: A Tutorial
• Quantum Capsule Networks
• Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning
• Enhancing Quantum Computation via Superposition of Quantum Gates
• Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Quantum-inspired attribute selection algorithm: A Fidelity-based Quantum Decision Tree
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• Quantum Active Learning
• Fully Quantum Lattice Gas Automata Building Blocks for Computational Basis State Encodings