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

arXiv:quant-ph/0701088 · Physical Review A

Quantum walks, quantum gates, and quantum computers

Andrew P. Hines, Philip C. E. Stamp

Published Jun 19, 2007• 53 citations
arXivHTMLPDF

Abstract

The physics of quantum walks on graphs is formulated in Hamiltonian language, both for simple quantum walks and for composite walks, where extra discrete degrees of freedom live at each node of the graph. It is shown how to map between quantum walk Hamiltonians and Hamiltonians for qubit systems and quantum circuits; this is done for both single-excitation and multiexcitation encodings. Specific examples of spin chains, as well as static and dynamic systems of qubits, are mapped to quantum walks, and walks on hyperlattices and hypercubes are mapped to various gate systems. We also show how to map a quantum circuit performing the quantum Fourier transform, the key element of Shor's algorithm, to a quantum walk system doing the same. The results herein are an essential preliminary to a Hamiltonian formulation of quantum walks in which coupling to a dynamic quantum environment is included.

DOI
10.1103/physreva.75.062321

Related papers

Quantum walk processes in quantum devices

Anandu Kalleri Madhu, Alexey A. Melnikov, Leonid Evgenevich Fedichkin +2 more

Simulation and programming of current quantum computers as Noisy Intermediate-Scale Quantum (NISQ) devices represent a hot topic at the border of current physical and information sciences. The quantum walk process represents a basic subroutine in many quantum algorithms and plays an important role in studying physical phenomena. Simulating quantum walk processes is computationally challenging for classical processors. With an increasing improvement in qubits fidelity and qubits number in a single register, there is a potential to improve quantum walks simulations substantially. However, efficient ways to simulate quantum walks in qubit registers still have to be explored. Here, we explore the relationship between quantum walk on graphs and quantum circuits. Firstly, we discuss ways to obtain graphs provided quantum circuit. We then explore techniques to represent quantum walk on a graph as a quantum circuit. Specifically, we study hypercube graphs and arbitrary graphs. Our approach to studying the relationship between graphs and quantum circuits paves way for the efficient implementation of quantum walks algorithms on quantum computers.

arXiv:2012.14386•Heliyon•Feb 7, 2023•4 citations

Quantum walks as mathematical foundation for quantum gates

Dmitry Solenov

It is demonstrated that in gate-based quantum computing architectures quantum walk is a natural mathematical description of quantum gates. It originates from field-matter interaction driving the system, but is not attached to specific qubit designs and can be formulated for very general field-matter interactions. It is shown that, most generally, gates are described by a set of coined quantum walks. Rotating wave and resonant approximations for field-matter interaction simplify the walks, factorizing the coin, and leading to pure continuous time quantum walk description. The walks reside on a graph formed by the Hilbert space of all involved qubits and auxiliary states, if present. Physical interactions between different parts of the system necessary to propagate entanglement through such graph---quantum network---enter via reduction of symmetries in graph edges. Description for several single- and two-qubit gates are given as examples.

arXiv:1906.11701•Quantum Information and Computation•Mar 1, 2020•1 citation

Implementing Quantum Gates With Length-3 Dynamic Graphs

Ibukunoluwa Adebimpe Adisa

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.

•May 4, 2021•0 citations

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•11 citations

Implementing quantum gates using length-3 dynamic quantum walks

Ibukunoluwa Adebimpe Adisa, Thomas G. Wong

It is well known that any quantum gate can be decomposed into the universal gate set {$T,H$, cnot}, and recent results have shown that each of these gates can be implemented using a dynamic quantum walk, which is a continuous-time quantum walk on a sequence of graphs. This procedure for converting a quantum gate into a dynamic quantum walk, however, can result in long sequences of graphs. To alleviate this, in this paper, we develop a length-3 dynamic quantum walk that implements any single-qubit gate. Furthermore, we extend this result to give length-3 dynamic quantum walks that implement any single-qubit gate controlled by any number of qubits. Using these, we implement Draper's quantum addition circuit, which is based on the quantum Fourier transform, using a dynamic quantum walk.

arXiv:2108.01055•Physical Review A•Oct 11, 2021•1 citation

Quantum Walk-Based Algorithms for Graph Traversal and Search

Jincheng Zhang

This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.

•Sep 6, 2026•0 citations
The physics of quantum walks on graphs is formulated in Hamiltonian language, both for simple quantum walks and for composite walks, where extra discrete degrees of freedom live at each node of the graph. It is shown how to map between quantum walk Hamiltonians and Hamiltonians for qubit systems and quantum circuits; this is done for both single-excitation and multiexcitation encodings. Specific examples of spin chains, as well as static and dynamic systems of qubits, are mapped to quantum walks, and walks on hyperlattices and hypercubes are mapped to various gate systems. We also show how to map a quantum circuit performing the quantum Fourier transform, the key element of Shor's algorithm, to a quantum walk system doing the same. The results herein are an essential preliminary to a Hamiltonian formulation of quantum walks in which coupling to a dynamic quantum environment is included.
Simulation and programming of current quantum computers as Noisy Intermediate-Scale Quantum (NISQ) devices represent a hot topic at the border of current physical and information sciences. The quantum walk process represents a basic subroutine in many quantum algorithms and plays an important role in studying physical phenomena. Simulating quantum walk processes is computationally challenging for classical processors. With an increasing improvement in qubits fidelity and qubits number in a single register, there is a potential to improve quantum walks simulations substantially. However, efficient ways to simulate quantum walks in qubit registers still have to be explored. Here, we explore the relationship between quantum walk on graphs and quantum circuits. Firstly, we discuss ways to obtain graphs provided quantum circuit. We then explore techniques to represent quantum walk on a graph as a quantum circuit. Specifically, we study hypercube graphs and arbitrary graphs. Our approach to studying the relationship between graphs and quantum circuits paves way for the efficient implementation of quantum walks algorithms on quantum computers.
It is demonstrated that in gate-based quantum computing architectures quantum walk is a natural mathematical description of quantum gates. It originates from field-matter interaction driving the system, but is not attached to specific qubit designs and can be formulated for very general field-matter interactions. It is shown that, most generally, gates are described by a set of coined quantum walks. Rotating wave and resonant approximations for field-matter interaction simplify the walks, factorizing the coin, and leading to pure continuous time quantum walk description. The walks reside on a graph formed by the Hilbert space of all involved qubits and auxiliary states, if present. Physical interactions between different parts of the system necessary to propagate entanglement through such graph---quantum network---enter via reduction of symmetries in graph edges. Description for several single- and two-qubit gates are given as examples.
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.
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.
It is well known that any quantum gate can be decomposed into the universal gate set {T,HT,HT,H, cnot}, and recent results have shown that each of these gates can be implemented using a dynamic quantum walk, which is a continuous-time quantum walk on a sequence of graphs. This procedure for converting a quantum gate into a dynamic quantum walk, however, can result in long sequences of graphs. To alleviate this, in this paper, we develop a length-3 dynamic quantum walk that implements any single-qubit gate. Furthermore, we extend this result to give length-3 dynamic quantum walks that implement any single-qubit gate controlled by any number of qubits. Using these, we implement Draper's quantum addition circuit, which is based on the quantum Fourier transform, using a dynamic quantum walk.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.