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

IEEE International Conference on Nanotechnology (IEEE-NANO)

Quantum switching and quantum walks

Ting-Hsu Chang, Tein-Sheng Lin, Chia-Hung Chien, Chin-Yung Lu, Sy‐Yen Kuo

Published Aug 1, 2013• 0 citations
Publisher

Abstract

Quantum walks can be implemented in the hypercube and general graphs, where hypercube is a regular graph. According to quantum walk algorithm, unitary property of quantum walks can be preserved. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. Quantum switching is the reversible and parallel computation circuits, where parallel computation circuit can achieve the better performance in time complexity and space complexity. Especially, this switching can trace the behavior of quantum walks from input sequence to output sequence, looking as quantum search algorithm. Furthermore, application of unicasting and multicasting can be implemented in this circuit.

DOI
10.1109/nano.2013.6720819

Related papers

Quantum walks for crossed cubes

Tein-Sheng Lin, Ting-Hsu Chang, Chia-Hung Chien +2 more

This paper proposes a quantum switching on crossed cube, the diameter of the crossed cube is almost half of that of the hypercube, to execute quantum walks. Quantum walks can be implemented in the hypercube and general graphs. Hypercube is a regular graph. According to quantum walk algorithm, the system can preserve unitary property of quantum walks. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. The proposed circuit is to use quantum state, transferring from source node to destination for find the searching object. The small diameter is the best criterion to simulate the behavior of the proposed mechanism. This work selects crossed cube as the research topics with the following two major clauses. One is the small diameter and the other is the exchanged crossed state. The crossed cube has the half diameter of the hypercube. This cube owns the exchanged crossed state that can be used to present the behavior of the entangled particles. Quantum switching is reversible circuit and parallel computation circuit. By using parallel computation circuit, the system can achieve the better performance in time complexity and space complexity. Based on quantum switching, the system can trace the behavior of quantum walks from input sequence to output sequence, and obtains the benefit in time complexity and space complexity for quantum search algorithm.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2013•1 citation

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

Quantum walk search algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

Acta Physica Sinica•Jan 1, 2015•0 citations

Efficient implementation of quantum walk-based algorithms into the quantum gate model of computation

Allan Wing Bocanegra

Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.

•Jan 1, 2023•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•21 citations

The quantum hypercube as a k-mer graph

Gustavo Becerra-Gaviño, Liliana Ibeth Barbosa-Santillán

The application of quantum principles in computing has garnered interest since the 1980s. Today, this concept is not only theoretical, but we have the means to design and execute techniques that leverage the quantum principles to perform calculations. The emergence of the quantum walk search technique exemplifies the practical application of quantum concepts and their potential to revolutionize information technologies. It promises to be versatile and may be applied to various problems. For example, the coined quantum walk search allows for identifying a marked item in a combinatorial search space, such as the quantum hypercube. The quantum hypercube organizes the qubits such that the qubit states represent the vertices and the edges represent the transitions to the states differing by one qubit state. It offers a novel framework to represent k-mer graphs in the quantum realm. Thus, the quantum hypercube facilitates the exploitation of parallelism, which is made possible through superposition and entanglement to search for a marked k-mer. However, as found in the analysis of the results, the search is only sometimes successful in hitting the target. Thus, through a meticulous examination of the quantum walk search circuit outcomes, evaluating what input-target combinations are useful, and a visionary exploration of DNA k-mer search, this paper opens the door to innovative possibilities, laying down the groundwork for further research to bridge the gap between theoretical conjecture in quantum computing and a tangible impact in bioinformatics.

Frontiers in Bioinformatics•Sep 12, 2024•1 citation
Quantum walks can be implemented in the hypercube and general graphs, where hypercube is a regular graph. According to quantum walk algorithm, unitary property of quantum walks can be preserved. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. Quantum switching is the reversible and parallel computation circuits, where parallel computation circuit can achieve the better performance in time complexity and space complexity. Especially, this switching can trace the behavior of quantum walks from input sequence to output sequence, looking as quantum search algorithm. Furthermore, application of unicasting and multicasting can be implemented in this circuit.
This paper proposes a quantum switching on crossed cube, the diameter of the crossed cube is almost half of that of the hypercube, to execute quantum walks. Quantum walks can be implemented in the hypercube and general graphs. Hypercube is a regular graph. According to quantum walk algorithm, the system can preserve unitary property of quantum walks. In the regular graph, to develop quantum walks algorithm is focused on quantum search algorithm. The proposed circuit is to use quantum state, transferring from source node to destination for find the searching object. The small diameter is the best criterion to simulate the behavior of the proposed mechanism. This work selects crossed cube as the research topics with the following two major clauses. One is the small diameter and the other is the exchanged crossed state. The crossed cube has the half diameter of the hypercube. This cube owns the exchanged crossed state that can be used to present the behavior of the entangled particles. Quantum switching is reversible circuit and parallel computation circuit. By using parallel computation circuit, the system can achieve the better performance in time complexity and space complexity. Based on quantum switching, the system can trace the behavior of quantum walks from input sequence to output sequence, and obtains the benefit in time complexity and space complexity for quantum search algorithm.
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.
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.
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.
The application of quantum principles in computing has garnered interest since the 1980s. Today, this concept is not only theoretical, but we have the means to design and execute techniques that leverage the quantum principles to perform calculations. The emergence of the quantum walk search technique exemplifies the practical application of quantum concepts and their potential to revolutionize information technologies. It promises to be versatile and may be applied to various problems. For example, the coined quantum walk search allows for identifying a marked item in a combinatorial search space, such as the quantum hypercube. The quantum hypercube organizes the qubits such that the qubit states represent the vertices and the edges represent the transitions to the states differing by one qubit state. It offers a novel framework to represent k-mer graphs in the quantum realm. Thus, the quantum hypercube facilitates the exploitation of parallelism, which is made possible through superposition and entanglement to search for a marked k-mer. However, as found in the analysis of the results, the search is only sometimes successful in hitting the target. Thus, through a meticulous examination of the quantum walk search circuit outcomes, evaluating what input-target combinations are useful, and a visionary exploration of DNA k-mer search, this paper opens the door to innovative possibilities, laying down the groundwork for further research to bridge the gap between theoretical conjecture in quantum computing and a tangible impact in bioinformatics.