PaperlayerView exact revision on arXiv

Source-linked AI summary

Predicting Resource Efficient Hamiltonian Decomposition for Continuous-Time Quantum Walk Simulations

Mostafa Atallah, Rebekah Herrman, Zain H. Saleem

arXiv:2608.20660v1quant-phcs.LG

TL;DR

Choosing between Pauli and matching Hamiltonian decompositions by directly compiling both circuits is expensive, so this paper learns to predict which yields fewer CX gates from inexpensive graph and decomposition features. Across models, the selector transfers from eight-vertex training graphs to larger held-out graphs, reaching MCC 0.785 at N = 8 and perfect agreement for N ≥64.

  • Problem

    Determining the cheaper decomposition requires synthesizing and transpiling both circuits, which can be prohibitively time-consuming for large graphs.

  • Method

    The study trains and evaluates machine-learning classifiers on all 11,117 connected eight-vertex graphs using topological properties and decomposition term counts.

  • Results

    The frozen selector reaches MCC 0.785 at N = 8 and perfect agreement for N ≥64 on balanced held-out larger graphs.

  • Takeaways & Limitations

    Decomposition choice is governed primarily by nPauli rather than conventional graph topology, with degree variance providing a useful complement.

  • Takeaways & Limitations

    Generalization beyond the two tested larger-graph datasets and beyond N = 256 remains untested, especially for graph families containing both classes.

Abstract

from arXiv · show

Simulating a continuous-time quantum walk (CTQW) on a graph in the circuit model of quantum computing requires decomposing its Hamiltonian into terms that can be Trotterized into hardware-native gates. We consider two such decompositions: the standard Pauli decomposition and the recently introduced matching decomposition. Prior work suggests that the matching decomposition uses fewer CX gates on sparse graphs, while the Pauli decomposition uses fewer on denser graphs. Since CX gates dominate error and runtime on current hardware, we train machine learning models to predict, for a given graph, which of the two decompositions produces the smaller CX gate count. We train and evaluate on the complete population of all 11,117 connected eight-vertex graphs from Brendan McKay's database, so the class balance and overlap are measured directly rather than estimated. We use twelve features: ten topological properties of the graph and two that count the terms the Pauli and matching decompositions produce (n_Pauli and n_match), both computable without transpiling the simulation circuit. Standard topological properties alone provide little predictive power. Instead, the dominant signal comes from n_Pauli, a property of the Hamiltonian decomposition rather than an intrinsic property of the graph; degree variance is the only other feature that carries signal. Across a range of models the Matthews correlation coefficient (MCC) falls in a narrow band, from 0.569 untuned to 0.593 after tuning, so no single architecture stands out. We adopt a single-hidden-layer neural network at MCC 0.593. Applied frozen to a held-out, class-balanced test set of larger graphs (up to 256 vertices) from structured and Erdos-Renyi families, the model transfers, with MCC rising from 0.785 at N=8 to 1 at N>=64.

I. INTRODUCTION

The paper predicts which Hamiltonian decomposition yields fewer CX gates for continuous-time quantum-walk simulations, avoiding costly synthesis and transpilation of both circuits. Its selector relies primarily on the Pauli term count and transfers from eight-vertex training graphs to larger graphs, reaching perfect agreement at N ≥64.

  • Background: Continuous-time quantum walks evolve under a graph-derived Hamiltonian and must implement e^−iHt when run on gate-based hardware.For the study, the Hamiltonian is the graph adjacency matrix, and vertices have sizes 2^n with n-bit labels.
  • Problem formulation: Because the cheaper decomposition varies by graph, the paper frames selection as supervised classification from inexpensive graph features before circuit construction.Matching is favored when edges cluster at a few Hamming distances, whereas Pauli is favored when distances are spread out, including dense or random graphs.
  • Contributions and findings: The study compiles all 11,117 connected eight-vertex graphs under both decompositions, establishing the class balance and class overlap exactly rather than by sampling.The labeled dataset records CX gate counts and circuit depth using IBM Qiskit at optimization level 3.
  • Contributions and findings: Among twelve features, Pauli term count provides the dominant predictive signal, while vertex-degree variance contributes secondarily.The decision is therefore governed mainly by a quantity exposed by the decomposition rather than by intrinsic graph topology.
  • Contributions and findings: The selector transfers from eight-vertex training graphs to larger graphs with increasing accuracy, reaching perfect agreement at N ≥64.This lets a compiler choose the lower-CX decomposition without constructing the more costly circuit.

II. PROBLEM FORMULATION

