CS Paper Radar

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

Mostafa Atallah, Rebekah Herrman, Zain H. Saleem

cs.LG quant-ph ·submitted 2026-08-21 01:34 UTC · v1

Abstract

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.

Comment
12 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Graph Convolutional Networks: Implementation and Trainability Analysis

cs.LG quant-ph ·2026-09-17 ·Paul San Sebastian Sein, Theodor Iosif, Tilen G. Limbäck-Stokin, Kin Ian Lo, Yidong Liao
benchmark similarity 0.71
Abstract

Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data, but training and inference on large graphs are often bottlenecked by memory constraints and sparse linear-algebra workloads. Quantum computing offers an alternative set of primitives that may improve scalability for graph learning. Building on the quantum graph neural network (QGNN) framework of Liao \textit{et al.}, this work implements two representative architectures --- the Simplified Graph Convolution (SGC) and Linear Graph Convolution (LGC) models --- and evaluates them on open benchmark graph datasets and semi-supervised learning tasks using quantum simulation. We compare predictive performance and optimization behavior against classical baselines, showing that the quantum models achieve competitive performance with fewer parameters. Finally, we present a cost gradient analysis that identifies the tasks for which the models showcased are trainable. This is followed by a classical simulability study to find regimes in which the proposed circuits remain robust during training.

0.34

Quantum Graph Neural Networks: Architectures, Trainability, and Applications

cs.LG ·2026-11-13 ·Zeinab Sharifi, Hossein Shirazi
survey similarity 0.69
Abstract

Quantum graph neural networks (QGNNs) apply parametrized quantum circuits to graph-structured data, with the aim of overcoming limits of classical graph neural networks in scalability, expressivity, and long-range information flow. Since the first Hamiltonian-based model in 2019, the field has produced many architectures, applications, and claims, but the evidence behind them has not been assessed systematically. This survey introduces a unified formalism that describes every QGNN as an encoder, a graph-conditioned circuit, observables, and an optional classical head, together with a circuit-level condition for permutation equivariance and a resource model for comparing costs. We organize the literature into five architecture families (convolutional, equivariant, message-passing and recurrent, Hamiltonian, and hybrid) and compare them by qubit cost, symmetry, scalability, and evidence. We then review symmetry and geometric inductive biases (permutation, rotation, and Lorentz), the results on expressivity, trainability, noise, and scalability, and applications in high-energy physics, chemistry, finance, healthcare, earth observation, and transportation. An audit of datasets and evaluation practices leads to a minimum reporting protocol. Our main finding is that the design space is rich and symmetry is the best-supported inductive bias, whereas the evidence remains thin: results are mostly simulated, on small graphs, at parity with classical models or with fewer parameters, and no advantage has yet been established on tasks over classical graph data. We identify five open challenges and a research agenda covering provable advantage, equivariant and geometric designs, fault-tolerant implementations, and shared benchmarks. The coverage extends through 2026 and emphasizes recent work.

0.16

Continuous-Time Quantum Walks based Graph Neural Network

cs.AI ·2026-08-21 ·Yuliang Zhan, Zefeng Gao, Jian Li, Yang Liu, Hao sun
top venue similarity 0.69
Abstract

Graph Neural Networks (GNNs) are widely used on graph-structured data, but most suffer from two key weaknesses. First, message passing behaves as a low-pass filter under the homophily assumption, leading to poor performance on heterophilic graphs. Second, stacking layers drives node features toward constants, causing over-smoothing. Existing methods usually address these issues separately, while the few joint solutions rely largely on empirical heuristics, and many over-smoothing remedies sacrifice model expressiveness. We propose \textbf{CTQW-GNN}, a GNN based on Continuous-Time Quantum Walks (CTQW), to address both issues with theoretical justification. Its design exploits two properties of the CTQW propagator $e^{-\mathrm{i}Ht}$. First, it is unitary and has eigenvalues on the unit circle, so no frequency component is damped, counteracting the low-pass bias. Second, unitarity preserves feature norms and prevents the Dirichlet energy from decaying exponentially with depth, thereby mitigating over-smoothing. CTQW-GNN combines three complementary aggregation modules. \textit{CTQW-based Aggregation} evolves node features through the unitary propagator, preserving mid- and high-frequency signals for heterophilic graphs while preventing Dirichlet-energy collapse. \textit{CTQW-Attention Aggregation} constructs a multi-hop neighbor graph from CTQW amplitudes and applies attention over it, enabling access to distant homophilic nodes missed by single-hop aggregation. \textit{LF Aggregation} uses a standard low-pass GAT branch to retain strong performance on homophilic graphs, where pure CTQW aggregation can be suboptimal. We further provide a spectral-gap analysis explaining energy preservation and a Lieb--Robinson-type bound that gives a principled rule for selecting the walk time $t$.

0.36

Hidden Circuits and Exact Counting in Ordered Graphs

cs.CC cs.DS ·2026-09-16 ·Chenghua Liu, Boning Meng
theory similarity 0.67
Abstract

We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and Müller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and Müller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and Müller's diagram (SIDMA 2019).

0.21

Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation

cs.ET quant-ph ·2026-09-08 ·Cesar Augusto do Amaral, Nicolás Legnazzi, Marcos Vinicius Reballo, Marcus Ritt, Alexsandro Santos da Rosa Júnior +1 more
similarity 0.66
Abstract

