acceptodds
Under review as a conference paper at ICLR 2027

Learning Interpretable Oblivious Trees with Variational Quantum Circuits

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
quantum machine learning, quantum computing, variational quantum circuits, decision oblivious trees

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_kFgYOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper, “Learning Interpretable Oblivious Trees with Variational Quantum Circuits,” introduces Quantum Oblivious Decision Trees (QODTs), a variational quantum learning framework designed to combine the interpretability of classical decision trees with quantum circuit-based optimization. The main contributions are three circuit architectures: (1) General, which employs conventional variational quantum circuits with angle encoding; (2) Structured, which explicitly represents each tree level using a phase-based quantum comparator with a trainable threshold; and (3) Recycle, which reuses a single comparator qubit through mid-circuit measurement, reset, and classical feed-forward. The latter two architectures allow learned feature-threshold relationships to be extracted and used to reconstruct classical oblivious decision trees. The recycle architecture is particularly noteworthy for maintaining a constant qubit count as tree depth increases.

Critical strengths
  1. A notable theoretical strength is the incorporation of oblivious decision-tree structure into the variational quantum circuit through phase-based quantum comparators. In the structured and recycle architectures, each decision level corresponds to an explicit feature-threshold comparison, allowing the learned splitting conditions to be recovered from circuit parameters. This establishes a meaningful connection between the mathematical structure of classical decision trees and parameterized quantum circuits. The approach is particularly valuable because it introduces an interpretable inductive bias into quantum model design, rather than relying entirely on generic variational ansätze.

  2. The recycle architecture provides a theoretically motivated approach to reducing quantum resource requirements while preserving the intended decision-tree structure. By combining mid-circuit measurement, qubit reset, and classical feed-forward, the number of required qubits becomes independent of tree depth, decreasing from (d+w) in the structured architecture to (1+w). This construction offers a clear architectural trade-off between qubit resources and sequential circuit execution. Its significance lies in demonstrating how classical control and quantum operations can be combined to represent increasingly deep decision structures without a corresponding increase in qubit count.

Critical weaknesses
  1. Although the structured and recycle architectures explicitly incorporate feature-threshold comparisons, the paper does not establish sufficient theoretical conditions under which the reconstructed classical decision tree faithfully reproduces the quantum model. In particular, the authors acknowledge that the thresholds in the structured architecture are not uniquely identifiable because subsequent variational operations can compensate for changes in their values. Moreover, the reconstruction procedure assigns leaf labels using the majority class of the training samples rather than directly recovering the quantum circuit's prediction mechanism. Consequently, extracting the learned thresholds does not necessarily yield a functionally equivalent classical tree. This limitation is consequential because interpretability is a central motivation of the proposed framework, yet the relationship between parameter interpretability and predictive equivalence remains insufficiently established.

  2. The recycle architecture is presented as a more resource-efficient and trainable alternative, primarily based on its constant qubit count and slower empirical gradient-variance decay. However, the paper does not provide a theoretical characterization of gradient scaling or establish conditions under which the architecture avoids severe optimization difficulties as tree depth increases. Furthermore, reducing the number of qubits introduces additional sequential measurements, resets, classical feed-forward operations, and variational parameters, whose combined computational costs are not theoretically quantified. Without a more complete complexity analysis, it remains unclear whether the observed improvements in qubit efficiency and gradient behavior translate into a meaningful computational advantage. This weakens the broader significance of the proposed architecture beyond the numerical settings considered.

Questions for authors

Q1: In Section 4.2, the authors reconstruct classical oblivious decision trees by extracting the learned feature-threshold pairs and assigning leaf labels according to the majority class of the corresponding training samples. However, Section 5.2 reports an average accuracy reduction of 2.9 percentage points for the structured architecture, with a particularly substantial decrease on the banknote dataset (from 92.8% to 68.8%). Could the authors clarify under what mathematical conditions the reconstructed classical tree can be considered functionally equivalent to the original quantum classifier? In particular, how does the non-identifiability of threshold parameters in the structured architecture affect the theoretical validity of the claimed interpretability?

