PaperlayerView exact revision on arXiv

Source-linked AI summary

A matching decomposition algorithm for simulating quantum walk Hamiltonians

Mostafa Atallah, Alvin Gonzales, Daniel Dilley, Igor Gaidai, Zain H. Saleem, Rebekah Herrman

arXiv:2601.11418v3quant-ph

TL;DR

General CTQW circuit implementation can require exponential resources, motivating lower-resource methods for sparse CTQWs. Matching decomposition combines greedy or compression-aware edge matchings with iterative graph compression and Trotterized CX and CRx circuit constructions. Across graph families, matching decomposition requires up to 43% fewer CX gates and up to 54% shallower circuits with the greedy heuristic, and up to 70% fewer CX gates with compression-aware matching than Pauli decomposition.

  • Problem

    General CTQW circuit implementation can require exponential resources, motivating lower-resource methods for sparse CTQWs.

    Source: §I · p. 2

  • Method

    Matching decomposition combines greedy or compression-aware edge matchings with iterative graph compression and Trotterized CX and CRx circuit constructions.

    Source: §I · p. 2, B. Iterative graph compression · p. 4

  • Results

    Across graph families, matching decomposition requires up to 43% fewer CX gates and up to 54% shallower circuits with the greedy heuristic, and up to 70% fewer CX gates with compression-aware matching than Pauli decomposition.

    Source: §I · p. 2

  • Takeaways & Limitations

    Matching decomposition provides a competitive circuit-construction primitive for sparse CTQW simulation with lower CX counts than Pauli decomposition in the reported experiments.

    Source: §V · p. 12

Abstract

from arXiv · show

In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. We develop a greedy matching heuristic and a compression-aware matching heuristic, both of which can be used in the quantum circuit algorithm. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare greedy (compression-aware) matching decomposition to a standard Pauli-based simulation pipeline and find that greedy (compression-aware) matching decomposition consistently yields substantial resource reductions, requiring up to 43$\%$ (70\%) fewer controlled gates and up to 54$\%$ (75\%) shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.

I. INTRODUCTION

The paper introduces matching decomposition for circuit simulation of sparse continuous-time quantum walks, combining matching heuristics, graph compression, and Trotterization. Against Pauli decomposition, the approach reduces controlled-gate counts and circuit depth while retaining comparable approximation accuracy.

Related work

Motivation

  • Matching decomposition targets sparse CTQWs, whose edge counts grow polynomially with the number of qubits and therefore require fewer resources than arbitrary CTQWs.Source: §I · p. 2

Contributions

  • Matching decomposition splits sparse CTQW Hamiltonians into matching Hamiltonians, then Trotterizes their exactly implementable evolutions.The algorithm uses greedy and compression-aware matching heuristics, with graph compression reducing CX overhead.Source: §I · p. 2

Results

  • Up to 43% fewer CX gates and 54% shallower circuits are achieved by greedy matching decomposition than Pauli decomposition on select graphs.Source: §I · p. 2
  • Up to 70% fewer CX gates and 75% shallower circuits are achieved by compression-aware matching decomposition than Pauli decomposition on select graphs.Source: §I · p. 2

B. Graph theory terminology

The paper defines the graph and matching concepts used by its decomposition, then groups edges by bit-flip structure before compressing compatible edges. Matchings enable independent edge evolutions, while compression reduces circuit-control requirements.

Graph theory terminology

Greedy matching decomposition

Iterative graph compression

C. Compression-aware matching decomposition

The compression-aware heuristic groups edges by complete XOR masks rather than only single-bit flips, prioritizing matchings that expose more merge opportunities. Multiple ordering trials are evaluated with a compression-based CX estimator.

Compression-aware matching decomposition

  • The compression-aware heuristic groups all edges by their full XOR mask, regardless of Hamming distance, because equal masks identify edges with the same differing positions.Source: C. Compression-aware matching… · p. 5

Iterative graph compression

  • Iterative compression initializes active qubits, weight-reducing lists, and original XOR masks, then repeatedly removes mergeable positions until no merge remains.Source: C. Compression-aware matching… · p. 5

Compression-aware matching decomposition

D. Circuit construction and Trotterization

Each compressed matching edge is implemented through basis-changing CX gates, a multicontrolled Rx rotation, and an inverse basis transformation. The resulting matching circuits are combined through Trotterization, with compression-aware grouping illustrated on a 16-vertex graph.

Circuit construction

  • A compressed edge uses three stages: CX basis transformation, multicontrolled Rx(2t) evolution, and reversal of the CX transformation.Source: D. Circuit construction and… · pp. 5–6
  • The 16-vertex example uses 6 greedy matchings versus 4 compression-aware matchings, with edge colors indicating matching assignments.Source: Figure 1 · p. 6
  • For fully compressed single-qubit labels, the edge evolution reduces to an uncontrolled Rx(2t) gate.Source: D. Circuit construction and… · p. 6

Trotterization

E. Example

The example applies greedy matching, compression, and circuit construction to decompose a graph walk into implementable components. The resulting compressed matchings determine the required single-qubit rotations and CX gates.

