Quantum Advantage in Decision Trees: A Weighted Graph and \(L_1\) Norm Approach
Published in arXiv, 2026
Abstract
The analysis of the computational power of single-query quantum algorithms is important because they must extract maximal information from one oracle call, revealing fundamental limits of quantum advantage and enabling optimal, resource-efficient quantum computation. This paper proposes a formulation of single-query quantum decision trees as weighted graphs. This formulation has the advantage that it facilitates the analysis of the \(L_1\) spectral norm of the algorithm output. This advantage is based on the fact that a high \(L_1\) spectral norm of the output of a quantum decision tree is a necessary condition to outperform its classical counterpart.
We propose heuristics for maximizing the \(L_1\) spectral norm, show how to combine weighted graphs to generate sequences with strictly increasing norm, and present functions exhibiting exponential quantum advantage. Finally, we establish a necessary condition linking single-query quantum advantage to the asymptotic growth of measurement projector dimensions.
Citation
@misc{grillo2026quantumadvantagedecisiontrees,
title={Quantum Advantage in Decision Trees: A Weighted Graph and Norm Approach},
author={Sebastian Alberto Grillo and Bernardo Daniel Dávalos and Rodney Fabian Franco Torres and Franklin de Lima Marquezino and Edgar López Pezoa},
year={2026},
eprint={2602.04700},
archivePrefix={arXiv},
primaryClass={quant-ph},
url={https://arxiv.org/abs/2602.04700},
}

Leave a Comment
Your email address will not be published. Required fields are marked *