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:1606.02136 · Physical Review A

Oscillatory localization of quantum walks analyzed by classical electric circuits

Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G. Wong

Published Dec 20, 2016• 13 citations
arXivHTMLPDF

Abstract

We examine an unexplored quantum phenomenon we call oscillatory localization, where a discrete-time quantum walk with Grover's diffusion coin jumps back and forth between two vertices. We then connect it to the power dissipation of a related electric network. Namely, we show that there are only two kinds of oscillating states, called uniform states and flip states, and that the projection of an arbitrary state onto a flip state is bounded by the power dissipation of an electric circuit. By applying this framework to states along a single edge of a graph, we show that low effective resistance implies oscillatory localization of the quantum walk. This reveals that oscillatory localization occurs on a large variety of regular graphs, including edge-transitive, expander, and high-degree graphs. As a corollary, high edge connectivity also implies localization of these states, since it is closely related to electric resistance.

DOI
10.1103/physreva.94.062324

Related papers

Oscillatory Localization of Quantum Walks by Classical Electric Circuits

Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs +1 more

Power dissipation and effective resistance are ubiquitous quantities in electric circuits. We connect these classical notions with a new quantum phenomenon, proving that a discrete-time quantum walk oscillates between two states if the power dissipation on a related electric network is low. By applying this framework to starting states along a single edge of the graph, we show that low effective resistance implies oscillatory localization of the quantum walk. This includes a large variety of regular graphs, such as edge-transitive, expander, and high degree graphs. As a corollary, it follows that high edge-connectivity also implies localization of these states, since it is closely related to electric resistance.

•Jun 7, 2016•1 citation

Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks

J. Mareš, J. Novotný, M. Štefaňák +1 more

Quantum walks exhibit properties without classical analogues. One of those is the phenomenon of asymptotic trapping---there can be nonzero probability of the quantum walker being localized in a finite part of the underlying graph indefinitely even though locally all directions of movement are assigned nonzero amplitudes at each step. We study quantum walks with the flip-flop shift operator and the Grover coin, where this effect has been identified previously. For the version of the walk further modified by a random dynamical disruption of the graph (percolated quantum walks) we provide a recipe for the construction of a complete basis of the subspace of trapped states allowing to determine the asymptotic probability of trapping for arbitrary finite connected simple graphs, thus significantly generalizing the previously known result restricted to planar 3-regular graphs. We show how the position of the source and sink together with the graph geometry and its modifications affect the excitation transport. This gives us a deep insight into processes where elongation or addition of dead-end subgraphs may surprisingly result in enhanced transport and we design graphs exhibiting this pronounced behavior. In some cases this even provides closed-form formulas for the asymptotic transport probability in dependence on some structure parameters of the graphs.

arXiv:2202.09582•Physical Review A•Jun 10, 2022•3 citations

Entanglement in coined quantum walks on regular graphs

Ivens Carneiro, Meng Loo, Xibai Xu +3 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.

arXiv:quant-ph/0504042•New Journal of Physics•Jul 12, 2005•140 citations

Percolated quantum walks with a general shift operator: From trapping to transport

Jan Mareš, Jaroslav Novotný, Igor Jex

We present an alternative definition of discrete-time coined quantum walks convenient for capturing a rather broad spectrum of a walker's behavior on arbitrary graphs. It includes and covers both the geometry of possible walker's positions with interconnecting links and the prescribed rule in which directions the walker will move at each vertex. While the former allows for the analysis of inhomogeneous quantum walks on graphs with vertices of varying degree, the latter offers us to choose, investigate, and compare quantum walks with different shift operators. The synthesis of both key ingredients constitutes a well-suited playground for analyzing percolated quantum walks on a quite general class of graphs. Analytical treatment of the asymptotic behavior of percolated quantum walks is presented and worked out in details for the Grover walk on graphs with maximal degree 3. We find that for these walks with cyclic shift operators, the existence of an edge-3 coloring of the graph allows for nonstationary asymptotic behavior of the walk. For different shift operators, the general structure of localized attractors is investigated, which determines the overall efficiency of a source-to-sink quantum transport across a dynamically changing medium. As a simple nontrivial example of the theory, we treat a single-excitation transport on a percolated cube.

