Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs

Thomas G. Wong

Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs

T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Permitting loopless isolated vertices in dynamic graphs yields simpler quantum-walk implementations of the Pauli, Hadamard, T, and CNOT gates, with the T gate reduced to a single graph.

desk verdict A modest but correct simplification of dynamic-graph quantum-walk gate constructions; fix two prose slips and accept. read the letter →

arxiv 1908.00507 v2 pith:HIHVCXHA submitted 2019-08-01 quant-ph

Thomas G. Wong This is my paper · ORCID

classification quant-ph

keywords quantumgatesgraphsverticesisolateddynamicwalkconsisting

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

A continuous-time quantum walk is a quantum particle moving on a graph, where the graph's vertices are the possible states and edges are the allowed jumps. The evolution is controlled by the graph's adjacency matrix. Previous work by Herrman and Humble showed that by switching the graph at chosen times, one can make the walk perform quantum logic gates; in their constructions, every isolated vertex carried a self-loop, so it gained a phase over time.

This paper adds a simple option: an isolated vertex with no self-loop. Because its row and column in the adjacency matrix are zero, its amplitude never changes. Using this, the author rebuilds the gate constructions with fewer vertices and fewer graph-switching steps. For example, the T gate, which multiplies one basis state by a 45-degree phase, becomes a single graph in which one vertex is looped for a specific time and the other is left untouched. A generalized phase gate covers Z, S, and T as special cases.

The paper also runs a numerical simulation of a three-qubit circuit made of alternating one- and two-qubit gates, similar to circuits used in quantum supremacy experiments, and shows the walk's probabilities match the circuit's expected outputs at each layer. The result is a cleaner bridge between abstract quantum circuits and physical quantum-walk implementations, though the simplifications are constant-factor improvements rather than a change in computational power.

Extended reading notes

Core claim

The abstract states: 'the T gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of four.' More generally, the paper claims that permitting loopless isolated vertices in dynamic graphs yields simpler implementations of the Pauli gates and the universal set {H, T, CNOT}, and these extend to multi-qubit systems.

Load-bearing premise

The Hamiltonian of the quantum walk is set equal to the graph's adjacency matrix, with jumping rate -1, rather than the graph Laplacian; this is stated in the introduction. It is this choice that makes a loopless isolated vertex have zero row and column and therefore stay constant, while a looped isolated vertex acquires phase e^{-it}. All gate times, such as 7π/4 for the T gate, are calibrated to this convention. If the physical walk were governed by the Laplacian, or if a self-loop contributed a different diagonal weight, the derived phases and gate implementations would no longer hold.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague—

A short, clean paper. It does what it claims: permitting loopless isolated vertices (K1) alongside looped ones (K1^loop) in dynamic graphs gives simpler gate constructions, and the derivations check out. The T gate becomes a single graph of two vertices instead of six graphs of eight; the Y/Z/H gates drop their ancillas; and there's a generalized phase gate that covers Z, S, and T. The three-qubit circuit simulation in Section IV matches the analytical layer states, so the central claim is supported.

The key observation is immediate from the adjacency matrix, so novelty is modest. But the paper is honest about that, and the simplified constructions are real. The arbitrary phase gate is a genuine convenience, and the multi-qubit extension is natural.

Two soft spots, both in prose. The Z-gate paragraph reverses K1 and K1^loop: it says |0> can be made stationary under K1^loop while |1> evolves under K1, which is exactly backwards. And the review of Herrman and Humble's Y gate has sign errors for |011> and |110> that don't follow from the described ancilla placement. Neither issue affects Wong's own constructions, which are derived by direct matrix exponentiation and verified by the simulation. They are revision-level fixes, not correctness problems.

The Hamiltonian convention (adjacency matrix with jumping rate -1) is stated explicitly up front, so the reader's concern about that is unfounded. No free parameters are fitted; evolution times are exact. No code is shipped, but the simulation is reproducible from the graph description.

This is a subfield paper, for people who build gate sets out of continuous-time quantum walks or study dynamic-graph simulation. It deserves a serious referee and would be accepted after minor revisions. I wouldn't cite it in my own work, but I'd point anyone doing circuit-to-walk compilation to it. The stress test's no-objection verdict holds up.

Referee Report

0 major / 4 minor

Summary. The paper considers continuous-time quantum walks on dynamic graphs, taking the Hamiltonian to be the graph adjacency matrix with jumping rate -1. It generalizes earlier work by Herrman and Humble by permitting isolated vertices to be either loopless (K1), whose amplitudes remain constant, or looped (K1^loop), which acquire a phase e^{-it}. Using this distinction, the author constructs simplified dynamic graphs for the Pauli X, Y, Z gates, the Hadamard, T, CNOT gates, and a generalized phase gate. The main claimed improvements are the elimination of ancillas for Y, Z, H, and T, and the reduction of the T gate from six static graphs on eight vertices to a single graph on two vertices. The paper validates the constructions by numerically simulating a three-qubit circuit with alternating one- and two-qubit gate layers; the simulated probabilities match the analytical state evolution at each layer.

