PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm

Charles Moussa, Hao Wang, Thomas Bäck, Vedran Dunjko

arXiv:2202.09408v2quant-ph

TL;DR

Finding good QAOA parameters is difficult because instance-dependent concentration can create multiple useful parameter regions. The paper uses unsupervised clustering of angles and instance encodings, achieving comparable performance to extensive angle optimization while reducing circuit calls. Its scope is limited by weaker clustering behavior for dense QUBO instances, where supervised prediction may be more suitable.

  • Problem

    Instance-dependent QAOA parameter concentration can produce multiple concentration regions, making good angles difficult to select while limiting circuit calls.

    Source: §1 · p. 1

  • Method

    The paper compares clustering based on angle values, instance features, and variational graph autoencoder embeddings for setting QAOA parameters without optimization.

    Source: §1 · p. 1, §4.2 · p. 6

  • Results

    Less than 1−2% average approximation-ratio reduction is obtained with fewer than 10 circuit calls, while Recursive-QAOA reaches a 0.94 median approximation ratio comparable to extensive angle optimization.

    Source: §6 · p. 13

  • Takeaways & Limitations

    Instance encodings outperform angle values alone, and simpler instance features are recommended over VGAE embeddings because VGAE adds computation overhead.

    Source: §6 · p. 13

    Performance deterioration is more substantial for QUBO instances, where dense-instance cluster centers may not represent all assigned points and supervised methods may be preferable.

    Source: §4.3.1 · p. 7

Abstract

from arXiv · show

As combinatorial optimization is one of the main quantum computing applications, many methods based on parameterized quantum circuits are being developed. In general, a set of parameters are being tweaked to optimize a cost function out of the quantum circuit output. One of these algorithms, the Quantum Approximate Optimization Algorithm stands out as a promising approach to tackling combinatorial problems. However, finding the appropriate parameters is a difficult task. Although QAOA exhibits concentration properties, they can depend on instances characteristics that may not be easy to identify, but may nonetheless offer useful information to find good parameters. In this work, we study unsupervised Machine Learning approaches for setting these parameters without optimization. We perform clustering with the angle values but also instances encodings (using instance features or the output of a variational graph autoencoder), and compare different approaches. These angle-finding strategies can be used to reduce calls to quantum circuits when leveraging QAOA as a subroutine. We showcase them within Recursive-QAOA up to depth $3$ where the number of QAOA parameters used per iteration is limited to $3$, achieving a median approximation ratio of $0.94$ for MaxCut over $200$ Erd\H{o}s-R\'{e}nyi graphs. We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.

1. Introduction

QAOA parameter concentration can reduce optimization and circuit calls, but multiple instance-dependent concentration regions make parameter selection challenging. The paper proposes clustering-based unsupervised angle setting and evaluates instance encodings across MaxCut and QUBO problems.

Motivation

  • QAOA’s concentration property suggests reusing parameters across instances, potentially reducing classical optimization and quantum-device calls.Multiple concentration regions can arise when algorithms generate diverse instance distributions, making the balance between parameter quality and circuit cost important.Source: §1 · p. 1

Approach

  • The paper proposes unsupervised clustering to set QAOA angles without a classical optimization loop.The approaches use angle values, instance features, or variational graph autoencoder outputs as clustering inputs.Source: §1 · p. 1

Evaluation

  • The methods are compared on MaxCut over Erdős-Rényi graphs and Quadratic Unconstrained Binary Problems on random dense matrices.These two problem families provide different instance settings for evaluating angle-setting strategies.Source: §1 · pp. 1–2

Results

  • A less than 1−2% reduction in relative approximation ratio is achieved in cross-validation while reducing circuit calls.The result compares learned angle-setting strategies with extensively optimized angles.Source: §1 · p. 2
  • Instance encodings yield better angle-setting results than using angle values alone.The paper also applies these strategies in Recursive-QAOA up to depth 3, limiting each iteration to 3 QAOA circuit calls and achieving a 0.94 median approximation ratio.Source: §1 · p. 2

2. Background

QUBO and related combinatorial problems can be encoded into QAOA Hamiltonians whose layered circuits depend on tunable angles. Prior work exploits parameter concentration, while this paper instead uses clustering to propose multiple parameters without a subsequent classical optimization loop.

