Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

A matching decomposition algorithm for simulating quantum walk Hamiltonians

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper establishes matching decomposition as a valid and cheaper circuit primitive for simulating quantum walks on sparse graphs, cutting CX gates by up to 43% and circuit depth by up to 54% relative to Pauli decomposition.

desk verdict A promising matching-decomposition primitive for CTQW simulation, but the compressed-edge circuit as written has a real gap and the headline numbers are not all substantiated in the body. read the letter →

arxiv 2601.11418 v3 pith:4LFZKNVI submitted 2026-01-16 quant-ph

Mostafa Atallah , Alvin Gonzales , Daniel Dilley , Igor Gaidai , Zain H. Saleem , Rebekah Herrman This is my paper · ORCID
classification quant-ph
keywords matchingdecompositioncontinuous-timequantumwalkHamiltoniansimulationgraphcompressionTrotterizationCXgatecountsparsegraphscircuitcompilation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces matching decomposition, a circuit-construction algorithm for continuous-time quantum walks on arbitrary sparse simple graphs. The idea is to split the walk Hamiltonian into matchings — sets of edges that share no vertices — so that the evolution along each matching factorizes into independent edge rotations, then to merge edges with identical bit-flip structure through an iterative graph-compression procedure that shrinks the qubit labels and reduces the number of control qubits. Trotterizing the resulting matching unitaries approximates the full walk with an error that scales like O(t^2/N) and, in benchmarks on graphs with 32 to 128 vertices, uses up to 43% fewer CX gates and gives circuits up to 54% shallower than a standard Pauli-decomposition pipeline. The authors also characterize when matchings commute, proving that two matchings commute exactly when their union is a disjoint union of isolated vertices, single edges, and 4-cycles, which yields an infinite family of graphs on which the matching approach simulates exactly while Pauli terms anticommute. The paper's claim, if correct, is that matching decomposition is a cheaper and sometimes exact primitive for simulating quantum walks in the circuit model.

What carries the argument

The central object is the matching decomposition plus an iterative graph-compression procedure. Because edges in a matching share no vertices, their single-edge Hamiltonians are disjoint and therefore commute, so each matching's evolution is a product of independent edge rotations. The compression step then looks for pairs of edges with identical original XOR masks and identical active- and weight-reducing-qubit metadata that differ only at one bit position; deleting that bit merges the two edges into one compressed edge that represents both original edges and needs fewer control qubits. The circuit primitive per compressed edge is a three-stage block: CX gates implement the basis transforma

What would settle it

Take a 3-qubit system with the two-edge matching {(000,011), (100,111)}, merge the edges at the constant bit to obtain the compressed edge (00,11) with an empty weight-reducing list, build the prescribed three-stage circuit (which lacks well-defined control values because the endpoints have no common bits), and compare the resulting unitary to e^{-iHt} for the matching Hamiltonian; any nonzero operator distance for generic t refutes the construction's universal correctness.

Watch

Extended reading notes

Core claim

Matching decomposition claims that a continuous-time quantum walk e^{-iAt} on a simple sparse graph can be approximated by a Trotter product of unitaries, one per matching in a decomposition of the graph's edges, where each matching's unitary is a product of independent edge evolutions. Each edge evolution is realized without Pauli terms as a multi-controlled Rx rotation, with CX gates providing basis transformations for edges whose endpoints differ in several bits. A graph-compression algorithm merges edges that share the same original XOR mask, active-qubit list, and weight-reducing-qubit list by deleting a common bit, so that a single compressed edge represents many original edges and req

Load-bearing premise

The three-stage circuit construction assumes that every compressed edge is exactly implemented by the CX–multi-controlled-Rx–CX block, including compressed edges whose endpoint labels share no common bits (so the control values of the Rx gate are not defined by the text); the paper gives no general proof of this unitary equivalence.

Editorial extensions