Significance. The central results are internally consistent and derived by explicit matrix exponentiation with exact evolution times. The constructions are parameter-free, and the Hamiltonian convention is stated in the introduction, so the gate times are reproducible. The numerical simulation in Section IV verifies the phases as well as the probabilities, giving confidence that the dynamic graphs implement the intended unitaries. The simplification of the T gate and the removal of ancillas for several gates is a concrete improvement over Herrman and Humble's constructions and should be useful for translating quantum circuits into continuous-time quantum walks. The contribution is incremental rather than groundbreaking, but it is technically sound and directly relevant to the quantum walk literature.

minor comments (4)

[II. Pauli Gates, Z gate paragraph] The sentence '|0⟩ can be made stationary under K ⟲ 1 while |1⟩ evolves by a phase under K1' is reversed: according to Table I, K1^loop produces a phase e^{-it} and K1 leaves the amplitude unchanged. The construction shown in the last row of Table II is correct, but the prose should be fixed to avoid instructing readers to implement the wrong graph.
[II. Pauli Gates, Y gate review] In the review of Herrman and Humble's Y gate, the stated net evolution of the ancilla vertices is −ic2|010⟩−ic3|011⟩−ic4|100⟩+ic5|101⟩+..., but tracing the described first graph (P2 π/2) and second graph (phase −1) for these vertices gives +ic2|010⟩+ic3|011⟩+ic4|100⟩−ic5|101⟩−.... The signs on the ancilla amplitudes are therefore inconsistent with the described evolution; since the ancillas begin with zero amplitude, the conclusion that |000⟩ and |001⟩ undergo a Y gate is unaffected, but the review should be corrected.
[Table III, CNOT row] The CNOT row of Table III lists graph times 3π/2, π/2, π/2, 3π/2 and reports a total time of 2π for each implementation; the sum of these times is 4π. If the two implementations each consist of two graphs (3π/2 and π/2), the linearized table should be relabeled to distinguish the two columns; otherwise the total time should be corrected.
[I. Introduction] The phrase 'the quantum approximate approximation algorithm (QAOA)' should be 'the Quantum Approximate Optimization Algorithm (QAOA)'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the gate constructions follow from explicit matrix exponentials under a clearly stated Hamiltonian convention.

full rationale

The derivation chain is self-contained. Section I fixes the model: the Hamiltonian is the adjacency matrix with jumping rate -1, so evolution is e^{-iAt}, and this is stated explicitly. Table I then gives the exact evolutions for K1, K1^loop, P2, and C4, each obtained by exponentiating the displayed adjacency matrix. Every gate construction in Sections II and III is a direct evaluation of these elementary evolutions. For example, the T gate places |0> on a loopless isolated vertex, whose zero row and column make it stationary, and |1> on a looped isolated vertex for time 7pi/4, so |1> acquires e^{-i(7pi/4)} = e^{i pi/4}, which is exactly the T gate by definition. No parameter is fitted to a data subset, and no target gate value is smuggled in as an input; the evolution times are algebraic solutions of the phase conditions. The Section IV simulation provides an independent numerical check of the full dynamic graph against the analytically computed circuit state, including phases. Herrman and Humble's prior constructions are used only as a baseline for comparison and as a starting point for simplification; they are not premises of the new derivations, which are supported by the paper's own exponentials and the simulation. The self-citations in the reference list, such as [7], [15], and [16], are unrelated to the gate constructions and are not load-bearing. The only textual defect found is a prose typo in the Z-gate paragraph of Section II, where the roles of K1 and K1^loop are momentarily reversed; this is contradicted by Table I and by the table's own construction, so it is an expository slip rather than a circular step.

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

The central claim rests on standard quantum-walk modeling: the Hamiltonian equals the adjacency matrix, self-loops add +1 to the diagonal, and the total evolution is the product of static-graph evolutions. These are explicitly stated conventions from the cited literature, not fitted parameters. No free parameters or invented entities are introduced.

assumptions (4)

domain assumption The Hamiltonian of the continuous-time quantum walk is the adjacency matrix A of the graph, with jumping rate -1.
Stated in the introduction: 'we choose the jumping rate to be -1, so the Hamiltonian is equal to the adjacency matrix.' All gate derivations depend on this choice.
domain assumption A self-loop on a vertex contributes +1 to the diagonal of the adjacency matrix, so an isolated looped vertex evolves by e^{-it}.
Implicit in the definition of K1^loop and the phase evolution in Table I; standard convention for adjacency matrices with loops.
domain assumption The total evolution over a dynamic graph is the product of exponentials e^{-iA_j t_j} for each static graph in sequence.
The paper treats dynamic graphs as sequences of static graphs and applies Schrodinger evolution piecewise; standard in the dynamic graph model.
standard math Schrodinger's equation with hbar = 1 gives |psi(t)> = e^{-iAt}|psi(0)>.
Standard quantum mechanics; the paper explicitly sets hbar = 1 in the introduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs." pith.science (2026). https://pith.science/paper/HIHVCXHA