Q2: Figure 3 demonstrates that the recycle architecture exhibits a slower empirical decay in gradient variance as tree depth increases. However, the analysis appears to rely primarily on numerical observations and fitted decay exponents. Could the authors provide a more rigorous explanation of how mid-circuit measurement, qubit reset, and classical feed-forward influence gradient propagation across successive decision levels? Specifically, is there a theoretical argument supporting the observed improvement in gradient scaling, or could this behavior depend on the selected ansatz, initialization strategy, and dataset characteristics?

Q3: The recycle architecture reduces the qubit requirement from (d+w) to (1+w), but introduces sequential comparator operations and classically conditioned variational blocks at each decision level. Could the authors clarify how the total computational cost scales with tree depth when circuit executions, measurement shots, reset latency, feed-forward operations, and trainable parameters are considered together? This distinction would help establish whether the reduction in qubit count provides a practical resource advantage rather than a trade-off that shifts computational overhead to circuit execution.

3 comments

Thank you for pushing on theory; we agree it was missing, and the revision adds it (changes highlighted in blue in the revised PDF).

Conditions for faithful reconstruction (W1, Q1). Proposition 1 (Sec. 4, proof in App. F) gives the exact form of recycle: ⟨Z⟩(x)=∑bπb(x)g(b)\langle Z\rangle(x) = \sum_{b} \pi_{b}(x) g(b), a soft oblivious tree whose leaf values g(b)g(b) are read from the circuit. Corollary 1 gives the conditions under which the hard tree T(x)=g(b∗)T(x) = g(b^{\ast}) reproduces the circuit: ∣⟨Z⟩−T∣≤2(1−π∗)|\langle Z\rangle - T| \le 2(1-\pi^{\ast}), and the two predict the same class whenever π∗(x)>1/(1+∣T(x)∣)\pi^{\ast}(x) > 1/(1+|T(x)|), where π∗\pi^{\ast} is the probability of the hard path. Functional equivalence therefore holds exactly in the sharp-comparator limit π∗→1\pi^{\ast} \to 1. Empirically, the hard tree agrees with the circuit on 90.7% of test predictions (Table 2). For structured no such decomposition exists: its thresholds can be absorbed by the ansatz (App. D), and only 63.3% of predictions agree, so we now restrict the claim of faithful extraction to recycle. This also explains the banknote case (92.8% → 68.8%).

Gradient scaling (W2, Q2). Proposition 2 (App. F, with proof) shows that for Haar-random blocks Var[∂ϕ⟨Z⟩]=Vw(pi(c))2∏j≠iqj\mathrm{Var}[\partial_\phi\langle Z\rangle] = V_w (p_i^{(c)})^2 \prod_{j\neq i} q_j, where qj=pj2+(1−pj)2=12(1+sin⁡2(xj−tj))∈[12,1]q_j = p_j^2 + (1-p_j)^2 = \frac{1}{2}\big(1+\sin^2(x_j-t_j)\big) \in [\frac{1}{2}, 1]. Mid-circuit measurement turns the circuit into a classical mixture over decision paths, so the cross-path terms of the gradient vanish. The register width, and hence VwV_w, does not grow with depth, and each additional level multiplies the variance by a factor between 12\frac{1}{2} (maximally uncertain split) and 11 (deterministic split), whereas a Haar-random circuit on d+wd+w qubits loses a factor 2 per level regardless. The measured decay rates (App. E, Figure 10) are 0.42–0.69 per level for recycle at w=2w=2, against 0.82–1.51 for general and structured. So yes, the rate depends on the data, through qjq_j, and on the ansatz, through how close the blocks are to Haar-random; the ansatz ablation of App. I shows that the advantage of recycle is preserved under two other ansätze.