If this is right

  • On connected and random sparse graphs with 32 or more vertices, matching decomposition consistently requires fewer CX gates and shallower circuits than the Pauli baseline, with savings growing with graph size (up to 43% CX / 54% depth at 128 vertices).
  • Approximation error matches Pauli decomposition's O(t^2/N) Trotter convergence in the tested operator norms, so the gate savings do not come at an accuracy cost.
  • For graphs whose matchings pairwise commute — for example, the infinite family of relabeled hypercubes — matching decomposition simulates the quantum walk exactly, with no Trotter error, while the Pauli decomposition of the same Hamiltonian contains anticommuting terms.
  • The method uses only polynomial classical overhead for greedy edge grouping and compression, so it can serve as an automatic circuit-generation primitive rather than a hand-crafted construction.
  • Pure Hamming-distance-1 matchings tend to cost more than Pauli; the reported savings rely on a mixed Hamming-weight distribution, i.e., edges whose endpoints differ in several bits.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Since compression exploits coincidences among vertex labels, relabeling a graph (applying a permutation to qubit bitstrings) before decomposition is a natural pre-optimization: an optimal label permutation could create more mergeable edges and push the crossover with Pauli decomposition to smaller graphs.
  • The commutativity condition (union of any two matchings is a union of 4-cycles) may be satisfied by other graph families, such as Cartesian products of even cycles, which would give more examples of exactly simulable walks beyond the hypercube relabelings presented.
  • The same compression-and-matching scheme applies to any sparse symmetric matrix whose off-diagonal support is a simple graph, so the circuit primitive could be reused for Laplacian-based walks or other graph-derived Hamiltonians; this extension is not discussed in the paper.
  • Ordering the matchings adaptively within the Trotter product is a direct testable extension: since commutator norms between matchings control the Trotter error, choosing an order that minimizes those norms could further reduce both error and circuit depth.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes 'matching decomposition' as a circuit-construction primitive for simulating continuous-time quantum walks on sparse graphs. The scheme decomposes the adjacency matrix into matchings, compresses each matching by merging edges with equal original XOR masks, and Trotterizes the resulting compressed-edge Hamiltonians using CX and multi-controlled Rx gates. The authors report operator-norm errors comparable to a Pauli-decomposition baseline and claim up to 43% fewer CX gates and 54% shallower circuits on connected graph benchmarks, with additional theoretical results on commuting matching decompositions.

Significance. If the circuit construction is correct and the reported reductions hold, matching decomposition would be a useful new primitive for near-term simulation of sparse-graph Hamiltonians, avoiding a full Pauli expansion. The graph-compression idea is intuitive and the numerical comparison against a standard Qiskit Pauli pipeline is a reasonable baseline. The paper makes its code available, which aids reproducibility. However, the central circuit description has a correctness gap for a natural class of compressed edges, and the abstract promises a compression-aware heuristic and headline numbers that never appear in the body. These issues must be resolved before the resource claims are fully supported.

major comments (3)
  1. [Section III.C] The three-stage circuit for a compressed edge e' is incomplete/incorrect when the compressed edge still has Hamming distance >1 among its active qubits and W_e' does not include the extra differing active qubits. Example: matching M = {(000,011),(100,111)} with n=3. Both edges have original XOR mask 011 and are mergeable at p=2 (u1⊕u2 = v1⊕v2 = 100). The merge yields e'=(00,11) with A=(0,1) and W={}. As written, Stage 1 applies no CX gates; Stage 2's control values are 'determined by the common bits of u' and v'', but u'=00 and v'=11 share no common bits, so the prescribed gate is an unconditional Rx on one active qubit. Such a gate acts nontrivially on |01> and |10>, whereas the represented Hamiltonian is e^{-it(|000><011| + |100><111| + h.c.)}, which does not. The correct construction requires CX gates between the differing active qubits (the usual [21] Hamming-distance-reduction step)
  2. [Abstract vs. Sections III–IV] The abstract states that 'greedy (compression-aware) matching decomposition' yields up to 43% (70%) fewer controlled gates and 54% (75%) shallower circuits, and promises a compression-aware matching heuristic. The body, however, defines only the greedy matching decomposition (Algorithm 1) and reports results only for that method. No compression-aware heuristic is described anywhere in Sections III or IV, and the 70%/75% figures never appear in the main text. The headline claims are therefore not reproducible from the manuscript as written. Either the missing heuristic and its experiments must be added, or the abstract must be corrected to match the body.
  3. [Section IV.B vs. Section V] The reported CX reductions for the connected graph datasets are internally inconsistent. Section IV.B states that matching decomposition requires 8% fewer CX gates at 32 vertices, 34% at 64, and 43% at 128. Section V states 'approximately 34%, 42%, and 45% fewer CX gates than Pauli decomposition respectively on the connected 32-, 64-, and 128-vertex graphs'. These two sets of numbers cannot both be correct. Since the paper's central quantitative claim is based on these reductions, the discrepancy must be fixed and the final numbers reconciled.