@misc{pith2026190800507,
  author       = {Pith},
  title        = {Pith review of: Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HIHVCXHA}},
  note         = {Machine review of arXiv:1908.00507}
}

abstract

It was recently shown that continuous-time quantum walks on dynamic graphs, i.e., sequences of static graphs whose edges change at specific times, can implement a universal set of quantum gates. This result treated all isolated vertices as having self-loops, so they all evolved by a phase under the quantum walk. In this paper, we permit isolated vertices to be loopless or looped, and loopless isolated vertices do not evolve at all under the quantum walk. Using this distinction, we construct simpler dynamic graphs that implement the Pauli gates and a set of universal quantum gates consisting of the Hadamard, $T$, and CNOT gates, and these gates are easily extended to multi-qubit systems. For example, the $T$ gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of four. We also construct a generalized phase gate, of which $Z$, $S$, and $T$ are specific instances. Finally, we validate our implementations by numerically simulating a quantum circuit consisting of layers of one- and two-qubit gates, similar to those in recent quantum supremacy experiments, using a quantum walk.

Figures

Figures reproduced from arXiv: 1908.00507 by the authors.

**Figure 2.** FIG. 2. A dynamic graph that applies the Pauli [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** FIG. 3. An alternate implementation of the Hadamard gate [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: FIG. 4. A quantum circuit of three qubits with four alter [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

**Figure 5.** Figure 5: FIG. 5. A dynamic graph on which a continuous-time quantum walk implements the circuit in Fig. 4. The eight vertices [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

**Figure 6.** Figure 6: FIG. 6. The probability at each vertex as the quantum [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

[1]

In other words, we simply swap the amplitudes at |10⟩ and|11⟩, which can be done using P2 for time π/2, but this includes an overall phase of−i

Then, it transforms c0|00⟩ +··· +c3|11⟩ to c0|00⟩ +c1|01⟩ +c3|10⟩ +c2|11⟩. In other words, we simply swap the amplitudes at |10⟩ and|11⟩, which can be done using P2 for time π/2, but this includes an overall phase of−i. To remove the phase, Herrman and Humble begin by evolving with isolated ver- tices with self-loop for time 3 π/2, as shown in the last ro...

work page
[2]

(2) Herrman and Humble’s implementation of the Hadamard gate is shown in the ﬁrst row of Table III

Thus, it transforms the superposition c0|0⟩ +c1|1⟩ to 1√ 2 (c0 +c1)|0⟩ + 1√ 2 (c0−c1)|1⟩. (2) Herrman and Humble’s implementation of the Hadamard gate is shown in the ﬁrst row of Table III. Their imple- mentation uses ancillas for a total of eight vertices or three qubits. As proved in their appendix, if the ini- tial state is c0|000⟩ +··· +c7|111⟩, their...

work page
[3]

A quantum al- gorithm for the Hamiltonian NAND tree,

E. Farhi, J. Goldstone, and S. Gutmann, “A quantum al- gorithm for the Hamiltonian NAND tree,” Theory Com- put. 4, 169–190 (2008)

work page 2008
[4]

Quantum computation and decision trees,

E. Farhi and S. Gutmann, “Quantum computation and decision trees,” Phys. Rev. A 58, 915–928 (1998)

work page 1998
[5]

Spatial search by quan- tum walk,

A. M. Childs and J. Goldstone, “Spatial search by quan- tum walk,” Phys. Rev. A 70, 022314 (2004)

work page 2004
[6]

Communication in XYZ all-to-all quantum networks with a missing link,

S. Bose, A. Casaccino, S. Mancini, and S. Severini, “Communication in XYZ all-to-all quantum networks with a missing link,” Int. J. Quantum Inf. 07, 713–723 (2009)

work page 2009
[7]

Exponential algorithmic speedup by a quantum walk,

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in Proceedings of the 35th Annual ACM Symposium on Theory of Computing , STOC ’03 (ACM, New York, NY, USA, 2003) pp. 59–68

work page 2003
[8]

Universal computation by quantum walk,

A. M. Childs, “Universal computation by quantum walk,” Phys. Rev. Lett. 102, 180501 (2009)

work page 2009

Show all 19 references

[9]

Continuous-time quan- tum walks on dynamic graphs,

R. Herrman and T. S. Humble, “Continuous-time quan- tum walks on dynamic graphs,” Phys. Rev. A 100, 012306 (2019)

2019
[10]

Lapla- cian versus adjacency matrix in quantum walk search,

T. G. Wong, L. Tarrataca, and N. Nahimov, “Lapla- cian versus adjacency matrix in quantum walk search,” Quantum Inf. Process. 15, 4029–4048 (2016)

2016
[11]

at an energy oﬀset from the other vertices (like a physical mode at a diﬀerent frequency or in the presence of a diﬀerent bias)

also changes the Hamiltonian at discrete times, cor- responding to turning on and oﬀ interactions. Quantum 3 walks on dynamic graphs are similar. Herrman and Humble’s formulation treated all isolated vertices as having self-loops (i.e., as K ⟲ 1 ’s), so their am- plitudes evol...
[12]

Perfect state transfer in quantum walks on graphs,

V. M. Kendon and C. Tamon, “Perfect state transfer in quantum walks on graphs,” J. Comput. Theor. Nanosci. 8, 422–433 (2011)

2011
[13]

M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press,
[14]

A quantum approximate optimization algorithm,

E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” arXiv:1411.4028 [quant-ph] (2014)

2014 arXiv
[15]

T. S. Humble, private communication
[16]

Complexity-Theoretic Foundations of Quantum Supremacy Experiments,

S. Aaronson and L. Chen, “Complexity-Theoretic Foundations of Quantum Supremacy Experiments,” 10 in 32nd Computational Complexity Conference (CCC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 79, edited by Ryan O’Donnell (Schloss Dagstuhl–Leibniz-Zentr...

2017
[17]

Quantum supremacy using a programmable supercon- ducting processor,

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graﬀ, K. Guerin, ...

2019
[18]

Grover search with lackadaisical quantum walks,

T. G. Wong, “Grover search with lackadaisical quantum walks,” J. Phys. A: Math. Theor. 48, 435304 (2015)

2015
[19]

Coined quantum walks on weighted graphs,

T. G. Wong, “Coined quantum walks on weighted graphs,” J. Phys. A: Math. Theor. 50, 475301 (2017)

2017

Pith tools

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

[1] [1]

In other words, we simply swap the amplitudes at |10⟩ and|11⟩, which can be done using P2 for time π/2, but this includes an overall phase of−i

Then, it transforms c0|00⟩ +··· +c3|11⟩ to c0|00⟩ +c1|01⟩ +c3|10⟩ +c2|11⟩. In other words, we simply swap the amplitudes at |10⟩ and|11⟩, which can be done using P2 for time π/2, but this includes an overall phase of−i. To remove the phase, Herrman and Humble begin by evolving with isolated ver- tices with self-loop for time 3 π/2, as shown in the last ro...

work page

[2] [2]

(2) Herrman and Humble’s implementation of the Hadamard gate is shown in the ﬁrst row of Table III

Thus, it transforms the superposition c0|0⟩ +c1|1⟩ to 1√ 2 (c0 +c1)|0⟩ + 1√ 2 (c0−c1)|1⟩. (2) Herrman and Humble’s implementation of the Hadamard gate is shown in the ﬁrst row of Table III. Their imple- mentation uses ancillas for a total of eight vertices or three qubits. As proved in their appendix, if the ini- tial state is c0|000⟩ +··· +c7|111⟩, their...

work page

[3] [3]

A quantum al- gorithm for the Hamiltonian NAND tree,

E. Farhi, J. Goldstone, and S. Gutmann, “A quantum al- gorithm for the Hamiltonian NAND tree,” Theory Com- put. 4, 169–190 (2008)

work page 2008

[4] [4]

Quantum computation and decision trees,

E. Farhi and S. Gutmann, “Quantum computation and decision trees,” Phys. Rev. A 58, 915–928 (1998)

work page 1998

[5] [5]

Spatial search by quan- tum walk,

A. M. Childs and J. Goldstone, “Spatial search by quan- tum walk,” Phys. Rev. A 70, 022314 (2004)

work page 2004

[6] [6]

Communication in XYZ all-to-all quantum networks with a missing link,

S. Bose, A. Casaccino, S. Mancini, and S. Severini, “Communication in XYZ all-to-all quantum networks with a missing link,” Int. J. Quantum Inf. 07, 713–723 (2009)

work page 2009

[7] [7]

Exponential algorithmic speedup by a quantum walk,

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in Proceedings of the 35th Annual ACM Symposium on Theory of Computing , STOC ’03 (ACM, New York, NY, USA, 2003) pp. 59–68

work page 2003

[8] [8]

Universal computation by quantum walk,

A. M. Childs, “Universal computation by quantum walk,” Phys. Rev. Lett. 102, 180501 (2009)

work page 2009