⚛️ quantum physics

Role of overparametrization in quantum approximate optimization

This paper investigates the role of overparameterization in the Quantum Approximate Optimization Algorithm (QAOA) and finds that while it is both necessary and sufficient for solving MAX-CUT problems, underparameterized circuits are often sufficient for MAX-2-SAT, suggesting QAOA's potential utility on current noisy quantum devices.

Original authors: Daniil Rabinovich, Andrey Kardashin, Soumik Adhikary

Published 2026-06-26

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniil Rabinovich, Andrey Kardashin, Soumik Adhikary

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Tuning a Radio in a Noisy Room

Imagine you are trying to tune an old-fashioned radio to find a specific song (the perfect solution to a math problem). The radio has many dials (parameters) that you can turn.

The Problem: You are in a very noisy room (this represents current quantum computers, which are imperfect and prone to errors). You can only turn the dials for a short amount of time before the battery dies or the noise drowns out the signal.
The Question: To find the song perfectly, do you need a radio with hundreds of dials (overparametrized), or will a radio with just a few dials (underparametrized) work just fine?

This paper investigates exactly that question for a specific type of quantum algorithm called QAOA (Quantum Approximate Optimization Algorithm). The researchers wanted to know: Is having "too many" dials necessary to solve these problems, or is it just a luxury?

The Two Types of Problems Tested

The researchers tested two different kinds of "songs" (math problems) to see how the number of dials affected the results:

MAX-CUT (The "Ring of Disagrees"): Imagine a group of friends sitting in a circle. Everyone wants to sit next to someone they disagree with. The goal is to arrange them so the maximum number of neighbors are enemies.
MAX-2-SAT: Imagine a logic puzzle where you have to turn on or off a series of switches to satisfy as many rules as possible (e.g., "Switch A must be on if Switch B is off").

The Findings: One Size Does Not Fit All

The researchers discovered that the answer depends entirely on which problem you are trying to solve.

1. The "Ring of Disagrees" (MAX-CUT)

The Analogy: Think of this problem like a complex lock that requires a very specific, long key to open.

What they found: For this specific problem, you absolutely need a radio with many dials.
The Result: The researchers proved mathematically that for a circle of $n$ people, you need a specific number of dials (roughly half the number of people) to guarantee a perfect solution.
The Surprise: They found that the "sweet spot" where the radio works perfectly is exactly the same point where the radio becomes "overparametrized" (has more dials than strictly necessary for basic physics).
Takeaway: For this problem, having extra dials isn't just helpful; it's necessary. If you don't have enough dials, you likely won't find the solution.

2. The Logic Puzzle (MAX-2-SAT)

The Analogy: Think of this problem like a simple maze. You don't need a giant map; a small sketch is enough to find the exit.

What they found: This is the opposite of the first problem. You do not need a radio with hundreds of dials.
The Result: Most of these logic puzzles could be solved perfectly using a radio with very few dials—far fewer than the "overparametrized" limit. In fact, the researchers found that for many instances, a tiny fraction of the available dials was enough to get the job done.
Takeaway: For this problem, overparametrization is not necessary. You can solve it with a much simpler, smaller machine.

Why Does This Matter?

The paper highlights a crucial insight for the future of quantum computing:

The "NISQ" Era: Current quantum computers are "Noisy Intermediate-Scale Quantum" (NISQ) devices. They are small, fragile, and can't run very long programs (circuits) without making mistakes.
The Good News: Because some problems (like MAX-2-SAT) can be solved with very few dials (short circuits), we might be able to solve them on today's noisy machines. We don't always need to wait for massive, perfect computers.
The Bad News: Other problems (like the specific MAX-CUT ring) might still require deep, complex circuits that current noisy machines can't handle yet.

Summary

The paper essentially says: "Don't assume you need a giant, complex machine for every job."

For some problems, you need a massive toolkit (overparametrization) to get the job done right.
For other problems, a simple pocket tool (underparametrization) is actually better and faster, especially when your hands are shaking (noisy hardware).

This helps scientists decide which problems are ready to be solved on today's quantum computers and which ones will have to wait for better hardware.

Technical Summary: Role of Overparametrization in Quantum Approximate Optimization

