{
  "total": 31,
  "devueltos": 31,
  "total_catalogo": 74,
  "filtro": {
    "categoria": "oracular",
    "q": null,
    "limit": 100
  },
  "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-09-09",
    "como_reconstruir": "Baja https://quantumalgorithmzoo.org/, recomputa su sha256 y corre scripts/build-quantum-catalog.mjs"
  },
  "items": [
    {
      "id": "searching",
      "nombre": "Searching",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Encontrar la aguja en un pajar sin estructura: buscar un elemento marcado entre N con solo un oráculo que responde sí/no. Es Grover.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [
        {
          "nombre": "Classiq",
          "url": "https://short.classiq.io/quantum_counting"
        },
        {
          "nombre": "Cirq",
          "url": "https://github.com/quantumlib/Cirq/blob/main/examples/grover.py"
        },
        {
          "nombre": "PennyLane",
          "url": "https://pennylane.ai/qml/demos/tutorial_grovers_algorithm"
        },
        {
          "nombre": "Cirq",
          "url": "https://github.com/quantumlib/Cirq/blob/main/examples/grover.py"
        },
        {
          "nombre": "Qrisp (Grover)",
          "url": "https://qrisp.eu/reference/Algorithms/Grover.html"
        },
        {
          "nombre": "Qrisp (Quantum Counting)",
          "url": "https://qrisp.eu/reference/Algorithms/quantum_counting.html"
        },
        {
          "nombre": "Qrisp (Amplitude Amplification)",
          "url": "https://qrisp.eu/reference/Primitives/amplitude_amplification.html"
        }
      ],
      "referencias": [
        {
          "n": 15,
          "cita": "M. Boyer, G. Brassard, P. Høyer, and A. Tapp Tight bounds on quantum searching. Fortschritte der Physik , 46:493-505, 1998.",
          "url": null
        },
        {
          "n": 16,
          "cita": "G. Brassard, P. Høyer, and A. Tapp Quantum counting. arXiv:quant-ph/9805082 , 1998.",
          "url": "http://arxiv.org/abs/quant-ph/9805082"
        },
        {
          "n": 17,
          "cita": "Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp Quantum amplitude amplification and estimation. In Samuel J. Lomonaco Jr. and Howard E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume , volume 305 of AMS Contemporary Mathematics Series . American Mathematical Society, 2002. [ arXiv:quant-ph/0005055 ]",
          "url": "http://arxiv.org/abs/quant-ph/0005055"
        },
        {
          "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": 48,
          "cita": "Lov K. Grover Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters , 79(2):325-328, 1997. [ arXiv:quant-ph/9605043 ]",
          "url": "http://arxiv.org/abs/quant-ph/9605043"
        },
        {
          "n": 73,
          "cita": "M. Mosca Quantum searching, counting, and amplitude amplification by eigenvector analysis. In R. Freivalds, editor, Proceedings of International Workshop on Randomized Algorithms , pages 90-100, 1998.",
          "url": null
        },
        {
          "n": 75,
          "cita": "Ashwin Nayak and Felix Wu The quantum query complexity of approximating the median and related statistics. In Proceedings of 31st ACM Symposium on the Theory of Computing , 1999. [ arXiv:quant-ph/9804066 ]",
          "url": "http://arxiv.org/abs/quant-ph/9804066"
        },
        {
          "n": 77,
          "cita": "Erich Novak Quantum complexity of integration. Journal of Complexity , 17:2-16, 2001. [ arXiv:quant-ph/0008124 ]",
          "url": "http://arxiv.org/abs/quant-ph/0008124"
        },
        {
          "n": 100,
          "cita": "Eli Biham, Ofer Biham, David Biron, Markus Grassl, and Daniel Lidar Grover's quantum search algorithm for an arbitrary initial amplitude distribution. Physical Review A , 60(4):2742, 1999. [ arXiv:quant-ph/9807027 and arXiv:quant-ph/0010077 ]",
          "url": "http://arxiv.org/abs/quant-ph/9807027"
        },
        {
          "n": 123,
          "cita": "Ashley Montanaro Quantum search with advice. In Proceedings of the 5th conference on Theory of quantum computation, communication, and cryptography (TQC 2010) [ arXiv:0908.3066 ]",
          "url": "http://arxiv.org/abs/0908.3066"
        },
        {
          "n": 133,
          "cita": "Andris Ambainis Quantum Search Algorithms. SIGACT News , 35 (2):22-35, 2004. [ arXiv:quant-ph/0504012 ]",
          "url": "http://arxiv.org/abs/quant-ph/0504012"
        },
        {
          "n": 134,
          "cita": "Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams Nested quantum search and NP-hard problems. Applicable Algebra in Engineering, Communication and Computing , 10 (4-5):311-338, 2000.",
          "url": null
        },
        {
          "n": 138,
          "cita": "Andris Ambainis Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arXiv:1010.4458 , 2010.",
          "url": "http://arxiv.org/abs/1010.4458"
        },
        {
          "n": 208,
          "cita": "Lov Grover Fixed-point quantum search. Phys. Rev. Lett. 95(15):150501, 2005. [ arXiv:quant-ph/0503205 ]",
          "url": "http://arxiv.org/abs/quant-ph/0503205"
        },
        {
          "n": 209,
          "cita": "Tathagat Tulsi, Lov Grover, and Apoorva Patel A new algorithm for fixed point quantum search. Quantum Information and Computation 6(6):483-494, 2005. [ arXiv:quant-ph/0505007 ]",
          "url": "http://arxiv.org/abs/quant-ph/0505007"
        },
        {
          "n": 216,
          "cita": "Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani Strengths and weaknesses of quantum computing SIAM J. Comput. 26(5):1524-1540, 1997 [ arXiv:quant-ph/9701001 ]",
          "url": "http://arxiv.org/abs/quant-ph/9701001"
        },
        {
          "n": 255,
          "cita": "L. A. B. Kowada, C. Lavor, R. Portugal, and C. M. H. de Figueiredo A new quantum algorithm for solving the minimum searching problem International Journal of Quantum Information, Vol. 6, No. 3, pg. 427-436 , 2008.",
          "url": null
        },
        {
          "n": 261,
          "cita": "David Cornwell Amplified Quantum Transforms arXiv:1406.0190 , 2015.",
          "url": "http://arxiv.org/abs/1406.0190"
        },
        {
          "n": 262,
          "cita": "T. Laarhoven, M. Mosca, and J. van de Pol Solving the shortest vector problem in lattices faster using quantum search Proceedings of PQCrypto13 , pp. 83-101, 2013. [ arXiv:1301.6176 ]",
          "url": "http://arxiv.org/abs/1301.6176"
        },
        {
          "n": 274,
          "cita": "Andrew Childs and Jeffrey Goldstone Spatial search by quantum walk Physical Review A , 70:022314, 2004. [ arXiv:quant-ph/0306054 ]",
          "url": "http://arxiv.org/abs/quant-ph/0306054"
        },
        {
          "n": 275,
          "cita": "Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, and Yasser Omar Spatial search by quantum walk is optimal for almost all graphs arXiv:1508.01327 , 2015.",
          "url": "http://arxiv.org/abs/1508.01327"
        },
        {
          "n": 303,
          "cita": "Thomas G. Wong Quantum walk search on Johnson graphs arXiv:1601.04212 , 2016.",
          "url": "http://arxiv.org/abs/1601.04212"
        },
        {
          "n": 304,
          "cita": "Jonatan Janmark, David A. Meyer, and Thomas G. Wong Global symmetry is unnecessary for fast quantum search Physical Review Letters 112:210502, 2014. [ arXiv:1403.2228 ]",
          "url": "http://arxiv.org/abs/1403.2228"
        },
        {
          "n": 305,
          "cita": "David A. Meyer and Thomas G. Wong Connectivity is a poor indicator of fast quantum search Physical Review Letters 114:110503, 2014. [ arXiv:1409.5876 ]",
          "url": "http://arxiv.org/abs/1409.5876"
        },
        {
          "n": 306,
          "cita": "Thomas G. Wong Spatial search by continuous-time quantum walk with multiple marked vertices Quantum Information Processing 15(4):1411-1443, 2016. [ arXiv:1501.07071 ]",
          "url": "http://arxiv.org/abs/1409.5876"
        },
        {
          "n": 330,
          "cita": "Peter Høyer and Mojtaba Komeili Efficient quantum walk on the grid with multiple marked elements Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) , 42, 2016. [ arXiv:1612.08958 ]",
          "url": "https://arxiv.org/abs/1612.08958"
        },
        {
          "n": 405,
          "cita": "Kun Zhang and Vladimir E. Korepin Low depth quantum search algorithm arXiv:1908.04171 , 2019.",
          "url": "https://arxiv.org/abs/1908.04171"
        },
        {
          "n": 433,
          "cita": "András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics Proceedings of STOC 2019 , pg. 193-204 [ arXiv:1806.01838 ]",
          "url": "https://arxiv.org/abs/1806.01838"
        },
        {
          "n": 465,
          "cita": "Robin Kothari and Ryan O'Donnell Mean estimation when you have the source code; or, quantum Monte Carlo methods Proceedings of SODA23 , 1186-1215, 2023. [ arXiv:2208.07544 ]",
          "url": "https://arxiv.org/abs/2208.07544"
        },
        {
          "n": 472,
          "cita": "Arjan Cornelissen, Yassine Hamoudi, Sofiene Jerbi Near-optimal quantum algorithms for multivariate mean estimation Proceedings of STOC22 , 33-43, 2022. [ arXiv:2111.09787 ]",
          "url": "https://arxiv.org/abs/2111.09787"
        },
        {
          "n": 492,
          "cita": "Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end Proceedings of STOC23 , 1131 - 1144, 2023. [ arXiv:2212.01513 ]",
          "url": "https://arxiv.org/abs/2212.01513"
        },
        {
          "n": 493,
          "cita": "M. B. Hastings A short path quantum algorithm for exact optimization Quantum , 2:78, 2018. [ arXiv:1802.10124 ]",
          "url": "https://arxiv.org/abs/1802.10124"
        }
      ],
      "n_referencias": 32,
      "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."
      }
    },
    {
      "id": "abelian-hidden-subgroup",
      "nombre": "Abelian Hidden Subgroup",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Hallar un subgrupo oculto de un grupo conmutativo consultando una función que es constante en cada coclase. Es el patrón común detrás de Shor: factorizar, logaritmo discreto y Pell se reducen todos a esto.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#abelian_HSP",
      "implementaciones": [
        {
          "nombre": "Classiq",
          "url": "https://short.classiq.io/simon"
        },
        {
          "nombre": "Cirq",
          "url": "https://github.com/quantumlib/Cirq/blob/main/examples/simon_algorithm.py"
        }
      ],
      "referencias": [
        {
          "n": 14,
          "cita": "D. Boneh and R. J. Lipton Quantum cryptanalysis of hidden linear functions. In Don Coppersmith, editor, CRYPTO '95 , Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.",
          "url": null
        },
        {
          "n": 30,
          "cita": "J. Niel de Beaudrap, Richard Cleve, and John Watrous Sharp quantum versus classical query complexity separations. Algorithmica , 34(4):449-461, 2002. [ arXiv:quant-ph/0011065v2 ]",
          "url": "http://arxiv.org/abs/quant-ph/0011065"
        },
        {
          "n": 76,
          "cita": "Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, Cambridge, UK, 2000.",
          "url": null
        },
        {
          "n": 108,
          "cita": "D. Simon On the Power of Quantum Computation. In Proceedings of the 35th Symposium on Foundations of Computer Science , pg. 116-123, 1994.",
          "url": null
        },
        {
          "n": 388,
          "cita": "Lisa Hales and Sean Hallgren An improved quantum Fourier transform algorithm and applications. In Proceedings of FOCS 2000 , pg. 515-525.",
          "url": null
        },
        {
          "n": 389,
          "cita": "Igor Shparlinski and Arne Winterhof Quantum period reconstruction of approximate sequences Information Processing Letters , 103:211-215, 2007.",
          "url": null
        }
      ],
      "n_referencias": 6,
      "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."
      }
    },
    {
      "id": "non-abelian-hidden-subgroup",
      "nombre": "Non-Abelian Hidden Subgroup",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "El mismo problema sobre grupos no conmutativos. Resolverlo en general daría ataque a isomorfismo de grafos y a retículos, y sigue abierto.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#nonabelian_HSP",
      "implementaciones": [],
      "referencias": [
        {
          "n": 9,
          "cita": "Dave Bacon, Andrew M. Childs, and Wim van Dam From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science , pages 469-478, 2005. [ arXiv:quant-ph/0504083 ]",
          "url": "http://arxiv.org/abs/quant-ph/0504083"
        },
        {
          "n": 22,
          "cita": "Dong Pyo Chi, Jeong San Kim, and Soojoon Lee Notes on the hidden subgroup problem on some semi-direct product groups. Phys. Lett. A 359(2):114-116, 2006. [ arXiv:quant-ph/0604172 ]",
          "url": "http://arxiv.org/abs/quant-ph/0604172"
        },
        {
          "n": 28,
          "cita": "Andrew M. Childs and Wim van Dam Quantum algorithm for a generalized hidden shift problem. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms , pages 1225-1232, 2007. [ arXiv:quant-ph/0507190 ]",
          "url": "http://arxiv.org/abs/quant-ph/0507190"
        },
        {
          "n": 37,
          "cita": "Mark Ettinger, Peter Høyer, and Emanuel Knill The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters , 91(1):43-48, 2004. [ arXiv:quant-ph/0401083 ]",
          "url": "http://arxiv.org/abs/quant-ph/0401083"
        },
        {
          "n": 43,
          "cita": "K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen Hidden translation and translating coset in quantum computing. SIAM Journal on Computing Vol. 43, pp. 1-24, 2014. Appeared earlier in Proceedings of the 35th ACM Symposium on Theory of Computing , pages 1-9, 2003. [ arXiv:quant-ph/0211091 ]",
          "url": "http://arxiv.org/abs/quant-ph/0211091"
        },
        {
          "n": 44,
          "cita": "D. Gavinsky Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian-groups. Quantum Information and Computation , 4:229-235, 2004.",
          "url": null
        },
        {
          "n": 51,
          "cita": "Sean Hallgren, Alexander Russell, and Amnon Ta-Shma Normal subgroup reconstruction and quantum computation using group representations. SIAM Journal on Computing , 32(4):916-934, 2003.",
          "url": null
        },
        {
          "n": 53,
          "cita": "Yoshifumi Inui and François Le Gall Efficient quantum algorithms for the hidden subgroup problem over a class of semi-direct product groups. Quantum Information and Computation , 7(5/6):559-570, 2007. [ arXiv:quant-ph/0412033 ]",
          "url": "http://arxiv.org/abs/quant-ph/0412033"
        },
        {
          "n": 55,
          "cita": "Gábor Ivanyos, Frédéric Magniez, and Miklos Santha Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures , pages 263-270, 2001. [ arXiv:quant-ph/0102014 ]",
          "url": "http://arxiv.org/abs/quant-ph/0102014"
        },
        {
          "n": 56,
          "cita": "Gábor Ivanyos, Luc Sanselme, and Miklos Santha An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups. In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science , 2007. [ arXiv:quant-ph/0701235 ]",
          "url": "http://arxiv.org/abs/quant-ph/0701235"
        },
        {
          "n": 57,
          "cita": "Gábor Ivanyos, Luc Sanselme, and Miklos Santha An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. In LATIN 2008: Theoretical Informatics , pg. 759-771, Springer (LNCS 4957). [ arXiv:0707.1260 ]",
          "url": "http://arxiv.org/abs/0707.1260"
        },
        {
          "n": 66,
          "cita": "Greg Kuperberg A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing , 35(1):170-188, 2005. [ arXiv:quant-ph/0302112 ]",
          "url": "http://arxiv.org/abs/quant-ph/0302112"
        },
        {
          "n": 69,
          "cita": "Chris Lomont The hidden subgroup problem - review and open problems. arXiv:quant-ph/0411037 , 2004.",
          "url": "http://arxiv.org/abs/quant-ph/0411037"
        },
        {
          "n": 71,
          "cita": "Carlos Magno, M. Cosme, and Renato Portugal Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups. arXiv:quant-ph/0703223 , 2007.",
          "url": "http://arxiv.org/abs/quant-ph/0703223"
        },
        {
          "n": 72,
          "cita": "Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman The power of basis selection in Fourier sampling: the hidden subgroup problem in affine groups. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms , pages 1113-1122, 2004. [ arXiv:quant-ph/0211124 ]",
          "url": "http://arxiv.org/abs/quant-ph/0211124"
        },
        {
          "n": 78,
          "cita": "Oded Regev Quantum computation and lattice problems. In Proceedings of the 43rd Symposium on Foundations of Computer Science , 2002. [ arXiv:cs/0304005 ]",
          "url": "http://arxiv.org/abs/cs/0304005"
        },
        {
          "n": 79,
          "cita": "Oded Regev A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv:quant-ph/0406151 , 2004.",
          "url": "http://arxiv.org/abs/quant-ph/0406151"
        },
        {
          "n": 81,
          "cita": "Martin Roetteler and Thomas Beth Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. arXiv:quant-ph/9812070 , 1998.",
          "url": "http://arxiv.org/abs/quant-ph/9812070"
        },
        {
          "n": 126,
          "cita": "Aaron Denney, Cristopher Moore, and Alex Russell Finding conjugate stabilizer subgroups in PSL(2;q) and related groups. Quantum Information and Computation 10(3):282-291, 2010. [ arXiv:0809.2445 ]",
          "url": "http://arxiv.org/abs/0809.2445"
        },
        {
          "n": 207,
          "cita": "Nolan Wallach A quantum polylog algorithm for non-normal maximal cyclic hidden subgroups in the affine group of a finite field. arXiv:1308.1415 , 2013.",
          "url": "http://arxiv.org/abs/1308.1415"
        },
        {
          "n": 218,
          "cita": "Greg Kuperberg Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem In Proceedings of TQC pg. 20-34, 2013 [ arXiv:1112.3333 ]",
          "url": "http://arxiv.org/abs/1112.3333"
        },
        {
          "n": 273,
          "cita": "Juan Bermejo-Vega and Kevin C. Zatloukal Abelian hypergroups and quantum computation arXiv:1509.05806 , 2015.",
          "url": "http://arxiv.org/abs/1509.05806"
        },
        {
          "n": 311,
          "cita": "Aram W. Harrow and Ashley Montanaro Sequential measurements, disturbance, and property testing arXiv:1607.03236 , 2016.",
          "url": "http://arxiv.org/abs/1607.03236"
        },
        {
          "n": 312,
          "cita": "Martin Roetteler Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups arXiv:1608.02005 , 2016.",
          "url": "http://arxiv.org/abs/1608.02005"
        }
      ],
      "n_referencias": 24,
      "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."
      }
    },
    {
      "id": "bernstein-vazirani",
      "nombre": "Bernstein-Vazirani",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Recuperar una cadena secreta oculta en una función lineal, consultándola lo menos posible.",
      "speedup_declarado": "Polynomial Directly, Superpolynomial Recursively",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [
        {
          "nombre": "Classiq",
          "url": "https://short.classiq.io/bernstein_vazirani"
        },
        {
          "nombre": "Cirq",
          "url": "https://github.com/quantumlib/Cirq/blob/main/examples/bernstein_vazirani.py"
        },
        {
          "nombre": "PennyLane",
          "url": "https://pennylane.ai/qml/demos/tutorial_qutrits_bernstein_vazirani"
        }
      ],
      "referencias": [
        {
          "n": 11,
          "cita": "Ethan Bernstein and Umesh Vazirani Quantum complexity theory. In Proceedings of the 25th ACM Symposium on the Theory of Computing , pages 11-20, 1993.",
          "url": null
        },
        {
          "n": 256,
          "cita": "Sean Hallgren and Aram Harrow Superpolynomial speedups based on almost any quantum circuit Proceedings of ICALP 2008 , pg. 782-795. [ arXiv:0805.0007 ]",
          "url": "http://arxiv.org/abs/0805.0007"
        },
        {
          "n": 257,
          "cita": "Fernando G.S.L. Brandao and Michal Horodecki Exponential quantum speed-ups are generic Quantum Information and Computation , Vol. 13, Pg. 0901, 2013 [ arXiv:1010.3654 ]",
          "url": "http://arxiv.org/abs/1010.3654"
        },
        {
          "n": 258,
          "cita": "Scott Aaronson and Andris Ambainis Forrelation: A problem that optimally separates quantum from classical computing. arXiv:1411.5729 , 2014.",
          "url": "http://arxiv.org/abs/1411.5729"
        },
        {
          "n": 270,
          "cita": "Scott Aaronson, Shalev Ben-David, and Robin Kothari Separations in query complexity using cheat sheets arXiv:1511.01937 , 2015.",
          "url": "http://arxiv.org/abs/1511.01937"
        }
      ],
      "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."
      }
    },
    {
      "id": "deutsch-jozsa",
      "nombre": "Deutsch-Jozsa",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Decidir si una función booleana es constante o balanceada con una sola consulta. Es el primer separador histórico entre cuántico y clásico.",
      "speedup_declarado": "Exponential over P, none over BPP",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [
        {
          "nombre": "Classiq",
          "url": "https://short.classiq.io/deutsch_josza"
        },
        {
          "nombre": "PennyLane",
          "url": "https://pennylane.ai/codebook/basic-quantum-algorithms/deutsch-jozsa"
        }
      ],
      "referencias": [
        {
          "n": 32,
          "cita": "David Deutsch Quantum theory, the Church-Turing principle, and the universal quantum computer. Proceedings of the Royal Society of London Series A , 400:97-117, 1985.",
          "url": null
        },
        {
          "n": 33,
          "cita": "David Deutsch and Richard Jozsa Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London Series A , 493:553-558, 1992.",
          "url": null
        },
        {
          "n": 259,
          "cita": "Z. Gedik Computational speedup with a single qutrit arXiv:1403.5861 , 2014.",
          "url": "http://arxiv.org/abs/1403.5861"
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "formula-evaluation",
      "nombre": "Formula Evaluation",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Evaluar el valor de una fórmula booleana (AND/OR/NOT) accediendo a sus entradas por oráculo.",
      "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."
      }
    },
    {
      "id": "hidden-shift",
      "nombre": "Hidden Shift",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Dadas dos funciones que difieren por un corrimiento desconocido, hallar ese corrimiento.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [
        {
          "nombre": "Classiq",
          "url": "https://short.classiq.io/hidden_shift"
        },
        {
          "nombre": "Cirq",
          "url": "https://github.com/quantumlib/Cirq/blob/main/examples/hidden_shift_algorithm.py"
        }
      ],
      "referencias": [
        {
          "n": 43,
          "cita": "K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen Hidden translation and translating coset in quantum computing. SIAM Journal on Computing Vol. 43, pp. 1-24, 2014. Appeared earlier in Proceedings of the 35th ACM Symposium on Theory of Computing , pages 1-9, 2003. [ arXiv:quant-ph/0211091 ]",
          "url": "http://arxiv.org/abs/quant-ph/0211091"
        },
        {
          "n": 66,
          "cita": "Greg Kuperberg A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing , 35(1):170-188, 2005. [ arXiv:quant-ph/0302112 ]",
          "url": "http://arxiv.org/abs/quant-ph/0302112"
        },
        {
          "n": 86,
          "cita": "Wim van Dam Quantum algorithms for weighing matrices and quadratic residues. Algorithmica , 34(4):413-428, 2002. [ arXiv:quant-ph/0008059 ]",
          "url": "http://arxiv.org/abs/quant-ph/0008059"
        },
        {
          "n": 88,
          "cita": "Wim van Dam and Sean Hallgren Efficient quantum algorithms for shifted quadratic character problems. arXiv:quant-ph/0011067 , 2000.",
          "url": "http://arxiv.org/abs/quant-ph/0011067"
        },
        {
          "n": 89,
          "cita": "Wim van Dam, Sean Hallgren, and Lawrence Ip Quantum algorithms for some hidden shift problems. SIAM Journal on Computing , 36(3):763-778, 2006. [ arXiv:quant-h/0211140 ]",
          "url": "http://arxiv.org/abs/quant-ph/0211140"
        },
        {
          "n": 105,
          "cita": "Martin Roetteler Quantum algorithms for highly non-linear Boolean functions. Proceedings of SODA 2010 [ arXiv:0811.3208 ]",
          "url": "http://arxiv.org/abs/0811.3208"
        },
        {
          "n": 130,
          "cita": "Martin Rötteler Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm. In Proceedings of MFCS 2009 , pg 663-674. [ arXiv:0911.4724 ]",
          "url": "http://arxiv.org/abs/0911.4724"
        },
        {
          "n": 142,
          "cita": "Dmitry Gavinsky, Martin Roetteler, and Jérémy Roland Quantum algorithm for the Boolean hidden shift problem. In Proceedings of the 17th annual international conference on Computing and combinatorics (COCOON '11) , 2011. [ arXiv:1103.3017 ]",
          "url": "http://arxiv.org/abs/1103.3017"
        },
        {
          "n": 143,
          "cita": "Mark Ettinger and Peter Høyer On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics , Vol. 25, No. 3, pg. 239-251, 2000. [ arXiv:quant-ph/9807029 ]",
          "url": "http://arxiv.org/abs/quant-ph/9807029"
        },
        {
          "n": 312,
          "cita": "Martin Roetteler Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups arXiv:1608.02005 , 2016.",
          "url": "http://arxiv.org/abs/1608.02005"
        },
        {
          "n": 407,
          "cita": "Gábor Ivanyos, Anupam Prakash, and Miklos Santha On learning linear functions from subset and its applications in quantum computing 26th Annual European Symposium on Algorithms (ESA 2018) , LIPIcs volume 112, 2018. [ arXiv:1806.09660 ]",
          "url": "https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16083"
        },
        {
          "n": 408,
          "cita": "Gábor Ivanyos On solving systems of random linear disequations Quantum Information and Computation , 8(6):579-594, 2008. [ arXiv:0704.2988 ]",
          "url": "https://arxiv.org/abs/0704.2988"
        }
      ],
      "n_referencias": 12,
      "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."
      }
    },
    {
      "id": "polynomial-interpolation",
      "nombre": "Polynomial interpolation",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Reconstruir los coeficientes de un polinomio consultándolo en puntos.",
      "speedup_declarado": "Varies",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 89,
          "cita": "Wim van Dam, Sean Hallgren, and Lawrence Ip Quantum algorithms for some hidden shift problems. SIAM Journal on Computing , 36(3):763-778, 2006. [ arXiv:quant-h/0211140 ]",
          "url": "http://arxiv.org/abs/quant-ph/0211140"
        },
        {
          "n": 360,
          "cita": "Dan Boneh and Mark Zhandry Quantum-secure message authentication codes In Proceedings of Eurocrypt , pg. 592-608, 2013.",
          "url": null
        },
        {
          "n": 361,
          "cita": "A. M. Childs, W. van Dam, S-H Hung, and I. E. Shparlinski Optimal quantum algorithm for polynomial interpolation In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP) , pg. 16:1-16:13, 2016. [ arXiv:1509.09271 ]",
          "url": "https://arxiv.org/abs/1509.09271"
        },
        {
          "n": 387,
          "cita": "Jianxin Chen, Andrew M. Childs, and Shih-Han Hung Quantum algorithm for multivariate polynomial interpolation Proceedings of the Royal Society A , 474:20170480, 2017. arXiv:1701.03990",
          "url": "http://arxiv.org/abs/1701.03990"
        },
        {
          "n": 390,
          "cita": "Alexander Russell and Igor E. Shparlinski Classical and quantum function reconstruction via character evaluation Journal of Complexity , 20:404-422, 2004.",
          "url": null
        },
        {
          "n": 391,
          "cita": "Sean Hallgren, Alexander Russell, and Igor Shparlinski Quantum noisy rational function reconstruction Proceedings of COCOON 2005 , pg. 420-429.",
          "url": null
        },
        {
          "n": 392,
          "cita": "G. Ivanyos, M. Karpinski, M. Santha, N. Saxena, and I. Shparlinski Polynomial interpolation and identity testing from high powers over finite fields Algorithmica , 80:560-575, 2017.",
          "url": null
        }
      ],
      "n_referencias": 7,
      "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."
      }
    },
    {
      "id": "pattern-matching",
      "nombre": "Pattern matching",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Localizar un patrón dentro de un texto largo.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 66,
          "cita": "Greg Kuperberg A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing , 35(1):170-188, 2005. [ arXiv:quant-ph/0302112 ]",
          "url": "http://arxiv.org/abs/quant-ph/0302112"
        },
        {
          "n": 215,
          "cita": "Ashley Montanaro Quantum pattern matching fast on average arXiv:1408.1816",
          "url": "http://arxiv.org/abs/1408.1816"
        },
        {
          "n": 216,
          "cita": "Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani Strengths and weaknesses of quantum computing SIAM J. Comput. 26(5):1524-1540, 1997 [ arXiv:quant-ph/9701001 ]",
          "url": "http://arxiv.org/abs/quant-ph/9701001"
        },
        {
          "n": 217,
          "cita": "H. Ramesh and V. Vinay String matching in \\( \\widetilde{O}(\\sqrt{n} + \\sqrt{m}) \\) quantum time Journal of Discrete Algorithms 1:103-110, 2003 [ arXiv:quant-ph/0011049 ]",
          "url": "http://arxiv.org/abs/quant-ph/0011049"
        },
        {
          "n": 435,
          "cita": "Pradeep Niroula and Yunseong Nam A quantum algorithm for string matching NPJ Quantum Information , 7:37, 2021.",
          "url": null
        }
      ],
      "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."
      }
    },
    {
      "id": "ordered-search",
      "nombre": "Ordered Search",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Buscar en una lista ordenada. El margen cuántico aquí es solo un factor constante, no un cambio de orden.",
      "speedup_declarado": "Constant factor",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 10,
          "cita": "Michael Ben-Or and Avinatan Hassidim Quantum search in an ordered list via adaptive learning. arXiv:quant-ph/0703231 , 2007.",
          "url": "http://arxiv.org/abs/quant-ph/0703231"
        },
        {
          "n": 24,
          "cita": "Andrew Childs and Troy Lee Optimal quantum adversary lower bounds for ordered search. Proceedings of ICALP 2008 [ arXiv:0708.3396 ]",
          "url": "http://arxiv.org/abs/0708.3396"
        },
        {
          "n": 39,
          "cita": "Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser Invariant quantum algorithms for insertion into an ordered list. arXiv:quant-ph/9901059 , 1999.",
          "url": "http://arxiv.org/abs/quant-ph/9901059"
        },
        {
          "n": 103,
          "cita": "A. M. Childs, A. J. Landahl, and P. A. Parrilo Quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A , 75 032335, 2007. [ arXiv:quant-ph/0608161 ]",
          "url": "http://arxiv.org/abs/quant-ph/0608161"
        },
        {
          "n": 219,
          "cita": "Peter Høyer, Jan Neerbek, and Yaoyun Shi Quantum complexities of ordered searching, sorting, and element distinctness In Proceedings of ICALP pg. 346-357, 2001 [ arXiv:quant-ph/0102078 ]",
          "url": "http://arxiv.org/abs/quant-ph/0102078"
        }
      ],
      "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."
      }
    },
    {
      "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."
      }
    },
    {
      "id": "graph-properties-in-the-adjacency-list-model",
      "nombre": "Graph Properties in the Adjacency List Model",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Lo mismo, pero accediendo al grafo por listas de vecinos: el modelo cambia el costo.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "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": 144,
          "cita": "Andris Ambainis, Andrew Childs, and Yi-Kai Liu Quantum property testing for bounded-degree graphs. In Proceedings of RANDOM '11 : Lecture Notes in Computer Science 6845, pp. 365-376, 2011. [ arXiv:1012.3174 ]",
          "url": "http://arxiv.org/abs/1012.3174"
        },
        {
          "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_referencias": 3,
      "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."
      }
    },
    {
      "id": "welded-tree",
      "nombre": "Welded Tree",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Atravesar dos árboles binarios unidos por las hojas. Es el ejemplo limpio de separación exponencial por caminata cuántica.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [
        {
          "nombre": "Classiq",
          "url": "https://short.classiq.io/glued_trees"
        }
      ],
      "referencias": [
        {
          "n": 26,
          "cita": "Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman Exponential algorithmic speedup by quantum walk. In Proceedings of the 35th ACM Symposium on Theory of Computing , pages 59-68, 2003. [ arXiv:quant-ph/0209131 ]",
          "url": "http://arxiv.org/abs/quant-ph/0209131"
        }
      ],
      "n_referencias": 1,
      "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."
      }
    },
    {
      "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."
      }
    },
    {
      "id": "graph-collision",
      "nombre": "Graph Collision",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Decidir si existe un par de vértices vecinos marcados con 1, consultando el etiquetado por oráculo.",
      "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."
      }
    },
    {
      "id": "matrix-commutativity",
      "nombre": "Matrix Commutativity",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Decidir si un conjunto de matrices conmuta entre sí.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 54,
          "cita": "Yuki Kelly Itakura Quantum algorithm for commutativity testing of a matrix set. Master's thesis, University of Waterloo, 2005. [ arXiv:quant-ph/0509206 ]",
          "url": "http://arxiv.org/abs/quant-ph/0509206"
        }
      ],
      "n_referencias": 1,
      "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."
      }
    },
    {
      "id": "group-commutativity",
      "nombre": "Group Commutativity",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Decidir si un grupo dado por sus generadores es conmutativo.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 139,
          "cita": "Frédéric Magniez and Ashwin Nayak Quantum complexity of testing group commutativity. In Proceedings of 32nd International Colloquium on Automata, Languages and Programming. LNCS 3580, pg. 1312-1324, 2005. [ arXiv:quant-ph/0506265 ]",
          "url": "http://arxiv.org/abs/quant-ph/0506265"
        }
      ],
      "n_referencias": 1,
      "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."
      }
    },
    {
      "id": "hidden-nonlinear-structures",
      "nombre": "Hidden Nonlinear Structures",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Hallar estructuras ocultas que no son subgrupos, sino objetos no lineales como esferas o conos.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 23,
          "cita": "A. M. Childs, L. J. Schulman, and U. V. Vazirani Quantum algorithms for hidden nonlinear structures. In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science , pages 395-404, 2007. [ arXiv:0705.2784 ]",
          "url": "http://arxiv.org/abs/0705.2784"
        },
        {
          "n": 31,
          "cita": "Thomas Decker, Jan Draisma, and Pawel Wocjan Quantum algorithm for identifying hidden polynomials. Quantum Information and Computation , 9(3):215-230, 2009. [ arXiv:0706.1219 ]",
          "url": "http://arxiv.org/abs/0706.1219"
        },
        {
          "n": 212,
          "cita": "Thomas Decker, Peter Høyer, Gabor Ivanyos, and Miklos Santha Polynomial time quantum algorithms for certain bivariate hidden polynomial problems arXiv:1305.1543",
          "url": "http://arxiv.org/abs/1305.1543"
        }
      ],
      "n_referencias": 3,
      "remisiones": [
        {
          "ancla": "nonabelian_HSP",
          "url": "https://quantumalgorithmzoo.org/#nonabelian_HSP"
        }
      ],
      "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."
      }
    },
    {
      "id": "center-of-radial-function",
      "nombre": "Center of Radial Function",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Localizar el centro de una función con simetría radial consultándola por puntos.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 110,
          "cita": "Yi-Kai Liu Quantum algorithms using the curvelet transform. Proceedings of STOC 2009 , pg. 391-400. [ arXiv:0810.4968 ]",
          "url": "http://arxiv.org/abs/0810.4968"
        }
      ],
      "n_referencias": 1,
      "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."
      }
    },
    {
      "id": "group-order-and-membership",
      "nombre": "Group Order and Membership",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Calcular el orden de un grupo y decidir si un elemento pertenece a él.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 74,
          "cita": "Michele Mosca Quantum Computer Algorithms . PhD thesis, University of Oxford, 1999.",
          "url": "http://www.iqc.ca/~mmosca/web/papers/moscathesis.pdf"
        },
        {
          "n": 91,
          "cita": "John Watrous Quantum algorithms for solvable groups. In Proceedings of the 33rd ACM Symposium on Theory of Computing , pages 60-67, 2001. [ arXiv:quant-ph/0011023 ]",
          "url": "http://arxiv.org/abs/quant-ph/0011023"
        },
        {
          "n": 124,
          "cita": "Laszlo Babai, Robert Beals, and Akos Seress Polynomial-time theory of matrix groups. In Proceedings of STOC 2009 , pg. 55-64.",
          "url": null
        }
      ],
      "n_referencias": 3,
      "remisiones": [
        {
          "ancla": "group_isomorphism",
          "url": "https://quantumalgorithmzoo.org/#group_isomorphism"
        }
      ],
      "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."
      }
    },
    {
      "id": "group-isomorphism",
      "nombre": "Group Isomorphism",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Decidir si dos grupos finitos dados por oráculo y generadores son el mismo grupo con otros nombres.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#group_isomorphism",
      "implementaciones": [],
      "referencias": [
        {
          "n": 127,
          "cita": "Kevin K. H. Cheung and Michele Mosca Decomposing finite Abelian groups. Quantum Information and Computation 1(2):26-32, 2001. [ arXiv:cs/0101004 ]",
          "url": "http://arxiv.org/abs/cs/0101004"
        },
        {
          "n": 128,
          "cita": "François Le Gall An efficient quantum algorithm for some instances of the group isomorphism problem. In Proceedings of STACS 2010 . [ arXiv:1001.0608 ]",
          "url": "http://arxiv.org/abs/1001.0608"
        },
        {
          "n": 202,
          "cita": "Kevin C. Zatloukal Classical and quantum algorithms for testing equivalence of group extensions. arXiv:1305.1327 , 2013.",
          "url": "http://arxiv.org/abs/1305.1327"
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "statistical-difference",
      "nombre": "Statistical Difference",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Estimar cuánto se diferencian dos distribuciones de probabilidad a las que solo se accede por muestreo.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 16,
          "cita": "G. Brassard, P. Høyer, and A. Tapp Quantum counting. arXiv:quant-ph/9805082 , 1998.",
          "url": "http://arxiv.org/abs/quant-ph/9805082"
        },
        {
          "n": 117,
          "cita": "Sergey Bravyi, Aram Harrow, and Avinatan Hassidim Quantum algorithms for testing properties of distributions. IEEE Transactions on Information Theory 57(6):3971-3981, 2011. [ arXiv:0907.3920 ]",
          "url": "http://arxiv.org/abs/0907.3920"
        },
        {
          "n": 265,
          "cita": "Ashley Montanaro Quantum speedup of Monte Carlo methods arXiv:1504.06987 , 2015.",
          "url": "http://arxiv.org/abs/1504.06987"
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "finite-rings-and-ideals",
      "nombre": "Finite Rings and Ideals",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Calcular estructura de anillos finitos y de sus ideales.",
      "speedup_declarado": "Superpolynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 118,
          "cita": "Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, and Joseph P. Brennan Efficient quantum processing of ideals in finite rings. arXiv:0908.0022 , 2009.",
          "url": "http://arxiv.org/abs/0908.0022"
        },
        {
          "n": 119,
          "cita": "V. Arvind, Bireswar Das, and Partha Mukhopadhyay The complexity of black-box ring problems. In Proceedings of COCCOON 2006 , pg 126-145.",
          "url": null
        },
        {
          "n": 120,
          "cita": "V. Arvind and Partha Mukhopadhyay Quantum query complexity of multilinear identity testing. In Proceedings of STACS 2009 , pg. 87-98.",
          "url": null
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "counterfeit-coins",
      "nombre": "Counterfeit Coins",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Identificar monedas falsas con la menor cantidad de pesajes: el problema clásico de acertijo, en versión de consultas.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 136,
          "cita": "Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Junichi Teruyama Quantum Counterfeit Coin Problems. In Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC2010) , LNCS 6506, pp.73-84, 2010. [ arXiv:1009.0416 ]",
          "url": "http://arxiv.org/abs/1009.0416"
        },
        {
          "n": 137,
          "cita": "Barbara Terhal and John Smolin Single quantum querying of a database. Physical Review A 58:1822, 1998. [ arXiv:quant-ph/9705041 ]",
          "url": "http://arxiv.org/abs/quant-ph/9705041"
        }
      ],
      "n_referencias": 2,
      "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."
      }
    },
    {
      "id": "matrix-rank",
      "nombre": "Matrix Rank",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Calcular el rango de una matriz accediendo a sus entradas por oráculo.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "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": 150,
          "cita": "Aleksandrs Belovs Span-program-based quantum algorithm for the rank problem. arXiv:1103.0842 , 2011.",
          "url": "http://arxiv.org/abs/1103.0842"
        },
        {
          "n": 151,
          "cita": "Sebastian Dörn and Thomas Thierauf The quantum query complexity of the determinant. Information Processing Letters Vol. 109, No. 6, pg. 305-328, 2009.",
          "url": null
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "matrix-multiplication-over-semirings",
      "nombre": "Matrix Multiplication over Semirings",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Multiplicar matrices sobre semianillos (por ejemplo min-plus), que es el núcleo de varios problemas de caminos mínimos.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 19,
          "cita": "Harry Buhrman and Robert Špalek Quantum verification of matrix products. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms , pages 880-889, 2006. [ arXiv:quant-ph/0409035 ]",
          "url": "http://arxiv.org/abs/quant-ph/0409035"
        },
        {
          "n": 155,
          "cita": "François Le Gall Improved output-sensitive quantum algorithms for Boolean matrix multiplication. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12) , 2012.",
          "url": null
        },
        {
          "n": 157,
          "cita": "Virginia Vassilevska Williams and Ryan Williams Subcubic equivalences between path, matrix, and triangle problems. In 51st IEEE Symposium on Foundations of Computer Science (FOCS '10) pg. 645 - 654, 2010.",
          "url": null
        },
        {
          "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": 206,
          "cita": "François Le Gall and Harumichi Nishimura Quantum algorithms for matrix products over semirings. arXiv:1310.3898 , 2013.",
          "url": "http://arxiv.org/abs/1310.3898"
        }
      ],
      "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."
      }
    },
    {
      "id": "subset-finding",
      "nombre": "Subset finding",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Hallar un subconjunto de k elementos que cumpla una propiedad dada.",
      "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": 162,
          "cita": "Andrew M. Childs and Jason M. Eisenberg Quantum algorithms for subset finding. Quantum Information and Computation 5(7):593-604, 2005. [ arXiv:quant-ph/0311038 ]",
          "url": "http://arxiv.org/abs/quant-ph/0311038"
        },
        {
          "n": 163,
          "cita": "Aleksandrs Belovs and Robert Špalek Adversary lower bound for the k-sum problem. In Proceedings of ITCS 2013 , pg. 323-328. [ arXiv:1206.6528 ]",
          "url": "http://arxiv.org/abs/1206.6528"
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "search-with-wildcards",
      "nombre": "Search with Wildcards",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Recuperar una cadena oculta cuando las consultas pueden dejar posiciones sin especificar.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 167,
          "cita": "Andris Ambainis and Ashley Montanaro Quantum algorithms for search with wildcards and combinatorial group testing. arXiv:1210.1148 , 2012.",
          "url": "http://arxiv.org/abs/1210.1148"
        }
      ],
      "n_referencias": 1,
      "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."
      }
    },
    {
      "id": "network-flows",
      "nombre": "Network flows",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Calcular el flujo máximo o el flujo de costo mínimo en una red con capacidades por arista.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 168,
          "cita": "Andris Ambainis and Robert Špalek Quantum algorithms for matching and network flows. Proceedings of STACS 2007 , pg. 172-183. [ arXiv:quant-ph/0508205 ]",
          "url": "http://arxiv.org/abs/quant-ph/0508205"
        }
      ],
      "n_referencias": 1,
      "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."
      }
    },
    {
      "id": "electrical-resistance",
      "nombre": "Electrical Resistance",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Calcular la resistencia efectiva entre dos nodos de un grafo con pesos leídos como resistencias.",
      "speedup_declarado": "Exponential",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 104,
          "cita": "Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd Quantum algorithm for solving linear systems of equations. Physical Review Letters 15(103):150502, 2009. [ arXiv:0811.3171 ]",
          "url": "http://arxiv.org/abs/0811.3171"
        },
        {
          "n": 210,
          "cita": "Guoming Wang Quantum algorithms for approximating the effective resistances of electrical networks. arXiv:1311.1851",
          "url": "http://arxiv.org/abs/1311.1851"
        },
        {
          "n": 280,
          "cita": "Tsuyoshi Ito and Stacey Jeffery Approximate span programs arXiv:1507.00432 , 2015.",
          "url": "http://arxiv.org/abs/1507.00432"
        }
      ],
      "n_referencias": 3,
      "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."
      }
    },
    {
      "id": "junta-testing-and-group-testing",
      "nombre": "Junta Testing and Group Testing",
      "categoria": "Oracular Algorithms",
      "categoria_id": "oracular",
      "problema": "Decidir si una función depende a lo más de k de sus n bits de entrada. Emparentado con el problema de testeo por grupos.",
      "speedup_declarado": "Polynomial",
      "declarado_por": "Quantum Algorithm Zoo",
      "fuente_url": "https://quantumalgorithmzoo.org/#oracular",
      "implementaciones": [],
      "referencias": [
        {
          "n": 167,
          "cita": "Andris Ambainis and Ashley Montanaro Quantum algorithms for search with wildcards and combinatorial group testing. arXiv:1210.1148 , 2012.",
          "url": "http://arxiv.org/abs/1210.1148"
        },
        {
          "n": 266,
          "cita": "Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf Efficient quantum algorithms for (gapped) group testing and junta testing arXiv:1507.03126 , 2015.",
          "url": "http://arxiv.org/abs/1507.03126"
        },
        {
          "n": 267,
          "cita": "A. Atici and R. A. Servedio Quantum algorithms for learning and testing juntas Quantum Information Processing , 6(5):323-348, 2007. [ arXiv:0707.3479 ]",
          "url": "http://arxiv.org/abs/0707.3479"
        },
        {
          "n": 268,
          "cita": "Aleksandrs Belovs Quantum algorithms for learning symmetric juntas via the adversary bound Computational Complexity , 24(2):255-293, 2015. (Also appears in proceedings of CCC'14). [ arXiv:1311.6777 ]",
          "url": "http://arxiv.org/abs/1311.6777"
        }
      ],
      "n_referencias": 4,
      "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."
      }
    }
  ]
}