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:2408.15653 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Circuit Implementation of Discrete-Time Quantum Walks on Complex Networks

Rei Sato, Kazuhiro Saito

Published Sep 15, 2024• 0 citations
arXivHTMLPDF

Abstract

In this paper, we propose a circuit design for implementing quantum walks on complex networks. Quantum walks are powerful tools for various graph-based applications such as spatial search, community detection, and node classification. Although many quantum-walk-based graph algorithms have been extensively studied, specific quantum circuits for implementing these algorithms have not yet been provided. To address this issue, we present a circuit design for implementing the discrete-time quantum walk on complex networks. We investigate the functionality of our circuit using the small-sized Watts-and-Strogatz model as the complex network model, comparing it with theoretical calculations. This work offers a new approach to constructing quantum circuits for implementing quantum walks on arbitrary complex networks.

DOI
10.1109/qce60285.2024.10313

Related papers

Coined Quantum Walks on Complex Networks for Quantum Computers

Rei Sato

We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately $N^{1.9}$ regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with $N=4$ and $N=8$. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.

quant-pharXiv:2512.16400•Quantum Information Processing•Dec 19, 2025•0 citations

Efficient circuit implementation of quantum walks on non-degree-regular graphs

T. Loke, Jingbo B. Wang

This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.

Physical Review A•Oct 31, 2012•18 citations

Efficient Circuit Implementations of Continuous-Time Quantum Walks for Quantum Search

Renato Portugal, Jalil Khatibi Moqadam

Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.

arXiv:2212.08889•Entropy•Apr 23, 2025•1 citation

Proposal for implementing quantum walks on multidimensional networks

Qi-Ping Su, Rui-Qi Shen, Li Zhi Yu +6 more

Discrete-time quantum walks (DTQWs) have broad applications in quantum computation and simulation, particularly in universal quantum computing. Prior research in circuit quantum electrodynamics (QED) has focused on implementing DTQWs in one-dimensional chains. However, to achieve practical quantum tasks, it is crucial to extend DTQWs to multidimensional networks with diverse structures. Here, we propose a protocol for realizing DTQWs in multidimensional networks, which accommodate nodes with different numbers of neighbors. Using this protocol, we numerically simulate a Grover walk search algorithm in a cubic network with circuit QED. Our simulations, which consider decoherence, align well with theoretical predictions. Our universal protocol can be adapted for various quantum systems and paves the way for DTQWs in multidimensional networks, which has potential applications in quantum computing and simulation.

Physical Review A•Aug 15, 2025•0 citations

Quantum Walk-Based Graph Algorithms for Scalable Network Analysis

Jincheng Zhang

This paper investigates the application of quantum walk algorithms to address the computational challenges inherent in analyzing large and complex networks. Traditional graph algorithms often suffer from exponential scaling, rendering them impractical for networks with a substantial number of nodes and edges. We propose a framework leveraging quantum walks to perform network exploration and analysis tasks, aiming to achieve significant speedups compared to their classical counterparts. The core of our approach lies in simulating a quantum walk on the graph, where the walker's movement is governed by quantum mechanical principles, promoting parallel exploration of the graph's connectivity. We detail the theoretical foundations of this approach, focusing on the mathematical formulation of quantum walk operators and their application to graph traversal and algorithm design. Furthermore, we explore specific network analysis problems, such as shortest path finding and community detection, demonstrating the potential of this methodology. The results presented suggest that quantum walk-based algorithms offer a promising avenue for scalable network analysis, particularly for large networks where classical algorithms face limitations.

•Sep 5, 2026•0 citations

Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem

Giacomo Lancellotti, Simone Perriello, Alessandro Barenghi +1 more

Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.

ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•4 citations
In this paper, we propose a circuit design for implementing quantum walks on complex networks. Quantum walks are powerful tools for various graph-based applications such as spatial search, community detection, and node classification. Although many quantum-walk-based graph algorithms have been extensively studied, specific quantum circuits for implementing these algorithms have not yet been provided. To address this issue, we present a circuit design for implementing the discrete-time quantum walk on complex networks. We investigate the functionality of our circuit using the small-sized Watts-and-Strogatz model as the complex network model, comparing it with theoretical calculations. This work offers a new approach to constructing quantum circuits for implementing quantum walks on arbitrary complex networks.
We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately N1.9N^{1.9}N1.9 regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with N=4N=4N=4 and N=8N=8N=8. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.
This paper presents a set of highly efficient quantum circuits for discrete-time quantum walks on non-degree-regular graphs. In particular, we describe a general procedure for constructing highly efficient quantum circuits for quantum walks on star graphs of any degree and Cayley trees with an arbitrary number of layers, which are nonsparse in general. We also show how to modify these circuits to implement a full quantum-walk search algorithm on these graphs, without reference to a ``black-box'' oracle. This provides a practically implementable method to explore quantum-walk-based algorithms with the aim of eventual real-world applications.
Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.
Discrete-time quantum walks (DTQWs) have broad applications in quantum computation and simulation, particularly in universal quantum computing. Prior research in circuit quantum electrodynamics (QED) has focused on implementing DTQWs in one-dimensional chains. However, to achieve practical quantum tasks, it is crucial to extend DTQWs to multidimensional networks with diverse structures. Here, we propose a protocol for realizing DTQWs in multidimensional networks, which accommodate nodes with different numbers of neighbors. Using this protocol, we numerically simulate a Grover walk search algorithm in a cubic network with circuit QED. Our simulations, which consider decoherence, align well with theoretical predictions. Our universal protocol can be adapted for various quantum systems and paves the way for DTQWs in multidimensional networks, which has potential applications in quantum computing and simulation.
This paper investigates the application of quantum walk algorithms to address the computational challenges inherent in analyzing large and complex networks. Traditional graph algorithms often suffer from exponential scaling, rendering them impractical for networks with a substantial number of nodes and edges. We propose a framework leveraging quantum walks to perform network exploration and analysis tasks, aiming to achieve significant speedups compared to their classical counterparts. The core of our approach lies in simulating a quantum walk on the graph, where the walker's movement is governed by quantum mechanical principles, promoting parallel exploration of the graph's connectivity. We detail the theoretical foundations of this approach, focusing on the mathematical formulation of quantum walk operators and their application to graph traversal and algorithm design. Furthermore, we explore specific network analysis problems, such as shortest path finding and community detection, demonstrating the potential of this methodology. The results presented suggest that quantum walk-based algorithms offer a promising avenue for scalable network analysis, particularly for large networks where classical algorithms face limitations.
Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.