Variational Decision Trees with Structured Ansatzes

Decision trees are among the most interpretable models in machine learning, widely valued for their transparency, simplicity, and alignment with human reasoning. However, traditional decision tree algorithms rely on greedy heuristics, splitting nodes one at a time based on local criteria, which often leads to suboptimal trees and limits their effectiveness in complex scenarios. In this work, we propose a quantum-enhanced approach for learning decision trees, with the aim of identifying a optimal tree according to a specified global criterion. This approach employs a Variational Quantum Algorithm (VQA) to encode and optimize the decision tree represented as matrix, leveraging tailored ansatzes that constrain the search to a specific subspace of the Hilbert space.