The problem formulation selects between Pauli and matching Hamiltonian decompositions using CX-gate count as the sole modeled cost. A binary classifier uses the signed CX-cost gap to label matching- versus Pauli-favorable graphs, excluding ties.

  • Cost function: CX count is the sole modeled cost because two-qubit gates dominate error and runtime, while circuit depth is recorded but left unmodeled.A multi-objective formulation is deferred to future work.
  • Selection criterion: The signed cost gap ΔCX(G) is positive exactly when matching decomposition requires fewer CX gates than Pauli decomposition.The gap compares CXmatch(G) and CXPauli(G) for the graph’s Trotterization circuits.
  • Classification target: The target is binary: y = 1 means use matching and y = 0 means use Pauli, with ties ΔCX = 0 excluded from training and evaluation.The model learns the decision surface separating matching-favorable from Pauli-favorable feature-space regions.

III. DATASET … C. The feature set

The study trains on the complete population of 11,117 connected eight-vertex graphs and evaluates only on a balanced held-out collection spanning 8–256 vertices. Its twelve inexpensive features combine ten topological descriptors with Pauli- and matching-decomposition term counts, while dataset construction and labeling costs limit validation scale.

  • A. The McKay population (primary): 418 graphs favor matching, 10,560 favor Pauli, and 139 tie; excluding ties leaves 10,978 modeling rows with roughly 25:1 Pauli-to-matching imbalance.Labels were generated with the code repository of [9].
  • B. Source families (held-out test): The companion datasets are used only as balanced held-out tests, with no training on them, and include deduplicated Erdős-Rényi graphs from N=8 through N=256.All datasets contain only connected graphs and are deduplicated by Weisfeiler-Leman hash before labeling or balancing.
  • B. Source families (held-out test): Validation stops at N=256 because labeling scales approximately as O(N^3.2), reaching projected runtimes of about 0.5 hours per graph at N=512 and 4 hours at N=1024.This labeling cost bounds the larger-graph validation, whereas feature extraction is substantially cheaper.
  • C. The feature set: Each graph receives twelve features: ten standard topological properties computed with NetworkX and two decomposition-derived term counts, nPauli and nmatch.The topological set includes degree statistics, degree variance, matching size, spectral gap, clustering, triangle count, and diameter.
  • C. The feature set: nPauli and nmatch count terms without building or transpiling Trotter circuits, serving as inexpensive surrogates for the true CX counts.nPauli uses Qiskit’s tensorized Pauli decomposition implementation [38], while nmatch uses the reference matching implementation [9].
  • C. The feature set: nPauli depends on the fixed binary vertex labeling, so it characterizes the labeled Hamiltonian rather than an invariant unlabeled graph property.A single fixed labeling is used for every graph, making nPauli well defined throughout the dataset.
  • C. The feature set: Computing all twelve features costs about O(N^1.5) per graph, far below the O(N^3.2) cost of obtaining true CX labels by building and transpiling both circuits.The matching count dominates feature extraction at larger graph sizes.

D. Split protocol

The complete eight-vertex McKay population was partitioned into disjoint, class-stratified subsets for training, validation, and testing, while larger structured and Erdős–Rényi families were held out in full.

  • D. Split protocol: The McKay population was split 64/16/20 into 7,025 training, 1,757 validation, and 2,196 test graphs, with class stratification and disjoint evaluation subsets.Results on the McKay population were averaged over five su…
  • D. Split protocol: Feature importance on the training population was measured by the mean predictive-performance drop after shuffling each feature across five seeds.This permutation-based analysis quantifies feature contributions without changing the split protocol.
  • D. Split protocol: Structured and Erdős–Rényi graph families were balanced within each vertex count and used in full as a held-out test set.Table II lists the datasets and this split.

IV. DATA ANALYSIS

Analysis of all 12 features shows that nPauli carries the dominant predictive signal, while degree variance is the strongest topological feature. Matching-wins are rare and dispersed among Pauli-wins in principal-component space, and nPauli is nearly uncorrelated with the other features.

  • Population balance: Only 418 graphs are matching-wins versus 10,560 Pauli-wins, producing an approximately 25:1 class imbalance.The labels define a matching-win as fewer compiled CX gates for matching than Pauli, and a Pauli-win otherwise.
  • Feature importance: nPauli has the greatest permutation importance at 0.575, nearly four times degree variance at 0.148, the strongest topological feature.All remaining features have substantially smaller importances, including nmatch at 0.019.
  • Feature-space structure: Matching-wins are dispersed among Pauli-wins in the first two principal components rather than occupying a distinct region.This projection does not by itself exclude a linear boundary in the full twelve-dimensional feature space.
  • Feature correlations: nPauli is nearly uncorrelated with the other features, with mean |ρ| ≈ 0.12, whereas topological features are strongly intercorrelated and nmatch behaves structurally.The topological features have mean pairwise |ρ| ≈ 0.51; nmatch has mean |ρ| ≈ 0.55 and correlates most strongly with maximum degree at 0.83.

