A methods preprint presents an efficient quantum-circuit framework for implementing discrete-time quantum walks on Cayley graphs. It compares a decomposed implementation of the walk's shift operator with a naive implementation that leaves the shift operator undecomposed. In an illustrative one-dimensional gate-count comparison, the decomposed implementation is listed with a model-based CNOT upper-bound entry of 362, compared with 720 for the naive implementation. The figures come from the study's stated resource model.
The document is an arXiv version 1 preprint dated 25 August 2026. Its method uses a multi-stage decomposition for one-dimensional Cayley graphs across three generating-set classes and extends the construction to d-dimensional torus graphs. The comparison is between the decomposed shift operator and a naive implementation without shift-operator decomposition.
A concrete comparison
A concrete one-dimensional example uses a Z8 Cayley graph of degree k = 7, encoded with three coin qubits and three position qubits. The naive circuit has 18 three-control rotation gates. The decomposed circuit has four three-control rotation gates, eight two-control rotation gates, five one-control rotation gates and two single-qubit rotation gates. The accompanying upper-bound CNOT entries are 720 for the naive implementation and 362 for the decomposed implementation.
The authors present the lower-control-degree decomposition as a scalable and hardware-conscious route toward practical discrete-time quantum-walk implementations.
The result depends on graph degree
The comparison changes with generating-set degree. In inverse-closed benchmarks, the decomposed implementation has a lower CNOT count for k at or below 64, but the naive version overtakes it beyond that range. In non-inverse-closed benchmarks, the decomposed implementation remains advantageous for k at or below 16. The ranges are reported for their respective benchmark classes.
System size shows a different pattern in the analyzed comparisons. At fixed k, the naive and decomposed implementations scale similarly with system size N and show a near-constant separation.
The same accounting in two dimensions
The paper also gives a two-dimensional torus example, Z16 × Z8 with degree K = 8. In that gate-count comparison, the naive implementation has 28 three-control rotation gates. The decomposed implementation has five three-control gates, 12 two-control gates, seven one-control gates and no single-qubit rotation gates. The reported CNOT values are 1120 for the naive implementation and 502 for the decomposed implementation. The example is an illustrative circuit instance.
In the d-dimensional construction, each dimension's phase-shift block can be treated as an independent one-dimensional phase-shift operator, so the one-dimensional decomposition remains applicable.
What the numbers mean
The CNOT figures are model-based upper-bound entries. The resource analysis uses the formula 16n − 24 for an n-controlled operation, together with an auxiliary qubit for local-phase correction. Accordingly, 720, 362, 1120 and 502 are model-based upper-bound entries rather than direct measurements of hardware cost. The study compares circuit constructions and gate counts under the stated model.
The paper identifies full fault-tolerant resource analysis, including T-gate cost, as an open question. Until that work is done, the reported comparison should be read as a result from the stated CNOT model and analyzed constructions, not as a complete fault-tolerant resource estimate.
Paper data and sources
Original title: Generalized Efficient Quantum Circuit Implementation of Discrete-Time Quantum Walks on Cayley Graphs
Authors: Seoyoon Kang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text