{
  "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": "collision-finding-and-element-distinctness",
  "nombre": "Collision Finding and Element Distinctness",
  "categoria": "Oracular Algorithms",
  "categoria_id": "oracular",
  "problema": "Hallar dos entradas con la misma salida, o decidir si todos los elementos de una lista son distintos.",
  "speedup_declarado": "Polynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
  "implementaciones": [],
  "referencias": [
    {
      "n": 7,
      "cita": "Andris Ambainis Quantum walk algorithm for element distinctness. SIAM Journal on Computing , 37:210-239, 2007. [ arXiv:quant-ph/0311001 ]",
      "url": "http://arxiv.org/abs/quant-ph/0311001"
    },
    {
      "n": 18,
      "cita": "Gilles Brassard, Peter Høyer, and Alain Tapp Quantum algorithm for the collision problem. ACM SIGACT News , 28:14-19, 1997. [ arXiv:quant-ph/9705002 ]",
      "url": "http://arxiv.org/abs/quant-ph/9705002"
    },
    {
      "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": 154,
      "cita": "Aleksandrs Belovs and Troy Lee Quantum algorithm for k-distinctness with prior knowledge on the input. arXiv:1108.3022 , 2011.",
      "url": "http://arxiv.org/abs/1108.3022"
    },
    {
      "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": 173,
      "cita": "Andrew Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez A time-efficient quantum walk for 3-distinctness using nested updates. arXiv:1302.7316 , 2013.",
      "url": "http://arxiv.org/abs/1302.7316"
    },
    {
      "n": 277,
      "cita": "Ashley Montanaro The quantum complexity of approximating the frequency moments arXiv:1505.00113 , 2015.",
      "url": "http://arxiv.org/abs/1505.00113"
    },
    {
      "n": 315,
      "cita": "Gilles Brassard, Peter Høyer, and Alain Tapp Quantum cryptanalysis of hash and claw-free functions In Proceedings of the 3rd Latin American symposium on Theoretical Informatics (LATIN'98) , pg. 163-169, 1998.",
      "url": null
    },
    {
      "n": 363,
      "cita": "Stacey Jeffery Frameworks for Quantum Algorithms PhD thesis, U. Waterloo, 2014.",
      "url": "http://uwspace.uwaterloo.ca/handle/10012/8710"
    },
    {
      "n": 364,
      "cita": "Seiichiro Tani An improved claw finding algorithm using quantum walk In Mathematical Foundations of Computer Science (MFCS) , pg. 536-547, 2007. [ arXiv:0708.2584 ]",
      "url": "https://arxiv.org/abs/0708.2584"
    },
    {
      "n": 365,
      "cita": "K. Iwama and A. Kawachi A new quantum claw-finding algorithm for three functions New Generation Computing , 21(4):319-327, 2003.",
      "url": null
    },
    {
      "n": 374,
      "cita": "Renato Portugal Element distinctness revisited arXiv:1711.11336 , 2017.",
      "url": "https://arxiv.org/abs/1711.11336"
    },
    {
      "n": 464,
      "cita": "Stacey Jeffery and Sebastian Zur Multidimensional quantum walks Proceedings of STOC23 , 1125-1130, 2023. [ arXiv:2208.13492 ]",
      "url": "https://arxiv.org/abs/2208.13492"
    },
    {
      "n": 535,
      "cita": "Xavier Bonnetain, André Chailloux, André Schrottenloher, and Yixin Shen Finding Many Collisions via Reusable Quantum Walks: Application to Lattice Sieving In Proceedings of Eurocrypt , pg. 221-251, 2022. [ arXiv:2205.14023 ]",
      "url": "https://arxiv.org/abs/2205.14023"
    }
  ],
  "n_referencias": 14,
  "remisiones": [
    {
      "ancla": "graph_collision",
      "url": "https://quantumalgorithmzoo.org/#graph_collision"
    }
  ],
  "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."
  }
}