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

Optica

Quantum fast hitting on glued trees mapped on a photonic chip

Zi-Yu Shi, Hao Long Tang, Zhen Feng, Yao Wang, Zhanming Li, Jun Gao, Yi-Jun Chang, Tian-Yu Wang, Jian-Peng Dou, Zhe-Yong Zhang, Zhi‐Qiang Jiao, Wenhao Zhou, Xian‐Min Jin

Published May 5, 2020• 21 citations
Publisher

Abstract

Quantum walks on graphs play an important role in the field of quantum algorithms. Fast hitting is one of the properties that quantum walk algorithms can utilize to outperform classical random walk algorithms. Fast hitting refers to a particle starting from the entrance node on a graph and trying to hit the exit node quickly. Especially, continuous-time quantum walks on random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and laser-written waveguide arrays to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph’s branching rate from 2 to 5, revealing that quantum walks can exhibit more superiority over classical random walks as the branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.

DOI
10.1364/optica.388451

Related papers

Quantum Fast Hitting on Glued Trees Mapped on a Photonic chip

Zi-Yu Shi, Hao Long Tang, Zhen Feng +7 more

Hitting the exit node from the entrance node faster on a graph is one of the properties that quantum walk algorithms can take advantage of to outperform classical random walk algorithms. Especially, continuous-time quantum walks on central-random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and waveguide arrays written by femtosecond laser to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph's branching rate from 2 to 5, revealing that quantum walks exhibit more superiority over classical random walks as branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.

arXiv:1907.12539•Jul 29, 2019•1 citation

Electric‐Circuit Simulation of Quantum Fast Hitting with Exponential Speedup

Hanxu Zhang, Tian Chen, Naiqiao Pan +1 more

Abstract The ultimate goal of developing quantum algorithms and constructing quantum computers is to achieve faster information processing than using current classical computers. Quantum walks are powerful kernels in quantum computing protocols and possess strong capabilities in speeding up various simulation and optimization tasks. One striking example is provided by quantum walkers evolving on unbalanced trees, which demonstrate faster hitting performances than classical random walk. However, direct experimental construction of unbalanced trees to prove quantum advantage with exponential speedup remains a great challenge due to the highly complex arrangements of the structure. This study attempts to simulate quantum algorithm by classical circuit. Inspired by the quantum algorithm, the classical circuit networks are designed and fabricated with unbalanced tree structures. It is then demonstrated, both theoretically and experimentally, that the quantum algorithm for the fast hitting problem can be simulated in the structure. It is shown that the hitting efficiency of electric signals in the circuit networks with unbalanced tree structures is exponentially faster than the corresponding cases of classical random walks. Because classical circuit networks possess good scalability and stability, the results open up a scalable new path toward quantum speedup in complex problems.

Advanced Quantum Technologies•Feb 5, 2022•16 citations

Large-scale full-programmable quantum walk and its applications

Yizhi Wang, Yingwen Liu, Junwei Zhan +22 more

With photonics, the quantum computational advantage has been demonstrated on the task of boson sampling. Next, developing quantum-enhanced approaches for practical problems becomes one of the top priorities for photonic systems. Quantum walks are powerful kernels for developing new and useful quantum algorithms. Here we realize large-scale quantum walks using a fully programmable photonic quantum computing system. The system integrates a silicon quantum photonic chip, enabling the simulation of quantum walk dynamics on graphs with up to 400 vertices and possessing full programmability over quantum walk parameters, including the particle property, initial state, graph structure, and evolution time. In the 400-dimensional Hilbert space, the average fidelity of random entangled quantum states after the whole on-chip circuit evolution reaches as high as 94.29$\pm$1.28$\%$. With the system, we demonstrated exponentially faster hitting and quadratically faster mixing performance of quantum walks over classical random walks, achieving more than two orders of magnitude of enhancement in the experimental hitting efficiency and almost half of the reduction in the experimental evolution time for mixing. We utilize the system to implement a series of quantum applications, including measuring the centrality of scale-free networks, searching targets on Erdös-Rényi networks, distinguishing non-isomorphic graph pairs, and simulating the topological phase of higher-order topological insulators. Our work shows one feasible path for quantum photonics to address applications of practical interests in the near future.

