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:1006.2405 · Mathematics of Control Signals and Systems

Controllability of quantum walks on graphs

Francesca Albertini, Domenico D’Alessandro

Published Mar 23, 2012• 8 citations
arXivHTMLPDF
DOI
10.1007/s00498-012-0084-0

Related papers

Implementing graph-theoretic quantum algorithms on a silicon photonic quantum walk processor

Xiaogang Qiang, Yizhi Wang, Shichuan Xue +15 more

Applications of quantum walks can depend on the number, exchange symmetry and indistinguishability of the particles involved, and the underlying graph structures where they move. Here, we show that silicon photonics, by exploiting an entanglement-driven scheme, can realize quantum walks with full control over all these properties in one device. The device we realize implements entangled two-photon quantum walks on any five-vertex graph, with continuously tunable particle exchange symmetry and indistinguishability. We show how this simulates single-particle walks on larger graphs, with size and geometry controlled by tuning the properties of the composite quantum walkers. We apply the device to quantum walk algorithms for searching vertices in graphs and testing for graph isomorphisms. In doing so, we implement up to 100 sampled time steps of quantum walk evolution on each of 292 different graphs. This opens the way to large-scale, programmable quantum walk processors for classically intractable applications.

Science Advances•Feb 26, 2021•105 citations

Quantum Walks on Finite Graphs

Renato Portugal

Springer eBooks•Jan 1, 2013•0 citations

Bounds of Quantum Mixing Processes via Controlled Walks

Li, Shang

Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.

•Apr 29, 2020•0 citations

Open quantum walks on graphs

Stéphane Attal, Francesco Petruccione, Ilya Sinayskiy

arXiv:1401.3305•Physics Letters A•Mar 21, 2012•72 citations

Order from chaos in quantum walks on cyclic graphs

Abhisek Panda, Colin Benjamin

It has been shown classically that combining two chaotic random walks can yield an ordered (periodic) walk. Our aim in this paper is to find a quantum analog for this rather counterintuitive result. We study the chaotic and periodic nature of cyclic quantum walks and focus on a unique situation wherein a periodic quantum walk on 3-cycle graph is generated via a deterministic combination of two chaotic quantum walks on the same graph. We extend our results to even numbered cyclic graphs, specifically a 4-cycle graph too. Our results will be relevant in quantum cryptography and quantum chaos control.

arXiv:2008.00316•Physical Review A•Jul 7, 2021•20 citations

Controllability of system dynamics on networks, quantum walks and random walks

Domenico D’Alessandro, Sevim Olmez

Automatica•Mar 15, 2013•1 citation
Applications of quantum walks can depend on the number, exchange symmetry and indistinguishability of the particles involved, and the underlying graph structures where they move. Here, we show that silicon photonics, by exploiting an entanglement-driven scheme, can realize quantum walks with full control over all these properties in one device. The device we realize implements entangled two-photon quantum walks on any five-vertex graph, with continuously tunable particle exchange symmetry and indistinguishability. We show how this simulates single-particle walks on larger graphs, with size and geometry controlled by tuning the properties of the composite quantum walkers. We apply the device to quantum walk algorithms for searching vertices in graphs and testing for graph isomorphisms. In doing so, we implement up to 100 sampled time steps of quantum walk evolution on each of 292 different graphs. This opens the way to large-scale, programmable quantum walk processors for classically intractable applications.
Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.
It has been shown classically that combining two chaotic random walks can yield an ordered (periodic) walk. Our aim in this paper is to find a quantum analog for this rather counterintuitive result. We study the chaotic and periodic nature of cyclic quantum walks and focus on a unique situation wherein a periodic quantum walk on 3-cycle graph is generated via a deterministic combination of two chaotic quantum walks on the same graph. We extend our results to even numbered cyclic graphs, specifically a 4-cycle graph too. Our results will be relevant in quantum cryptography and quantum chaos control.