E. Example

  • Greedy matching assigns edges with compatible bit-flip positions to M0 and places conflicting edges into M1.In the example, 00-01 and 10-11 form M0, while 00-11 and 01-10 form M1.Source: E. Example · p. 6
  • Compression merges M0 into one edge and reduces M1 by eliminating a varying qubit while retaining it in the weight-reducing set W.The compressed M0 edge has A = {0}, W = {}, whereas M1 has A = {1}, W = {0}.Source: E. Example · p. 6
  • The compressed M0 circuit uses one Rx(2t) gate, while M1 adds a CX–Rx(2t)–CX sequence to account for W = {0}.Repeating the circuit with scaled rotation angles implements multiple Trotter steps.Source: E. Example · pp. 6–7
  • The compression-aware algorithm groups edges by XOR mask, processes groups and edges in randomized orders, and prioritizes compatible same-mask assignments before broader or new matchings.Its output is a matching list intended to minimize an estimated circuit-related quantity.Source: E. Example · p. 7

IV. RESULTS

The results compare matching-decomposition and Pauli-based Trotterization using operator error and compiled-circuit resources. Experiments use first-order Trotterization and optimized Qiskit circuits across sparse graphs with 8 to 128 vertices.

IV. RESULTS

  • Matching and Pauli decompositions are compared using operator-norm error, CX gate count, and circuit depth on sparse graph test sets.The circuit benchmarks evaluate compiled circuits rather than coefficient-finding cost.Source: §IV · p. 7
  • The Pauli reference expands the adjacency matrix over all 4^n Pauli strings before constructing each Trotter step with SparsePauliOp and PauliEvolutionGate.Nonzero terms are collected in Qiskit’s SparsePauliOp.Source: §IV · p. 7
  • All reported circuits use first-order Trotterization, Qiskit 1.2.2, full connectivity, CX and U3 basis gates, and optimization level 3.Source: §IV · p. 7

A. Operator difference 2-norm

The operator-difference experiment measures Trotterization error for greedy and compression-aware matching decompositions against Pauli decomposition across connected and disconnected sparse graphs. At t = 1.0 and N = 100, connected graphs have mean errors near 9 × 10^-3, while disconnected graphs have lower means but greater relative variance.

A. Operator difference 2-norm

  • At t = 1.0 and N = 100, connected graphs achieve mean errors of 9.1–9.5 × 10^-3 with approximately 15% relative standard deviation.The measurements cover connected graph sets across multiple sizes.Source: A. Operator difference 2-norm · p. 7
  • Disconnected graphs achieve lower mean errors of 6.1–6.7 × 10^-3 but higher relative variance of approximately 30%.The passage attributes the lower errors to fewer edges and therefore fewer non-commuting terms.Source: A. Operator difference 2-norm · p. 7
  • The study compares matching-based Trotterization error, ||e^-iAt − Umatching||2, with Pauli-based error, ||e^-iAt − UPauli||2, using averages and ±1 standard-deviation regions.The comparison includes greedy and compression-aware matching decomposition.Source: A. Operator difference 2-norm · p. 7

B. CX gate count and circuit depth

Matching decomposition is evaluated against Pauli decomposition using CX counts and circuit depth across connected and Erdős-Rényi graph datasets. Its resource advantage grows with graph size but depends on graph structure, while accuracy remains comparable across decompositions.

Connected graph scaling

  • 70% fewer CX gates and 75% shallower circuits are achieved by compression-aware matching on 128-vertex connected graphs, while greedy matching achieves 43% and 54% reductions, respectively.Compression-aware matching crosses below Pauli decomposition at 16 vertices, whereas greedy matching crosses at 32 vertices.Source: B. CX gate count and circuit depth · p. 8

Accuracy evaluation

  • Operator 2-norm error is compared across greedy, compression-aware, and Pauli Trotterizations for connected 8-vertex graphs at three evolution times.The evaluation uses 80 randomly generated graphs, five runs, and ±1σ bands.Source: B. CX gate count and circuit depth · p. 7, Figure 4 · p. 9

Structural dependence

  • Mixed Hamming-distance structure is associated with reduced CX counts, whereas matchings consisting purely of H1 edges can require more CX gates than Pauli decomposition.The authors therefore expect lower CX counts mainly for sparse, irregular graphs containing edges with large Hamming distance.Source: B. CX gate count and circuit depth · pp. 9–10

Erdős-Rényi graphs

  • 25–33% fewer CX gates and 37–49% shallower circuits are obtained by greedy matching on gnp random graph(N, .01) for N = 32, 64, and 128.Compression-aware and greedy matching results are almost identical for this dataset.Source: B. CX gate count and circuit depth · p. 10

Structural dependence

  • Connected graphs can outperform Pauli decomposition despite greater density when their edge distributions have suitable Hamming weights, but Hamming-weight distribution alone does not explain the observed variance.Other structural properties likely contribute to performance.Source: B. CX gate count and circuit depth · p. 10

C. Commutativity