V. MODEL AND EVALUATION PROTOCOL

This section presents the evaluation metrics and models used in the study’s evaluation protocol.

  • The section defines the evaluation metrics used for each model.
  • It also identifies the models included in the evaluation.
  • Together, these elements establish the study’s model-evaluation protocol.

A. Metrics

The study evaluates binary predictions with confusion-matrix counts, accuracy, MCC, ROC-AUC, and PR-AUC. MCC and PR-AUC are primary because severe class imbalance makes accuracy misleading, while precision and recall expose the tradeoff between detecting matching-wins and ensuring matching predictions are correct.

  • Metric definitions: The confusion matrix records true positives, false negatives, true negatives, and false positives with matching as the positive class.True matching rows and predicted matching columns determine whether each outcome is a matching-wins or Pauli-wins classification.
  • Metric choice: The evaluation reports accuracy, F1, MCC, ROC-AUC, and PR-AUC, combining threshold-fixed and threshold-independent measures.ROC-AUC and PR-AUC vary the decision threshold, whereas accuracy and MCC use fixed predictions.
  • Metric choice: MCC and PR-AUC are primary metrics because matching-wins are outnumbered roughly 25 to 1, making accuracy unreliable for minority-class detection,.A trivial always-Pauli classifier achieves about 96% accuracy despite failing to identify the rare matching-wins class.
  • Metric definitions: Precision and recall are examined together because increasing recall by predicting matching more often can reduce precision.Recall measures the fraction of matching-wins detected, while precision measures the fraction of matching predictions that are correct.

B. Models · VI. RESULTS · A. Comparison of models

The study compares twelve classifiers under a shared protocol on all twelve features, first with default settings and then after per-model tuning. Gradient boosting leads the untuned comparison at MCC 0.569, while the evaluation also motivates MCC and PR-AUC over accuracy for imbalanced outcomes.

  • B. Models: Twelve classifiers spanning different decision-boundary shapes are compared on the complete twelve-feature set rather than selecting one model in advance.The candidates include logistic regression, Gaussian naive Bayes, shallow decision trees, and k-nearest neighbors, among others.
  • B. Models: Each model is evaluated first with default settings and then with a per-model grid search over the McKay population and the same features.Reported values are means over five random train/test splits.
  • VI. RESULTS: The results comprise untuned full-feature evaluation, tuned-model selection, and frozen transfer evaluation on a balanced held-out set of larger graphs.The tuned model is a small artificial neural network and is evaluated without retraining in the final experiment.
  • A. Comparison of models: MCC 0.569 makes gradient boosting the best untuned model, ahead of logistic regression at MCC 0.554 on the full twelve-feature set.Gradient boosting also achieves precision 0.766, recall 0.445, and PR-AUC 0.636; logistic regression has precision 0.742, recall 0.436, and PR-AUC 0.653.
  • A. Comparison of models: Neural and tree-ensemble models follow the two leading untuned models closely, with MCC values between 0.506 and 0.515.Table III sorts the full-feature models by MCC.
  • A. Comparison of models: MCC and PR-AUC are preferred to accuracy because the data are imbalanced and models can achieve similar nonzero MCC through contrasting precision–recall trade-offs.The RBF-SVM has precision 0.96 but recall 0.183, whereas Gaussian naive Bayes has recall 0.329 with lower precision.

B. Hyperparameter tuning · C. Model behavior · D. Feature ablation

Hyperparameter tuning selected a compact ANN with mean MCC 0.593, while held-out behavior remained strong under class imbalance. Feature ablation showed that topological features alone fail, whereas nPauli provides the strongest predictive signal and supports a simpler threshold rule.

  • B. Hyperparameter tuning: The lowest-capacity ANN was preferred because larger networks added parameters without enough signal and instead memorized the training data.The selected model’s training and validation losses and MCC tracked together with a small, stable gap.
  • B. Hyperparameter tuning: MCC 0.558 for the random forest reflected recall 0.698 at precision 0.48, while SVM and logistic regression exceeded 0.9 recall with precision near 0.22.The ANN and tuned tree ensembles combined higher MCC with more balanced precision and recall.
  • C. Model behavior: 0.654 average precision on held-out test graphs exceeded the 0.038 random-guess baseline, while precision stayed above 0.8 at approximately 0.4 recall.The precision-recall curve summarizes performance under strong class imbalance, and test graphs were scored only after being held out from training.
  • D. Feature ablation: MCC 0.062 at recall 0.01 showed that the ten topological features alone could not identify graphs where matching uses fewer CX gates.The targeted ablations kept the training and evaluation protocol fixed while changing only the feature subset.
  • D. Feature ablation: nPauli was the single most useful feature but was insufficient alone, motivating combinations with decomposition counts and degree variance.The ablation compared topological features, individual and paired decomposition counts, nPauli with degree variance, and all twelve features.
  • B. Hyperparameter tuning: 0.593 mean MCC made the 32-node single-hidden-layer ANN the best tuned model, although the leading models were closely bunched.The ANN used tanh activation and ℓ2 penalty α = 10^-4.
  • D. Feature ablation: MCC 0.466 was achieved by a training-selected nPauli threshold rule on the N = 8 test split, below the tuned ANN’s result.The selected threshold was t = 11 on three splits and t = 12 on two, with the rule’s direction learned from training data.

