On the role of overparametrization in Quantum Approximate Optimization

Daniil Rabinovich, Andrey Kardashin, Soumik Adhikary · 2025

Read On the role of overparametrization in Quantum Approximate Optimization by Daniil Rabinovich, Andrey Kardashin, Soumik Adhikary (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10086.txt.

Introduction

Daniil Rabinovich, Andrey Kardashin, and Soumik Adhikary ask how big a quantum circuit must be in this 2025 study. They study a leading quantum method that hunts for the best answer to hard choice problems. In machine learning, extra settings often help a model learn; the team tests whether the same holds for this quantum method.

They tried two problems: cutting a network into two parts, and a logic task with pairs of terms. For the cutting task, extra settings were both enough and, in most tests, needed to reach exact answers, even at twenty qubits. For the logic task, lean circuits solved most cases. That contrast is good news for today's noisy quantum machines, which handle small circuits best.

Catalog record

CREATORDaniil Rabinovich, Andrey Kardashin, Soumik Adhikary
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-10086

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the role of overparametrization in Quantum Approximate Optimization Daniil Rabinovich, Andrey Kardashin, Soumik Adhikary Abstract Variational quantum algorithms have emerged as a cornerstone of contemporary quantum algorithms research. While they have demonstrated considerable promise in solving problems of practical interest, efficiently determining the minimal quantum resources necessary to obtain such a solution remains an open question. In this work, inspired by concepts from classical machine learning, we investigate the impact of overparameterization on the performance of variational algorithms. Our study focuses on the quantum approximate optimization algorithm (QAOA)—a prominent variational quantum algorithm designed to solve combinatorial optimization problems. We investigate if circuit overparametrization is necessary and sufficient to solve such problems in QAOA, considering two representative problems — MAX-CUT and MAX-2-SAT. For MAX-CUT we observe that overparametriation is both sufficient and (statistically) necessary for attaining exact solutions, as confirmed numerically for up to 20 20 qubits. In fact, for MAX-CUT on 2-regular graphs we show the necessity to be exact, based on the analytically found optimal depth. In sharp contrast, for MAX-2-SAT, underparametrized circuits suffice to solve most instances. This result highlights the potential of QAOA in the underparametrized regime, supporting its utility for current noisy devices. I Introduction Noisy intermediate scale quantum (NISQ) devices are inherently limited by short coherence times, gate errors and other hardware imperfections Preskill2018 . As a result, these quantum processors can only execute short quantum circuits within a fixed error tolerance weidenfeller2022scaling ; ratcliffe2018scaling ; hegde2022toward ; mills2022two . This naturally limits the scale of problems that can be effectively implemented. Variational quantum computing is a novel approach designed to operate within these practical limitations by leveraging both classical and quantum computational resources cerezo2021variational ; Kishore_review ; mcclean2016theory_VQE . Variational quantum algorithms (VQAs) utilize a short-depth parametrized quantum circuit (called an ansatz) which can be executed within the coherence time and does not require error correction rabinovich2024robustness ; uvarov2024mitigating . In a process reminiscent of machine learning, VQAs find a solution to a given problem by iteratively optimizing the ansatz parameters to minimize a cost function; the optimization step is executed on a classical co-processor. The specific form of the cost function is dictated by the problem. For instance, in Variational quantum eigensolvers (VQEs), which aim to prepare the ground state of a problem Hamiltonian, the cost is defined as the expectation value of the problem Hamiltonian with respect to the ansatz state. While variational quantum algorithms (VQAs) have shown immense promise in addressing problems of practical significance farhi2014quantum ; peruzzo2014variational ; schuld2019quantum ; bravo2023variational ; adhikary2020supervised ; adhikary2021entanglement , determining the minimal resources required to solve a specific problem remains a challenge. In the context of VQAs these resources are typically quantified by the number of required parameterized gates. A similar question has been explored in the context of classical neural networks (CNNs), where the resources are typically quantified by the number of model parameters. It has been shown that overparametrized models — models with more parameters than needed to represent the training data — may partially address this issue by finding solutions that can reduce both training and generalization errors belkin_overparam ; allen2019learning . Motivated by the similarities that the VQAs and CNNs share, the impact of overparametrization on VQAs has been investigated, with promising results. It has been shown to improve the success probability and convergence rate larocca2023theory of VQE, help in avoiding spin-glass-like cost landscapes bukov2018reinforcement ; rabitz2004quantum and assist in mitigating the effect of noise fontana2021evaluating . More strikingly, in connection to the question of required quantum resources, overparametrization was shown to improve the probability of finding solutions to certain problems with specific problem dependent ansatz larocca2023theory . Despite showing promise in improving VQA performance, reaching the overparametrization regime can often require circuit depth that exceed the capabilities of NISQ devices larocca2022diagnosing ; larocca2023theory . Moreover, such large circuit depths may hinder trainability by inducing barren plateaus in the cost landscape. Motivated by this, we study if overparametrization is (i) sufficient and (ii) necessary for attaining solutions with a high probability for a given problem and a variational ansatz. We accomplish this by investigating the relationship between the circuit overparametrization depth and the optimal depth — depths required to achieve overparametrization and to find a solution to a given problem, respectively. In this work, we address this question with a focus on a special class of VQAs — Quantum Approximate Optimization Algorithm (QAOA). It is an algorithm designed to solve combinatorial optimization problems on near-term quantum processors, utilizing a problem dependent ansatz. With long enough circuits, QAOA is known to approximate the adiabatic evolution, thus guaranteeing success farhi2001quantum ; kadowaki1998quantum ; boixo2014evidence . However no such guarantee is known for intermediate depth QAOA sequences. Thus, establishing a relationship between the optimal QAOA depth and the overparametrization depth, may offer valuable insights into performance guarantees for QAOA in the intermediate depth regime. In this work we benchmark the performance of a QAOA sequence with respect to MAX-CUT problem on regular and random unweighted graphs as well as with random instances of the MAX-2-SAT problem. For the MAX-CUT problem on 2-regular graphs (a.k.a. rings of disagrees), we analytically establish that optimal QAOA depth scales as \lfloor\frac{n}{2}\rfloor for even number of qubits n . For odd n the same scaling is confirmed numerically. Importantly, we observe that overparametrization depth exactly coincides with the optimal circuit depth for up to 20 qubits. We numerically demonstrate that this agreement approximately holds for the MAX-CUT problem on unweighted regular graphs as well as unweighted random graphs: the solutions are likely to be found exactly at (or in a close vicinity of) the overparametrization depth. The case of MAX-2-SAT problem, however, demonstrates a different behavior. We find that the solutions to MAX-2-SAT instances could be obtained at depths much smaller than the overparametrized depth, with a high probability. These observations demonstrate that while overparametrization is sufficient to obtain solutions with a high probability, it may not be a necessary condition across all problems considered; while it is statistically necessary for MAX-CUT, it is not so in the case for MAX-2-SAT. II Preliminaries II.1 Quantum Approximate Optimization Algorithm The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, originally designed to approximately solve combinatorial optimization problems niu2019optimizing ; farhi2014quantum ; lloyd2018quantum ; morales2020universality ; Zhou2020 ; wang2020x ; Brady2021 ; Farhi2016 ; Akshay2020 ; Farhi2019a ; Wauters2020 ; Claes2021 ; Zhou . Instances of these problems are given as pseudo-Boolean functions \mathcal{C}:\{0,1\}^{\times n}\rightarrow\mathbb{R} . The objective of the algorithm is to approximate a bit string that minimizes \mathcal{C} . To accomplish this, \mathcal{C} is first encoded as a problem Hamiltonian H=\sum_{{\bf x}\in\{0,1\}^{\times n}}\mathcal{C}({\bf x}){|{\bf x}\rangle\!\langle{\bf x}|}. (1) The ground state of H encodes the solution to the problem; in other words QAOA searches for a solution \ket{g} such that {\langle g|H|g\rangle}=\min H=E_{g} . The algorithm utilizes a p -depth ansatz \ket{\psi_{p}(\bm{\gamma},\bm{\beta})}=\prod\limits_{k=1}^{p}e^{-i\beta_{k}H_{x}}e^{-i\gamma_{k}H}\ket{+}^{\otimes{n}}, (2) with real parameters \gamma_{k}\in[0,2\pi) , \beta_{k}\in[0,\pi) . Here H_{x}=\sum_{j=1}^{n}X_{j} is the standard one-body mixer Hamiltonian with Pauli matrix X_{j} applied to the j -th qubit, and \ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1}) . The cost function is given by the expectation of the problem Hamiltonian with respect to the ansatz state. The algorithm minimizes this cost function to

Read the complete text