arXiv:2208.13186•Aug 28, 2022•5 citations

Silicon photonic chips for search on improved-glued-binary-tree based on continuous-time quantum walk

Qi Fan, Qingyan Ma, Yufei Wang +1 more

Search on improved-glued-binary-trees is a representative example of quantum superiority, where exponential acceleration can be achieved using quantum walk with respect to any classical algorithms. Here we analyzed the evolution process of this quantum-walk-based algorithm. Several remarkable features of the process are revealed. Generation of the model by introducing tunable defect strength and double defects is also discussed and the effects of these generalization on evolution process, arrival probability and residual probability are discussed in details. Physical implementation with silicon ridge waveguide array is presented. The design of the array with FEM method are presented and light propagation simulation with FDTD method shows that this kind of structure is feasible for the task. Lastly, preliminary experimental demonstration with classical coherent light simulation are presented. Our results show that silicon photonic chips are suitable for such search problems and opening a route towards large-scale photonic quantum computation.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Nov 3, 2016•1 citation

Improved upper bounds for the hitting times of quantum walks

Yosi Atia, Shantanav Chakraborty

Continuous-time quantum walks have proven to be an extremely useful framework for the design of several quantum algorithms. Often, the running time of quantum algorithms in this framework is characterized by the quantum hitting time: the time required by the quantum walk to find a vertex of interest with a high probability. In this article, we provide improved upper bounds for the quantum hitting time that can be applied to several continuous-time quantum walk (CTQW) based quantum algorithms. In particular, we apply our techniques to the glued-trees problem, improving their hitting time upper bound by a polynomial factor: from $O({n}^{5})$ to $O({n}^{2}logn)$. Furthermore, our methods also help to exponentially improve the dependence on precision of the CTQW based algorithm to find a marked node on any ergodic, reversible Markov chain by Chakraborty et al. [Phys. Rev. A 102, 022227 (2020)].

arXiv:2005.04062•Physical Review A•Sep 21, 2021•9 citations

Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs

Ellinor Wanzambi, Andersson, Stina

In recent years, quantum walks have been widely researched and have shown exciting properties. One such is a quadratic speed-up in hitting time compared to its classical counterpart. In this paper, we design a quantum circuit for the MNRS algorithm, which finds a marked node in a graph with a quantum walk, and use it to find a hitting time for the marked nodes in the walk. We do this by implementing the circuit on IBM quantum simulators and show that the execution on a noise-free simulator results in hitting times that agree with the theoretical expectations. We also run the algorithm on a mock backend that simulates the noise of the IBM Melbourne computer. As expected, the noise has an extensive impact on the output, resulting in outcomes far from the noise-free simulation.

