pith. sign in

arxiv: 2512.16400 · v2 · pith:J7WQNEE2new · submitted 2025-12-18 · 🪐 quant-ph

Coined Quantum Walks on Complex Networks for Quantum Computers

Rei Sato This is my paper

Pith reviewed 2026-05-16 21:23 UTC · model grok-4.3

classification 🪐 quant-ph
keywords coined quantum walkscomplex networksquantum circuitsdual-register encodingcircuit depth scalingNISQ hardwareErdos-RenyiBarabasi-Albert
0
0 comments X

The pith

Dual-register encoding lets quantum circuits run coined walks on complex networks with depth scaling as N to the 1.9

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

The paper develops a quantum circuit that implements coined quantum walks on networks whose nodes have varying numbers of connections. It encodes the walk using two registers so the shift operator stays simple even when degrees differ. Numerical tests on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert networks show the total circuit depth grows roughly as N to the power 1.9, independent of the chosen topology. Small instances run on IBM superconducting hardware confirm that the circuits can be executed, though noise limits the scale. The scaling result indicates the approach remains feasible once fault-tolerant hardware arrives.

Core claim

The central claim is that a dual-register encoding simplifies the shift operator for degree-varying networks and yields coined quantum walk circuits whose depth scales as approximately N to the 1.9 for Erdős-Rényi, Watts-Strogatz, and Barabási-Albert graphs, with small-N demonstrations on superconducting hardware showing that hardware-aware optimization can improve fidelity for the larger tested instances.

What carries the argument

Dual-register encoding, which uses separate registers for position and coin degrees of freedom to keep the shift operator independent of individual node degrees.

If this is right

  • The same circuit construction applies unchanged to any network topology.
  • The polynomial depth makes the method viable for fault-tolerant quantum computers once error correction is available.
  • Walk-based quantum algorithms on real-world irregular graphs become implementable without topology-specific rewrites.
  • Small-scale hardware runs already show measurable improvement in variation distance when connectivity-aware optimization is applied.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same encoding may allow quantum simulation of dynamical processes on empirical networks such as epidemic spread or information diffusion.
  • Extending the method to directed or weighted networks would require only minor adjustments to the coin operator.
  • Hybrid classical-quantum schemes could use the circuit as a subroutine inside larger variational algorithms for network analysis.

Load-bearing premise

The dual-register encoding faithfully reproduces the coined walk dynamics on arbitrary degree sequences without introducing systematic bias or extra depth that grows faster than the reported scaling for large N.

What would settle it

A simulation or hardware run on a network with N greater than 20 that produces circuit depth growing faster than N squared or that yields probability distributions deviating from the expected coined-walk evolution by more than a few percent.

Figures

Figures reproduced from arXiv: 2512.16400 by Rei Sato.

