{
  "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": "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 daria ataque a isomorfismo de grafos y a reticulos, 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."
  }
}