{
  "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": "graph-properties-in-the-adjacency-matrix-model",
  "nombre": "Graph Properties in the Adjacency Matrix Model",
  "categoria": "Oracular Algorithms",
  "categoria_id": "oracular",
  "problema": "Decidir propiedades de un grafo (conectividad, bipartito, ciclos) consultando su matriz de adyacencia.",
  "speedup_declarado": "Polynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
  "implementaciones": [],
  "referencias": [
    {
      "n": 13,
      "cita": "A. Berzina, A. Dubrovsky, R. Frivalds, L. Lace, and O. Scegulnaja Quantum query complexity for some graph problems. In Proceedings of the 30th Conference on Current Trends in Theory and Practive of Computer Science , pages 140-150, 2004.",
      "url": null
    },
    {
      "n": 21,
      "cita": "Harry Burhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf Quantum algorithms for element distinctness. In Proceedings of the 16th IEEE Annual Conference on Computational Complexity , pages 131-137, 2001. [ arXiv:quant-ph/0007016 ]",
      "url": "http://arxiv.org/abs/quant-ph/0007016"
    },
    {
      "n": 34,
      "cita": "Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla Quantum query complexity of some graph problems. SIAM Journal on Computing , 35(6):1310-1328, 2006. [ arXiv:quant-ph/0401091 ]",
      "url": "http://arxiv.org/abs/quant-ph/0401091"
    },
    {
      "n": 35,
      "cita": "Christoph Dürr and Peter Høyer A quantum algorithm for finding the minimum. arXiv:quant-ph/9607014 , 1996.",
      "url": "http://arxiv.org/abs/quant-ph/9607014"
    },
    {
      "n": 36,
      "cita": "Christoph Dürr, Mehdi Mhalla, and Yaohui Lei Quantum query complexity of graph connectivity. arXiv:quant-ph/0303169 , 2003.",
      "url": "http://arxiv.org/abs/quant-ph/0303169"
    },
    {
      "n": 52,
      "cita": "Mark Heiligman Quantum algorithms for lowest weight paths and spanning trees in complete graphs. arXiv:quant-ph/0303131 , 2003.",
      "url": "http://arxiv.org/abs/quant-ph/0303131"
    },
    {
      "n": 70,
      "cita": "Frédéric Magniez, Miklos Santha, and Mario Szegedy Quantum algorithms for the triangle problem. SIAM Journal on Computing , 37(2):413-424, 2007. [ arXiv:quant-ph/0310134 ]",
      "url": "http://arxiv.org/abs/quant-ph/0310134"
    },
    {
      "n": 140,
      "cita": "Andrew Childs and Robin Kothari Quantum query complexity of minor-closed graph properties. In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011) , pg. 661-672 [ arXiv:1011.1443 ]",
      "url": "http://arxiv.org/abs/1011.1443"
    },
    {
      "n": 141,
      "cita": "Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha Search via quantum walk. In Proceedings STOC 2007 , pg. 575-584. [ arXiv:quant-ph/0608026 ]",
      "url": "http://arxiv.org/abs/quant-ph/0608026"
    },
    {
      "n": 152,
      "cita": "Aleksandrs Belovs Span programs for functions with constant-sized 1-certificates. In Proceedings of STOC 2012 , pg. 77-84. [ arXiv:1105.4024 ]",
      "url": "http://arxiv.org/abs/1105.4024"
    },
    {
      "n": 153,
      "cita": "Troy Lee, Frédéric Magniez, and Mikos Santha A learning graph based quantum query algorithm for finding constant-size subgraphs. Chicago Journal of Theoretical Computer Science , Vol. 2012, Article 10, 2012. [ arXiv:1109.5135 ]",
      "url": "http://arxiv.org/abs/1109.5135"
    },
    {
      "n": 171,
      "cita": "Stacey Jeffery, Robin Kothari, and Frédéric Magniez Nested quantum walks with quantum data structures. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA'13) , pg. 1474-1485, 2013. [ arXiv:1210.1199 ]",
      "url": "http://arxiv.org/abs/1210.1199"
    },
    {
      "n": 175,
      "cita": "Troy Lee, Frédéric Magniez, and Miklos Santha Improved quantum query algorithms for triangle finding and associativity testing. arXiv:1210.1014 , 2012.",
      "url": "http://arxiv.org/abs/1210.1014"
    },
    {
      "n": 240,
      "cita": "Guoming Wang Span-program-based quantum algorithm for tree detection arXiv:1309.7713 , 2013.",
      "url": "http://arxiv.org/abs/1309.7713"
    },
    {
      "n": 241,
      "cita": "François Le Gall, Harumichi Nishimura, and Seiichiro Tani Quantum algorithm for finding constant-sized sub-hypergraphs over 3-uniform hypergraphs In Proceedings of COCOON, 2014. pg. 429-440 [ arXiv:1310.4127 ]",
      "url": "http://arxiv.org/abs/1310.4127"
    },
    {
      "n": 272,
      "cita": "Agnis Āriņš Span-program-based quantum algorithms for graph bipartiteness and connectivity arXiv:1510.07825 , 2015.",
      "url": "http://arxiv.org/abs/1510.07825"
    },
    {
      "n": 276,
      "cita": "François Le Gall Improved quantum algorithm for triangle finding via combinatorial arguments In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pg. 216-225, 2014. [ arXiv:1407.0085 ]",
      "url": "http://arxiv.org/abs/1407.0085"
    },
    {
      "n": 317,
      "cita": "Chris Cade, Ashley Montanaro, and Aleksandrs Belovs Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness arXiv:1610.00581 , 2016.",
      "url": "http://arxiv.org/abs/1610.00581"
    },
    {
      "n": 318,
      "cita": "A. Belovs and B. Reichardt Span programs and quantum algorithms for st-connectivity and claw detection In European Symposium on Algorithms (ESA'12) , pg. 193-204, 2012. [ arXiv:1203.2603 ]",
      "url": "http://arxiv.org/abs/1203.2603"
    },
    {
      "n": 319,
      "cita": "Titouan Carette, Mathieu Laurière, and Frédéric Magniez Extended learning graphs for triangle finding arXiv:1609.07786 , 2016.",
      "url": "http://arxiv.org/abs/1609.07786"
    },
    {
      "n": 320,
      "cita": "F. Le Gall and N. Shogo Quantum algorithm for triangle finding in sparse graphs In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15) , pg. 590-600, 2015.",
      "url": null
    }
  ],
  "n_referencias": 21,
  "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."
  }
}