Variational quantum optimization provides a useful setting for examining how circuit structure, parameterization, and trainability interact in practice. Objectives: Among the most promising variational quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA) depends critically on circuit architecture, but greater circuit complexity does not necessarily lead to easier optimization or better solutions. Using the Maximum Cut (MaxCut) problem on graphs as a controlled setting, we investigate how variational behavior changes as problem-specific QAOA structure is progressively removed, with particular attention to representational capacity, optimization geometry, and finite-budget trainability. Methods: We analytically characterize a graph-agnostic product-state formulation of MaxCut and derive exact equivalences, redundancies, and local-landscape properties. These results motivate a controlled comparison among separable product ansätze, a representative graphagnostic entangling circuit, and graph-structured QAOA at several depths, including a parameter-count-matched control. The numerical benchmark comprises 95 small unweighted graph instances optimized under a common objective-evaluation budget. Results: The product-state formulation preserves the exact discrete MaxCut optimum, while its strict local maxima correspond to classical cuts that are stable under singlevertex flips. Redundant phase parameters increase optimization effort without enlarging the objective-relevant family. Under the prescribed optimization budget, the productstate ansatz attains higher average solution quality than the tested QAOA depths while requiring substantially fewer objective evaluations. The graph-agnostic entangling comparator provides no consistent advantage over the separable baseline, and a simple classical local-search method remains highly competitive. Conclusion: In the regime considered here, objective-relevant parameterization and optimization geometry can be as important as circuit richness.
- Open Access
- Article
From Problem-Structured QAOA to Problem-Agnostic Variational MaxCut Solvers: Representation, Redundancy, and Optimization Landscapes
- Leonardo Lavagna *,
- Massimo Panella
Author Information
Received: 30 Aug 2026 | Revised: 18 Sep 2026 | Accepted: 08 Oct 2026 | Published: 13 Oct 2026
Abstract
Keywords
quantum approximate optimization algorithm | MaxCut | variational quantum algorithms | product-state ansatz
References
- 1.
McClean, J.R.; Romero, J.; Babbush, R.; et al. The Theory of Variational Hybrid Quantum-Classical Algorithms. New J. Phys. 2016, 18, 023023. https://doi.org/10.1088/1367-2630/18/2/023023.
- 2.
Cerezo, M.; Arrasmith, A.; Babbush, R.; et al. Variational quantum algorithms. Nat. Rev. Phys. 2021, 3, 625–644. https://doi.org/10.1038/s42254-021-00348-9.
- 3.
Wang, Z.; Huang, J.; Ye, R. A Review of Variational Quantum Algorithms: Insights into Fault-Tolerant Quantum Computing. arXiv 2026, arXiv:2604.07909.
- 4.
Farhi, E.; Goldstone, J.; Gutmann, S. A Quantum Approximate Optimization Algorithm. arXiv 2014, arXiv:1411.4028.
- 5.
Blekos, K.; Brand, D.; Ceschini, A.; et al. A Review on Quantum Approximate Optimization Algorithm and Its Variants. Phys. Rep. 2024, 1068, 1–66. https://doi.org/10.1016/j.physrep.2024.03.002.
- 6.
Korte, B.; Vygen, J. Combinatorial Optimization: Theory and Algorithms, 6th ed.; Springer: Berlin/Heidelberg, Germany, 2018.
- 7.
Wang, Z.; Hadfield, S.; Jiang, Z.; et al. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Phys. Rev. A 2018, 97, 022304. https://doi.org/10.1103/physreva.97.022304.
- 8.
Herrman, R.; Lotshaw, P.C.; Ostrowski, J.; et al. Multi-angle Quantum Approximate Optimization Algorithm. Sci. Rep. 2022, 12, 6781. https://doi.org/10.1038/s41598-022-10555-8.
- 9.
Chalupnik, M.; Melo, H.; Alexeev, Y. Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer. In Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE), Broomfield, CO, USA, 18–23 September 2022; pp. 97–103.
- 10.
Egger, D.J.; Mareček, J.; Woerner, S. Warm-starting Quantum Optimization. Quantum 2021, 5, 479. https://doi.org/10.22331/q-2021-06-17-479.
- 11.
Wurtz, J.; Love, P. Classically Optimal Variational Quantum Algorithms. IEEE Trans. Quantum Eng. 2021, 2, 3104107. https://doi.org/10.1109/tqe.2021.3122568.
- 12.
Rajakumar, J.; Golden, J.; Bärtschi, A.; et al. Trainability Barriers in Low-Depth QAOA Landscapes. In Proceedings of the CF ’24: 21st ACM International Conference on Computing Frontiers, Naples, Italy, 7–9 May 2024; pp. 199–206. https://doi.org/10.1145/3649153.3649204.
- 13.
Larocca, M.; Thanasilp, S.; Wang, S.; et al. Barren plateaus in variational quantum computing. Nat. Rev. Phys. 2025, 7, 174–189. https://doi.org/10.1038/s42254-025-00813-9.
- 14.
Mao, R.; Yuan, P.; Allcock, J.; et al. QAOA-MaxCut has barren plateaus for almost all graphs. arXiv 2025, arXiv:2512.24577.
- 15.
De Falco, F.; Lavagna, L.; Ceschini, A.; et al. Enhancing QAOA Ansatz via Multi-Parameterized Layer and Blockwise Optimization. In Proceedings of the ICASSP 2026—2026 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Barcelona, Spain, 3–8 May 2026. https://doi.org/10.1109/icassp55912.2026.11461345.
- 16.
Bauer, N.M.; Alam, R.; Siopsis, G.; et al. Combinatorial Optimization with Quantum Imaginary Time Evolution. Phys. Rev. A 2024, 109, 052430. https://doi.org/10.1103/physreva.109.052430.
- 17.
Rohe, T.; Baumann, M.; Harjes Ruiloba, F. Detrimental Agnostic Entanglement: The Case Against Hardware-Efficient Ansätze for Combinatorial Optimization. arXiv 2026, arXiv:2605.19827.
- 18.
Banerjee, D.; Mahapatra, S.; Chaudhury, K.N. Local-Minima-Preserving Continuous Relaxation of Ising Problems. In Proceedings of the International Conference on Machine Learning, Seoul, Republic of Korea, 6–11 July 2026.
- 19.
Zhou, L.; Wang, S.T.; Choi, S.; et al. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices. Phys. Rev. X 2020, 10, 021067. https://doi.org/10.1103/physrevx.10.021067.
- 20.
Sherali, H.D. Convex Envelopes of Multilinear Functions over a Unit Hypercube and over Special Discrete Sets. Acta Math. Vietnam. 1997, 22, 245–270.
- 21.
Fernández-Pendás, M.; Combarro, E.F.; Vallecorsa, S.; et al. A Study of the Performance of Classical Minimizers in the Quantum Approximate Optimization Algorithm. J. Comput. Appl. Math. 2022, 404, 113388. https://doi.org/10.1016/j.cam.2021.113388.
- 22.
Goemans, M.X.; Williamson, D.P. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 1995, 42, 1115–1145. https://doi.org/10.1145/227683.227684.
- 23.
Allcock, J.; Yuan, P.; Zhang, S. The Dynamical Lie Algebra of QAOA-MaxCut on the Complete Graph. arXiv 2026, arXiv:2607.00945.
- 24.
Akshay, V.; Rabinovich, D.; Campos, E.; et al. Parameter Concentrations in Quantum Approximate Optimization. Phys. Rev. A 2021, 104, L010401. https://doi.org/10.1103/physreva.104.l010401.
- 25.
Galda, A.; Gupta, E.; Falla, J.; et al. Similarity-Based Parameter Transferability in the Quantum Approximate Optimization Algorithm. Front. Quantum Sci. Technol. 2023, 2, 1200975. https://doi.org/10.3389/frqst.2023.1200975.
- 26.
Brahmandam, S.; Ramkumar, V. Dimensionality Reduction of QAOA Parameter Space with Kernel PCA for Max-Cut. arXiv 2026, arXiv:2606.23718.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Suite 4002 Level 4, 447 Collins Street, Melbourne, Victoria 3000, Australia
General Inquiries: info@sciltp.com