⚛️ quantum physics

Simplification Rules for Continuous-Time Quantum Walks on Dynamic Graphs

This paper introduces simplification rules and graph rewrite techniques for continuous-time quantum walks on dynamic graphs, enabling the reduction of redundant Hamiltonian sequences and facilitating transpilation between the circuit and dynamic graph models.

Original authors: Mostafa Atallah, Daniel Dilley, Jishnu Mahmud, Zain H Saleem, Rebekah Herrman

Published 2026-09-17

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Mostafa Atallah, Daniel Dilley, Jishnu Mahmud, Zain H Saleem, Rebekah Herrman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the realm of quantum computing, information is processed not by the steady clicks of classical switches, but by the fluid evolution of particles that can exist in multiple states at once. One powerful way to describe how these particles move and interact is through a concept called a continuous-time quantum walk. Imagine a particle moving across a network of connected points, or a graph, where its path is determined not by a pre-set list of instructions, but by the natural laws of physics governing its journey. In a static version of this system, the network of connections remains fixed, and the particle evolves over time. However, a more flexible approach allows the network itself to change. By rapidly altering which points are connected to which, researchers can guide the particle to perform specific tasks, effectively turning the changing shape of the network into a series of logical operations. This dynamic approach offers a universal way to build quantum computers, but it comes with a significant challenge: the sequences of changes required to perform even simple tasks can become incredibly long and filled with unnecessary steps, much like a travel itinerary that includes backtracking and redundant stops.

A team of researchers has now developed a new set of rules to streamline these complex sequences, making them shorter and more efficient without changing the final result. The team, working across institutions in the United States and Egypt, focused on the problem of "redundancy" in these dynamic graph sequences. In the standard model of quantum computing, engineers use "circuit identities"—known shortcuts that replace a long string of operations with a single, simpler one. This new work brings that same logic to the dynamic graph framework. The researchers demonstrated how to take a long, winding sequence of changing graphs and collapse it into a much shorter path that does the exact same job. They achieved this by identifying specific patterns where different parts of the sequence could be swapped, merged, or removed entirely. For instance, they found that if two graphs in a sequence commute—meaning the order in which they are applied does not matter—their positions can be swapped to facilitate simplification. They also discovered that certain sequences of graphs that look different on paper actually produce the same final state, allowing them to be replaced by a single, simpler graph.

The paper introduces several new ways to construct fundamental building blocks of quantum computing, known as gates, using these dynamic graphs. Previously, creating certain types of gates, such as those that rotate the state of a particle or apply a specific phase shift, required complex arrangements. The authors showed how to build these gates using simple graphs with just two points and specific connections, such as a single line between them or a loop on one point. They provided explicit instructions for creating these gates and even showed how to take a complex gate and break it down into its "n-th root," a mathematical operation that allows a gate to be applied partially. This is particularly useful for fine-tuning quantum operations. To prove their rules work, the team walked through concrete examples, taking a known sequence of graphs that performed a specific operation and showing step-by-step how their new rules could reduce it to a much simpler form. In one case, a sequence involving seven different graphs was reduced to just three, while still performing the exact same logical function.

Beyond simplifying existing sequences, the researchers also introduced new rules for combining graphs. They found that if a set of graphs share specific properties, such as having edges that do not interfere with each other, they can be merged into a single graph that evolves for a calculated amount of time. This is akin to realizing that three separate short trips can be replaced by one longer, direct journey. The team also showed how to move "loops"—connections that a point has to itself—throughout a sequence of graphs, allowing them to be grouped together or cancelled out. These techniques are not just theoretical exercises; they have practical implications for building better quantum computers. By reducing the number of steps required to run an algorithm, these simplification rules can lead to circuits that are shorter and require fewer physical connections, which in turn reduces the chance of errors. The authors suggest that these rules could serve as the foundation for "transpilers," software tools that automatically convert quantum algorithms from one format to another, choosing the most efficient path for a given task. While the list of rules presented is not exhaustive, and the researchers acknowledge that more simplifications may exist, this work provides a crucial toolkit for making the dynamic graph approach to quantum computing more practical and manageable.

Technical Summary: Simplification Rules for Continuous-Time Quantum Walks on Dynamic Graphs

Problem Statement
Continuous-Time Quantum Walks (CTQWs) on dynamic graphs offer a universal framework for quantum computation where quantum gates are realized as sequences of time-evolving graph Hamiltonians. While this framework provides clear equivalences to the standard circuit model and algorithms like QAOA, straightforward constructions of these dynamic graph sequences often result in long, redundant sequences that are inefficient for implementation. Although previous research has identified specific simplification techniques for dynamic graph sequences (e.g., adding isolated vertices or decomposing graphs into matchings), existing lists of simplification rules are not comprehensive. There is a recognized need for a more robust set of "graph rewrite rules" that can shorten dynamic graph sequences while preserving the implemented unitary, analogous to circuit identities in the gate model. This work addresses the gap in available simplification techniques and the lack of explicit CTQW realizations for certain standard gates.

