Quantum Walks are among the most widely used techniques with which we can construct new quantum algorithms. This paper aims to outline how to construct a circuit for the continuous-time quantum walk (CTQW) over circulant graphs using the Quantum Fourier Transform (QFT) due to the spectral properties of those graphs. Furthermore, we examine how the Approximate Quantum Fourier Transform (AQFT) allows us to shorten the size of the circuit by reducing the number of controlled rotation gates. The contributions of this paper consist of the development of a general circuit implementation of the CTQW for an important class of graphs that does not scale up with time, and the study of the cases where the AQFT decreases the error by controlling the approximation. Finally, we provide a statistical analysis for several circulant graphs, running experiments in a IBM's superconducting quantum computer, and we also explore the pretty good state transfer (PGST) for some graphs.
Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study the implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator ${e}^{\ensuremath{-}iHt}$, where $H=\ensuremath{\gamma}A$ ($\ensuremath{\gamma}$ is a constant and
A corresponds to the adjacency matrix of a graph). Our result is, for a
d-sparse graph with
N vertices and evolution time
t, we can approximate ${e}^{\ensuremath{-}iHt}$ by a quantum circuit with gate complexity $({d}^{3}\ensuremath{\parallel}H\ensuremath{\parallel}tN{log}_{2}{(N))}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\ensuremath{\parallel}H\ensuremath{\parallel}t{N}^{4}{log}_{2}{(N))}^{1+o(1)}$. For sparse graphs, for instance,
d=O(1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian
H can be represented as the sum of some Hamiltonians
Hj, where each ${e}^{\ensuremath{-}i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.
The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.
Quantum-circuit implementations of continuous-time quantum walks (CTQWs) can provide an efficient route to model graph-based algorithms. However, constructing circuits that faithfully reproduce CTQW dynamics across arbitrary graphs remains a major challenge. In this work, we introduce a Laplacian partitioning algorithm (LPA) that enables an efficient and scalable quantum-circuit realization of CTQWs on random graphs. A common algorithm to simulate a general graph (of size
N=2n for
n qubits) on a quantum circuit is based on Pauli decomposition of the graph Hamiltonian, which can yield
O(4n) terms, and require
O(N2logN) time for coefficient computation. In contrast, our LPA uses
O(2n) terms, in
O(N2) time. Our circuit provides a graph-agnostic framework for CTQWs, implemented via a Trotter-Suzuki product formula and confirming error scaling consistent with theoretical Trotter error bounds. To further test the circuit performance, we study the localization behavior of the CTQW. In our case, localization originates from Laplacian spectral degeneracies rather than disorder (Anderson-type), and our circuit faithfully reproduces these localization phenomena and spectral structure for a random graphs with high accuracy.
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.
The continuous-time quantum walk is a quantum version of a random walk that evolves by Schrodinger's equation. With the Hamiltonian equal to the adjacency matrix of a sequence of graphs, called a dynamic graph, continuous-time quantum walks have been shown to implement quantum gates, including the T gate, Hadamard gate, and the Controlled{NOT gate. Since these gates make up a universal set of quantum gates, they can implement any other arbitrary quantum gate up to an arbitrary approximation. This process, however, can be tedious and ine cient. To alleviate this, we have developed a parameterized dynamic graph on which a continuous-time quantum walk can implement any arbitrary single-qubit quantum gate, and we have also extended this result to implement any two-qubit controlled-unitary quantum gate. These dynamic graphs have at most length three. Using these, we implemented Draper's quantum addition circuit, which is based on the quantum Fourier transform, using a continuous-time quantum walk on a dynamic graph.
Continuous-time quantum walks (CTQWs) on static graphs provide efficient methods for search and sampling as well as a model for universal quantum computation. We consider an extension of CTQWs to the case of dynamic graphs, in which an ordered sequence of graphs governs free evolution of the quantum walk. We then consider how perfect state transfer during the quantum walk can be used to design dynamic graphs that implement a universal set of quantum logic gates. We give explicit examples for a complete logical basis, and we validate implementations using numerical simulations for quantum teleportation and addition circuits. Finally, we discuss the potential for realizing CTQWs on dynamic graphs using actively controlled quantum optical waveguides.