A Comparison Between Heuristic and Automatic Design in Variational Quantum Circuits for the MaxCut Problem Under Noise Effects
Emmanuel Isaac Juárez Caballero, Horacio Tapia‐McClung, Efrén Mezura‐Montes · Mathematical and Computational Applications · 2026
The selection of the right topology (ansatz) for a Variational Quantum Algorithm (VQA) is a complex task that usually involves deep knowledge of a particular problem. The importance of the selection is greater when we consider the current state of quantum hardware, particularly the noise associated with the complexity of Variational Quantum Circuits (VQCs) that implement VQAs. Here, a comparison is presented between two confronted approaches for solving the MaxCut problem: QAOA, which has a theoretical proof of convergence, and the automatic design proposal (QNAS), which relies on evolutionary algorithms (NSGA-II) to discover efficient circuits. The comparison was made across 490 graph instances from different graph topologies and sizes (n=4 to n=16), accounting for noise models such as depolarizing noise, gate errors, and readout noise. The results show that QAOA achieves an approximation ratio (rA) ≈1 on complete graphs at the cost of being almost 12 times more complex than QNAS in ideal conditions while approaching the random noise floor (rA≈0.5). QNAS was capable of finding circuits less complex while maintaining 69% of the fidelity at a cost of having an rA on the interval 0.7≤rA≤0.8. However, when the comparison is made across sparse graphs, performance is comparable, while QNAS is less complex.