Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Certifying When Temporal Order Can Be Ignored in Continuous-Time Quantum Walks

Madjid Eshaghi Gordji, Mohamadali Berahman

Published Oct 28, 2026• 0 citations
PDF (CC BY)Publisher

Abstract

Abstract Continuous-time quantum walks on dynamic graphs are generated by an ordered sequence of Hamiltonians. Replacing that sequence by one average Hamiltonian can simplify analysis and control, but it may change the transported quantum state. We study this replacement in the single-excitation sector for sequential, undirected edge couplings. Nonzero edge Hamiltonians commute precisely when their edges coincide or are vertex-disjoint, giving a pulse-independent exact reduction for schedules supported on a matching. For general schedules, we derive a nonperturbative spectral-norm bound between the ordered unitary and the exponential of the integrated Hamiltonian. In the edge model, the bound becomes a weighted count of temporal wedges—pairs of distinct event edges meeting at one vertex—and is computable in expected linear time. The same certificate controls state-transfer amplitudes and probabilities, process fidelity, average gate fidelity, and sensitivity to event reordering. A weak-pulse expansion shows that its quadratic scaling is generally sharp. An exact three-vertex calculation and reproducible numerical tests illustrate when the certificate is informative and when cancellation makes it conservative. The result is a directly checkable sufficient condition for replacing a dynamic quantum walk by its weighted aggregate.

DOI
10.21203/rs.3.rs-10777819/v1

Related papers

Control of vertex probability via edge-weight modulation in continuous-time quantum walks

Rafael Vieira, Edgard P. M. Amorim

Abstract Continuous-time quantum walks (CTQWs) provide a versatile framework for exploring quantum transport on graphs. In this work, we investigate how the introduction of edge-weight modulation at a single vertex can suppress its occupation probability. We show that when the edges connected to the root vertex are enhanced by a factor J , the probability of detecting the walker at this vertex decays as $$1/J^2$$ 1 / J 2 , provided the initial state has no components on the vertex itself or its nearest neighbors. We derive the full eigenvalue and eigenvector structure of this system, revealing that the suppression arises from the decoupling of two symmetric line subgraphs and the destructive interference of higher-order contributions. The analysis is extended to tree graphs, where we demonstrate the same scaling behavior and identify the role of local graph geometry in controlling vertex probabilities. These results suggest edge-weight modulation as a mechanism for manipulating transport pathways in CTQWs, with potential applications in quantum information transfer and state engineering, and may serve as a probe of decoherence effects in open quantum systems.

arXiv:2404.04094•Quantum Information Processing•Mar 2, 2026•1 citation

Isolated vertices in continuous-time quantum walks on dynamic graphs

Thomas G. Wong

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 controlled-not gates, and these gates are easily extended to multiqubit 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 4. 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.

arXiv:1908.00507•Physical Review A•Dec 18, 2019•14 citations

A matching decomposition algorithm for simulating quantum walk Hamiltonians

Mostafa Atallah, Alvin Gonzales, Daniel Dilley +3 more

In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. We develop a greedy matching heuristic and a compression-aware matching heuristic, both of which can be used in the quantum circuit algorithm. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare greedy (compression-aware) matching decomposition to a standard Pauli-based simulation pipeline and find that greedy (compression-aware) matching decomposition consistently yields substantial resource reductions, requiring up to 43$\%$ (70\%) fewer controlled gates and up to 54$\%$ (75\%) shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.

quant-pharXiv:2601.11418•Jan 19, 2026•4 citations

Reproducing Spectral Edge Control in Small-World Networks Using Continuous-Time Quantum Walks

Konstantin Olegovich Gnidko, Sofia Shiryaeva, Vlada Petrenko

This paper investigates edge control strategies for influencing information spreading in complex networks through spectral radius modification. We show that edge ranking based on quantum-dynamical centrality derived from continuous-time quantum walks (CTQW) provides a spectral impact on the largest eigenvalue of the network connectivity matrix that is comparable to, and in some cases exceeds, that of a classical spectral method based on leading eigenvectors, under an identical topology modification budget. In the classical simulation regime, the CTQW-based approach requires higher computational costs due to repeated matrix exponentiation; however, it is naturally formulated in terms of unitary time evolution and can be implemented on quantum computing hardware without explicit matrix diagonalization, potentially reducing asymptotic complexity. From a conceptual perspective, the proposed quantum algorithm reproduces the spectral structure of the network through an alternative mechanism of fundamentally different physical nature. Experimental evaluation was conducted on small-world graphs generated using the Watts-Strogatz model. A classical spectral baseline, ranking edges by the dominant eigenvector of the symmetrized adjacency matrix, was compared with a CTQWbased method using time-averaged quantum probabilities. The results demonstrate that CTQW-based edge selection reproduces the spectral control effect while providing a physically motivated alternative suitable for quantum implementation.

Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT)•May 14, 2026•0 citations

Continuous-Time Quantum State Transfer with a Generalized Laplacian

Yujia Shi

Quantum walks generated by the adjacency matrix or the Laplacian are known to exhibit low transfer fidelity on general graphs. In this paper, we study continuous-time quantum walks governed by the generalized Laplacian operator L_k = A+kD, where A is the adjacency matrix, D is the degree matrix, and k is a real-valued parameter. Recent work of Duda, McLaughlin, and Wong showed that in the single-excitation Heisenberg (XYZ) spin model, one can realize walks generated by this family of operators on signed weighted graphs. Motivated by earlier studies on vertex-weighted graphs, we demonstrate that for certain graphs, tuning the parameter k can significantly enhance the fidelity of state transfer between endpoints.

arXiv:2509.05454•Sep 5, 2025•0 citations

Continuous-time quantum walks on directed bipartite graphs

Beat Tödtli, Monika Laner, Jouri Semenov +3 more