minor comments (5)
  1. [Section IV.B] The text says the shaded regions in Figure 4 show standard deviation 'expressed as a coefficient of variation (CV = std/mean)'. A shaded band cannot directly display both a standard deviation and a CV; please clarify which quantity is plotted and how the normalization is applied.
  2. [Section IV.C / Lemma references] In the paragraph before Lemma 5, 'a characterization of the graphs that satisfy Lemma??' contains a missing lemma reference. Please replace with the correct cross-reference.
  3. [Section III.C / [21] relationship] The text states that non-compressed edges are implemented using the single-edge construction from [21], while compressed edges use the three-stage circuit. Since the three-stage circuit should be a special case of the same construction, a short remark explaining the relationship (and why the compressed representation does not change the edge-walk unitary) would help.
  4. [Code and data availability] The GitHub repository is a positive step, but no version/commit hash is provided. A tagged release or commit identifier would improve reproducibility of the numerical benchmarks.
  5. [Remark 1 formatting] The inline 'Remark 1.[64]' formatting is awkward; consider presenting it as a quoted remark with a proper reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: matching decomposition, graph compression, and Trotterization are derived from graph labels and benchmarked against an external Pauli pipeline; the self-citations are not load-bearing.

full rationale

The paper's central derivation is self-contained on its own definitions and algorithmic steps. Matching decomposition (Algorithm 1) partitions edges by bit-flip structure and vertex conflicts; compression (Algorithm 2) merges edges by explicit mergeability criteria (Definition 4) and bit-deletion (Definition 6). The resource claims are comparisons against an external standard pipeline (Qiskit SparsePauliOp / PauliEvolutionGate) with identical transpilation settings, so no fitted parameter is renamed as a prediction and no benchmark is reduced to an input assumption. The only substantive self-citation is [21], which supplies the single-edge circuit construction; however, the paper itself restates this construction in Section II.A as a standard CX/multicontrolled-Rx pattern, and the matching-compression claim does not depend on accepting [21] as an unverified premise. The commuting-matching results in Section IV.C are proven via Lemmas 1-3 rather than imported from the cited related works [64,67], and the paper explicitly notes that its algorithm need not find the commuting decomposition. The potential weakness in Section III.C — that a compressed edge with no common control bits may not be exactly implemented by the described three-stage circuit — is a correctness gap or underspecification, not circularity: the claimed gate-count reduction does not reduce by construction to the correctness of that circuit. No step was found in which an output is an input by definition, a fitted quantity is presented as a prediction, or a load-bearing premise is justified only by the authors' own prior work.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard Trotter theory, the published [21] edge circuit, and an unproved compression-circuit equivalence. There are no fitted constants and no invented physical entities; the 'compressed edge' is a bookkeeping object, not a new physical postulate.

assumptions (4)
  • standard math Trotter-Lie formula (Eq. 2): the product of matchings' exponentials approximates e^{-iA_G t} with error O(t^2/N).
    Invoked in Sec. II.C and used for all circuits; a standard theorem.
  • domain assumption Single-edge evolution can be implemented by the CX/Rx circuit construction of Ref. [21], including Hamming-distance reduction via CNOTs.
    Central building block from prior published work; the paper does not re-derive it.
  • ad hoc to paper A compressed edge e' with metadata (A_e', W_e') exactly represents the sum of its constituent original edge evolutions via the three-stage circuit in Sec. III.C.
    Asserted but not proved. For compressed edges retaining Hamming distance >1 among active qubits, the described circuit is underspecified and no unitary-equivalence proof is given.
  • domain assumption The graph embedding is fixed: vertices are labeled by n-bit strings and the walk is defined on that state space.
    Used throughout Sec. III; changing labels changes circuits, and the paper notes this in Sec. V.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A matching decomposition algorithm for simulating quantum walk Hamiltonians." pith.science (2026). https://pith.science/paper/4LFZKNVI

@misc{pith2026260111418,
  author       = {Pith},
  title        = {Pith review of: A matching decomposition algorithm for simulating quantum walk Hamiltonians},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4LFZKNVI}},
  note         = {Machine review of arXiv:2601.11418}
}
abstract

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.

Figures

Figures reproduced from arXiv: 2601.11418 by the authors.

