{
  "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": "polynomial-quantum-speedups-for-constraint-satisfaction-prob",
  "nombre": "Polynomial Quantum Speedups for Constraint Satisfaction Problems",
  "categoria": "Optimization, Numerics, and Machine Learning",
  "categoria_id": "ONML",
  "problema": "Resolver problemas de satisfaccion de restricciones (SAT y familia) con una mejora polinomica sobre el mejor backtracking clasico.",
  "speedup_declarado": "Polynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#ONML",
  "implementaciones": [
    {
      "nombre": "Classiq",
      "url": "https://short.classiq.io/grover"
    },
    {
      "nombre": "PennyLane",
      "url": "https://pennylane.ai/qml/demos/tutorial_QUBO"
    },
    {
      "nombre": "Qrisp (Quantum Backtracking)",
      "url": "https://qrisp.eu/reference/Algorithms/QuantumBacktrackingTree.html"
    }
  ],
  "referencias": [
    {
      "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": 264,
      "cita": "Ashley Montanaro Quantum walk speedup of backtracking algorithms arXiv:1509.02374 , 2015.",
      "url": "http://arxiv.org/abs/1509.02374"
    },
    {
      "n": 298,
      "cita": "Salvatore Mandra, Gian Giacomo Guerreschi, and Alan Aspuru-Guzik Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems arXiv:1512.00859 , 2015.",
      "url": "http://arxiv.org/abs/1512.00859"
    },
    {
      "n": 422,
      "cita": "Andris Ambainis and Martins Kokainis Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games Proceedings of STOC 2017 , pg. 989-1002 [ arXiv:1704.06774 ]",
      "url": "https://arxiv.org/abs/1704.06774"
    },
    {
      "n": 423,
      "cita": "Fernando G.S L. Brandão, Richard Kueng, Daniel Stilck França Faster quantum and classical SDP approximations for quadratic binary optimization arXiv:1909.04613",
      "url": "https://arxiv.org/abs/1909.04613"
    },
    {
      "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": 8,
  "remisiones": [
    {
      "ancla": "adiabatic",
      "url": "https://quantumalgorithmzoo.org/#adiabatic"
    }
  ],
  "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."
  }
}