{"id":"arxiv/2602.04700","url":"https://arxiv.org/abs/2602.04700","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach","domain":"quant-ph","source":"arxiv","authors":["Sebastian Alberto Grillo","Bernardo Daniel Dávalos","Rodney Fabian Franco Torres","Franklin de Lima Marquezino","Edgar López Pezoa"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-04","reactions":{}}