Total cost (W2, Q3). App. D quantifies qubits, gates, sequential depth, mid-circuit measurements, resets, feed-forward steps, parameters, evaluations per gradient and wall-clock time (Table 9). We agree that the qubit reduction is a trade-off, not a free saving, and the paper now says so.

Ethics flag. The revised PDF now includes an ethics statement: all datasets are public tabular benchmarks commonly used in machine learning, and no human subjects or new data are involved. We are happy to address any specific concern.

I've revised the scores in recognition of your efforts.

Thank you for revisiting the paper and for raising your score. We appreciate your feedback, which pushed us to add the theoretical results (prop 1 and 2) that now ground the paper.

Reviewer_KnsoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces three quantum circuit approaches for learning oblivious decision trees: general, structured, and recycle. Additionally, the paper investigates how these approaches compare to baselines at different tree depths and finds that different approaches have tradeoffs in terms of tree depth scaling and resource utilization.

Critical strengths

The problem is clearly framed and does a good job at providing necessary background for unfamiliar readers to understand the technique.

The choices for quantum circuit approaches are useful to assess a reasonable breadth of different quantum implementations. Additionally, the evaluation looks at 12 different datasets which provides a good perspective on the performance of the techniques on a good variety of use cases. Overall, I appreciate the breadth of experiments considered in this work and see this as a key strength.

Critical weaknesses

The motivation for using quantum decision trees in this implementation is not clear. While an association is created between decision trees and a quantum implementation, it is not hypothesized explicitly or suggested empirically if this approach may provide a favorable result over a classical algorithm, so it is unclear why one would use this approach in practice.

The paper does not evaluate using simulated noise or real quantum hardware noise. This would help provide understanding as to how the techniques compare in more realistic conditions.

Questions for authors

Do the authors think there is an underlying reason as to why some circuit structures are preferred in certain cases?

Were any other ansatzes considered? It would be helpful to understand if the pattern of the results is consistent across ansatzes with different properties (e.g expressibility).

Why does the recycle design fall behind at a larger number of ensemble members?

3 comments

Thank you for the positive assessment. We address each point below; all changes are highlighted in blue in the revised PDF.

Motivation (W1). We now state the motivation explicitly (Sec. 1), and we do not claim a quantum advantage (Sec. 6). The question is how an interpretable inductive bias can be built into a variational circuit, and what it costs in qubits, depth, trainability and noise. These design questions come before any advantage claim for quantum machine learning on tabular data. The answer is mixed but informative. Building the tree structure in as structured does buys little, since structured is equivalent to general up to a rescaling of the inputs (App. D). Building it in through mid-circuit measurement, as recycle does, yields a provably faithful soft tree (Prop. 1) with better-behaved gradients (Prop. 2).

Noise (W2). See Sec. 5.1 and App. H: under IBM's calibration-based noise model for the Heron r3 processor ibm_aachen, including the mid-circuit measurements and resets of recycle and the decoherence of its ansatz qubits while they wait for each measurement, the accuracy of every circuit stays within 0.001 of noiseless sampling, and 99% of the predictions agree with the exact ones.

Why some circuits are preferred (Q1). Structured and general implement the same model class up to input scaling (App. D). Recycle is a different class: a mixture over decision paths (Prop. 1). This explains why it keeps its accuracy as depth grows, why its gradients decay more slowly (Prop. 2), and why it does best among the circuits on small, noisy datasets such as heart and pima (on pima it is the best of all eight models, Table 1).

Other ansätze (Q2). App. I retrains every circuit with two other ansätze, a low-expressibility RYR_Y + CNOT ring and a hardware-efficient RXRZR_X R_Z + CZ chain (Table 13). Recycle is almost insensitive to the ansatz (mean accuracy 0.836, 0.835 and 0.829) and ranks first among the three circuits on every dataset under both alternatives. General and structured are stable with the RYR_Y ansatz but lose 0.13 and 0.12 with the hardware-efficient one. The pattern therefore holds across ansätze of different expressibility, and the explanation is structural: in recycle the decision logic lives in the measured comparisons, and the ansatz only shapes the leaf values.

