{
  "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-collision",
  "nombre": "Graph Collision",
  "categoria": "Oracular Algorithms",
  "categoria_id": "oracular",
  "problema": "Decidir si existe un par de vertices vecinos marcados con 1, consultando el etiquetado por oraculo.",
  "speedup_declarado": "Polynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#graph_collision",
  "implementaciones": [],
  "referencias": [
    {
      "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": 161,
      "cita": "Stacey Jeffery, Robin Kothari, and Frédéric Magniez Improving quantum query complexity of Boolean matrix multiplication using graph collision. In Proceedings of ICALP 2012 , pg. 522-532. [ arXiv:1112.5855 ]",
      "url": "http://arxiv.org/abs/1112.5855"
    },
    {
      "n": 172,
      "cita": "Aleksandrs Belovs Learning-graph-based quantum algorithm for k-distinctness. Proceedings of STOC 2012 , pg. 77-84. [ arXiv:1205.1534 ]",
      "url": "http://arxiv.org/abs/1205.1534"
    },
    {
      "n": 200,
      "cita": "D. Gavinsky and T. Ito A quantum query algorithm for the graph collision problem. arXiv:1204.1527 , 2012.",
      "url": "http://arxiv.org/abs/1204.1527"
    },
    {
      "n": 201,
      "cita": "Andris Ambainis, Kaspars Balodis, Jānis Iraids, Raitis Ozols, and Juris Smotrovs Parameterized quantum query complexity of graph collision. arXiv:1305.1021 , 2013.",
      "url": "http://arxiv.org/abs/1305.1021"
    }
  ],
  "n_referencias": 5,
  "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."
  }
}