arXiv:1812.02519•Physical Review A•Apr 30, 2019•13 citations

Stationary states in quantum walk search

Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G. Wong

When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.

arXiv:1608.00136•Physical Review A•Sep 29, 2016•13 citations

Efficient quantum algorithms for analyzing large sparse electrical networks

Guoming Wang

Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N), 1/λ, 1/e), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and e is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.

arXiv:1311.1851•Quantum Information and Computation•Sep 1, 2017•40 citations
We examine an unexplored quantum phenomenon we call oscillatory localization, where a discrete-time quantum walk with Grover's diffusion coin jumps back and forth between two vertices. We then connect it to the power dissipation of a related electric network. Namely, we show that there are only two kinds of oscillating states, called uniform states and flip states, and that the projection of an arbitrary state onto a flip state is bounded by the power dissipation of an electric circuit. By applying this framework to states along a single edge of a graph, we show that low effective resistance implies oscillatory localization of the quantum walk. This reveals that oscillatory localization occurs on a large variety of regular graphs, including edge-transitive, expander, and high-degree graphs. As a corollary, high edge connectivity also implies localization of these states, since it is closely related to electric resistance.
Power dissipation and effective resistance are ubiquitous quantities in electric circuits. We connect these classical notions with a new quantum phenomenon, proving that a discrete-time quantum walk oscillates between two states if the power dissipation on a related electric network is low. By applying this framework to starting states along a single edge of the graph, we show that low effective resistance implies oscillatory localization of the quantum walk. This includes a large variety of regular graphs, such as edge-transitive, expander, and high degree graphs. As a corollary, it follows that high edge-connectivity also implies localization of these states, since it is closely related to electric resistance.
Quantum walks exhibit properties without classical analogues. One of those is the phenomenon of asymptotic trapping---there can be nonzero probability of the quantum walker being localized in a finite part of the underlying graph indefinitely even though locally all directions of movement are assigned nonzero amplitudes at each step. We study quantum walks with the flip-flop shift operator and the Grover coin, where this effect has been identified previously. For the version of the walk further modified by a random dynamical disruption of the graph (percolated quantum walks) we provide a recipe for the construction of a complete basis of the subspace of trapped states allowing to determine the asymptotic probability of trapping for arbitrary finite connected simple graphs, thus significantly generalizing the previously known result restricted to planar 3-regular graphs. We show how the position of the source and sink together with the graph geometry and its modifications affect the excitation transport. This gives us a deep insight into processes where elongation or addition of dead-end subgraphs may surprisingly result in enhanced transport and we design graphs exhibiting this pronounced behavior. In some cases this even provides closed-form formulas for the asymptotic transport probability in dependence on some structure parameters of the graphs.
Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.
We present an alternative definition of discrete-time coined quantum walks convenient for capturing a rather broad spectrum of a walker's behavior on arbitrary graphs. It includes and covers both the geometry of possible walker's positions with interconnecting links and the prescribed rule in which directions the walker will move at each vertex. While the former allows for the analysis of inhomogeneous quantum walks on graphs with vertices of varying degree, the latter offers us to choose, investigate, and compare quantum walks with different shift operators. The synthesis of both key ingredients constitutes a well-suited playground for analyzing percolated quantum walks on a quite general class of graphs. Analytical treatment of the asymptotic behavior of percolated quantum walks is presented and worked out in details for the Grover walk on graphs with maximal degree 3. We find that for these walks with cyclic shift operators, the existence of an edge-3 coloring of the graph allows for nonstationary asymptotic behavior of the walk. For different shift operators, the general structure of localized attractors is investigated, which determines the overall efficiency of a source-to-sink quantum transport across a dynamically changing medium. As a simple nontrivial example of the theory, we treat a single-excitation transport on a percolated cube.
When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.
Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N), 1/λ, 1/e), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and e is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.