Ensembles (Q3). Bagging helps only when members make different errors, so we measured the mean pairwise disagreement of the ten members on the test set for all 360 ensembles (App. C, Table 8). Recycle (0.198) and structured (0.206) have the least diverse members of all eight models (classical baselines 0.211–0.235, general 0.271), and the gain over the average member follows the same order (recycle +0.035, structured +0.039, general +0.069). Across the 72 (dataset, model) cells, gain and disagreement have Spearman correlation 0.78. On banknote, where members share the same features and differ only by seed, disagreement is 0.148 for general, 0.051 for structured and 0.017 for recycle: the threshold structure pins down the decision boundary, so members converge to similar trees. Recycle has the most accurate members among the circuits (0.734) but the least diversity, so its small bagging gain reflects the tree-like inductive bias rather than a training failure.

I appreciate the changes the authors have made, however much of the motivation is still not clear. I would appreciate if the authors would dive deeper into the following statement: "The question is how an interpretable inductive bias can be built into a variational circuit, and what it costs in qubits, depth, trainability and noise. These design questions come before any advantage claim for quantum machine learning on tabular data." What could this goal of building this inductive bias lead to?

Thank you for following up. We see three directions that this inductive bias opens.

1. Quantum models whose decision logic is readable by construction. Post-hoc explanation methods need many additional circuit executions and explain an opaque model only approximately. In recycle the decision logic is exposed by design: the splits are read from the trained parameters, and the leaf table is obtained by running the circuit once per decision path (Prop. 1). Prop. 1 holds for any size of the ansatz register, so the splits and the leaf table remain readable even when the leaf circuits are too large to simulate classically, which is the regime where interpretability of a quantum model is hardest to obtain by other means.

2. Deeper trees and other models built from measurement-separated quantum blocks, in which depth affects the gradient variance through the routing, not through the register width. Prop. 2 shows that when small quantum blocks are separated by measurements and classical feed-forward, the gradient decay is governed by how concentrated the classical routing is, not by the width of the register. This is not specific to trees: any model that can be written as classical routing among small quantum blocks inherits it, so depth and input features can be added without widening the circuit. The comparison with structured gives the complementary lesson: structure that is only encoded coherently is absorbed by the ansatz (App. D), so it has to be enforced by measurement.

3. A place to look for a quantum benefit. At the scale studied here all circuits are easy to simulate classically, and we make no advantage claim. However, the architecture separates the model into a readable classical routing part and quantum leaf blocks. Enlarging the leaf blocks makes the leaf functions richer while the routing stays interpretable, so the open question becomes whether richer quantum leaves help on some data.

Thank you for the question, which is central to our work. We included these clarifications into the conclusion (Sec. 6) to make the motivation of the paper clearer.

Reviewer_N1uROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This is a thoughtful study of quantum circuits that encode oblivious-tree structure. The recycle architecture is the most interesting contribution: it uses mid-circuit measurement and reset to keep qubit count constant with tree depth and empirically shows slower gradient-variance decay. The benchmarking and reproducibility are strong. My main concern is that the headline interpretability wording exceeds the evidence: the extracted classical trees are not functionally equivalent to the trained circuits, and structured has non-identifiable thresholds.

Critical strengths

The three architectures provide a clean comparison of expressivity, explicit structure, and qubit reuse.

Recycle is a novel and practically relevant dynamic-circuit construction with favorable qubit scaling.

Critical weaknesses

The claim that extracted parameters reconstruct an “equivalent” classical ODT is inaccurate. Leaf labels are reassigned by training-set majority vote, extraction loses 0.016–0.029 accuracy on average and 0.240 in one case, and prediction-level fidelity is not reported.

