Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2502.11412

Quantum decision trees with information entropy

Z. Li, Koji Terashi

Published Feb 17, 2025• 0 citations
arXivHTMLPDF

Abstract

We present a classification algorithm for quantum states, inspired by decision-tree methods. To adapt the decision-tree framework to the probabilistic nature of quantum measurements, we utilize conditional probabilities to compute information gain, thereby optimizing the measurement scheme. For each measurement shot on an unknown quantum state, the algorithm selects the observable with the highest expected information gain, continuing until convergence. We demonstrate using the simulations that this algorithm effectively identifies quantum states sampled from the Haar random distribution. However, despite not relying on circuit-based quantum neural networks, the algorithm still encounters challenges akin to the barren plateau problem. In the leading order, we show that the information gain is proportional to the variance of the observable's expectation values over candidate states. As the system size increases, this variance, and consequently the information gain, are exponentially suppressed, which poses significant challenges for classifying general Haar-random quantum states. Finally, we apply the quantum decision tree to classify the ground states of various Hamiltonians using physically-motivated observables. On both simulators and quantum computers, the quantum decision tree yields better performances when compared to methods that are not information-optimized. This indicates that the measurement of physically-motivated observables can significantly improve the classification performance, guiding towards the future direction of this approach.

DOI
10.48550/arxiv.2502.11412

Related papers

Information-Theoretic Analysis of Bayesian Quantum State Search

Z. Liang, Koji Terashi

We present an information-theoretic approach to quantum state classification based on sequential Bayesian inference. In each measurement step, the algorithm updates a probability distribution over candidate states by applying Bayes' rule to the observed outcome. For each measurement shot on an unknown quantum state, the algorithm selects the observable with the highest expected information gain, continuing until convergence. We demonstrate using the simulations that this algorithm effectively identifies quantum states sampled from the Haar random distribution. However, despite not relying on circuit-based quantum neural networks, the algorithm still encounters challenges akin to the barren plateau problem. In the leading order, we show that the information gain is proportional to the variance of the observable's expectation values over candidate states. As the system size increases, the variance, and consequently the information gain, are exponentially suppressed, which poses significant challenges for classifying general Haar-random quantum states. Finally, we apply the Bayesian search algorithm to classify the ground states of various Hamiltonians using physically-motivated observables. On both simulators and quantum computers, the Bayesian search algorithm yields better performances when compared to methods that are not information-optimized. This indicates that the measurement of physically-motivated observables can significantly improve the classification performance, guiding towards the future direction of this approach.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Representation of binary classification trees with binary features by quantum circuits

Raoul Heese, Patricia Bickert, Astrid Elisa Niederle

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:2108.13207•Quantum•Mar 30, 2022•22 citations

Optimal quantum likelihood estimation

Alon Levi, Ziv Ossi, Eliahu Cohen +1 more

Abstract A hybrid quantum–classical algorithm is a computational scheme in which quantum circuits are used to extract information that is then processed by a classical routine to guide subsequent quantum operations. These algorithms are especially valuable in the noisy intermediate-scale quantum era, where quantum resources are constrained and classical optimization plays a central role. Here, we improve the performance of a hybrid algorithm through principled, information-theoretic optimization. We focus on Quantum Likelihood Estimation (QLE)–-a hybrid algorithm designed to identify the Hamiltonian governing a quantum system by iteratively updating a weight distribution based on measurement outcomes and Bayesian inference. While QLE already achieves convergence using quantum measurements and Bayesian inference, its efficiency can vary greatly depending on the choice of parameters at each step. We propose an optimization strategy that dynamically selects the initial state, measurement basis, and evolution time in each iteration to maximize the mutual information between the measurement outcome and the true Hamiltonian. This approach builds upon the information-theoretic framework recently developed in Te’eni et al (2024 arXiv:2409.15549), and leverages mutual information as a guiding cost function for parameter selection. Our implementation employs a simulated annealing routine to minimize the conditional von Neumann entropy, thereby maximizing information gain in each iteration. The results demonstrate that our optimized version significantly reduces the number of iterations required for convergence, thus proposing a practical method for accelerating Hamiltonian learning in quantum systems. Finally, we propose a general scheme that extends our approach to solve a broader family of quantum learning problems.

