Technical Summary: A Framework to Evaluate the Performance of Variational Quantum Algorithms

1. Problem Statement

Variational Quantum Algorithms (VQAs) are a leading approach for solving combinatorial optimization problems, specifically Quadratic Unconstrained Binary Optimization (QUBO), on Noisy Intermediate-Scale Quantum (NISQ) devices. However, benchmarking VQAs remains challenging due to their inherent stochastic nature and the lack of standardized performance criteria. Existing studies often report single-run metrics without explicitly accounting for the variability introduced by finite measurement shots and noisy cost evaluations. Consequently, there is no universally accepted criterion to classify VQAs based on their suitability for solving specific QUBO instances under resource constraints.

2. Methodology

The authors propose a general framework for evaluating VQAs applied to QUBO problems. The methodology is grounded in interpreting quantum circuits as probability distributions over the binary space and characterizing VQA performance through statistical measures derived from these distributions.

A. Theoretical Framework

The framework defines a VQA as a tuple $VQA := (U, [C, s, A])$, comprising an ansatz ($U$), a cost function ($C$), the number of shots ($s$), and a classical optimizer ($A$). The performance is visualized in a Quality Diagram ($D \subset \mathbb{R}^2$), where each point represents a VQA execution defined by:

1. Normalized Resource Consumption: The number of circuit evaluations ($n_{calls}$) relative to a maximum limit ($n_{max}$).
2. Success Probability: The probability of measuring the global minimum ($p_{min}$), transformed as $1 - p_{min}$.

The ideal solution corresponds to the point $(0,0)$, representing a single function call with a probability of 1 for finding the global minimum. Due to stochasticity, repeated runs generate a distribution of points ($\rho$) over $D$.

B. Three Core Metrics

The framework evaluates VQAs using three complementary metrics derived from the distribution $\rho$:

1. Feasibility ($F$): The a priori probability that the algorithm succeeds in finding a solution with $p_{min}$ above a predefined threshold ($p_{threshold}$). It is calculated as the integral of the distribution $\rho$ over the region where $p_{min} \geq p_{threshold}$.
2. Quality ($Q$): A scalar value quantifying the efficiency of the search process, balancing success probability against resource consumption. It is defined as the expected value of a quality function $q(n_{calls}, p_{min})$, which assigns zero quality if $p_{min} < p_{threshold}$ and otherwise calculates a weighted Euclidean distance from the ideal point $(0,0)$.
3. Reproducibility ($R$): A measure of the certainty of the results, formalized using Shannon entropy ($S[\rho]$). Reproducibility is defined as $R[\rho] = 1 - \frac{S[\rho]}{S_{max}}$, where a value of 1 indicates a fully concentrated distribution (high certainty) and 0 indicates a uniform spread (high uncertainty).

C. Selection Criterion

The framework establishes a decision process for algorithm selection based on thresholds $(F_0, Q_0, R_0)$. A VQA is considered a "well-suited solver" only if it sequentially satisfies:

1. $F[\rho] \geq F_0$
2. $Q[\rho] \geq Q_0$
3. $R[\rho] \geq R_0$

3. Experimental Results

As a proof of concept, the authors applied the framework to a 16-qubit random QUBO instance using simulation. They evaluated multiple VQA configurations varying the CVaR parameter ($\alpha \in \{0.15, 0.25, 0.50, 0.75, 1.00\}$) and the number of shots ($s \in \{1,000 \dots 100,000\}$), using the RealAmplitudes ansatz and the COBYLA optimizer. Each configuration was tested over 400 optimization runs.

Key Findings:

• Feasibility: Feasibility generally increased with both higher $\alpha$ values and higher shot counts ($s$), eventually reaching saturation. For instance, with $\alpha=1.00$, feasibility reached 0.95 at $s=60,000$.
• Quality: Similar to feasibility, quality improved with higher $\alpha$ and $s$. However, saturation was observed for most cases beyond $s=20,000$, with the exception of $\alpha=0.25$.
• Reproducibility: Unlike the other metrics, reproducibility was largely insensitive to changes in $s$ and $\alpha$. Lower values of $\alpha$ and $s$ occasionally yielded higher reproducibility, likely because the algorithm terminated early without exploring diverse solutions.
• Optimal Configurations: Based on the selection criteria ($F_0=0.70, Q_0=1.20, R_0=0.60$), the most suitable VQA configurations were identified as those with higher $\alpha$ (specifically 0.75 and 1.00) and higher shot counts (ranging from 10,000 to 100,000).

4. Key Contributions

• Unified Evaluation Framework: Introduces a structured methodology combining feasibility, quality, and reproducibility to address the gap in systematic VQA benchmarking.
• Stochastic Characterization: Moves beyond single-run metrics by treating VQA performance as a probability distribution, utilizing Shannon entropy to quantify reproducibility.
• Quality Diagram: Proposes a visual and mathematical tool to capture trade-offs between success probability and resource consumption.
• Decision Criterion: Provides a formal, threshold-based selection process for identifying optimal VQA configurations under resource constraints.

5. Significance and Claims

The authors claim that this work contributes a principled approach for comparing VQAs in the NISQ era. By explicitly accounting for the stochastic nature of variational algorithms, the framework enables more reliable algorithm selection in hybrid quantum-classical workflows.

The paper modestly frames its results as a proof of concept. It acknowledges limitations, noting that the analysis was restricted to a single QUBO instance, one ansatz, and one optimizer, all evaluated via simulation. The authors state that the framework provides a foundation for future research, including validation on real hardware, exploration of diverse ansätze, and the development of adaptive selection criteria for large-scale problems. They do not claim immediate superiority of specific algorithms over others in all contexts, but rather the utility of the framework in systematically identifying the best-performing algorithms for a given problem instance and resource budget.