Problem Statement
Variational Quantum Algorithms (VQAs) are a leading approach for solving problems on Noisy Intermediate-Scale Quantum (NISQ) devices, which are constrained by short coherence times and gate errors. A critical open question in this field is determining the minimal quantum resources (specifically circuit depth) required to efficiently solve practical problems. While overparametrization—using a number of parameters exceeding a certain threshold—has been shown in classical machine learning and some quantum contexts to improve convergence and avoid barren plateaus, it often requires circuit depths exceeding NISQ capabilities. This work investigates whether overparametrization is both sufficient and necessary to obtain high-probability solutions for combinatorial optimization problems using the Quantum Approximate Optimization Algorithm (QAOA).

Methodology
The authors define overparametrization using the concept of Effective Quantum Dimension (EQD), which quantifies the expressivity of a variational circuit based on the rank of the Quantum Fisher Information (QFI) matrix. A circuit is considered overparametrized when increasing the number of parameters (depth) no longer increases the EQD.

The study focuses on two representative NP-hard combinatorial optimization problems:

MAX-CUT: Investigated on 2-regular graphs (rings of disagrees), $k$ -regular graphs, and random unweighted graphs.
MAX-2-SAT: Investigated on random instances with varying clause densities.

For each problem, the authors compare the overparametrization depth ( $p_c$ , where EQD saturates) against the optimal depth ( $p^*$ , the minimum depth required to achieve a solution within a specific energy error tolerance $\epsilon$ ). They employ numerical simulations with layerwise heuristic strategies and random parameter initializations to track energy errors and success probabilities across different circuit depths.

Key Contributions and Results

MAX-CUT on 2-Regular Graphs:
- The authors provide an analytical proof that for an even number of qubits $n$ , the optimal QAOA depth scales as $p^* = \lfloor n/2 \rfloor$ .
- Numerical results confirm that the overparametrization depth $p_c$ coincides exactly with this optimal depth ( $p_c = p^*$ ) for systems up to $n=20$ .
- Conclusion: For this specific class of problems, overparametrization is both sufficient and necessary to find solutions with high probability.
MAX-CUT on General Graphs (Regular and Random):
- Numerical analysis shows that for most instances, the optimal solution is found exactly at or in the immediate vicinity of the overparametrization depth.
- The success probability of finding a solution exhibits an abrupt increase when transitioning from the underparametrized to the overparametrized regime.
- Conclusion: Overparametrization is sufficient for high-probability success. While not strictly necessary for every single instance, it is statistically necessary for the dominant fraction of instances.
MAX-2-SAT:
- In sharp contrast to MAX-CUT, the majority of MAX-2-SAT instances are solved well within the underparametrized regime ( $p/p_c \ll 1$ ).
- For $n=7$ , approximately 85% of instances were solved with circuit depths as low as half the overparametrization depth.
- The optimal depth scales as $p^* \sim \sqrt{2^n}$ , whereas the overparametrization depth scales as $p_c \sim 2^n$ . Consequently, the ratio $p^*/p_c$ decreases exponentially with problem size.
- Conclusion: Overparametrization is not necessary for solving MAX-2-SAT instances; high success probabilities are achieved with significantly shallower circuits.

Significance and Claims
The paper claims that the relationship between overparametrization and optimal circuit depth is problem-dependent.

For MAX-CUT, overparametrization acts as a critical threshold; the depth required to saturate the circuit's expressivity (EQD) aligns with the depth required to solve the problem.
For MAX-2-SAT, the results highlight the potential of QAOA in the underparametrized regime. Since these problems can be solved with circuits much shallower than the overparametrization depth, QAOA may be more viable for current NISQ devices than previously suggested by studies focusing solely on overparametrized regimes.

The authors emphasize that while overparametrization guarantees convergence in certain theoretical frameworks, it is not a universal requirement for all combinatorial problems. This finding suggests that for specific problem classes like MAX-2-SAT, resource-efficient solutions can be found without the deep circuits that typically induce noise and trainability issues (such as barren plateaus) on near-term hardware. However, the authors also note that even in the underparametrized regime, trainability limitations like barren plateaus may still persist for large problem sizes.