Methodology
The authors utilize the adjacency matrix formalism where the Hamiltonian of a graph $G$ is its adjacency matrix $H_G$ . A CTQW on a dynamic graph sequence $\{(G_k, t_k)\}$ is defined by the evolution operator $\prod_k e^{-iH_k t_k}$ . The methodology involves:

Deriving Gate Equivalents: Constructing specific dynamic graph sequences that implement standard single-qubit gates (Phase, Rotation, and Identity gates) and the $n$ -th root of arbitrary unitaries.
Developing Rewrite Rules: Identifying algebraic and structural properties of graph sequences (such as commutativity, subgraph relationships, and specific time intervals) that allow for the reduction of sequence length or propagation time.
Verification: Proving the equivalence of new sequences and simplification rules through matrix exponentiation and spectral analysis, often utilizing the axis-angle representation of $SU(2)$ and De Moivre's theorem.

Key Contributions

New Gate Realizations:
- Identity and Phase Gates: The paper provides explicit dynamic graph constructions for the Identity gate (as a sequence of two graphs), $iI$ , $-iI$ , and the general Phase gate $P(\theta)$ and its conjugate transpose $P^\dagger(\theta)$ .
- Rotation Gates: New constructions are presented for $R_y(\alpha)$ and $R_z(\alpha)$ . Specifically, $R_z(\alpha)$ is shown to require two graphs (self-loops on $|0\rangle$ and $|1\rangle$ ) for an exact, global-phase-free implementation, while $R_y(\alpha)$ is decomposed via an $S R_x(\alpha) S^\dagger$ sequence.
- $n$ -th Roots of Unitaries: The authors derive the dynamic graph sequence for the principal $n$ -th root of an arbitrary single-qubit gate $U^{1/n}$ . Unlike direct parameter scaling, this derivation uses the spectral decomposition of $U$ in axis-angle form. The rotation angle $\beta$ is scaled to $\beta/n$ , and the global phase is scaled to $\alpha/n$ , while the rotation axis $\hat{a}$ is preserved. This allows for the construction of roots of Pauli-axis gates (e.g., $Z^{1/2} = S$ , $Z^{1/4} = T$ ) and more complex gates like $\sqrt{H}$ .
Five New Simplification Rules:
The paper introduces five new graph rewrite rules (Observations IV.1 through IV.5) that reduce sequence complexity:
1. Commutativity of Self-Loops and Edges: A rule allowing the swapping of a self-loop on one vertex with an edge connecting two vertices under specific time conditions ( $t_{jk} = (2m+1)\pi/2$ ).
2. Combining Commuting Subgraphs: A rule for combining a sequence of commuting subgraphs with equal norms into a single graph, provided edges appear a consistent number of times across the subgraphs.
3. Pulling Self-Loops Through Edges: A rule demonstrating that a self-loop on a vertex can be "pulled" through an edge connecting two vertices if the edge evolution time is an odd multiple of $\pi/2$ .
4. Conjugating Self-Loops by Edges: A rule showing that a sequence of a self-loop, an edge (at time $(2k+1)\pi$ ), and the self-loop again is equivalent to just the self-loop, effectively absorbing phases into edges.
5. Absorbing Edge Evolution into Self-Loops: A rule stating that a self-loop sequence followed by an edge evolution at time $\pi$ is equivalent to a single self-loop sequence with an adjusted time ( $t + \pi$ ).

Results
The authors demonstrate the utility of these rules through worked examples.

Circuit Reduction: The paper shows how a sequence representing $HZH$ (which simplifies to the $X$ gate) can be reduced from a 7-graph sequence to a 3-graph sequence using the new rules.
$\sqrt{H}$ Construction: A detailed derivation is provided for the $\sqrt{H}$ gate as a length-3 CTQW. The authors verify that squaring this dynamic graph sequence yields the $H$ gate (up to a tracked global phase), confirming the validity of the $n$ -th root construction.
Transpilation Primitives: The new gates and rules are positioned as primitives for transpilation, enabling the conversion between the circuit model and the dynamic graph framework. This is particularly relevant for algorithms like sparse state preparation and Hamiltonian simulation, where dynamic graph approaches have been shown to require fewer CX gates than Pauli decomposition methods.

Significance and Claims
The paper claims that these contributions expand the toolkit for compiler primitives in the dynamic CTQW framework. By providing a more comprehensive list of simplification rules and explicit gate equivalents, the work allows for more compact representations of quantum algorithms within the dynamic graph model. The authors explicitly state that their list of simplification rules is not exhaustive and that future work is needed to explore rules for directed graphs and to develop automated transpiler routines or AI models to determine the optimal computational form (gate model vs. dynamic CTQW) for specific applications. The work serves to bridge the gap between the theoretical universality of CTQWs and their practical implementation efficiency.

More like this