Figure 1
Figure 1. Figure 1: The definition of coined quantum walk on com [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The quantum circuit for implementing the coined qu [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) The node-dependent depths of coined quan [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 3
Figure 3. Figure 3: The probability histogram of quantum walk on [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Time-evolution of the probability distribution fo [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Quantum circuit for the coined quantum walk synthe [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
read the original abstract

We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erd\H{o}s-R\'enyi, Watts-Strogatz, and Barab\'asi-Albert models. The results show that the circuit depth scales as approximately $N^{1.9}$ regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with $N=4$ and $N=8$. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a dual-register encoding for coined quantum walks on complex networks with heterogeneous node degrees, implements the resulting circuits in the Qmod high-level language, and reports numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert ensembles showing circuit depth scaling as approximately N^{1.9} independent of topology. Small-scale executions on ibm_torino for N=4 and N=8 Watts-Strogatz graphs are also presented, with hardware-aware optimization yielding modest improvements in variation distance and Hellinger fidelity.

Significance. If the reported polynomial scaling is asymptotically robust, the work supplies a concrete, topology-agnostic circuit construction for quantum walks on irregular graphs, a setting relevant to network-based quantum algorithms. The explicit Qmod implementation and cross-ensemble numerical evidence are strengths; the small-N hardware runs provide initial feasibility data but do not yet constrain large-scale performance.

major comments (2)
  1. [Results / scaling analysis] Results section (scaling plots and fits): the central claim that depth scales as N^{1.9} independent of topology rests on empirical Qmod depth measurements for modest N. For Barabási-Albert graphs, where maximum degree grows as N^{1/2}, the coin-register width and the controlled-neighbor lookup decomposition must be shown not to introduce super-quadratic overhead; no closed-form depth expression or asymptotic analysis of the dual-register shift operator is supplied to confirm the exponent remains stable.
  2. [Methods / circuit design] Circuit-construction section (dual-register encoding): the paper states that the encoding yields a simplified shift operator that faithfully reproduces the coined-walk dynamics for arbitrary degree sequences, yet no explicit verification (e.g., operator-norm distance between the implemented unitary and the standard walk operator on a small irregular graph) is given to exclude systematic bias or extra depth that grows faster than the reported scaling.
minor comments (2)
  1. [Abstract / hardware experiments] Abstract and results: variation distance and Hellinger fidelity for the ibm_torino runs are reported without error bars, shot counts, or statistical details, making quantitative assessment of the hardware improvements difficult.
  2. [Methods] Notation: the dual-register encoding is introduced without a compact diagram or explicit mapping table showing how the coin and position registers are allocated for a node of degree d; this would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive report. The comments help clarify the presentation of our empirical scaling results and the need for explicit verification of the dual-register construction. We respond to each major comment below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [Results / scaling analysis] Results section (scaling plots and fits): the central claim that depth scales as N^{1.9} independent of topology rests on empirical Qmod depth measurements for modest N. For Barabási-Albert graphs, where maximum degree grows as N^{1/2}, the coin-register width and the controlled-neighbor lookup decomposition must be shown not to introduce super-quadratic overhead; no closed-form depth expression or asymptotic analysis of the dual-register shift operator is supplied to confirm the exponent remains stable.

    Authors: We acknowledge that the N^{1.9} scaling is obtained from numerical Qmod depth measurements rather than a closed-form derivation. For Barabási-Albert graphs the maximum degree grows as O(N^{1/2}), so the coin register requires only O(log N) qubits; the dual-register shift is realized by a sequence of controlled-SWAP and neighbor-selection gates whose depth is linear in the (bounded) average degree plus the logarithmic coin width. This structure prevents super-quadratic growth, consistent with the observed exponent across all three ensembles. In the revised manuscript we will add an explicit breakdown of the depth contributions from the coin operator, the dual-register preparation, and the controlled shift, together with a short argument bounding the overhead for power-law degree sequences. revision: partial

  2. Referee: [Methods / circuit design] Circuit-construction section (dual-register encoding): the paper states that the encoding yields a simplified shift operator that faithfully reproduces the coined-walk dynamics for arbitrary degree sequences, yet no explicit verification (e.g., operator-norm distance between the implemented unitary and the standard walk operator on a small irregular graph) is given to exclude systematic bias or extra depth that grows faster than the reported scaling.

    Authors: We agree that an explicit numerical check strengthens the claim. The dual-register encoding stores node degrees in the second register and uses them to select the correct neighbor via controlled operations, so the implemented unitary is constructed to be identical to the standard coined-walk operator on any graph. In the revision we will include a verification subsection that computes the operator-norm distance (and the diamond distance) between the Qmod-generated circuit and the ideal walk operator for a small irregular graph (e.g., a 5-node Barabási-Albert realization), confirming that the distance is at the level of floating-point precision and that no additional depth is incurred beyond the reported scaling. revision: yes

Circularity Check

0 steps flagged

No significant circularity; reported scaling is empirical output of explicit circuit construction and simulation

full rationale

The paper's central result (depth ~N^{1.9}) is obtained by implementing the dual-register coined-walk circuit in Qmod, decomposing the shift operator for each topology, and measuring depth on concrete Erdős-Rényi, Watts-Strogatz and Barabási-Albert instances. No equation defines the depth in terms of itself, no parameter is fitted to the target scaling, and no self-citation is invoked as a uniqueness theorem or ansatz that forces the exponent. The derivation chain consists of standard gate decomposition plus numerical measurement; these steps are independent of the final scaling number and do not reduce to it by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The design rests on standard quantum circuit axioms and the definition of coined walks; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Unitary evolution of coined quantum walks on graphs
    Invoked as the target dynamics the circuit must implement.

pith-pipeline@v0.9.0 · 5502 in / 1238 out tokens · 29031 ms · 2026-05-16T21:23:01.812443+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · 1 internal anchor

  1. [1]

    Marsh and J

    S. Marsh and J. B. Wang. Combinatorial opti- mization via quantum walks. Physical Review A , 101(5):052319, 2020. 7

    work page 2020

  2. [2]

    A quantum walk model of financial op- tions

    David Orrell. A quantum walk model of financial op- tions. Wilmott, 2021(112):62–69, 2021

    work page 2021

  3. [3]

    Qfold: quan- tum walks and deep learning to solve protein folding

    Pablo Antonio Moreno Casares, Roberto Campos, and Miguel Angel Martin-Delgado. Qfold: quan- tum walks and deep learning to solve protein folding. Quantum Science and Technology , 7(2):025013, 2022

    work page 2022

  4. [4]

    Childs and Jeffrey Goldstone

    Andrew M. Childs and Jeffrey Goldstone. Spatial search by quantum walk. Phys. Rev. A , 70:022314, Aug 2004

    work page 2004

  5. [5]

    Aharonov, L

    Y. Aharonov, L. Davidovich, and N. Zagury. Quan- tum random walks. Phys. Rev. A , 48:1687–1690, Aug 1993

    work page 1993

  6. [6]

    M. Szegedy. Quantum speed-up of markov chain based algorithms. In 45th Annual IEEE Symposium on Foundations of Computer Science , pages 32–41, 2004

    work page 2004

  7. [7]

    Coins make quantum walks faster

    Andris Ambainis, Julia Kempe, and Alexander Rivosh. Coins make quantum walks faster. In Proceed- ings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’05, page 1099–1108, USA, 2005. Society for Industrial and Applied Math- ematics

    work page 2005

  8. [8]

    Universal scaling hypoth- esis of quantum spatial search in complex networks

    Rei Sato, Tetsuro Nikuni, Kayoko Nohara, Giorgio Salani, and Shohei Watabe. Universal scaling hypoth- esis of quantum spatial search in complex networks. Phys. Rev. Res. , 6:043119, Nov 2024

    work page 2024

  9. [9]

    Discrete-time quantum walk algo- rithm for ranking nodes on a network

    Prateek Chawla, Roopesh Mangal, and C Madaiah Chandrashekar. Discrete-time quantum walk algo- rithm for ranking nodes on a network. Quantum In- formation Processing, 19:1–21, 2020

    work page 2020

  10. [10]

    Quan- tum google in a complex network

    Giuseppe Davide Paparo, Markus Müller, Francesc Comellas, and Miguel Angel Martin-Delgado. Quan- tum google in a complex network. Scientific reports , 3(1):2773, 2013

    work page 2013

  11. [11]

    Quantum walk neural networks with feature dependent coins

    Stefan Dernbach, Arman Mohseni-Kabir, Siddharth Pal, Miles Gepner, and Don Towsley. Quantum walk neural networks with feature dependent coins. Applied Network Science , 4:1–16, 2019

    work page 2019

  12. [12]

    Vqne: Varia- tional quantum network embedding with application to network alignment

    Xinyu Ye, Ge Yan, and Junchi Yan. Vqne: Varia- tional quantum network embedding with application to network alignment. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 3105–3115, 2023

    work page 2023

  13. [13]

    Qwalkvec: Node embedding by quan- tum walk

    Rei Sato, Shuichiro Haruta, Kazuhiro Saito, and Mori Kurokawa. Qwalkvec: Node embedding by quan- tum walk. In Pacific-Asia Conference on Knowledge Discovery and Data Mining , pages 93–104. Springer, 2024

    work page 2024

  14. [14]

    A quantum approach to walk on networks

    Anurag Singh and Binshumesh Sachan. A quantum approach to walk on networks. In 2021 6th Inter- national Conference on Signal Processing, Computing and Control (ISPCC) , pages 636–643. IEEE, 2021

    work page 2021

  15. [15]

    Coined quantum walk on a quantum network

    Jigyen Bhavsar, Shashank Shekhar, and Siddhartha Santra. Coined quantum walk on a quantum network. Physical Review A , 110(5):052428, 2024

    work page 2024

  16. [16]

    Quan- tum walks and dirac cellular automata on a pro- grammable trapped-ion quantum computer

    C Huerta Alderete, Shivani Singh, Nhung H Nguyen, Daiwei Zhu, Radhakrishnan Balu, Christopher Mon- roe, CM Chandrashekar, and Norbert M Linke. Quan- tum walks and dirac cellular automata on a pro- grammable trapped-ion quantum computer. Nature communications, 11(1):3720, 2020

    work page 2020

  17. [17]

    Implementation of quantum walks on ibm quantum computers

    Frank Acasiete, Flavia P Agostini, J Khatibi Mo- qadam, and Renato Portugal. Implementation of quantum walks on ibm quantum computers. Quan- tum Information Processing , 19:1–20, 2020

    work page 2020

  18. [18]

    Circuit implementation of discrete-time quantum walks via the shunt decomposition method

    Allan Wing-Bocanegra and Salvador E Venegas- Andraca. Circuit implementation of discrete-time quantum walks via the shunt decomposition method. Quantum Information Processing , 22(3):146, 2023

    work page 2023

  19. [19]

    Circuit implemen- tation and analysis of a quantum-walk based search complement algorithm

    Allan Wing-Bocanegra, Carlos E Quintero-Narvaez, and Salvador E Venegas-Andraca. Circuit implemen- tation and analysis of a quantum-walk based search complement algorithm. Scientific Reports , 15(1):4865, 2025

    work page 2025

  20. [20]

    Efficient implementation of discrete-time quantum walks on quantum computers

    Luca Razzoli, Gabriele Cenedese, Maria Bondani, and Giuliano Benenti. Efficient implementation of discrete-time quantum walks on quantum computers. Entropy, 26(4):313, 2024

    work page 2024

  21. [21]

    Efficient circuit implementa- tion of quantum walks on non-degree-regular graphs

    T Loke and JB Wang. Efficient circuit implementa- tion of quantum walks on non-degree-regular graphs. Physical Review A , 86(4):042338, 2012

    work page 2012

  22. [22]

    Efficient quantum circuits for continuous-time quantum walks on com- posite graphs

    Thomas Loke and Jingbo B Wang. Efficient quantum circuits for continuous-time quantum walks on com- posite graphs. Journal of Physics A: Mathematical and Theoretical, 50(5):055303, 2017

    work page 2017

  23. [23]

    Quantum circuits for discrete-time quantum walks with position-dependent coin operator

    Ugo Nzongani, Julien Zylberman, Carlo-Elia Doncec- chi, Armando Pérez, Fabrice Debbasch, and Pablo Ar- nault. Quantum circuits for discrete-time quantum walks with position-dependent coin operator. Quan- tum Information Processing , 22(7):270, 2023

    work page 2023

  24. [24]

    Ef- ficient circuit implementations of continuous-time quantum walks for quantum search

    Renato Portugal and Jalil Khatibi Moqadam. Ef- ficient circuit implementations of continuous-time quantum walks for quantum search. Entropy, 27(5):454, 2025

    work page 2025

  25. [25]

    Continuous-time quantum walk on a random graph using quantum cir- cuits

    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

    work page internal anchor Pith review arXiv 2025

  26. [26]

    Im- plementation of a continuous-time quantum walk on a sparse graph

    Zhaoyang Chen, Guanzhong Li, and Lvzhou Li. Im- plementation of a continuous-time quantum walk on a sparse graph. Phys. Rev. A , 110:052215, Nov 2024

    work page 2024

  27. [27]

    Circuit Implementation of Discrete-Time Quantum Walks on Complex Net- works

    Rei Sato and Kazuhiro Saito. Circuit Implementation of Discrete-Time Quantum Walks on Complex Net- works . In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) , pages 376–377, Los Alamitos, CA, USA, September 2024. IEEE Computer Society

    work page 2024

  28. [28]

    Col- lective dynamics of ‘small-world’networks

    Duncan J Watts and Steven H Strogatz. Col- lective dynamics of ‘small-world’networks. nature, 393(6684):440–442, 1998

    work page 1998

  29. [29]

    Emer- gence of scaling in random networks

    Albert-László Barabási and Réka Albert. Emer- gence of scaling in random networks. science, 286(5439):509–512, 1999

    work page 1999

  30. [30]

    On random graphs i

    P ERDdS and A R&wi. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959

    work page 1959

  31. [31]

    arXiv:2502.19368 [quant-ph] doi:10.48550/arXiv.2502.19368 Finn Voichick, Liyi Li, Robert Rand, and Michael Hicks

    Matan Vax, Peleg Emanuel, Eyal Cornfeld, Israel Re- ichental, Ori Opher, Ori Roth, Tal Michaeli, Lior Pre- minger, Lior Gazit, Amir Naveh, et al. Qmod: Ex- pressive high-level quantum modeling. arXiv preprint arXiv:2502.19368, 2025

    work page arXiv 2025

  32. [32]

    De- sign and synthesis of scalable quantum programs

    Tomer Goldfriend, Israel Reichental, Amir Naveh, Lior Gazit, Nadav Yoran, Ravid Alon, Shmuel Ur, Shahak Lahav, Eyal Cornfeld, A vi Elazari, et al. De- sign and synthesis of scalable quantum programs. arXiv preprint arXiv:2412.07372 , 2024

    work page arXiv 2024

  33. [33]

    Quantum walks: a comprehensive review

    Salvador Elías Venegas-Andraca. Quantum walks: a comprehensive review. Quantum Information Pro- cessing, 11(5):1015–1106, 2012

    work page 2012

  34. [34]

    Hardware-aware synthe- sis

    Classiq Technologies. Hardware-aware synthe- sis. https://docs.classiq.io/latest/user-guide/ synthesis/hardware-aware-synthesis/, 2024. Ac- cessed on 15.11.2025

    work page 2024

  35. [35]

    Quantum computation and quantum information

    Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information . Cambridge university press, 2010

    work page 2010

  36. [36]

    Coined Quantum Walks on Complex Networks for Quantum Computers

    Google Quantum AI. Suppressing quantum errors by scaling a surface code logical qubit. Nature, 614(7949):676–681, 2023. 8 Supplemental Material for "Coined Quantum Walks on Complex Networks for Quantum Computers" Appendix A: Implementation with Qmod Here, we provide a step-by-step explanation of the Qmod impl ementation corresponding to the mathematical m...

    work page 2023

  37. [37]

    The operato r ˆU1 creates a uniform superposition over all nodes in the first register x (representing node i)

    State Preparation The preparation of the state involves two steps. The operato r ˆU1 creates a uniform superposition over all nodes in the first register x (representing node i). ˆU1 |0⟩n = 1√ N N − 1∑ i=0 |i⟩ (A1) In Qmod, if N is a power of 2, this is a simple Hadamard transform. Otherwise, we use inplace_prepare_state with a uniform probability distribu...

    work page

  38. [38]

    Coin Operator The coin operator ˆC applies a local Grover diffusion operator at each node. Mathe matically, for each node i, the local coin ˆCi is: ˆCi = 2 ˆU (i) 2 |0⟩ ⟨0|( ˆU (i) 2 )† − ˆI (A3) In Qmod, the grover_diffuser function automatically implements the reflection 2 |s⟩ ⟨s| − I given a state preparation oracle. Here, the oracle is exactly the inpla...

    work page

  39. [39]

    ˆS |i⟩ |j⟩ = |j⟩ |i⟩ (A4) This corresponds to a swap of the two quantum registers x and y

    Shift Operator The shift operator performs a flip-flop shift by swapping the p osition and direction registers. ˆS |i⟩ |j⟩ = |j⟩ |i⟩ (A4) This corresponds to a swap of the two quantum registers x and y. In Qmod, this is concisely expressed using the multiswap gate. @qfunc def my_shift ( x : QNum [ num_qubits ] , y : QNum [ num_qubits ]) : multiswap (x , y )

    work page

  40. [40]

    The power function in Qmod efficiently implements the repetition of the step unitary U t = ( ˆS ˆC)t

    Whole Circuit Finally, the discrete-time quantum walk is constructed by i teratively applying the coin and shift operators. The power function in Qmod efficiently implements the repetition of the step unitary U t = ( ˆS ˆC)t. @qfunc def d i s c r e t e _ q u a n t u m _ w a l k ( time : CInt , coin_qfun c s : QCallable [ QNum , QNum ] , s h i f t _ q f u n ...

    work page

  41. [41]

    IBM Quantum

    Circuit Synthesis We employ two distinct synthesis strategies to generate the final quantum circuits: hardware-agnostic syn- thesis for simulation and hardware-aware synthesis for exe cution on real devices. For numerical simulations and logical verification, we gene rate the circuit without targeting a specific backend. This approach optimizes for general l...

    work page

  42. [42]

    The show() function opens an interactive circuit viewer, allowing for a hierarchical inspection of the block- encoded operators, as shown in Fig

    Visualization Finally, Qmod provides built-in tools to visualize the synt hesized quantum circuit and analyze its properties. The show() function opens an interactive circuit viewer, allowing for a hierarchical inspection of the block- encoded operators, as shown in Fig. 6. This command generate s the quantum circuit diagrams presented in 11 the main text...

    work page