Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

1. Problem Statement

The paper addresses the practical efficacy of Variational Quantum Algorithms (VQAs), specifically the Variational Quantum Eigensolver (VQE), for solving Combinatorial Optimization (CO) problems on current Noisy Intermediate-Scale Quantum (NISQ) hardware.

• Context: While VQAs are theoretically promising for CO, they often suffer from "barren plateaus" and poor local minima, requiring resources (samples/iterations) that scale superpolynomially with problem size.
• The Gap: Many existing benchmarks are "proof-of-principle" demonstrations that do not account for realistic resource constraints or compare VQAs against sufficiently strong classical baselines.
• Objective: To numerically investigate what the superpolynomial scaling of training resources implies in practice. The authors aim to determine the minimum problem size at which a shallow VQE can consistently outperform classical baselines (random sampling and greedy search) given a fixed computational budget.

2. Methodology

A. Benchmark Problem: Max-Cut

The authors use the Max-Cut problem on 3-regular graphs as the benchmark.

• Instance Generation: They generated 25 instances for each problem size $N \in \{11, 21, 31, 41, 51, 61\}$.
• Normalization: To ensure fair comparison across different graph scales, the objective function was normalized by the solution found by the Goemans-Williamson (GW) semidefinite programming algorithm (the best-known classical approximation).
• Optimal Solutions: Exact optimal solutions were obtained using the Gurobi solver to calculate the true approximation ratio.

B. Algorithms Compared

The study compares three algorithms based on the number of objective function evaluations ($N_{evals}$):

1. Variational Quantum Eigensolver (VQE):
   • Circuit: A shallow, hardware-efficient ansatz consisting of a single layer of parameterized $RY$ rotations followed by a "brick-wall" pattern of CNOT entangling gates.
   • Cost Function: Uses Conditional Value at Risk (CVaR) with $\gamma=0.1$ to focus on the tail of the distribution (high objective values) rather than the mean.
   • Optimizer: Gradient-free COBYLA algorithm.
   • Constraints: Limited to $N_{evals} = 10^6$ total evaluations ($N_{iter} \times N_{shots} = 1000 \times 1000$).
2. Sampling with Replacement:
   • A classical baseline that uniformly samples computational basis states randomly. This tests if the VQE is merely "guessing" better than random chance.
3. Greedy Algorithm:
   • A classical heuristic that starts from a specific state and iteratively flips bits to maximize the objective function until a local optimum is reached.
   • Crucial Control: The greedy algorithm is initialized with the same computational basis state generated by the VQE's initial parameters. This allows for a direct comparison of how well the VQE's "initial point" performs versus how well the VQE optimizes that point.

C. Performance Metrics

• Approximation Ratio ($\alpha$): The ratio of the found solution to the optimal solution.
• Success Probability: The probability of finding the exact optimal solution (relevant only for small $N$).
• Binned Statistics: Instead of just comparing means, the authors analyze the correlation of performance by instance. They group instances by the VQE's performance and check how the baselines perform on those same specific instances.

3. Key Results

A. Comparison with Random Sampling

• Small Problems ($N \le 21$): The VQE performs worse than random sampling. For $N=11$, the VQE's high approximation ratio is misleading because random sampling also finds near-optimal solutions due to the small solution space ($2^{11}$).
• Threshold: The VQE only begins to consistently outperform random sampling for problem sizes $N > 30$.
• Scaling: As $N$ increases, the advantage of VQE over sampling grows. At $N=61$, the VQE achieves an average approximation ratio advantage of $\approx 0.11$ over sampling, whereas sampling's performance degrades exponentially.

B. Comparison with Greedy Algorithm

• Early Convergence: The greedy algorithm converges very quickly to a local minimum, often outperforming the early iterations of the VQE.
• Crossover Point: The VQE eventually catches up and surpasses the greedy algorithm, but the number of iterations required increases with problem size (from $\approx 100$ iterations for $N=31$ to $\approx 600$ for $N=61$).
• Diminishing Returns: While the VQE beats the greedy algorithm for $N > 30$, the magnitude of the advantage decreases as problem size increases.
  • At $N=31$, VQE is better in $\approx 75\%$ of instances (avg. diff $\approx 0.025$).
  • At $N=61$, VQE is better in $\approx 60\%$ of instances (avg. diff $\approx 0.005$).
• Conclusion: For $N \le 21$, both VQE and greedy algorithms perform worse than simple random sampling.

C. Correlation Analysis (Instance Hardness)

• VQE vs. Sampling: There is a mild positive correlation. Instances that are "easy" for random sampling are also generally "easy" for VQE.
• VQE vs. Greedy: There is no correlation. The performance of the greedy algorithm is largely independent of the VQE's performance on a specific instance.
• Implication: This suggests that the mechanisms driving the success of VQE (quantum interference/entanglement) and the greedy algorithm (local gradient ascent) are fundamentally different. A "good" initial point for the greedy algorithm is not necessarily a "good" initial point for the VQE.

4. Key Contributions

1. Resource-Aware Benchmarking: The study moves beyond "proof-of-principle" by imposing a strict, realistic limit on computational resources ($10^6$ evaluations) and comparing VQAs against strong classical baselines (sampling and greedy search) under identical constraints.
2. Identification of the "Crossover" Regime: The authors identify that for shallow VQAs, there is a specific regime ($N \approx 30$) where quantum algorithms begin to offer a practical advantage over random sampling, but they struggle to beat optimized classical heuristics (greedy) significantly until much larger problem sizes.
3. Decoupling Initialization from Optimization: By forcing the greedy algorithm to start from the VQE's initial state, the paper demonstrates that the VQE's ability to find a good starting point is not the primary source of its advantage; rather, the advantage comes from the optimization process itself, which is distinct from local search.
4. Statistical Rigor: The use of binned statistics and Wilson score intervals provides a more nuanced view of algorithm performance than simple mean approximation ratios, highlighting the non-normal distribution of VQE results.

5. Significance and Outlook

• Realistic Expectations: The paper cautions that for small-to-medium instances ($N < 30$), current shallow VQAs offer no practical advantage over classical methods, including simple random sampling. Claims of quantum advantage in this regime may be artifacts of insufficient classical baselines.
• Path Forward: To demonstrate a meaningful advantage, future benchmarks must target larger problem sizes ($N > 30$) where the exponential scaling of the solution space suppresses classical random sampling.
• Algorithmic Development: The diminishing advantage of VQE over greedy algorithms as $N$ increases suggests that current shallow ansätze may not be sufficient for large-scale CO. More complex circuits or better initialization strategies (e.g., warm starts) are likely required.
• Extension to Physics: The authors suggest extending these benchmarks to physical problems (e.g., measuring observables) where classical baselines like Markov Chain Monte Carlo (MCMC) would be the appropriate comparison, rather than simple sampling.

In summary, the paper provides a rigorous, resource-constrained benchmark showing that while shallow VQAs can outperform random sampling for sufficiently large problems, they currently struggle to outperform classical greedy heuristics significantly, highlighting the need for more advanced algorithms and hardware to achieve practical quantum advantage in combinatorial optimization.