Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918322930450432 |
|---|---|
| author | Grillo, Sebastian Alberto Dávalos, Bernardo Daniel Torres, Rodney Fabian Franco Marquezino, Franklin de Lima Pezoa, Edgar López |
| author_facet | Grillo, Sebastian Alberto Dávalos, Bernardo Daniel Torres, Rodney Fabian Franco Marquezino, Franklin de Lima Pezoa, Edgar López |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04700 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach Grillo, Sebastian Alberto Dávalos, Bernardo Daniel Torres, Rodney Fabian Franco Marquezino, Franklin de Lima Pezoa, Edgar López Quantum Physics Computational Complexity 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. |
| title | Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2602.04700 |