Quantum Circuits Map Graphs to Distributions with 66 Qubits

A new quantum graph embedding technique, QuIC, translates graphs into sorted output distributions using a fixed circuit, as presented by Luke Miller and Yugyung Lee of the University of Missouri–Kansas City. The approach achieves completeness on isomorphism classes under ideal conditions and retains key structural properties despite practical limitations including finite measurements, noise, and hardware constraints. Empirical separation of graphs up to 66 qubits is established on the IBM Heron processor, identifying performance limits and a practical operating point through head truncation of the sorted distribution. This advances quantum machine learning for graph analysis.

Quantum graph embedding distinguishes 66-qubit structures using fixed-length truncation

Separation of graphs reached 66 qubits using QuIC on IBM Heron hardware, a substantial increase over previous methods limited to smaller instances. This achievement represents a practical operating point for quantum graph embeddings, overcoming a longstanding challenge in quantum machine learning. The QuIC method, a training-free quantum approach, concentrates discriminative signal in a compact ‘head’ of the output distribution, enabling effective fixed-length truncation and reliable performance even with limited computational resources.

Validation of the operational separation criterion occurred across all tested graph pairs, including strongly regular graphs that challenge 2-WL methods and CFI families used as hard instances for fixed-k WL methods. This confirms the ability to distinguish complex structures. Detailed analysis of graphs revealed that structural information is encoded globally, maintaining a consistent separation even when retaining only three qubits versus the full seventeen.

Simulations showed all tested graph pairs satisfied the operational separation criterion; the encoding angle proved most sensitive, while the entangling layer exhibited a single commuting step. Despite these advances, results do not demonstrate scalability beyond these specific graph families, and a practical pathway to fault-tolerant quantum computation remains a vital hurdle. Tests using ss tests and CFI families served as hard instances for fixed-k WL Methods.

A hardware study comprising 14,800 transpiled circuits across 37 CFI families on IBM Heron (ibm_fez, 156 qubits), including paired one- and two-repetition evaluations, reports empirical separation up to 66 qubits for the tested families under the reported execution protocol. The study identifies a device-dependent depth limit near 210, 250 layers and characterizes the current practical boundary of the method. Graph representations are central to combinatorial optimisation, network analysis, chemistry, and machine learning.

Constructing representations that are invariant to vertex relabeling while remaining expressive enough to separate non-isomorphic structures is a persistent challenge. The preprint contains the complete manuscript with all mathematical proofs and experimental details in the appendices, and a condensed version fitting the IEEE QCE 2026-page limit has been submitted for review. Classical expressiveness is commonly measured against the Weisfeiler, Leman (WL) hierarchy, which bounds standard message-passing architectures and motivates evaluation on canonical hard instances such as Cai, Furer, Immerman (CFI) graph pairs.

Higher-order methods can exceed 1-WL, but at rapidly growing computational cost. Quantum circuits offer an alternative encoding mechanism, but existing quantum graph Methods are limited; some remain simulation-based, others require training and labelled data, and still others lack formal guarantees about injectivity or permutation invariance. A gap persists between mathematically analyzable quantum graph representations and Methods validated on NISQ hardware.

This paper presents QuIC, a training-free quantum graph embedding designed to connect ideal analysis with practical execution within a single framework. QuIC assigns one qubit per vertex, encodes degree via RX rotations, encodes edges via RZZ entangling gates, and applies global mixer layers before measurement. Sorting the output distribution removes label dependence, yielding a graph-level embedding. In the ideal one-repetition setting, the resulting sorted distribution is permutation-invariant and injective on labelled graphs under an irrational-angle condition, yielding completeness on isomorphism classes for the ideal one-repetition exact-arithmetic embedding.

These ideal structural properties motivate a practical embedding pipeline, which is then studied under the constraints that govern real execution: finite-shot estimation, fixed-length head truncation, noise, transpilation, and hardware depth limits. Unlike WL-style Methods, the entangling layer acts in a single commuting step, encoding the full graph topology globally rather than through iterative neighbourhood refinement. The work proceeds in two stages: first, ideal analysis of the one-repetition circuit; second, empirical characterisation of practical realizations that approximate that ideal object under current hardware constraints.