The paper characterizes when matching-based decompositions commute, including a structural criterion for pairs of matchings and examples where matching decompositions commute while Pauli decompositions do not. These results identify when continuous-time quantum walks can be exactly implemented through commuting matching components.

Limitations and scope

  • A commuting matching decomposition may exist without being found by the proposed algorithm, and the general class of graphs satisfying the required factorization property remains unclear.For k-regular graphs, the relevant condition is a 1-factorization whose pairwise unions are disjoint unions of C4 cycles.Source: C. Commutativity · pp. 10, 12

General criterion

  • Commutativity of arbitrary subgraphs is equivalent to equality of the numbers of length-2 walks under the two possible edge-orderings between every vertex pair.This walk-count criterion follows directly from comparing the corresponding adjacency-matrix products.Source: C. Commutativity · p. 11

Matching commutativity

  • Two matchings commute if and only if every connected component of their union is an isolated vertex, a single edge K2, or a 4-cycle C4.The proof excludes longer paths and even cycles because they create unbalanced alternating length-2 walks.Source: C. Commutativity · p. 11

Examples and extensions

  • An infinite family of relabeled hypercubes has commuting matching decompositions but non-commuting Pauli decompositions, including anticommuting Pauli terms after local three-qubit relabelings.For the eight-vertex case, the transformed adjacency matrix contains IXI and IY Y, which anticommute; the construction extends to relabelings gi for any valid block position.Source: C. Commutativity · pp. 11–12

Exact implementation

  • A matching decomposition exactly implements a CTQW when the adjacency matrices of all constituent matchings pairwise commute.Otherwise, the matching decomposition requires approximation, with error governed by commutator norms.Source: C. Commutativity · p. 12

V. DISCUSSION

Matching decomposition offers a polynomial-overhead basis for Trotterizing sparse CTQW Hamiltonians, with compression-aware matching reducing controlled-gate costs by exploiting shared control patterns. Its accuracy is comparable to Pauli decomposition, while several scaling and applicability questions remain open.

Method

  • Matching decomposition uses polynomial classical overhead and Trotterizes adjacency matrices of matchings to approximate sparse CTQW evolution.The approach compares greedy and compression-aware matching decompositions with Pauli-decomposition Trotterization.Source: §V · p. 12

Resource comparisons

  • 70% fewer CX gates were achieved by compression-aware matching than Pauli decomposition on the connected 128-vertex dataset.The corresponding reductions were approximately 0.5%, 39%, 56%, and 70% on connected 16-, 32-, 64-, and 128-vertex datasets.Source: §V · p. 13

Open directions

  • More precise CX-scaling bounds and better matching-ordering heuristics remain open directions for reducing gate counts and validating near-term utility.The discussion also identifies randomized gate ordering and stronger characterization of favorable graph regimes as future work.Source: §V · p. 13

Mechanism

  • Compression-aware matching merges or eliminates controls when multi-controlled gates share control patterns, a structure Pauli decomposition does not inherently exploit.This shared-control recognition is identified as the likely source of the observed gate-count gap.Source: §V · p. 13

CODE AND DATA AVAILABILITY

The research code and data are publicly identified through a GitHub repository, while the manuscript carries Argonne National Laboratory publication and licensing information.

Availability

  • The research code and data are available at the dyn-CTQW GitHub repository.The cited repository is https://github.com/Mostafa-Atallah2020/dyn-CTQW.Source: CODE AND DATA AVAILABILITY · p. 13

Publication notice

  • The manuscript was created by UChicago Argonne, LLC, Operator of Argonne National Laboratory.The notice identifies Argonne as a U.S. Department of Energy Office of Science laboratory operated under contract DE-AC02-06CH11357.Source: CODE AND DATA AVAILABILITY · p. 13
  • The U.S. Government retains a paid-up, nonexclusive, irrevocable worldwide license to reproduce and distribute the article.The notice also covers derivative works and public performance or display.Source: CODE AND DATA AVAILABILITY · p. 13

Appendix A: Operator norm convergence plots

The appendix compares operator-norm errors for greedy, compression-aware, and Pauli decompositions on sparse connected graphs. The plotted approximations exhibit comparable convergence behavior as Trotter-step counts increase.

Convergence result

  • The matching and Pauli decompositions have comparable convergence rates, with errors scaling as O(t^2/N).This comparison concerns the operator-norm difference between exact CTQW evolution and the Trotterized approximations.Source: Appendix A · p. 16

Figure setup

  • The figure plots operator difference 2-norm against Trotter steps for greedy matching, compression-aware matching, and Pauli decompositions.Panels cover 200 sparse connected graphs on 16 and 32 vertices, with Trotter steps ranging from N = 10 to N = 100.Source: Figure 7 · p. 16

Figure encoding

  • Mean errors are shown across graph sets, with shaded regions indicating ±1 standard deviation.Colors and markers distinguish the three decomposition methods, while line styles denote t = 0.1, 0.5, and 1.0.Source: Figure 7 · p. 16

Related papers

Loading 2601.11418v3…