I think QODT does not learn feature selection: features are preselected by mutual information and assigned one per level. Thus, it solves only part of tree induction and forbids feature reuse.

All training uses exact state-vector expectations. Finite-shot analysis is performed only on trained checkpoints, with no device noise. Recycle’s measurement/reset latency and hardware feed-forward errors are unmodeled.

The constant qubit count obscures other scaling costs: recycle’s parameters and sequential depth grow with tree depth. No gate, shot, wall-clock, or latency comparison is provided.

Questions for authors

Can you report prediction agreement between each circuit and its extracted tree and remove or qualify “equivalent”?

Can feature choice be learned jointly while preserving interpretability and qubit efficiency?

How does this method compare to existing interpretable research like integrated gradient for VQEs (e.g., https://arxiv.org/abs/2510.02497)?

3 comments

Thank you for a precise review; each of your four points led to a concrete change in the revised PDF (changes in blue).

"Equivalent" tree / fidelity (W1, Q1). You are right, and we removed the claim. We now report prediction-level agreement for two leaf rules (Table 2, App. G). Recycle: 90.7% with leaves read from the circuit and 89.8% with majority-vote leaves; with circuit leaves the tree reaches 0.742 accuracy without using any training label. Structured: 63.3% and 85.6%. Proposition 1 explains the difference: recycle is exactly a soft oblivious tree, ⟨Z⟩(x)=∑bπb(x)g(b)\langle Z\rangle(x) = \sum_{b} \pi_{b}(x) g(b), so its extracted tree approximates the circuit by following only the most likely path. Corollary 1 (App. F) bounds the gap by 2(1−π∗)2(1-\pi^{\ast}), where π∗\pi^{\ast} is the probability of that path, and guarantees agreement pointwise; the guarantee holds on 29% of test points (Table 10), and agreement on the others is empirical, because the comparator routing is soft. The banknote case you cite (structured, 0.928 → 0.688) is now explained: structured relies on interference between comparison outcomes, so its thresholds are not identifiable, and measuring its comparators before the ansatz changes 36% of its predictions. We therefore restrict the claim of faithful extraction to recycle.

Feature selection (W2, Q2). Correct: QODT learns thresholds and leaf values, not the features, which are selected by mutual information on the training split. We now state this explicitly as a limitation (Sec. 6). A learnable per-level feature selection before each comparator would keep the qubit count and the readable splits, and we list it as a natural next step.

Noise (W3). We added a noise study with IBM's calibration-based noise model for the Heron r3 processor ibm_aachen (Sec. 5.1, App. H): calibrated gate and readout errors and T1T_1/T2T_2 relaxation over the real gate and measurement durations, after transpilation to the device. Recycle is simulated as a dynamic circuit: at each level the comparator is measured and reset by a measurement and a conditional XX, as on IBM hardware, while the ansatz qubits decohere during the 2.58 µs measurement. Accuracy is unchanged: within 0.001 of noiseless sampling for every circuit, with 99% of predictions agreeing with the exact ones (Tables 11–12). Waiting for the measurements costs recycle some margin (mean ∣p−12∣|p-\frac{1}{2}| decreases by 11%, against 6% for the other circuits) but almost no accuracy. The classical feed-forward latency is not part of the calibration data and is not modelled.

Hidden costs (W4). Agreed. App. D gives closed forms and counts (Table 9). At d=4d=4, L=w=1L=w=1, general uses 5 qubits and sequential depth 9, whereas recycle uses 2 qubits, depth 27, 4 mid-circuit measurements and resets, and 28 parameters. Its depth grows by about 6 layers per level against 1, and each shot waits dd times for a measurement (2.58 µs each on the Heron device of App. H) and the feed-forward. Simulated training takes 93 s against 15–17 s.

Integrated gradients (Q3). We added HattriQ (arXiv:2510.02497) to the related work (Sec. 2), in a new paragraph on post-hoc interpretability of quantum machine learning that also covers Shapley-value explanations of circuit gates (Heese et al., 2025) and LIME for quantum neural networks (Pira & Ferrie, 2024). These methods explain an opaque circuit after training through input or gate attributions, whereas QODT exposes splits and a leaf table by design. The two are complementary, and integrated gradients could be applied to the leaf circuits of recycle.

Thank you for the revision, I will keep my current score but tend to give a 2.5, which is slightly better than the first submission.

Thank you for the follow-up and for recognising the improvements over the first submission. We are glad that the revision led you to raise your assessment above 2, and we appreciate the time you spent on both rounds of review.

Comments on the paper

1 comment

We thank the reviewers for their careful reading. All three identified the same strengths (the recycle construction and the controlled three-way comparison) and raised overlapping concerns: the faithfulness of the extracted trees, the hidden costs of recycle, the absence of noise, and the lack of theory for its gradient behaviour. We addressed each with new analyses and results. All changes with respect to the submitted version are highlighted in blue in the revised PDF, and the updated supplementary code contains every new experiment (folder rebuttal/).

  1. Interpretability, now at the prediction level (Sec. 4, 5.2, App. G). We removed the word "equivalent". We prove that recycle computes exactly a soft oblivious tree, ⟨Z⟩(x)=∑bπb(x)g(b)\langle Z\rangle(x) = \sum_{b} \pi_{b}(x) g(b) (Prop. 1), whose leaf values g(b)g(b) can be read from the circuit without training labels. The extracted tree agrees with the circuit on 90.7% of test predictions (worst dataset 79%), and Corollary 1 bounds the difference between the two. For structured, agreement is only 63.3%, and measuring its comparators before the ansatz changes 36% of its predictions, so we now restrict the claim of faithful extraction to recycle.

  2. Theory of recycle's gradients (Prop. 2, App. F). Under the standard Haar assumption, Var[∂ϕ⟨Z⟩]=Vw(pi(c))2∏j≠iqj\mathrm{Var}[\partial_\phi\langle Z\rangle] = V_w (p_i^{(c)})^2 \prod_{j\neq i} q_j with qj=pj2+(1−pj)2∈[12,1]q_j = p_j^2 + (1-p_j)^2 \in [\frac{1}{2}, 1]. The width term VwV_w does not depend on depth, and qjq_j measures how concentrated the routing is at level jj, so each additional level multiplies the gradient variance by a factor between 12\frac{1}{2} and 11. Depth enters through the mixture over decision paths, not through the width of the register.

  3. Costs (App. D). A full resource model: gates, sequential depth, mid-circuit operations, parameters, circuit evaluations per gradient and wall-clock time. The constant qubit count of recycle is paid in depth (about 6 layers per level against 1), parameters and measurement latency (on the IBM Heron device of App. H a measurement takes 2.58 µs, against 68 ns for a CZ gate).

  4. Noise (Sec. 5.1, App. H). We use the calibration-based noise model that Qiskit Aer builds for the IBM Heron r3 processor ibm_aachen (calibration snapshot of 17 April 2026): per-qubit gate and readout errors and T1T_1/T2T_2 relaxation over the calibrated durations, after transpilation to the device. Recycle runs as a real dynamic circuit, with mid-circuit measurements, resets (a measurement followed by a conditional XX, as on IBM hardware) and its ansatz qubits idling during each measurement. For every circuit, mean accuracy stays within 0.001 of a noiseless simulation with the same number of shots, and 99% of the predictions agree with the exact ones.

  5. Further additions. An ansatz ablation (App. I): recycle ranks first on average under all three ansätze, while general and structured lose about 0.12 with a hardware-efficient ansatz. An ensemble-diversity analysis (App. C): structured and recycle have the least diverse bagged members of all models, which explains their small bagging gain (Spearman correlation 0.78 between gain and disagreement). We also added a related-work paragraph on post-hoc interpretability of quantum machine learning and an ethics statement.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.