arXiv:2509.00825•Quantum Science and Technology•Dec 10, 2025•1 citation

Quantum Machine Learning in Non-Linear Decision Trees

Jincheng Zhang

Quantum Machine Learning (QML) has emerged as a promising field, offering the potential to revolutionize various computational tasks, including machine learning. This paper investigates the application of QML to decision tree algorithms, specifically focusing on the development of a novel non-linear decision tree model designed for optimized decision-solving. We explore how quantum computation can enhance the optimization process inherent in decision tree construction, leading to improved efficiency and accuracy. The core claim is that leveraging quantum mechanics allows for automatic parameter adjustment within the decision tree, significantly increasing its effectiveness. This work introduces a framework where quantum algorithms are employed to refine the decision tree structure, addressing limitations of traditional methods. The research also investigates the potential benefits of this approach in complex decision scenarios, highlighting the advantages over conventional techniques. The paper concludes with a discussion of future research directions and the expected impact of QML on the field of decision tree learning.

•Sep 4, 2026•0 citations

Empirical Study of Observable Sets in Multiclass Quantum Classification

Paul San Sebastian, Mikel Cañizo, Roman Orus

Variational quantum algorithms have gained attention as early applications of quantum computers for learning tasks. In the context of supervised learning, most of the works that tackle classification problems with parameterized quantum circuits constrain their scope to the setting of binary classification or perform multiclass classification via ensembles of binary classifiers (strategies such as one versus rest). Those few works that propose native multiclass models, however, do not justify the choice of observables that perform the classification. This work studies two main classification criteria in multiclass quantum machine learning: maximizing the expected value of an observable representing a class or maximizing the fidelity of the encoded quantum state with a reference state representing a class. To compare both approaches, sets of Pauli strings and sets of projectors into the computational basis are chosen as observables in the quantum machine learning models. Observing the empirical behavior of each model type, the effect of different observable set choices on the performance of quantum machine learning models is analyzed in the context of Barren Plateaus and Neural Collapse. The results provide insights that may guide the design of future multiclass quantum machine learning models.