arXiv:2108.02723•Aug 5, 2021•4 citations
Quantum walks on graphs play an important role in the field of quantum algorithms. Fast hitting is one of the properties that quantum walk algorithms can utilize to outperform classical random walk algorithms. Fast hitting refers to a particle starting from the entrance node on a graph and trying to hit the exit node quickly. Especially, continuous-time quantum walks on random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and laser-written waveguide arrays to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph’s branching rate from 2 to 5, revealing that quantum walks can exhibit more superiority over classical random walks as the branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.
Hitting the exit node from the entrance node faster on a graph is one of the properties that quantum walk algorithms can take advantage of to outperform classical random walk algorithms. Especially, continuous-time quantum walks on central-random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and waveguide arrays written by femtosecond laser to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph's branching rate from 2 to 5, revealing that quantum walks exhibit more superiority over classical random walks as branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.
Abstract The ultimate goal of developing quantum algorithms and constructing quantum computers is to achieve faster information processing than using current classical computers. Quantum walks are powerful kernels in quantum computing protocols and possess strong capabilities in speeding up various simulation and optimization tasks. One striking example is provided by quantum walkers evolving on unbalanced trees, which demonstrate faster hitting performances than classical random walk. However, direct experimental construction of unbalanced trees to prove quantum advantage with exponential speedup remains a great challenge due to the highly complex arrangements of the structure. This study attempts to simulate quantum algorithm by classical circuit. Inspired by the quantum algorithm, the classical circuit networks are designed and fabricated with unbalanced tree structures. It is then demonstrated, both theoretically and experimentally, that the quantum algorithm for the fast hitting problem can be simulated in the structure. It is shown that the hitting efficiency of electric signals in the circuit networks with unbalanced tree structures is exponentially faster than the corresponding cases of classical random walks. Because classical circuit networks possess good scalability and stability, the results open up a scalable new path toward quantum speedup in complex problems.
With photonics, the quantum computational advantage has been demonstrated on the task of boson sampling. Next, developing quantum-enhanced approaches for practical problems becomes one of the top priorities for photonic systems. Quantum walks are powerful kernels for developing new and useful quantum algorithms. Here we realize large-scale quantum walks using a fully programmable photonic quantum computing system. The system integrates a silicon quantum photonic chip, enabling the simulation of quantum walk dynamics on graphs with up to 400 vertices and possessing full programmability over quantum walk parameters, including the particle property, initial state, graph structure, and evolution time. In the 400-dimensional Hilbert space, the average fidelity of random entangled quantum states after the whole on-chip circuit evolution reaches as high as 94.29$\pm1.281.281.28\%$. With the system, we demonstrated exponentially faster hitting and quadratically faster mixing performance of quantum walks over classical random walks, achieving more than two orders of magnitude of enhancement in the experimental hitting efficiency and almost half of the reduction in the experimental evolution time for mixing. We utilize the system to implement a series of quantum applications, including measuring the centrality of scale-free networks, searching targets on Erdös-Rényi networks, distinguishing non-isomorphic graph pairs, and simulating the topological phase of higher-order topological insulators. Our work shows one feasible path for quantum photonics to address applications of practical interests in the near future.
Search on improved-glued-binary-trees is a representative example of quantum superiority, where exponential acceleration can be achieved using quantum walk with respect to any classical algorithms. Here we analyzed the evolution process of this quantum-walk-based algorithm. Several remarkable features of the process are revealed. Generation of the model by introducing tunable defect strength and double defects is also discussed and the effects of these generalization on evolution process, arrival probability and residual probability are discussed in details. Physical implementation with silicon ridge waveguide array is presented. The design of the array with FEM method are presented and light propagation simulation with FDTD method shows that this kind of structure is feasible for the task. Lastly, preliminary experimental demonstration with classical coherent light simulation are presented. Our results show that silicon photonic chips are suitable for such search problems and opening a route towards large-scale photonic quantum computation.
Continuous-time quantum walks have proven to be an extremely useful framework for the design of several quantum algorithms. Often, the running time of quantum algorithms in this framework is characterized by the quantum hitting time: the time required by the quantum walk to find a vertex of interest with a high probability. In this article, we provide improved upper bounds for the quantum hitting time that can be applied to several continuous-time quantum walk (CTQW) based quantum algorithms. In particular, we apply our techniques to the glued-trees problem, improving their hitting time upper bound by a polynomial factor: from O(n5)O({n}^{5})O(n5) to O(n2logn)O({n}^{2}logn)O(n2logn). Furthermore, our methods also help to exponentially improve the dependence on precision of the CTQW based algorithm to find a marked node on any ergodic, reversible Markov chain by Chakraborty et al. [Phys. Rev. A 102, 022227 (2020)].
In recent years, quantum walks have been widely researched and have shown exciting properties. One such is a quadratic speed-up in hitting time compared to its classical counterpart. In this paper, we design a quantum circuit for the MNRS algorithm, which finds a marked node in a graph with a quantum walk, and use it to find a hitting time for the marked nodes in the walk. We do this by implementing the circuit on IBM quantum simulators and show that the execution on a noise-free simulator results in hitting times that agree with the theoretical expectations. We also run the algorithm on a mock backend that simulates the noise of the IBM Melbourne computer. As expected, the noise has an extensive impact on the output, resulting in outcomes far from the noise-free simulation.