arXiv:2609.18463
Simplification Rules for Continuous-Time Quantum Walks on Dynamic Graphs
Mostafa Atallah, Daniel Dilley, Jishnu Mahmud, Zain H Saleem, Rebekah Herrman
Abstract
Continuous-time quantum walks (CTQWs) on dynamic graphs realize quantum gates as sequences of time-evolving graph Hamiltonians, but naive constructions produce long sequences with redundancy. Simplification rules, which are graph rewrite rules that shorten a dynamic graph sequence while preserving the unitary it implements, are the CTQW analogue of circuit identities in the gate model. In this work, we give CTQW realizations of the standard single-qubit gates and introduce new graph rewrite rules. We demonstrate the simplification rules through worked circuit reductions and outline their use as transpilation primitives for converting between the circuit model and the dynamic graph framework.
AI Summary
The paper studies how to shorten continuous-time quantum-walk (CTQW) implementations of quantum gates on dynamic graphs. In this framework, computational basis states label graph vertices, adjacency matrices serve as Hamiltonians, and a gate is implemented by a sequence of evolutions $e^{-iA_k t_k}$. The goal is to develop graph-level identities that preserve the implemented unitary while reducing sequence length or propagation time. It gives explicit constructions for phase gates, their adjoints, and single-qubit rotations: $R_z(\alpha)$ uses two self-loop graphs for an exact implementation, while $R_y(\alpha)$ uses three graphs through $S R_x(\alpha)S^\dagger$. Building on an existing three-graph construction for arbitrary single-qubit gates up to global phase, it derives a recipe for $n$-th roots using axis-angle parametrization and conversion back to Euler angles, with $\sqrt H$ as a worked example. Five rewrite rules cover moving self-loop phases across perfect-transfer edges, merging commuting subgraphs with uniform edge multiplicity, passing loops through two-vertex transfer operations, cancelling equal edge evolutions around an odd-$\pi$ loop phase, and absorbing a $\pi$ edge evolution into paired self-loops. The identities are established by matrix exponentiation, commutativity, and Pauli algebra, with illustrative reductions. The rule set is explicitly not claimed to be exhaustive. Directed-graph extensions and automated transpilation are left for future work; compiler applications are outlined rather than evaluated through an implemented optimizer or benchmark suite.
Error found: The general single-qubit root recipe loses quadrant information: for Ry(−π/2), its stated inverse Euler formulas return Ry(+π/4) as the square root instead of Ry(−π/4). The Z^(1/n) entry in Table 3 implements diag(1,e^{−iπ/n}) up to global phase, giving S† rather than the explicitly claimed S at n=2. The claimed five new simplification techniques include 'looppassing', which is merely the two-vertex specialization of 'movingselfloop'. The proof of 'movingselfloop' incorrectly evaluates the edge propagator at odd multiples of π/2, although direct multiplication confirms the rewrite identity itself. The proof of 'loopedgeshift' incorrectly uses off-diagonal matrix units for a diagonal self-loop propagator, although the rewrite identity itself is valid.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.