# Efficient Quantum Agnostic Improper Learning of Decision Trees

arXiv: https://arxiv.org/abs/2210.00212 · HTML: https://mlsanity.com/paper/2210.00212/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 68 references that are in the map.
- First posted on arXiv 1 Oct 2022.

## Builds on (most cited first, 10 of 10)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Quantum Boosting](https://mlsanity.com/paper/2002.05056/) (2020)
- [Improved Quantum Boosting](https://mlsanity.com/paper/2009.08360/) (2020)
- [Provable guarantees for decision tree induction: the agnostic setting](https://mlsanity.com/paper/2006.00743/) (2020)
- [Universal guarantees for decision tree induction via a higher-order splitting criterion](https://mlsanity.com/paper/2010.08633/) (2020)
- [Quantum and Randomised Algorithms for Non-linearity Estimation](https://mlsanity.com/paper/2103.07934/) (2021)
- [Quantum Boosting using Domain-Partitioning Hypotheses](https://mlsanity.com/paper/2110.12793/) (2021)
- [Few Quantum Algorithms on Amplitude Distribution](https://mlsanity.com/paper/2208.00162/) (2022)

## Built on by (most cited first, 2 of 2)

- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)

## Abstract (arXiv)

The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a poly(n,t,frac1varepsilon) quantum algorithm for learning size t decision trees with uniform marginal over instances, in the agnostic setting, without membership queries. Our algorithm is the first algorithm (classical or quantum) for learning decision trees in polynomial time without membership queries. We show how to construct a quantum agnostic weak learner by designing a quantum version of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. We show how to quantize the agnostic boosting algorithm by Kalai and Kanade (NIPS 2009) to obtain the first efficient quantum agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial improvement in the dependence of the bias of the weak learner over all adaptive quantum boosting algorithms while retaining the standard speedup in the VC dimension over classical boosting algorithms. We then use our quantum boosting algorithm to boost the weak quantum learner we obtained in the previous step to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms for both the realizable setting and random classification noise model, again without membership queries.