This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter $\ensuremath{\alpha}$. We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes $N$, time $t$, and the model parameter $\ensuremath{\alpha}$. We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near $\ensuremath{\alpha}=\ensuremath{\pi}/2$. By proving two mirror symmetries around $\ensuremath{\alpha}=0$ and $\ensuremath{\pi}/2$ we show that these quantum walks have a period of $\ensuremath{\pi}$ in $\ensuremath{\alpha}$. We show that undirected edges lose their effect on the quantum walk at $\ensuremath{\alpha}=\ensuremath{\pi}/2$ and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.

arXiv:1606.00992•Physical Review A•Nov 30, 2016•11 citations
Abstract Continuous-time quantum walks on dynamic graphs are generated by an ordered sequence of Hamiltonians. Replacing that sequence by one average Hamiltonian can simplify analysis and control, but it may change the transported quantum state. We study this replacement in the single-excitation sector for sequential, undirected edge couplings. Nonzero edge Hamiltonians commute precisely when their edges coincide or are vertex-disjoint, giving a pulse-independent exact reduction for schedules supported on a matching. For general schedules, we derive a nonperturbative spectral-norm bound between the ordered unitary and the exponential of the integrated Hamiltonian. In the edge model, the bound becomes a weighted count of temporal wedges—pairs of distinct event edges meeting at one vertex—and is computable in expected linear time. The same certificate controls state-transfer amplitudes and probabilities, process fidelity, average gate fidelity, and sensitivity to event reordering. A weak-pulse expansion shows that its quadratic scaling is generally sharp. An exact three-vertex calculation and reproducible numerical tests illustrate when the certificate is informative and when cancellation makes it conservative. The result is a directly checkable sufficient condition for replacing a dynamic quantum walk by its weighted aggregate.
Abstract Continuous-time quantum walks (CTQWs) provide a versatile framework for exploring quantum transport on graphs. In this work, we investigate how the introduction of edge-weight modulation at a single vertex can suppress its occupation probability. We show that when the edges connected to the root vertex are enhanced by a factor J , the probability of detecting the walker at this vertex decays as 1/J21/J^21/J2 1 / J 2 , provided the initial state has no components on the vertex itself or its nearest neighbors. We derive the full eigenvalue and eigenvector structure of this system, revealing that the suppression arises from the decoupling of two symmetric line subgraphs and the destructive interference of higher-order contributions. The analysis is extended to tree graphs, where we demonstrate the same scaling behavior and identify the role of local graph geometry in controlling vertex probabilities. These results suggest edge-weight modulation as a mechanism for manipulating transport pathways in CTQWs, with potential applications in quantum information transfer and state engineering, and may serve as a probe of decoherence effects in open quantum systems.
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, TTT, and controlled-not gates, and these gates are easily extended to multiqubit systems. For example, the TTT gate is simplified from a sequence of six graphs to a single graph, and the number of vertices is reduced by a factor of 4. We also construct a generalized phase gate, of which ZZZ, SSS, and TTT 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.
In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. We develop a greedy matching heuristic and a compression-aware matching heuristic, both of which can be used in the quantum circuit algorithm. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare greedy (compression-aware) matching decomposition to a standard Pauli-based simulation pipeline and find that greedy (compression-aware) matching decomposition consistently yields substantial resource reductions, requiring up to 43%\%% (70\%) fewer controlled gates and up to 54%\%% (75\%) shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.
This paper investigates edge control strategies for influencing information spreading in complex networks through spectral radius modification. We show that edge ranking based on quantum-dynamical centrality derived from continuous-time quantum walks (CTQW) provides a spectral impact on the largest eigenvalue of the network connectivity matrix that is comparable to, and in some cases exceeds, that of a classical spectral method based on leading eigenvectors, under an identical topology modification budget. In the classical simulation regime, the CTQW-based approach requires higher computational costs due to repeated matrix exponentiation; however, it is naturally formulated in terms of unitary time evolution and can be implemented on quantum computing hardware without explicit matrix diagonalization, potentially reducing asymptotic complexity. From a conceptual perspective, the proposed quantum algorithm reproduces the spectral structure of the network through an alternative mechanism of fundamentally different physical nature. Experimental evaluation was conducted on small-world graphs generated using the Watts-Strogatz model. A classical spectral baseline, ranking edges by the dominant eigenvector of the symmetrized adjacency matrix, was compared with a CTQWbased method using time-averaged quantum probabilities. The results demonstrate that CTQW-based edge selection reproduces the spectral control effect while providing a physically motivated alternative suitable for quantum implementation.
Quantum walks generated by the adjacency matrix or the Laplacian are known to exhibit low transfer fidelity on general graphs. In this paper, we study continuous-time quantum walks governed by the generalized Laplacian operator L_k = A+kD, where A is the adjacency matrix, D is the degree matrix, and k is a real-valued parameter. Recent work of Duda, McLaughlin, and Wong showed that in the single-excitation Heisenberg (XYZ) spin model, one can realize walks generated by this family of operators on signed weighted graphs. Motivated by earlier studies on vertex-weighted graphs, we demonstrate that for certain graphs, tuning the parameter k can significantly enhance the fidelity of state transfer between endpoints.
This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter $\ensuremath{\alpha}$. We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes NNN, time ttt, and the model parameter $\ensuremath{\alpha}$. We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near $\ensuremath{\alpha}=\ensuremath{\pi}/2$. By proving two mirror symmetries around $\ensuremath{\alpha}=0$ and $\ensuremath{\pi}/2$ we show that these quantum walks have a period of $\ensuremath{\pi}$ in $\ensuremath{\alpha}$. We show that undirected edges lose their effect on the quantum walk at $\ensuremath{\alpha}=\ensuremath{\pi}/2$ and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.