Ideal-theory contributions include a training-free quantum graph embedding with fixed parameters and no labelled data requirements. The ideal one-repetition sorted output distribution is permutation-invariant and injective on labelled graphs under an irrational-angle condition, yielding completeness on isomorphism classes in that exact regime. The circuit’s global encoding structure is characterised; the entangling layer encodes full-graph topology in a single step, and the resulting practical bottleneck is sampling rather than information reach.

Practical characterisation contributions include empirical characterisation of the distributional head, supporting fixed-length head truncation as a practical operating point in the tested shot budgets and graph families. Evidence from noise-models suggests that all tested graph pairs satisfied the operational separation criterion across exhaustive, random, structured, and CFI test suites, including strongly regular graphs indistinguishable by 2-WL and CFI pairs indistinguishable by k-WL for any fixed k. Quantum representations of graph-structured data fall into two categories: graph embeddings studied as mathematical objects, and quantum models that process graphs within a learning pipeline. The dominant classical framework for measuring graph representation expressiveness is the Weisfeiler, Leman (WL) hierarchy.

WL-based graph kernels and message-passing graph neural networks (MPNNs) are bounded by the 1-WL test. Higher-order k-dimensional GNNs exceed this at O(nk) cost, rendering k > 3 impractical. Subgraph counting, topological message passing, and subgraph aggregation also surpass 1-WL but at substantial additional cost; recent work proposes finer-grained quantitative expressiveness measures. The canonical hard instances for any fixed-k WL method are Cai, Furer, Immerman (CFI) pairs, constructed to defeat k-variable counting logic.

Practical isomorphism tools, nauty/Traces, bliss, and Babai’s quasipolynomial algorithm, solve GI efficiently but return canonical labelings or yes/no decisions, not vectorial embeddings usable for downstream tasks. Complete graph kernels (injective on isomorphism classes) are GI-hard, and none in practical use achieves completeness. On the quantum side, graph-state invariants based on Wigner-function measurements have been validated in simulation up to nine nodes and on strongly regular graphs up to 29 nodes, though CFI instances remained out of reach.

Related work studies efficiently computable invariants under local-complementation equivalence. Both remain simulation-based. Neutral-atom processors have been applied to graph algorithms, and the GDQC kernel extends this to attributed graphs with expressiveness comparable to GD-WL. Permutation-invariant quantum machine learning is the most structurally related work; ansatze symmetrized under node permutations improve graph classification on tasks including connectivity, bipartiteness, and Hamiltonian path existence.

Like QuIC, these exploit permutation invariance as an inductive bias, but they produce learned representations optimised on labelled data and subject to barren plateaus. QuIC requires no training; its parameters are fixed, the output distribution is the embedding, and completeness is a structural property of the map. QuIC is not naturally situated within the WL hierarchy, nor is it an extension in the spirit of beyond-1-WL methods. Unlike WL-style refinement procedures, QuIC does not operate through iterative neighbourhood aggregation; its entangling layer encodes graph structure globally within a single circuit application.

For this reason, CFI pairs and other classically difficult instances are used here as empirical stress tests rather than as evidence of a formal separation from WL. Its closest precursors are quantum-walk approaches to graph discrimination, where interacting two-particle walks distinguish all tested non-isomorphic strongly regular graph pairs while non-interacting walks cannot. QuIC replaces particle dynamics with a parameterised circuit whose entangling layer plays the role of the interaction mechanism. QuIC is distinct from prior quantum graph Methods in both framework and hardware scope.

Quantum kernels, and permutation-invariant QML, require training, whereas QuIC is a fixed, training-free graph embedding. Prior quantum invariants remain simulation-based. QuIC’s completeness result (Theorem 3, Corollary 4) is also unusual; in the ideal one-repetition setting, it yields an invariant and injective embedding on isomorphism classes, an ideal exact-regime guarantee not typically provided by practical graph kernels in common use. This work follows that ideal construction through noisy simulation and physical hardware execution.

