Lecture notes in computer science

Implementation of Classical Decision Trees in a Quantum Computing Paradigm

Manuel Pegalájar Cuéllar, L. G. B. Ruiz, M. C. Pegalajar

Published Oct 8, 2024• 1 citation

DOI: 10.1007/978-3-031-74183-8_19

Related papers

Kvantti puudiagrammit

Oskari Luukkonen

Quantum computers and machine learning are on the forefront of research in both science and engineering. Quantum computers offer significant computational speed-ups in certain tasks. Machine learning on the other hand requires a lot of computational power and is heavily used by both governments and businesses. Thus it is no wonder that the possibility of leveraging the computational efficiency of quantum computers for machine learning tasks is attractive. This thesis focuses on decision trees models, due to their interpretability and wide use cases. This thesis tries to answer the question, how can quantum technology be leveraged to improve the performance and construction of decision trees. The thesis will explore the full implementation of decision trees in quantum circuits as quantum decision trees and their viability in modern hardware and its future relevance. Quantum algorithms for construction and retraining of classical decision trees will also be explored and compared to classical methods. The work found that quantum decision trees show comparable performance to classical decision trees when applied to simple data sets. However, due to hardware limitations quantum decision trees suffer when applied to more complex data sets. Quantum algorithms for tree construction show significant theoretical speed-ups at larger models when compared to classical methods of tree construction.

May 11, 20260 citations

Quantum decision tree classifier

Songfeng Lu, Samuel L. Braunstein

Quantum Information ProcessingNov 18, 2013121 citations

BBQ-Tree: A unified classifier and regressor combining Boolean and quantum logic decisions

Alexander Stahl, Ingo Schmitt

This article provides a detailed explanation of the BBQ-Tree, a unified logic-based model that integrates both classical Decision Trees and Quantum-Logic Decision Trees into a generalized framework for classification and regression. As it combines these paradigms, the BBQ-Tree effectively addresses problems with both linear and curved decision boundaries while prioritizing interpretability. We provide a detailed description of the underlying concepts, a possible training algorithm, experimental evaluations and the incorporation of regression functionality, broadening its applicability beyond classification tasks. Strategies for efficient training and model optimization are also presented. Experimental results demonstrate that the BBQ-Tree produces compact, interpretable models capable of revealing data trends, while achieving accuracy comparable to Decision Trees. Furthermore, its new regression capabilities highlight its versatility and performance across a wider range of tasks.

Information SystemsSep 30, 20251 citation

Tree search and quantum computation

Luís Tarrataca, Andreas Wichert

arXiv:1502.01951Quantum Information ProcessingNov 20, 201010 citations

Decision Diagrams for Quantum Computing

Robert Wille, Stefan Hillmich, Lukas Burgholzer

arXiv:2302.04687Springer eBooksAug 13, 202222 citations

Improved quantum query upper bounds based on classical decision trees

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up in the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example. Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor. Their upper bounds are in terms of a quantity which we call the “guessing complexity” of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to edges of the tree. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are strictly stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes in their construction could yield better upper bounds.

Dec 14, 20220 citations