{
  "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": "quantum-approximate-optimization",
  "nombre": "Quantum Approximate Optimization",
  "categoria": "Optimization, Numerics, and Machine Learning",
  "categoria_id": "ONML",
  "problema": "Buscar buenas soluciones aproximadas a problemas combinatorios con un circuito parametrizado corto. Es QAOA, y es la familia sobre la que descansa casi toda la promesa comercial de optimizacion cuantica.",
  "speedup_declarado": "Superpolynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#ONML",
  "implementaciones": [
    {
      "nombre": "Classiq",
      "url": "https://short.classiq.io/qaoa"
    },
    {
      "nombre": "Cirq",
      "url": "https://github.com/quantumlib/Cirq/blob/main/examples/qaoa.py"
    },
    {
      "nombre": "PennyLane",
      "url": "https://pennylane.ai/qml/demos/tutorial_qaoa_intro"
    },
    {
      "nombre": "Qrisp",
      "url": "https://qrisp.eu/reference/Algorithms/qaoa/QAOA.html#qaoa"
    }
  ],
  "referencias": [
    {
      "n": 242,
      "cita": "Edward Farhi, Jeffrey Goldstone, and Sam Gutmann A quantum approximate optimization algorithm arXiv:1411.4028 , 2014.",
      "url": "http://arxiv.org/abs/1411.4028"
    },
    {
      "n": 243,
      "cita": "Edward Farhi, Jeffrey Goldstone, and Sam Gutmann A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem arXiv:1412.6062 , 2014.",
      "url": "http://arxiv.org/abs/1412.6062"
    },
    {
      "n": 260,
      "cita": "Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright Beating the random assignment on constraint satisfaction problems of bounded degree arXiv:1505.03424 , 2015.",
      "url": "http://arxiv.org/abs/1505.03424"
    },
    {
      "n": 300,
      "cita": "Cedric Yen-Yu Lin and Yechao Zhu Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree arXiv:1601.01744 , 2016.",
      "url": "http://arxiv.org/abs/1601.01744"
    },
    {
      "n": 301,
      "cita": "Dave Wecker, Matthew B. Hastings, and Matthias Troyer Training a quantum optimizer arXiv:1605.05370 , 2016.",
      "url": "http://arxiv.org/abs/1605.05370"
    },
    {
      "n": 302,
      "cita": "Edward Farhi and Aram W. Harrow Quantum supremacy through the quantum approximate optimization algorithm arXiv:1602.07674 , 2016.",
      "url": "http://arxiv.org/abs/1602.07674"
    },
    {
      "n": 314,
      "cita": "Z-C Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon Optimizing variational quantum algorithms using Pontryagins's minimum principle arXiv:1607.06473 , 2016.",
      "url": "http://arxiv.org/abs/1607.06473"
    },
    {
      "n": 451,
      "cita": "R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J. Johansen, M. Matheny, T. Mengle, M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, and M. Pistoia Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem Science Advances 10(22):eadm6761, 2024. [ arXiv:2308.02342 ]",
      "url": "https://arxiv.org/abs/2308.02342"
    },
    {
      "n": 452,
      "cita": "Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou The Quantum Approximate Optimization Algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington-Kirkpatrick model Proceedings of TQC22 7:1-7:21, 2022. [ arXiv:2110.14206 ]",
      "url": "https://arxiv.org/abs/2110.14206"
    },
    {
      "n": 476,
      "cita": "Sami Boulebnane and Ashley Montanaro Solving boolean satisfiability problems with the quantum approximate optimization algorithm arXiv:2208.06909 , 2022.",
      "url": "https://arxiv.org/abs/2208.06909"
    },
    {
      "n": 531,
      "cita": "Edward Farhi, Sam Gutmann, Daniel Ranard, and Benjamin Villalonga Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA arXiv:2503.12789 , 2023.",
      "url": "https://arxiv.org/abs/2503.12789"
    },
    {
      "n": 532,
      "cita": "Sami Boulebnane, Abid Khan, Minzhao Liu, Jeffrey Larson, Dylan Herman, Ruslan Shaydulin, and Marco Pistoia Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case arXiv:2505.07929 , 2023.",
      "url": "https://arxiv.org/abs/2505.07929"
    }
  ],
  "n_referencias": 12,
  "remisiones": [],
  "evidencia_rosetta": {
    "medido": true,
    "recetas": [
      {
        "recipe_id": "RQ-0012",
        "nota": "Compresion de portafolio con restricciones (Finanzas)",
        "estado": "measuring"
      },
      {
        "recipe_id": "RQ-0019",
        "nota": "Ruteo de flota bajo incertidumbre (Mineria)",
        "estado": "in test"
      },
      {
        "recipe_id": "RQ-0033",
        "nota": "Expansion de red electrica bajo estres (Energia)",
        "estado": "measuring"
      }
    ],
    "donde": "https://rosettaquantum.com/v1/runs?recipe=RQ-0012"
  }
}