QuIC maps a simple undirected graph G = (V, E) with |V | = k vertices to a k-qubit circuit, one qubit per vertex. The circuit resembles a QAOA ansatz, graph-dependent entanglers alternating with mixers, but parameters are fixed rather than optimised, and the full sorted output distribution serves as the embedding. Three operator families compose the circuit: a degree-encoding layer Uenc, an edge-based entangling layer Uent, and a mixing layer Umix, with the entangling and mixing layers repeated for r rounds: U(G) = (UmixUent)r Uenc, applied to |0⟩⊗k. All gate angles are assumed to satisfy θenc, θent, θmix /∈πQ; this condition is formalized in Section IV. Encoding layer: Each qubit receives an RX rotation proportional to its vertex’s normalized degree: Uenc = k O i=1 RX(φi), φi = θenc di dmax, dmax > 0 where di = deg(vi) and dmax = max(d). Degree information is implicitly present in the entangling layer through the number of RZZ gates per qubit; the encoding layer makes it explicitly available in the initial amplitudes, ensuring the entangler operates on a state already differentiated by local connectivity.

A training-free quantum graph embedding, QuIC, maps graphs to sorted output distributions via a fixed parameterised circuit. In the ideal one-repetition setting, the resulting sorted distribution is permutation-invariant and injective on labelled graphs under an irrational-angle condition, yielding completeness on isomorphism classes for exact-arithmetic embedding. These ideal structural properties motivate a practical embedding pipeline, with analysis of how behaviour survives under finite-shot estimation, truncation, noise, transpilation, and hardware execution.

The sorted distribution concentrates discriminative signal in a compact head, making fixed-length head truncation an effective operating point. Noise-model simulation indicates all tested graph pairs satisfied the operational separation criterion, including strongly regular graphs and CFI families used as hard instances for fixed-k WL methods. A hardware study comprising 14,800 transpiled circuits on IBM Heron (ibm_fez, 156 qubits) reports empirical separation up to 66 qubits for the tested families, identifies a device-dependent depth limit near 210, 250 layers, and characterizes the method’s practical boundary.

Output: The QuIC embedding is the sorted distribution p(G) obtained by arranging pG(x) = ⟨x | U(G) | 0⟩⊗k2, x ∈{0, 1}k, in non-increasing order. Sorting removes dependence on vertex labelling; permutation invariance is formalized in Section IV. Computational profile: The logical QuIC circuit uses |V (G)| qubits and |E(G)| two-qubit entangling gates per repetition, so its pre-transpilation serial depth is O(|E(G)|) under a naive schedule and may be reduced by parallel gate packing when graph structure and hardware connectivity permit. Exact statevector simulation remains exponential in |V (G)|, as with any full-amplitude simulation of an n-qubit circuit.

In practical finite-shot settings, however, QuIC is compared through sampled output counts and top-k extraction rather than full-state sorting, so the dominant post-processing cost scales with the number of collected samples or observed bitstrings rather than the full 2|V (G)| output space. These costs are not presented as a claim of computational advantage over classical graph isomorphism or graph kernels; rather, they clarify that the main practical bottlenecks in the present study arise from sampling, transpilation variability, and hardware noise rather than from circuit construction itself. Ideal and practical regimes are distinguished throughout. The ideal QuIC embedding is the full sorted output distribution of the one-repetition circuit under exact arithmetic, the object for which completeness is proven in Section IV. All experiments evaluate practical QuIC embeddings, obtained under finite-shot estimation and, on hardware, under transpilation and device noise with vector truncation. These practical studies include both the one-repetition circuit.

Quantum graph embedding differentiates complex networks using limited-depth circuits

A quantum-based method for graph embedding has been demonstrated, capable of distinguishing complex network structures.

The study introduces a quantum graph embedding approach called QuIC, which maps graphs into sorted distributions using fixed quantum circuits. This method successfully differentiates between pairs of graphs, including those that are difficult for classical algorithms, using systems of up to 66 qubits on IBM Heron hardware. By concentrating key structural information into sorted distributions, the approach enables effective analysis even with limited data and in the presence of noise. The researchers tested circuits with up to 250 layers and found that practical limitations arise mainly from sampling, circuit translation, and hardware noise, rather than from the embedding method itself.