Figure 1
Figure 1. FIG. 1. Matching decomposition and space reduction example. The original 4-vertex graph [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Trotterized circuit for the example graph with [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. The 2-norm of the operator difference [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: FIG. 4. CX gate counts and circuit depths for the matching and Pauli decompositions on the connected graph datasets. Shaded [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. CX gate counts and circuit depth for matching decomposition (blue) and Pauli decomposition (orange) on Erd˝os-R´enyi [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6. Operator difference 2-norm [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7. Operator difference 2-norm [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Benchmarking Hybrid Quantum-Classical Algorithms for Power Grid Optimization Problems

    quant-ph 2026-07 conditional novelty 6.0 of 10

    For AC-OPF-UC instances with 5-13 generators, the qubit-efficient hybrid VQA does not outperform uniform random bitstring sampling on ideal-time quantum hardware.

Reference graph

Works this paper leans on

69 extracted references · 9 linked inside Pith · cited by 1 Pith paper

  1. [21]

    Ef- ficient sparse state preparation via quantum walks.npj Quantum Information, 11(1):143, 2025

    Alvin Gonzales, Rebekah Herrman, Colin Campbell, Igor Gaidai, Ji Liu, Teague Tomesh, and Zain H Saleem. Ef- ficient sparse state preparation via quantum walks.npj Quantum Information, 11(1):143, 2025

    2025

  2. [1]

    Hamiltonian simulation in the interaction picture.arXiv preprint arXiv:1805.00675, 2018

    Guang Hao Low and Nathan Wiebe. Hamiltonian simulation in the interaction picture.arXiv preprint arXiv:1805.00675, 2018

    arXiv 2018

  3. [2]

    Optimal hamilto- nian simulation by quantum signal processing.Physical review letters, 118(1):010501, 2017

    Guang Hao Low and Isaac L Chuang. Optimal hamilto- nian simulation by quantum signal processing.Physical review letters, 118(1):010501, 2017

    2017

  4. [3]

    Black- box hamiltonian simulation and unitary implementation

    Dominic W Berry and Andrew M Childs. Black- box hamiltonian simulation and unitary implementation. arXiv preprint arXiv:0910.4157, 2009

    arXiv 2009

  5. [4]

    Shadow hamil- tonian simulation.Nature Communications, 16(1):2690, 2025

    Rolando D Somma, Robbie King, Robin Kothari, Thomas E O’Brien, and Ryan Babbush. Shadow hamil- tonian simulation.Nature Communications, 16(1):2690, 2025

    2025

  6. [5]

    The power of block-encoded matrix powers: im- proved regression techniques via faster hamiltonian sim- ulation.arXiv preprint arXiv:1804.01973, 2018

    Shantanav Chakraborty, Andr´ as Gily´ en, and Stacey Jef- fery. The power of block-encoded matrix powers: im- proved regression techniques via faster hamiltonian sim- ulation.arXiv preprint arXiv:1804.01973, 2018

    arXiv 2018

  7. [6]

    Hamiltonian simulation with nearly optimal dependence on all parameters

    Dominic W Berry, Andrew M Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In2015 IEEE 56th annual sympo- sium on foundations of computer science, pages 792–809. IEEE, 2015

    2015

  8. [7]

    Efficient quantum walk on a quantum processor.Nature commu- nications, 7(1):11511, 2016

    Xiaogang Qiang, Thomas Loke, Ashley Montanaro, Kanin Aungskunsiri, Xiaoqi Zhou, Jeremy L O’Brien, Jingbo B Wang, and Jonathan CF Matthews. Efficient quantum walk on a quantum processor.Nature commu- nications, 7(1):11511, 2016

    2016

Show all 69 references
  1. [8]

    Universal computation by quantum walk.Physical review letters, 102(18):180501, 2009

    Andrew M Childs. Universal computation by quantum walk.Physical review letters, 102(18):180501, 2009

    2009

  2. [9]

    Spatial search by quantum walk.Physical Review A, 70(2):022314, 2004

    Andrew M Childs and Jeffrey Goldstone. Spatial search by quantum walk.Physical Review A, 70(2):022314, 2004

    2004

  3. [10]

    Continuous- time quantum walks on dynamic graphs.Physical Review A, 100(1):012306, 2019

    Rebekah Herrman and Travis S Humble. Continuous- time quantum walks on dynamic graphs.Physical Review A, 100(1):012306, 2019

    2019

  4. [11]

    Finding a marked node on any graph via continuous-time quantum walks.Physical Review A, 102(2):022227, 2020

    Shantanav Chakraborty, Leonardo Novo, and J´ er´ emie Roland. Finding a marked node on any graph via continuous-time quantum walks.Physical Review A, 102(2):022227, 2020

    2020

  5. [12]

    Continuous- time quantum-walk spatial search on the Bollob´ as scale- free network.Physical Review A, 101(2):022310, 2020

    Tomo Osada, Bruno Coutinho, Yasser Omar, Kaoru Sanaka, William J Munro, and Kae Nemoto. Continuous- time quantum-walk spatial search on the Bollob´ as scale- free network.Physical Review A, 101(2):022310, 2020

    2020

  6. [13]

    Quadratic speedup for spatial search by continuous-time quantum walk.Physical re- view letters, 129(16):160502, 2022

    Simon Apers, Shantanav Chakraborty, Leonardo Novo, 13 and J´ er´ emie Roland. Quadratic speedup for spatial search by continuous-time quantum walk.Physical re- view letters, 129(16):160502, 2022

    2022

  7. [14]

    Spatial search on johnson graphs by continuous- time quantum walk.Quantum Information Processing, 21(2):74, 2022

    Hajime Tanaka, Mohamed Sabri, and Renato Portu- gal. Spatial search on johnson graphs by continuous- time quantum walk.Quantum Information Processing, 21(2):74, 2022

    2022

  8. [15]

    Link prediction with continuous-time classi- cal and quantum walks.Entropy, 25(5):730, 2023

    Mark Goldsmith, Harto Saarinen, Guillermo Garc ´ ıa- P´ erez, Joonas Malmi, Matteo AC Rossi, and Sabrina Maniscalco. Link prediction with continuous-time classi- cal and quantum walks.Entropy, 25(5):730, 2023

    2023

  9. [16]

    Quantum link prediction in complex networks.Physical Review A, 107(3):032605, 2023

    Jo˜ ao P Moutinho, Andr´ e Melo, Bruno Coutinho, Istv´ an A Kov´ acs, and Yasser Omar. Quantum link prediction in complex networks.Physical Review A, 107(3):032605, 2023

    2023

  10. [17]

    A 2d quan- tum walk simulation of two-particle dynamics.Science, 336(6077):55–58, 2012

    Andreas Schreiber, Aur´ el G´ abris, Peter P Rohde, Kaisa Laiho, Martin ˇStefaˇ n´ ak, V´ aclav Potoˇ cek, Craig Hamil- ton, Igor Jex, and Christine Silberhorn. A 2d quan- tum walk simulation of two-particle dynamics.Science, 336(6077):55–58, 2012

    2012

  11. [18]

    Combinatorial op- timization via highly efficient quantum walks.Physical Review Research, 2(2):023302, 2020

    Samuel Marsh and Jingbo B Wang. Combinatorial op- timization via highly efficient quantum walks.Physical Review Research, 2(2):023302, 2020

    2020

  12. [19]

    Quantum walk-based portfolio optimi- sation.Quantum, 5:513, 2021

    Nicholas Slate, Edric Matwiejew, Samuel Marsh, and Jingbo B Wang. Quantum walk-based portfolio optimi- sation.Quantum, 5:513, 2021

    2021

  13. [20]

    Quantum walk informed variational algorithm design.arXiv preprint arXiv:2406.11620, 2024

    Edric Matwiejew and Jingbo B Wang. Quantum walk informed variational algorithm design.arXiv preprint arXiv:2406.11620, 2024

    2024 arXiv

  14. [22]

    Protein-dna target search relies on quantum walk.Biosystems, 201:104340, 2021

    Mario D’Acunto. Protein-dna target search relies on quantum walk.Biosystems, 201:104340, 2021

    2021

  15. [23]

    Diego Santiago-Alarcon, Horacio Tapia-McClung, Ser- gio Lerma-Hern´ andez, and Salvador E Venegas-Andraca. Quantum aspects of evolution: a contribution towards evolutionary explorations of genotype networks via quan- tum walks.Journal of the Royal Society Interface, 17(172):20...

    2020

  16. [24]

    Experimental realization of continuous-time quantum walks on directed graphs and their application in pagerank.Optica, 7(11):1524– 1530, 2020

    Kunkun Wang, Yuhao Shi, Lei Xiao, Jingbo Wang, Yo- gesh N Joglekar, and Peng Xue. Experimental realization of continuous-time quantum walks on directed graphs and their application in pagerank.Optica, 7(11):1524– 1530, 2020

    2020

  17. [25]

    Continuous-time quantum walk based centrality testing on weighted graphs.Scientific Reports, 12(1):6001, 2022

    Yang Wang, Shichuan Xue, Junjie Wu, and Ping Xu. Continuous-time quantum walk based centrality testing on weighted graphs.Scientific Reports, 12(1):6001, 2022

    2022

  18. [26]

    Transport and quantum walk of nonclassical light in cou- pled waveguides.Physical Review A—Atomic, Molecular, and Optical Physics, 78(4):042304, 2008

    Amit Rai, Girish Saran Agarwal, and Jacques HH Perk. Transport and quantum walk of nonclassical light in cou- pled waveguides.Physical Review A—Atomic, Molecular, and Optical Physics, 78(4):042304, 2008

    2008

  19. [27]

    Re- alization of quantum walks with negligible decoher- ence in waveguide lattices.Physical review letters, 100(17):170506, 2008

    Hagai B Perets, Yoav Lahini, Francesca Pozzi, Marc Sorel, Roberto Morandotti, and Yaron Silberberg. Re- alization of quantum walks with negligible decoher- ence in waveguide lattices.Physical review letters, 100(17):170506, 2008

    2008

  20. [28]

    Experimental perfect state transfer of an entangled photonic qubit.Na- ture communications, 7(1):11339, 2016

    Robert J Chapman, Matteo Santandrea, Zixin Huang, Giacomo Corrielli, Andrea Crespi, Man-Hong Yung, Roberto Osellame, and Alberto Peruzzo. Experimental perfect state transfer of an entangled photonic qubit.Na- ture communications, 7(1):11339, 2016

    2016

  21. [29]

    Experimental two- dimensional quantum walk on a photonic chip.Science advances, 4(5):eaat3174, 2018

    Hao Tang, Xiao-Feng Lin, Zhen Feng, Jing-Yuan Chen, Jun Gao, Ke Sun, Chao-Yue Wang, Peng-Cheng Lai, Xiao-Yun Xu, Yao Wang, et al. Experimental two- dimensional quantum walk on a photonic chip.Science advances, 4(5):eaat3174, 2018

    2018

  22. [30]

    Implemen- tation of continuous-time quantum walks on quantum computers.arXiv preprint arXiv:2212.08889, 2022

    Renato Portugal and Jalil Khatibi Moqadam. Implemen- tation of continuous-time quantum walks on quantum computers.arXiv preprint arXiv:2212.08889, 2022

    2022 arXiv

  23. [31]

    Circuit design for continuous time quantum walks on cycle graph and its experimental demonstration in ibm quantum computer

    Anjishnu Adhikari, Bikash K Behera, and Prasanta K Panigrahi. Circuit design for continuous time quantum walks on cycle graph and its experimental demonstration in ibm quantum computer

  24. [32]

    Efficient quantum cir- cuits for continuous-time quantum walks on composite graphs.Journal of Physics A: Mathematical and Theo- retical, 50(5):055303, 2017

    T Loke and Jingbo B Wang. Efficient quantum cir- cuits for continuous-time quantum walks on composite graphs.Journal of Physics A: Mathematical and Theo- retical, 50(5):055303, 2017

    2017

  25. [33]

    Deterministic search on star graphs via quantum walks.Physical review letters, 128(5):050501, 2022

    Dengke Qu, Samuel Marsh, Kunkun Wang, Lei Xiao, Jingbo Wang, and Peng Xue. Deterministic search on star graphs via quantum walks.Physical review letters, 128(5):050501, 2022

    2022

  26. [34]

    Efficient quantum cir- cuit implementation of quantum walks.Physical Review A—Atomic, Molecular, and Optical Physics, 79(5):052335, 2009

    BL Douglas and JB Wang. Efficient quantum cir- cuit implementation of quantum walks.Physical Review A—Atomic, Molecular, and Optical Physics, 79(5):052335, 2009

    2009

  27. [35]

    Quantum computa- tion and decision trees.Physical Review A, 58(2):915, 1998

    Edward Farhi and Sam Gutmann. Quantum computa- tion and decision trees.Physical Review A, 58(2):915, 1998

    1998

  28. [36]

    Continuous-time quantum walk on a random graph using quantum cir- cuits.arXiv preprint arXiv:2510.14905, 2025

    Sabyasachi Chakraborty, Rohit Sarma Sarkar, Sonjoy Majumder, and Rohit Kishan Ray. Continuous-time quantum walk on a random graph using quantum cir- cuits.arXiv preprint arXiv:2510.14905, 2025

    2025 arXiv

  29. [37]

    Isolated vertices in continuous-time quantum walks on dynamic graphs.Physical Review A, 100(6):062325, 2019

    Thomas G Wong. Isolated vertices in continuous-time quantum walks on dynamic graphs.Physical Review A, 100(6):062325, 2019

    2019

  30. [38]

    Simplify- ing continuous-time quantum walks on dynamic graphs

    Rebekah Herrman and Thomas G Wong. Simplify- ing continuous-time quantum walks on dynamic graphs. Quantum Information Processing, 21(2):54, 2022

    2022

  31. [39]

    Imple- menting quantum gates using length-3 dynamic quantum walks.Physical Review A, 104(4):042604, 2021

    Ibukunoluwa A Adisa and Thomas G Wong. Imple- menting quantum gates using length-3 dynamic quantum walks.Physical Review A, 104(4):042604, 2021

    2021

  32. [40]

    Relating the multi-angle quantum ap- proximate optimization algorithm and continuous-time quantum walks on dynamic graphs.arXiv preprint arXiv:2209.00415, 2022

    Rebekah Herrman. Relating the multi-angle quantum ap- proximate optimization algorithm and continuous-time quantum walks on dynamic graphs.arXiv preprint arXiv:2209.00415, 2022

    2022 arXiv

  33. [41]

    A quantum approximate optimization algorithm.arXiv preprint arXiv:1411.4028, 2014

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm.arXiv preprint arXiv:1411.4028, 2014

    2014 arXiv

  34. [42]

    Analyzing the quan- tum approximate optimization algorithm: ans¨ atze, sym- metries, and lie algebras.PRX Quantum, 6(4):040345, 2025

    Sujay Kazi, Mart ´ ın Larocca, Marco Farinati, Patrick J Coles, M Cerezo, and Robert Zeier. Analyzing the quan- tum approximate optimization algorithm: ans¨ atze, sym- metries, and lie algebras.PRX Quantum, 6(4):040345, 2025

    2025

  35. [43]

    Quantum approximate optimization algorithm with random and subgraph phase operators

    Anthony Wilkie, Igor Gaidai, James Ostrowski, and Re- bekah Herrman. Quantum approximate optimization algorithm with random and subgraph phase operators. Physical Review A, 110(2):022441, 2024

    2024

  36. [44]

    The symmetry-based expressive qaoa for the maxcut problem.Advanced Quantum Tech- nologies, page 2500199, 2025

    Xiumei Zhao, Yongmei Li, Guanghui Li, Yijie Shi, Su- juan Qin, and Fei Gao. The symmetry-based expressive qaoa for the maxcut problem.Advanced Quantum Tech- nologies, page 2500199, 2025

    2025

  37. [45]

    Preparing angular momentum eigen- states using engineered quantum walks.Physical Review A, 110(6):062214, 2024

    Yuan Shi, Kristin M Beck, Veronika Anneliese Kruse, and Stephen B Libby. Preparing angular momentum eigen- states using engineered quantum walks.Physical Review A, 110(6):062214, 2024

    2024

  38. [46]

    Imple- 14 mentation of a continuous-time quantum walk on a sparse graph.Physical Review A, 110(5), November 2024

    Zhaoyang Chen, Guanzhong Li, and Lvzhou Li. Imple- 14 mentation of a continuous-time quantum walk on a sparse graph.Physical Review A, 110(5), November 2024

    2024

  39. [47]

    Generalized trotter’s formula and sys- tematic approximants of exponential operators and inner derivations with applications to many-body problems

    Masuo Suzuki. Generalized trotter’s formula and sys- tematic approximants of exponential operators and inner derivations with applications to many-body problems. Communications in Mathematical Physics, 51(2):183– 190, Jun 1976

    1976

  40. [48]

    Quclear: Clifford extrac- tion and absorption for quantum circuit optimization

    Ji Liu, Alvin Gonzales, Benchen Huang, Zain Hamid Saleem, and Paul Hovland. Quclear: Clifford extrac- tion and absorption for quantum circuit optimization. In2025 IEEE International Symposium on High Perfor- mance Computer Architecture (HPCA), pages 158–172. IEEE, 2025

    2025

  41. [49]

    Sparsepauliop.https://docs.quantum.ibm.com/ api/qiskit/qiskit.quantum_info.SparsePauliOp

    IBM. Sparsepauliop.https://docs.quantum.ibm.com/ api/qiskit/qiskit.quantum_info.SparsePauliOp

  42. [50]

    Efficient attributed graph matching and its application to image analysis

    Horst Bunke and Bruno T Messmer. Efficient attributed graph matching and its application to image analysis. In Image Analysis and Processing: 8th International Con- ference, ICIAP’95 San Remo, Italy, September 13–15, 1995 Proceedings 8, pages 44–55. Springer, 1995

    1995

  43. [51]

    Gpm: A graph pattern matching kernel with diffusion for chem- ical compound classification

    Aaron Smalter, Jun Huan, and Gerald Lushington. Gpm: A graph pattern matching kernel with diffusion for chem- ical compound classification. In2008 8th IEEE Interna- tional Conference on BioInformatics and BioEngineer- ing, pages 1–6. IEEE, 2008

    2008

  44. [52]

    An optimal algorithm for on-line bipartite match- ing

    Richard M Karp, Umesh V Vazirani, and Vijay V Vazi- rani. An optimal algorithm for on-line bipartite match- ing. InProceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990

    1990

  45. [53]

    Matching algorithms: Fundamentals, ap- plications and challenges.IEEE Transactions on Emerg- ing Topics in Computational Intelligence, 5(3):332–350, 2021

    Jing Ren, Feng Xia, Xiangtai Chen, Jiaying Liu, Min- gliang Hou, Ahsan Shehzad, Nargiz Sultanova, and Xi- angjie Kong. Matching algorithms: Fundamentals, ap- plications and challenges.IEEE Transactions on Emerg- ing Topics in Computational Intelligence, 5(3):332–350, 2021

    2021

  46. [54]

    Paths, trees, and flowers.Canadian Jour- nal of mathematics, 17:449–467, 1965

    Jack Edmonds. Paths, trees, and flowers.Canadian Jour- nal of mathematics, 17:449–467, 1965

    1965

  47. [55]

    An efficient implementation of ed- monds’ algorithm for maximum matching on graphs

    Harold N Gabow. An efficient implementation of ed- monds’ algorithm for maximum matching on graphs. Journal of the ACM (JACM), 23(2):221–234, 1976

    1976

  48. [56]

    An nˆ5/2 algo- rithm for maximum matchings in bipartite graphs.SIAM Journal on computing, 2(4):225–231, 1973

    John E Hopcroft and Richard M Karp. An nˆ5/2 algo- rithm for maximum matchings in bipartite graphs.SIAM Journal on computing, 2(4):225–231, 1973

    1973

  49. [57]

    Ano( p |v||e|) algo- ithm for finding maximum matching in general graphs

    Silvio Micali and Vijay V Vazirani. Ano( p |v||e|) algo- ithm for finding maximum matching in general graphs. In21st Annual symposium on foundations of computer science (Sfcs 1980), pages 17–27. IEEE, 1980

    1980

  50. [58]

    A new approach to maximum matching in general graphs

    Norbert Blum. A new approach to maximum matching in general graphs. InAutomata, Languages and Program- ming: 17th International Colloquium Warwick Univer- sity, England, July 16–20, 1990 Proceedings 17, pages 586–597. Springer, 1990

    1990

  51. [59]

    Faster scaling algorithms for general graph matching problems.Journal of the ACM (JACM), 38(4):815–853, 1991

    Harold N Gabow and Robert E Tarjan. Faster scaling algorithms for general graph matching problems.Journal of the ACM (JACM), 38(4):815–853, 1991

    1991

  52. [60]

    Generalization of the trotter-lie for- mula.Integral Equations and Operator Theory, 4:366– 415, 1981

    Michel L Lapidus. Generalization of the trotter-lie for- mula.Integral Equations and Operator Theory, 4:366– 415, 1981

    1981

  53. [61]

    Paulievolutiongate.https://docs.quantum

    IBM. Paulievolutiongate.https://docs.quantum. ibm.com/api/qiskit/qiskit.circuit.library. PauliEvolutionGate

  54. [62]

    Qiskit transpiler.https://docs.quantum.ibm

    IBM. Qiskit transpiler.https://docs.quantum.ibm. com/api/qiskit/transpiler, 2024. Accessed: 2025

    2024

  55. [63]

    net- workx.generators.random graphs.gnp random graph

    NetworkX Developers. net- workx.generators.random graphs.gnp random graph. https://networkx.org/documentation/stable/ reference/generated/networkx.generators.random_ graphs.gnp_random_graph.html, 2024. Accessed: 2025

    2024

  56. [64]

    Commuting decom- positions of complete graphs.Journal of Combinatorial Designs, 15(2):133–142, 2007

    Saieed Akbari and Allen Herman. Commuting decom- positions of complete graphs.Journal of Combinatorial Designs, 15(2):133–142, 2007

    2007

  57. [65]

    Semi-perfect 1-factorizations of the hypercube.Discrete Mathematics, 342(6):1696–1702, 2019

    Natalie C Behague. Semi-perfect 1-factorizations of the hypercube.Discrete Mathematics, 342(6):1696–1702, 2019

    2019

  58. [66]

    On strongly hamiltonian complete bipartite graphs.Ars Combin, 9:43–46, 1980

    PJ Laufer. On strongly hamiltonian complete bipartite graphs.Ars Combin, 9:43–46, 1980

    1980

  59. [67]

    Com- mutativity of the adjacency matrices of graphs.Discrete mathematics, 309(3):595–600, 2009

    Saieed Akbari, F Moazami, and A Mohammadian. Com- mutativity of the adjacency matrices of graphs.Discrete mathematics, 309(3):595–600, 2009

    2009

  60. [68]

    Random compiler for fast hamiltonian simulation.Physical review letters, 123(7):070503, 2019

    Earl Campbell. Random compiler for fast hamiltonian simulation.Physical review letters, 123(7):070503, 2019

    2019

  61. [69]

    Decomposition of sparse amplitude permutation gates with application to preparation of sparse clustered quantum states.arXiv preprint arXiv:2504.08705, 2025

    Igor Gaidai and Rebekah Herrman. Decomposition of sparse amplitude permutation gates with application to preparation of sparse clustered quantum states.arXiv preprint arXiv:2504.08705, 2025. 15 Appendix A: Operator norm convergence plots Figures 6 and 7 show the operator 2-nor...

    2025 arXiv

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.