2.1. QUBO and QAOA

  • QUBO minimizes a quadratic binary objective and can express combinatorial problems including Quadratic Assignment, Constraint Satisfaction, Graph Coloring, and Maximum Cut.Its matrix formulation uses binary variables and a coefficient matrix Q.Source: §2.1 · p. 2
  • QAOA encodes the classical cost function in a cost Hamiltonian and combines it with a mixer Hamiltonian in a layered quantum circuit.The circuit starts in an equal superposition and applies p layers of parameterized operators.Source: §2.1 · p. 2
  • The QAOA circuit uses 2p angles, and classical optimization seeks the angle sequence minimizing the expected cost from measurement outcomes.At infinite depth, the output distribution converges to the global optimum.Source: §2.1 · p. 2
  • Parameter concentration allows good angles from a subset of instances to be reused, but finite-size problems can exhibit multiple concentration regions.Characterizing the relevant instance distribution may itself be difficult.Source: §2.1 · p. 2

2.2. Related Work

  • Prior strategies include density models, parameter fixing, graph-topology methods, and meta-learning for selecting or initializing QAOA angles.The cited meta-learning approach uses circuit metafeatures rather than instance-related features.Source: §2.2 · p. 3
  • This paper uses clustering to propose multiple parameter values for new circuits without a classical optimization loop.The design targets settings such as divide-and-conquer schemes and Recursive-QAOA where circuit calls are limited.Source: §2.2 · p. 3

3. Revisiting the concentration property

The paper revisits QAOA parameter concentration and uses exploratory analysis to motivate clustering-based angle recommendations for unseen instances. Across generated MaxCut and QUBO data, angle distributions show concentration and multiple clusters, while greater depth improves performance.

3.1. Data generation

  • The study generates 200 Erdős-Rényi MaxCut graphs and 100 QUBO instances, then obtains database angles using 1,000 BFGS runs for each problem at depths p = 1, 2, 3.The resulting angles are used to learn settings for unseen instances, but the approach is optimization-method-specific.Source: §3.1 · pp. 3–4

3.2. Exploratory Data Analysis

  • Angle densities are sharply concentrated yet multimodal, and t-SNE visualizations suggest multiple clusters across depths and problem types.The analysis notes that these angles may not be global or unique optima.Source: §3 · p. 3, §3.2 · p. 4
  • Cluster structure varies by problem setting: edge-creation probability does not visibly influence MaxCut clusters, while dense QUBOs show one major cluster and some secondary structure.Dense instances also show greater angle spread at depth 1, affecting the benchmarking of parameter-setting strategies.Source: §3.2 · p. 4

3. Revisiting the concentration property

  • Clustering angle values can identify candidate regions for good QAOA parameters, enabling recommendations for new instances with fewer quantum-circuit calls.The approach is intended for QAOA used as a subroutine, where runtime and circuit evaluations matter.Source: §3 · p. 3, §3.2 · p. 4

3.2. Exploratory Data Analysis

  • 0.802954, 0.827901, and 0.840478 are the MaxCut median ratios at p = 1, 2, and 3, while QUBO median optimality gaps are 0.457434, 0.335144, and 0.278984.The reported medians indicate improved performance with increased depth for both problem classes.Source: Figure 1 · p. 4, §3.2 · p. 4

4. Clustering-based (unsupervised) learning for angles

The paper uses clustering to recommend QAOA angles from angle values or instance encodings, avoiding a classical optimization loop. Instance encodings generally outperform angle-only clustering, while the methods reduce circuit calls and retain near-optimized performance.

4. Clustering-based (unsupervised) learning for angles

  • Angle distributions are concentrated and multimodal, motivating clustering several representative parameter settings for new QAOA instances.The approach clusters either optimal angle values directly or representations of problem instances, then tests the recommended settings on new circuits.Source: Figure 2 · p. 5, §4.1 · p. 5

4.2. Instance encodings

  • Instance encodings cluster graph features or VGAE embeddings, then select training instances nearest to cluster centers and reuse their optimal angles.VGAE produces fixed-dimensional graph embeddings for unweighted MaxCut instances; its use is therefore restricted to that setting.Source: §4.1 · p. 5, §4.2 · pp. 5–6

4.3.1. FROM ANGLE VALUES

  • Median aggregation improves over averaging, reaching median ratios of 0.950 for MaxCut and 0.941 for QUBOs versus 0.524 and 0.672 for averages.The paper attributes this difference to the median’s greater robustness to datasets with large variability.Source: §4.3.1 · p. 7
  • With 10 angle clusters, median ratios reach 0.998 for MaxCut and 0.985 for QUBOs, corresponding to less than 1–2% performance reduction versus optimal angles.Increasing cluster count improves median ratios, although performance deteriorates with depth, particularly for QUBOs.Source: §4.3.1 · p. 7, Figure 4 · p. 8
  • For MaxCut, replacing distant cluster centroids with the closest data points avoids about a 30% deterioration for 3 or 4 clusters at p = 3, whereas QUBOs favor centroids directly.The recommendation rule therefore differs between the two problem types.Source: §4.3.1 · p. 7