E. Transfer to larger graphs · VII. DISCUSSION AND CONCLUSION

A frozen ANN trained on all connected eight-vertex graphs transfers to larger held-out graphs, reaching perfect agreement at N ≥ 64, but this strong transfer may partly reflect graph-family differences. The study concludes that nPauli, rather than conventional topology, primarily controls decomposition cost, while labeling remains expensive and generalization beyond N = 256 is unestablished.

  • E. Transfer to larger graphs: Transfer scores are qualified because ER graphs are almost entirely Pauli-wins while structured graphs are mostly matching-wins, making family identity correlated with the prediction.The held-out test composition therefore cannot distinguish universal learning from separation between the two graph families.
  • VII. DISCUSSION AND CONCLUSION: Training on all 11,117 connected eight-vertex graphs makes class balance and class overlap exact rather than estimated.The models were trained to predict which decomposition requires fewer CX gates for CTQW evolution.
  • VII. DISCUSSION AND CONCLUSION: The main signal is nPauli, a Hamiltonian-representation feature, while conventional graph topology contributes little; degree variance is the other informative feature.Gradient boosting reproduced the ranking, with nPauli at 0.547 and degree variance at 0.152, and all other features much smaller.
  • E. Transfer to larger graphs: MCC rises from 0.785 at N = 8 to perfect agreement for N ≥ 64 when the frozen ANN selects the cheaper decomposition on larger held-out graphs.The model was trained only on eight-vertex graphs and applied without retraining to the balanced held-out dataset.
  • VII. DISCUSSION AND CONCLUSION: The adopted single-hidden-layer ANN has 32 nodes and achieves MCC 0.593, while its decomposition-count features are cheaper to compute than the CX-based labels.Counting terms costs about O(N^1.5) per graph, versus O(N^3.2) for building and transpiling both circuits.
  • VII. DISCUSSION AND CONCLUSION: The exhaustive training population exists only at N = 8, and larger-graph validation uses two datasets, so broader generalization remains unresolved.Additional graph families containing both classes are needed to test whether the learned boundary is family-specific.
  • VII. DISCUSSION AND CONCLUSION: Labeling limits validation size: true CX counts scale as O(N^3.2), take about four hours per graph at N = 1024, and support no claim beyond N = 256.The cost model considers CX gate count alone, excluding other circuit properties.

REPRODUCIBILITY

Reported results are reproducible: analyses run from the released feature matrix, with values read from output files and seed means computed over five fixed seeds. Runtime, scaling, and cost measurements use a specified single-core hardware and software environment.

  • Reproducible analyses: All reported table values and analyses are generated by scripts over the released feature matrix, with values read from corresponding output files.This covers permutation importance, model comparisons, tuning sweeps, transfer tests, and multi-seed intervals.
  • Reproducible analyses: Means over seeds consistently use the same five fixed seeds.
  • Measurement environment: Measurements use one Intel Core i5-13420H core with 40 GB RAM, Windows 11, Python 3.10, Qiskit 2.4, scikit-learn 1.7, and NumPy 2.This environment supports the reported timings, feature and labeling costs, scaling laws, and larger-N labeling-cost projection.

APPENDIX A ADDITIONAL METRICS

Appendix A reports precision, recall, specificity, and negative predictive value (NPV) omitted from the corresponding main-text tables. Tables VIII–XI preserve the main-text row order and models, with specificity and NPV defined from confusion-matrix counts.

  • Additional metrics: Tables VIII–XI report the four metrics omitted from the corresponding main-text tables: precision, recall, specificity, and negative predictive value (NPV).The appendix presents these metrics for completeness.
  • Additional metrics: Specificity is Tn/(Tn+Fp), while NPV is Tn/(Tn+Fn), using the confusion-matrix counts from Section V.
  • Additional metrics: The appendix uses the same row order and models as the corresponding main-text tables.
Loading 2608.20660v1…