quant-pharXiv:2602.08485•Feb 10, 2026•0 citations

Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up 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 particular, we obtain a bounded-error quantum query algorithm of cost $O(\sqrt{s})$ to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size $s$. Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds 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 [Inf. Comp.'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 complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank 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 its edges. 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 asymptotically 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 could yield better upper bounds.

arXiv:2203.02968•Leibniz international proceedings in informatics•Jan 1, 2022•2 citations
We present a classification algorithm for quantum states, inspired by decision-tree methods. To adapt the decision-tree framework to the probabilistic nature of quantum measurements, we utilize conditional probabilities to compute information gain, thereby optimizing the measurement scheme. For each measurement shot on an unknown quantum state, the algorithm selects the observable with the highest expected information gain, continuing until convergence. We demonstrate using the simulations that this algorithm effectively identifies quantum states sampled from the Haar random distribution. However, despite not relying on circuit-based quantum neural networks, the algorithm still encounters challenges akin to the barren plateau problem. In the leading order, we show that the information gain is proportional to the variance of the observable's expectation values over candidate states. As the system size increases, this variance, and consequently the information gain, are exponentially suppressed, which poses significant challenges for classifying general Haar-random quantum states. Finally, we apply the quantum decision tree to classify the ground states of various Hamiltonians using physically-motivated observables. On both simulators and quantum computers, the quantum decision tree yields better performances when compared to methods that are not information-optimized. This indicates that the measurement of physically-motivated observables can significantly improve the classification performance, guiding towards the future direction of this approach.
We present an information-theoretic approach to quantum state classification based on sequential Bayesian inference. In each measurement step, the algorithm updates a probability distribution over candidate states by applying Bayes' rule to the observed outcome. For each measurement shot on an unknown quantum state, the algorithm selects the observable with the highest expected information gain, continuing until convergence. We demonstrate using the simulations that this algorithm effectively identifies quantum states sampled from the Haar random distribution. However, despite not relying on circuit-based quantum neural networks, the algorithm still encounters challenges akin to the barren plateau problem. In the leading order, we show that the information gain is proportional to the variance of the observable's expectation values over candidate states. As the system size increases, the variance, and consequently the information gain, are exponentially suppressed, which poses significant challenges for classifying general Haar-random quantum states. Finally, we apply the Bayesian search algorithm to classify the ground states of various Hamiltonians using physically-motivated observables. On both simulators and quantum computers, the Bayesian search algorithm yields better performances when compared to methods that are not information-optimized. This indicates that the measurement of physically-motivated observables can significantly improve the classification performance, guiding towards the future direction of this approach.
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.
Abstract A hybrid quantum–classical algorithm is a computational scheme in which quantum circuits are used to extract information that is then processed by a classical routine to guide subsequent quantum operations. These algorithms are especially valuable in the noisy intermediate-scale quantum era, where quantum resources are constrained and classical optimization plays a central role. Here, we improve the performance of a hybrid algorithm through principled, information-theoretic optimization. We focus on Quantum Likelihood Estimation (QLE)–-a hybrid algorithm designed to identify the Hamiltonian governing a quantum system by iteratively updating a weight distribution based on measurement outcomes and Bayesian inference. While QLE already achieves convergence using quantum measurements and Bayesian inference, its efficiency can vary greatly depending on the choice of parameters at each step. We propose an optimization strategy that dynamically selects the initial state, measurement basis, and evolution time in each iteration to maximize the mutual information between the measurement outcome and the true Hamiltonian. This approach builds upon the information-theoretic framework recently developed in Te’eni et al (2024 arXiv:2409.15549), and leverages mutual information as a guiding cost function for parameter selection. Our implementation employs a simulated annealing routine to minimize the conditional von Neumann entropy, thereby maximizing information gain in each iteration. The results demonstrate that our optimized version significantly reduces the number of iterations required for convergence, thus proposing a practical method for accelerating Hamiltonian learning in quantum systems. Finally, we propose a general scheme that extends our approach to solve a broader family of quantum learning problems.
Quantum Machine Learning (QML) has emerged as a promising field, offering the potential to revolutionize various computational tasks, including machine learning. This paper investigates the application of QML to decision tree algorithms, specifically focusing on the development of a novel non-linear decision tree model designed for optimized decision-solving. We explore how quantum computation can enhance the optimization process inherent in decision tree construction, leading to improved efficiency and accuracy. The core claim is that leveraging quantum mechanics allows for automatic parameter adjustment within the decision tree, significantly increasing its effectiveness. This work introduces a framework where quantum algorithms are employed to refine the decision tree structure, addressing limitations of traditional methods. The research also investigates the potential benefits of this approach in complex decision scenarios, highlighting the advantages over conventional techniques. The paper concludes with a discussion of future research directions and the expected impact of QML on the field of decision tree learning.
Variational quantum algorithms have gained attention as early applications of quantum computers for learning tasks. In the context of supervised learning, most of the works that tackle classification problems with parameterized quantum circuits constrain their scope to the setting of binary classification or perform multiclass classification via ensembles of binary classifiers (strategies such as one versus rest). Those few works that propose native multiclass models, however, do not justify the choice of observables that perform the classification. This work studies two main classification criteria in multiclass quantum machine learning: maximizing the expected value of an observable representing a class or maximizing the fidelity of the encoded quantum state with a reference state representing a class. To compare both approaches, sets of Pauli strings and sets of projectors into the computational basis are chosen as observables in the quantum machine learning models. Observing the empirical behavior of each model type, the effect of different observable set choices on the performance of quantum machine learning models is analyzed in the context of Barren Plateaus and Neural Collapse. The results provide insights that may guide the design of future multiclass quantum machine learning models.
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up 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 particular, we obtain a bounded-error quantum query algorithm of cost O(s)O(\sqrt{s})O(s​) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size sss. Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds 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 [Inf. Comp.'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 complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank 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 its edges. 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 asymptotically 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 could yield better upper bounds.