We introduce a sparse Walsh-Pauli correlation encoding for MaxCut, in which graph variables are represented by diagonal Pauli-string expectation values computed classically as normalized XOR autocorrelations of Walsh coefficients. The complete Walsh basis can reproduce the diagonal correlators of arbitrary quantum states, while a structured sparse support reduces the number of trainable coefficients to $m+1$ for $m$ graph variables. We evaluate the method on $1{,}400$ held-out random graphs with up to $7{,}000$ vertices, obtaining empirical approximation ratios near $0.98$ relative to MQLib heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of $0.9828$, $0.9926$, $0.9781$, and $0.9369$, respectively, with $80.4\%$-$89.3\%$ fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above $0.99994$ and preserve all correlator signs. Separately, a seven-qubit experiment on a $15$-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of $0.927\pm0.049$ relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.

0.25

Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling

cs.ET quant-phmath.OC ·2026-10-07 ·Amana Liaqat, Ahmed Darwish, Stephen DiAdamo, Dan Holme, Kieran McDowall +4 more
benchmark similarity 0.64
Abstract

The Minimum Birkhoff Decomposition (MBD) seeks a sparse weighted sum of matchings and is a challenging optimization problem with applications in network scheduling and energy trading. We scale a quantum-assisted decomposition method by combining single-layer QAOA sampling with Extended Fully-Corrective Frank-Wolfe (E-FCFW) optimization, spectral graph partitioning, and greedy feasibility repair. We demonstrate the pipeline on the 1,354-node PEGASE bus test case (representing a 1,354-bus transmission grid with 1,710 transmission lines), whose 1,710 edges define a native 1,710-variable matching optimization problem requiring 1,710 qubits in the unpartitioned encoding. Partitioning enables distributed execution on IBM superconducting quantum processors. The best reported hardware result uses a 50-qubit partition bound, while reducing partitions to 20 qubits degrades convergence in the partition-size comparison. Larger partitions are more demanding for matrix product state (MPS) simulation, and bond-dimension tests show that truncating quantum correlations reduces candidate quality. The results therefore motivate retaining a substantive quantum sampling task within each partition as the overall problem scales. On the PEGASE-1354 benchmark, repaired QAOA samples achieve lower residual decomposition error than both simulated annealing and uniform random sampling baselines, while spatial circuit packing reduces hardware execution time by approximately a factor of three. These results demonstrate that combining spectral partitioning, spatial circuit packing, and classical feasibility repair provides an executable path for deploying gate-based quantum sampling on thousand-variable constrained optimization problems on current hardware.

0.07

Fully quantum training of parametric circuits with Quantum Hamiltonian Descent

cs.LG quant-ph ·2026-10-23 ·Marco Burato, Leonardo Banchi
benchmarktheory similarity 0.64
Abstract

Parametric quantum circuits are usually trained by classical, local optimizers, which use the quantum computer only to evaluate the cost function, or its gradient, one point at a time. Quantum Hamiltonian Descent (QHD) takes a different route: in this quantum algorithm for continuous optimization, the parameters become the position of a quantum particle, with the cost function as its potential, and two time schedules control kinetic and potential energy so that the wavefunction explores the whole landscape and tunnels towards the global minimum. QHD, however, assumes a classically computable cost function, and its digital implementation is poorly understood: standard error bounds grow exponentially with the number of qubits per parameter, and the schedules are borrowed from classical optimization. Here we propose to train parametric circuits with QHD entirely on the quantum computer, through an online step in which the qubits encoding the parameters coherently control the circuit on a second register. We prove that, for cost functions with a smooth periodic extension, including those of parametric circuits, the simulation error admits a bound independent of the grid resolution, and that for circuits the bound grows at most linearly with the number of parameters. We also show that the ideal dynamics depends on the two schedules only through a single curve, which controls the adiabaticity of the search, and that the remaining freedom can be used to minimize the gate count. Simulations on benchmark functions and parametric circuits show that, at equal cost, schedules designed in this way markedly increase the probability of finding the global minimum.

0.05

Supervised Learning with Quantum Hamiltonian Embeddings

cs.LG quant-ph ·2026-10-19 ·Riccardo Molteni, Minjun Jeon, Paolo Braccia, Abhinav Deshpande, Vedran Dunjko +6 more
benchmark similarity 0.63
Abstract · 59 pages, 7 figures

Machine learning is widely regarded as a promising application in which quantum computing could offer a computational advantage. However, general quantum machine learning models with provable guarantees on performance, trainability, and efficient inference remain limited. In this work, we introduce quantum Hamiltonian embeddings, a supervised learning framework in which a classical training dataset is encoded into a single effective, parameterized Hamiltonian. Training optimizes the parameters of this data-dependent Hamiltonian, whose approximate ground state defines the classification rule. Once the ground state has been approximated using a quantum algorithm, inference can be performed either classically using a classical representation of the learned state, or with a quantum representation of the state. We establish efficient methods for gradient estimation and prove favorable generalization guarantees. Furthermore, under standard cryptographic assumptions, we show that Hamiltonian embeddings can realize hypothesis functions beyond the reach of efficient classical algorithms. We then demonstrate the framework at scale on IBM Heron processors using a standard benchmark dataset. Together, these results establish Hamiltonian embeddings as a new framework for quantum machine learning, combining theoretical guarantees with a path for experimental investigations at scale on quantum hardware.

0.28