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

Reducing computations in quantum walk algorithms

Asif Shakeel

Published Dec 2, 2019• 0 citations
OpenAlex

Abstract

Quantum walks (QWs) are of interest as examples of uniquely quantum behavior and are applicable in a variety of quantum search and simulation models. Implementing QWs on quantum devices is useful from both points of view. We describe a prototype one-dimensional QW algorithm that economizes resources required in its implementation. Our algorithm needs only a single shift (increment) operation. It also allows complete flexibility in choosing the shift circuit, a resource intensive part of QW implementations. This is desirable for Noisy Intermediate-Scale Quantum (NISQ) devices, in which fewer computations implies faster execution and reduced effects of noise and decoherence. We implement versions of the algorithm, with two different shift circuit structures, on publicly accessible IBM quantum computers.

Related papers

Comparison of quantum-walk implementations on noisy intermediate-scale quantum computers

Κωνσταντίνος Γεωργόπουλος, Clive Emary, Paolo Zuliani

This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.

arXiv:1911.00305•Physical Review A•Feb 8, 2021•22 citations

Comparison of quantum-walk implementations on noisy intermediate-scale quantum computers

K Georgopoulos, C Emary, P Zuliani

This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.

•Feb 8, 2021•0 citations

Gate-based circuit designs for quantum adder-inspired quantum random walks on superconducting qubits

Daniel Koch, Michael Samodurov, Andrew M. Projansky +1 more

Quantum random walks, which drew much attention over the past few decades for their distinctly nonclassical behavior, are a promising subfield within quantum computing. Theoretical framework and applications for these walks have seen many great mathematical advances, with experimental demonstrations now catching up. In this study, we examine the viability of implementing coin quantum random walks using a Quantum Adder-based Shift Operator, with quantum circuit designs specifically for superconducting qubits. We focus on the strengths and weaknesses of these walks, particularly circuit depth, gate count, connectivity requirements and scalability. We propose and analyze a novel approach to implementing boundary conditions for these walks, demonstrating the technique explicitly in one and two dimensions. Finally, we present several fidelity results from running our circuits on IBM’s quantum volume 32 ‘Toronto’ chip, showcasing the extent to which these noisy intermediate-scale quantum devices can currently handle quantum walks.

arXiv:2012.10268•International Journal of Quantum Information•Feb 26, 2022•4 citations

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

Cycle discrete-time quantum walks on a noisy quantum computer

Vivek Wadhia, Nicholas Chancellor, Viv M. Kendon

Abstract The rapid development of quantum computing has led to increasing interest in quantum algorithms for a variety of different applications. Quantum walks have also experienced a surge in interest due to their potential use in quantum algorithms. Using the qiskit software package, we test how accurately the current generation of quantum computers provided by IBM can simulate a cycle discrete-time quantum walk. Implementing an 8-node, 8-step walk and a simpler 4-node, 4-step discrete-time quantum walk on an IBM quantum device known as , the results for each step of the respective walks are presented. A custom noise model is developed in order to estimate that noise levels in the quantum device would need to be reduced by at least 94% in order to execute a 16-node, 16-step cycle discrete-time quantum walk to a reasonable level of fidelity. Graphic abstract

arXiv:2307.11027•The European Physical Journal D•Mar 1, 2024•8 citations

Gate-level Implementation and Resource Analysis of Lackadaisical Quantum Walk Search

Amit Saha, Debanjan Kola, Nishanka Das +1 more

Lackadaisical quantum walks (LQW) extend discrete-time quantum walks (DTQW) by introducing weighted self-loops, enabling improved spatial-search performance through controlled localization of the walker. Despite substantial theoretical progress, practical gate-level implementations suitable for quantum hardware remain largely unexplored, limiting evaluation under realistic architectural constraints, noise, and resource requirements. In this work, we present a gate-level implementation framework for lackadaisical quantum walk search. The proposed construction encodes the position and coin spaces into qubit registers, and realizes the walk dynamics through oracle, coin, and flip-flop shift operations. We validate the circuit by reproducing the expected search behavior for single and multiple marked vertices and by analyzing the effect of the self-loop weight on the success probability. We further evaluate the implementation under realistic noisy settings using superconducting hardware's noise models. Logical resource analysis shows that, for grids ranging from $8\times8$ to $64\times64$, the transpiled gate count increases from $3.63\times10^{5}$ to $4.38\times10^{6}$ and the circuit depth from $2.13\times10^{5}$ to $2.56\times10^{6}$. Finally, fault-tolerant resource estimates based on a surface-code model using the Microsoft Quantum Resource Estimator demonstrate the substantial space-time trade-off associated with magic-state production. The results establish a practical circuit-level pathway for implementing the LQW search and provide a basis for evaluating its performance.

