Generalized Efficient Quantum Circuit Implementation of Discrete-Time Quantum Walks on Cayley Graphs

• URL: http://arxiv.org/abs/2608.25136v1
• Date: Tue, 25 Aug 2026 20:35:46 GMT
• Title: Generalized Efficient Quantum Circuit Implementation of Discrete-Time Quantum Walks on Cayley Graphs
• Abstract summary: We introduce a systematic multi-stage decomposition of the shift operator for 1D Cayley graphs.<n>We provide explicit circuit implementations for an 8-Cayley graph and a $mathbbZ_16 times mathbbZ_8$ torus graph.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a generalized and efficient quantum circuit framework for implementing discrete-time quantum walks (DTQWs) on Cayley graphs of arbitrary dimension. Building on the Boundary QFT scheme of Razzoli et al., we introduce a systematic multi-stage decomposition of the shift operator for 1D Cayley graphs across three classes of generating sets: inverse-closed without involutions, inverse-closed with an involution, and non-inverse-closed. The decomposition hierarchically factorizes the QFT-diagonalized shift operator into structured block components, progressively reducing the control degree of the required rotation gates and replacing high-degree multi-qubit controlled operations with collections of lower-degree equivalents. We extend this construction to $d$-dimensional torus graphs and provide explicit circuit implementations for an 8-Cayley graph and a $\mathbb{Z}_{16} \times \mathbb{Z}_8$ torus graph as concrete illustrations. Gate complexity analysis using the linear CNOT scaling of Rosa et al. demonstrates that the decomposed implementation achieves a substantial reduction in upper-bound CNOT cost relative to the naive implementation within the regime $k \leq 64$ for inverse-closed graphs and $k \leq 16$ for non-inverse-closed graphs, where $k$ denotes the degree of the generating set. Benchmarking further reveals that this efficiency gain is largely insensitive to the system size $N$, identifying $k$ as the dominant resource parameter for the shift operator. These results provide a scalable and hardware-conscious pathway toward practical DTQW implementations on near-term quantum devices.

Related papers

• Quantum Circuits for Quantum Spatial Search on $d$-Dimensional Lattices [2.2336243882030025]
  We propose an explicit quantum circuit for quantum spatial search based on discrete-time quantum walks on $d$-dimensional lattices.<n>We verify that the proposed circuits reproduce the theoretical dynamics on two- and three-dimensional periodic lattices.
  arXiv  Detail & Related papers  (2026-07-21T14:51:25Z)
• Explicit Block Encodings of Discrete Laplacians with Mixed Boundary Conditions [45.88028371034407]
  Block encoding provides the standard method for accessing matrix data within quantum circuits.<n>We present a unified framework for efficiently block encoding finite-difference discretizations of the Laplacian.
  arXiv  Detail & Related papers  (2026-03-12T19:35:16Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Explicit Quantum Circuits for Simulating Linear Differential Equations via Dilation [0.0]
  We present a concrete pipeline that connects the dilation formalism with explicit quantum circuit constructions.<n>On the analytical side, we introduce a discretization of the continuous dilation operator that is tailored for quantum implementation.<n>We prove that the resulting scheme achieves a global error bound of order $O(M-3/2)$, up to exponentially small boundary effects.
  arXiv  Detail & Related papers  (2025-09-20T18:54:49Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Efficient compilation of quantum circuits using multi-qubit gates [0.0]
  We present a compilation scheme which implements a general-circuit decomposition to a sequence of Ising-type, long-range, multi-qubit entangling gates.<n>We numerically test our compilation and show that, compared to conventional realizations with two-qubit gates, our compilations improves the logarithm of quantum volume by $20%$ to $25%$.
  arXiv  Detail & Related papers  (2025-01-28T19:08:13Z)
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes [34.225996865725605]
  We develop a hardware-efficient, fault-tolerant approach to realizing quantum sampling circuits.<n>We develop a theory of second-moment properties of degree-$D$ IQP circuits for analyzing hardness and verification of random sampling.<n>Our results highlight fault-tolerant compiling as a powerful tool in co-configurable algorithms with specific error-correcting codes and realistic hardware.
  arXiv  Detail & Related papers  (2024-04-29T18:00:03Z)
• AltGraph: Redesigning Quantum Circuits Using Generative Graph Models for Efficient Optimization [2.089191490381739]
  AltGraph is a novel search-based circuit transformation approach. It generates equivalent quantum circuits using existing generative graph models. It achieves on average a 37.55% reduction in the number of gates and a 37.75% reduction in the circuit depth post-transpiling.
  arXiv  Detail & Related papers  (2024-02-23T19:01:47Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• Near-optimal quantum circuit construction via Cartan decomposition [4.900041609957432]
  We show the applicability of the Cartan decomposition of Lie algebras to quantum circuits. This approach can be used to synthesize circuits that can efficiently implement any desired unitary operation.
  arXiv  Detail & Related papers  (2022-12-25T17:01:13Z)
• Universal qudit gate synthesis for transmons [44.22241766275732]
  We design a superconducting qudit-based quantum processor. We propose a universal gate set featuring a two-qudit cross-resonance entangling gate. We numerically demonstrate the synthesis of $rm SU(16)$ gates for noisy quantum hardware.
  arXiv  Detail & Related papers  (2022-12-08T18:59:53Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Arbitrary controlled-phase gate on fluxonium qubits using differential ac-Stark shifts [1.8568045743509223]
  We show a resource-efficient control over the interaction of strongly-anharmonic fluxonium qubits. Our result demonstrates the advantages of strongly-anharmonic circuits over transmons in designing the next generation of quantum processors.
  arXiv  Detail & Related papers  (2021-03-08T00:02:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.