4.3.2. FROM INSTANCE ENCODINGS

  • The clustering approaches use at most 10 circuit calls, compared with BFGS medians of 56–320 calls on MaxCut and 44–252 on QUBO across depths.The methods avoid multiple restarts and substantially reduce calls relative to de novo optimization.Source: §4.3.2 · p. 8
  • Instance-feature clustering achieves median ratios of 0.998429 on Erdős–Rényi graphs and 0.982964 on dense QUBOs with 10 clusters.These results correspond to less than 1–2% reduction relative to optimal-angle expectations.Source: §4.3.2 · p. 8, Figure 5 · p. 9

4.4. Aggregating results

  • Instance-encoding clustering generally yields better angles than clustering angle values alone, especially with few clusters and increased depth.ECDF aggregation places instance-encoding results farther right, while feature-based methods improve mainly for 3–4 clusters; VGAE and instance features perform similarly on MaxCut.Source: §4.3.2 · p. 8, Figure 6 · p. 9, §4.4 · p. 10

5. Demonstration with RQAOA

The study applies three clustering strategies to restrict QAOA parameter trials within RQAOA, evaluating their approximation ratios against alternative angle-selection approaches. Across MaxCut and QUBO analyses, instance encodings generally outperform angle-only clustering, while RQAOA achieves near-optimized performance with few circuit calls.

RQAOA setup

  • RQAOA limited each iteration to three QAOA parameter recommendations while applying clustering to recursively shrinking MaxCut instances.The dense QUBO instances were excluded because their recursive intermediate subproblems were not represented in the database.Source: §5 · p. 10

RQAOA results

  • 0.94117 median approximation ratio was achieved in RQAOA using three clustering approaches, with optima found on 33 instances.The minimum ratio was 0.8367, and VGAE achieved the best-found ratio on 165 instances, compared with 118 for graph features and 88 for angle-value clustering.Source: §5 · p. 10

Clustering comparison

  • Instance features generally produced better ratios than angle values, with VGAE competitive on MaxCut and instance features stronger on QUBOs.The ECDF comparisons aggregate depths and cluster counts; lower curves indicate better results, and three-cluster results favor VGAE for MaxCut and instance features for QUBOs.Source: Figure 8 · p. 11, Figure 9 · p. 11
  • 0.981618 was the MaxCut median ratio using VGAE on the largest-node instances, compared with 0.976959 using instance features and 0.928519 using angle values.For QUBOs, the corresponding reported medians were 0.963677 for instance features, 0.936679 for angle-value clustering, and 0.926136 for the angle-value median.Source: Figure 10 · p. 12

Circuit-call efficiency

  • Clustering achieved performance similar to BFGS-optimized approaches while saving many circuit calls.Further optimization from the clustering recommendations did not improve the reported results relative to the optimized approaches.Source: §5 · pp. 12–13

6. Discussion

The discussion concludes that unsupervised clustering can set QAOA parameters with small circuit-call budgets while retaining performance across larger unseen instances. It recommends instance features over VGAE in practice because VGAE adds computation overhead, while identifying deeper circuits and dense QUBOs as important boundaries.

Performance and generalization

  • Less than 10 circuit calls yielded less than a 1–2% average approximation-ratio reduction from cross-validated best angles.The approaches retained performance for unseen problem instances larger than the training set when using instance features or VGAE.Source: §6 · p. 13

Strategy comparison

  • Instance encodings outperformed angle-only strategies, while VGAE remained competitive but added computation overhead.The discussion recommends simpler instance features for practical use despite VGAE’s competitiveness.Source: §6 · p. 13

Scope and scaling

  • Dense QUBOs showed less benefit from increasing cluster counts because their clusters were more spread out and less separable.For both problem types, deeper circuits require more clusters to retain good performance.Source: §6 · p. 13

RQAOA application

  • The RQAOA showcase achieved a 0.94 median approximation ratio with QAOA depth and parameter trials per iteration limited to 3.Further angle optimization did not improve the result, and performance was comparable to extensively optimized angles.Source: §6 · p. 13

Future work

  • The study leaves extension to other clustering methods, semi-supervised prediction, weighted-graph autoencoders, noisy hardware, and additional QAOA settings for future work.VGAE was not applied to dense QUBOs because the employed graph autoencoder was designed for unweighted graphs.Source: §6 · p. 13

Related papers

Loading 2202.09408v2…