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.

43 pages, 20 figures, 3 tables

References in corpus (12)

• An introduction to quantum machine learning
• Quantum random access memory
• Synthesis of Quantum Logic Circuits
• Quantum-state preparation with universal gate decompositions
• Creating superpositions that correspond to efficiently integrable probability distributions
• Experimental Evidence of Quantum Randomness Incomputability
• A Domain-agnostic, Noise-resistant, Hardware-efficient Evolutionary Variational Quantum Eigensolver
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Quantum information and randomness
• Study of Decoherence in Quantum Computers: A Circuit-Design Perspective
• Low-depth Quantum State Preparation
• Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits

Cited by in corpus (10)

• 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
• 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