Learning Interpretable Oblivious Trees with Variational Quantum Circuits

Decision trees offer an attractive balance between predictive performance and interpretability. In this work, we explore whether quantum computing can advance interpretable tree learning beyond traditional induction techniques. We introduce Quantum Oblivious Decision Trees, a variational quantum approach for learning oblivious decision trees, i.e., a subclass of trees in which all nodes at the same depth share a common split. Building on a phase-based quantum comparator, we design and study three quantum circuits: general, a conventional hardware-efficient design; structured, which uses one quantum comparator per decision level; and recycle, which reuses a single comparator qubit across all levels via mid-circuit measurement and reset. The advantage of the latter two circuits is that they are interpretable by design. Indeed, their learned feature-threshold pairs can be extracted to reconstruct an equivalent classical oblivious decision tree. We evaluate the proposed circuits on several binary tabular datasets against classical oblivious and non-oblivious tree baselines. When restricted to the same feature set, the quantum circuits achieve comparable performance, with no statistically significant differences from the baselines. As tree depth increases, recycle maintains a constant qubit count and stable accuracy, while general and structured require one additional qubit per level and general loses up to roughly one quarter of its accuracy. Its gradient variance also decays at half the rate observed for the other circuits. Overall, these results characterize the trade-offs between expressivity, interpretability, and qubit efficiency in quantum tree learning.