{
  "$type": "site.standard.document",
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.04700v1",
  "publishedAt": "2026-02-05T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sebastian Alberto Grillo",
    "Bernardo Daniel Dávalos",
    "Rodney Fabian Franco Torres",
    "Franklin de Lima Marquezino",
    "Edgar López Pezoa"
  ],
  "textContent": "**Authors:** Sebastian Alberto Grillo, Bernardo Daniel Dávalos, Rodney Fabian Franco Torres, Franklin de Lima Marquezino, Edgar López Pezoa\n\nThe 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"
}