{
  "aviso": "speedup_declarado es lo que declara la fuente citada, NO una medición de Rosetta. Lo que Rosetta midió va en evidencia_rosetta, y para la mayoría del catálogo está vacío.",
  "procedencia": {
    "fuente": "Quantum Algorithm Zoo",
    "fuente_url": "https://quantumalgorithmzoo.org/",
    "instantanea_sha256": "dee7e76b5f19096ed329c88714744b93babf7b7d0296eb97e357b2582d16b75e",
    "generado_at": "2026-08-09"
  },
  "id": "formula-evaluation",
  "nombre": "Formula Evaluation",
  "categoria": "Oracular Algorithms",
  "categoria_id": "oracular",
  "problema": "Evaluar el valor de una formula booleana (AND/OR/NOT) accediendo a sus entradas por oraculo.",
  "speedup_declarado": "Polynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
  "implementaciones": [],
  "referencias": [
    {
      "n": 8,
      "cita": "Andris Ambainis, Andrew M. Childs, Ben W.Reichardt, Robert Špalek, and Shengyu Zheng Every AND-OR formula of size N can be evaluated in time \\( n^{1/2+o(1)} \\) on a quantum computer. In Proceedings of the 48th IEEE Symposium on the Foundations of Computer Science , pages 363-372, 2007. [ arXiv:quant-ph/0703015 and arXiv:0704.3628 ]",
      "url": "http://arxiv.org/abs/quant-ph/0703015"
    },
    {
      "n": 27,
      "cita": "Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo Discrete-query quantum algorithm for NAND trees. Theory of Computing , 5:119-123, 2009. [ arXiv:quant-ph/0702160 ]",
      "url": "http://arxiv.org/abs/quant-ph/0702160"
    },
    {
      "n": 29,
      "cita": "Richard Cleve, Dmitry Gavinsky, and David L. Yonge-Mallo Quantum algorithms for evaluating MIN-MAX trees. In Theory of Quantum Computation, Communication, and Cryptography , pages 11-15, Springer, 2008. (LNCS Vol. 5106) [ arXiv:0710.5794 ]",
      "url": "http://arxiv.org/abs/0710.5794"
    },
    {
      "n": 38,
      "cita": "Edward Farhi, Jeffrey Goldstone, and Sam Gutmann A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing 4:169-190, 2008. [ arXiv:quant-ph/0702144 ]",
      "url": "http://arxiv.org/abs/quant-ph/0702144"
    },
    {
      "n": 80,
      "cita": "Ben Reichardt and Robert Špalek Span-program-based quantum algorithm for evaluating formulas. Proceedings of STOC 2008 [ arXiv:0710.2630 ]",
      "url": "http://arxiv.org/abs/0710.2630"
    },
    {
      "n": 101,
      "cita": "Andrew Childs, Shelby Kimmel, and Robin Kothari The quantum query complexity of read-many formulas In Proceedings of ESA 2012 , pg. 337-348, Springer. (LNCS 7501) [ arXiv:1112.0548 ]",
      "url": "http://arxiv.org/abs/1112.0548"
    },
    {
      "n": 149,
      "cita": "Ben Reichardt Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS '09) , pg. 544-551, 2009. [ arXiv:0904.2759 ]",
      "url": "http://arxiv.org/abs/0904.2759"
    },
    {
      "n": 158,
      "cita": "Ben W. Reichardt Reflections for quantum query algorithms. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA) , pg. 560-569, 2011. [ arXiv:1005.1601 ]",
      "url": "http://arxiv.org/abs/1005.1601"
    },
    {
      "n": 159,
      "cita": "Ben W. Reichardt Span-program-based quantum algorithm for evaluating unbalanced formulas. arXiv:0907.1622 , 2009.",
      "url": "http://arxiv.org/abs/0907.1622"
    },
    {
      "n": 160,
      "cita": "Ben W. Reichardt Faster quantum algorithm for evaluating game trees. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA) , pg. 546-559, 2011. [ arXiv:0907.1623 ]",
      "url": "http://arxiv.org/abs/0907.1623"
    },
    {
      "n": 164,
      "cita": "Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure. ITCS 2012: Proceedings of the 3rd Innovations in Theoretical Computer Science , ACM, pg. 249-265. [ arXiv:1101.0796 ]",
      "url": "http://arxiv.org/abs/1101.0796"
    },
    {
      "n": 165,
      "cita": "Shelby Kimmel Quantum adversary (upper) bound. 39th International Colloquium on Automata, Languages and Programming - ICALP 2012 Volume 7391, p. 557-568. [ arXiv:1101.0797 ]",
      "url": "http://arxiv.org/abs/1101.0797"
    },
    {
      "n": 269,
      "cita": "Stacey Jeffery and Shelby Kimmel NAND-trees, average choice complexity, and effective resistance arXiv:1511.02235 , 2015.",
      "url": "http://arxiv.org/abs/1511.02235"
    }
  ],
  "n_referencias": 13,
  "remisiones": [],
  "evidencia_rosetta": {
    "medido": false,
    "lectura": "Rosetta no tiene ninguna corrida sellada sobre este algoritmo. Que esté catalogado no significa que lo hayamos medido ni que lo ofrezcamos."
  }
}