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

EPJ Web of Conferences

Noise Characterization: Keeping Reduction Based Per-turbed Quantum Walk Search Optimal

Chen-Fu Chiang, Chang‐Yu Hsieh

Published Jan 1, 2019• 3 citations
Publisher

Abstract

In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). In this work, we adopt the aforementioned method to investigate the optimality of a perturbed quantum walk search of a marked element in a noisy environment on various graphs. We formulate the necessary condition of the noise distribution in the system such that the invariant subspace method remains effective and efficient. Based on the noise, we further formulate how to set the appropriate coupling factor to preserve the optimality of the quantum walker.

DOI
10.1051/epjconf/201919800001

Related papers

Optimizing Quantum Walk Search on a Reduced Uniform Complete Multi-Partite Graph

Chen-Fu Chiang, Chang‐Yu Hsieh

In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). The method helps to reduce a graph into a simpler version that allows more transparent analyses of the quantum walk model. In this work, we adopt the aforementioned method to investigate the optimality of a quantum walk search of a marked element on a complete multi-partite graph. We formulate the eigenbasis that would facilitate the transport between the two lowest energy eigenstates and demonstrate how to set the appropriate coupling factor to preserve the optimality.

arXiv:1706.05403•Jun 16, 2017•2 citations

Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs

Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni +2 more

Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.

arXiv:1412.7209•Scientific Reports•Sep 2, 2015•89 citations

Optimality of spatial search via continuous-time quantum walks

Shantanav Chakraborty, Leonardo Novo, Jérémie Roland

One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.

arXiv:2004.12686•Physical Review A•Sep 14, 2020•37 citations

Quantum Walk on Dimensionality Reduced Complete Bipartite Graphs with k Edges Removed

Chen-Fu Chiang, Aaron Gregory

Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random $k$ edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2019•1 citation

Spatial search by continuous-time quantum walks on complex networks

Joonas Malmi

Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.

•Dec 8, 2020•0 citations

The optimal search on graph by continuous-time quantum walks

Xi Li, Hanwu Chen, Ruan, Yue +3 more

Chakraborty and Leonardo have shown that a spatial search by quantum walk is optimal for almost all graphs. However, we observed that on some graphs, certain states cannot be searched optimally. We present a method for constructing an optimal graph that searches an arbitrary state and provides the optimal condition. We also analyze the monotonicity of the search performance and conclude that the search performance can be improved by adding edges.

arXiv:1711.01765•Nov 6, 2017•0 citations
In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). In this work, we adopt the aforementioned method to investigate the optimality of a perturbed quantum walk search of a marked element in a noisy environment on various graphs. We formulate the necessary condition of the noise distribution in the system such that the invariant subspace method remains effective and efficient. Based on the noise, we further formulate how to set the appropriate coupling factor to preserve the optimality of the quantum walker.
In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of continuous-time quantum walk (CTQW). The method helps to reduce a graph into a simpler version that allows more transparent analyses of the quantum walk model. In this work, we adopt the aforementioned method to investigate the optimality of a quantum walk search of a marked element on a complete multi-partite graph. We formulate the eigenbasis that would facilitate the transport between the two lowest energy eigenstates and demonstrate how to set the appropriate coupling factor to preserve the optimality.
Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of nnn nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n)O(\sqrt{n})O(n​) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
Due to scalability issue in current quantum technologies, many quantum algorithms can only be implemented for small size problems. Scalability remains a bottleneck for current quantum technologies. For solving real-life size hard problems in the near-term, we explore classes of search graphs that can be efficiently reduced to a implementable scale for many quantum algorithms. The reduced Hamiltonian preserves the dynamics of the original Hamiltonian. One of the quantum algorithms we choose for the reduced Hamiltonian is continuous time quantum walk (CTQW). We further show how to determine the correct value of the coupling factor of the underlying CTQW. With wrong couple factor values, the optimality (quadratic speedup) from CTQW might be lost. In this work, we extend the class of reducible graphs to complete bipartite graphs with random kkk edges removed. We further demonstrate through mathematical proof and simulation experiment using IBM Qiskit to show that the quadratic speed-up is preserved for the CTQW.
Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.