quant-pharXiv:2608.17136•Aug 19, 2026•0 citations
Quantum walks (QWs) are of interest as examples of uniquely quantum behavior and are applicable in a variety of quantum search and simulation models. Implementing QWs on quantum devices is useful from both points of view. We describe a prototype one-dimensional QW algorithm that economizes resources required in its implementation. Our algorithm needs only a single shift (increment) operation. It also allows complete flexibility in choosing the shift circuit, a resource intensive part of QW implementations. This is desirable for Noisy Intermediate-Scale Quantum (NISQ) devices, in which fewer computations implies faster execution and reduced effects of noise and decoherence. We implement versions of the algorithm, with two different shift circuit structures, on publicly accessible IBM quantum computers.
This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.
This paper explores two circuit approaches for quantum walks: The first consists of generalized controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits, and detriments, as well as the computational resources needed for each approach. We show that the inverter approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.
Quantum random walks, which drew much attention over the past few decades for their distinctly nonclassical behavior, are a promising subfield within quantum computing. Theoretical framework and applications for these walks have seen many great mathematical advances, with experimental demonstrations now catching up. In this study, we examine the viability of implementing coin quantum random walks using a Quantum Adder-based Shift Operator, with quantum circuit designs specifically for superconducting qubits. We focus on the strengths and weaknesses of these walks, particularly circuit depth, gate count, connectivity requirements and scalability. We propose and analyze a novel approach to implementing boundary conditions for these walks, demonstrating the technique explicitly in one and two dimensions. Finally, we present several fidelity results from running our circuits on IBM’s quantum volume 32 ‘Toronto’ chip, showcasing the extent to which these noisy intermediate-scale quantum devices can currently handle quantum walks.
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.
Abstract The rapid development of quantum computing has led to increasing interest in quantum algorithms for a variety of different applications. Quantum walks have also experienced a surge in interest due to their potential use in quantum algorithms. Using the qiskit software package, we test how accurately the current generation of quantum computers provided by IBM can simulate a cycle discrete-time quantum walk. Implementing an 8-node, 8-step walk and a simpler 4-node, 4-step discrete-time quantum walk on an IBM quantum device known as , the results for each step of the respective walks are presented. A custom noise model is developed in order to estimate that noise levels in the quantum device would need to be reduced by at least 94% in order to execute a 16-node, 16-step cycle discrete-time quantum walk to a reasonable level of fidelity. Graphic abstract
Lackadaisical quantum walks (LQW) extend discrete-time quantum walks (DTQW) by introducing weighted self-loops, enabling improved spatial-search performance through controlled localization of the walker. Despite substantial theoretical progress, practical gate-level implementations suitable for quantum hardware remain largely unexplored, limiting evaluation under realistic architectural constraints, noise, and resource requirements. In this work, we present a gate-level implementation framework for lackadaisical quantum walk search. The proposed construction encodes the position and coin spaces into qubit registers, and realizes the walk dynamics through oracle, coin, and flip-flop shift operations. We validate the circuit by reproducing the expected search behavior for single and multiple marked vertices and by analyzing the effect of the self-loop weight on the success probability. We further evaluate the implementation under realistic noisy settings using superconducting hardware's noise models. Logical resource analysis shows that, for grids ranging from 8×88\times88×8 to 64×6464\times6464×64, the transpiled gate count increases from 3.63×1053.63\times10^{5}3.63×105 to 4.38×1064.38\times10^{6}4.38×106 and the circuit depth from 2.13×1052.13\times10^{5}2.13×105 to 2.56×1062.56\times10^{6}2.56×106. Finally, fault-tolerant resource estimates based on a surface-code model using the Microsoft Quantum Resource Estimator demonstrate the substantial space-time trade-off associated with magic-state production. The results establish a practical circuit-level pathway for implementing the LQW search and provide a basis for evaluating its performance.