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

AIP conference proceedings

On training a classifier of hitting times for quantum walks

Alexey A. Melnikov, Leonid Evgenevich Fedichkin, A. P. Alodjants

Published Jan 1, 2020• 2 citations
Publisher

Abstract

We study hitting times of quantum walks on graphs from a machine learning perspective. Given a graph it is difficult to decide if quantum walks give an advantage relative to classical random walks. It was shown that machine learning can help to detect quantum advantage even though quantum walk and random walk dynamics on the graph has never been simulated. Here we describe the procedure by which training data is generated for the machine learning approach, and discuss possible future improvements.

DOI
10.1063/5.0011365

Related papers

Detecting quantum speedup of random walks with machine learning

Hanna Linn, Yu Zheng, Anton Frisk Kockum

We explore the use of machine-learning techniques to detect quantum speedup in random walks on graphs. Specifically, we investigate the performance of three different neural-network architectures (variations on fully connected and convolutional neural networks) for identifying linear, cyclic, and random graphs that yield quantum speedups in terms of the hitting time for reaching a target node after starting in another node of the graph. Our results indicate that carefully building the data set for training can improve the performance of the neural networks, but all architectures we test struggle to classify large random graphs and generalize from training on one graph size to testing on another. If classification accuracy can be improved further, valuable insights about quantum advantage may be gleaned from these neural networks, not only for random walks, but more generally for quantum computing and quantum transport.

arXiv:2309.02212•Sep 5, 2023•0 citations

Predicting quantum advantage by quantum walk with convolutional neural networks

Alexey A. Melnikov, Leonid Evgenevich Fedichkin, A. P. Alodjants

Abstract Quantum walks are at the heart of modern quantum technologies. They allow to deal with quantum transport phenomena and are an advanced tool for constructing novel quantum algorithms. Quantum walks on graphs are fundamentally different from classical random walks analogs, in particular, they walk faster than classical ones on certain graphs, enabling in these cases quantum algorithmic applications and quantum-enhanced energy transfer. However, little is known about the possible advantages on arbitrary graphs not having explicit symmetries. For these graphs one would need to perform simulations of classical and quantum walk dynamics to check if the speedup occurs, which could take a long computational time. Here we present a new approach for the solution of the quantum speedup problem, which is based on a machine learning algorithm that predicts the quantum advantage by just ‘looking’ at a graph. The convolutional neural network, which we designed specifically to learn from graphs, observes simulated examples and learns complex features of graphs that lead to a quantum advantage, allowing to identify graphs that exhibit quantum advantage without performing any quantum walk or random walk simulations. The performance of our approach is evaluated for line and random graphs, where classification was always better than random guess even for the most challenging cases. Our findings pave the way to an automated elaboration of novel large-scale quantum circuits utilizing quantum walk based algorithms, and to simulating high-efficiency energy transfer in biophotonics and material science.

arXiv:1901.10632•New Journal of Physics•Nov 27, 2019•47 citations

Machine Learning Transfer Efficiencies for Noisy Quantum Walks

Alexey A. Melnikov, Leonid Evgenevich Fedichkin, Ray‐Kuang Lee +1 more

Abstract Quantum effects are known to provide an advantage in particle transfer across networks. In order to achieve this advantage, requirements on both a graph type and a quantum system coherence must be found. Here, it is shown that the process of finding these requirements can be automated by learning from simulated examples. The automation is done by using a convolutional neural network of a particular type that learns to understand with which network and under which coherence requirements quantum advantage is possible. The machine learning approach is applied to study noisy quantum walks on cycle graphs of different sizes. It is found that it is possible to predict the existence of quantum advantage for the entire decoherence parameter range, even for graphs outside of the training set. The results are of importance for demonstration of advantage in quantum experiments and pave the way toward automating scientific research and discoveries.

arXiv:2001.05472•Advanced Quantum Technologies•Feb 13, 2020•20 citations

Machine-Learning-Assisted Parameterization of Quantum Walk Algorithms

Parham Ghayour

Abstract Quantum walk algorithms constitute a central primitive in quantum computation, yet their practical performance often depends sensitively on the choice of execution parameters such as walk depth and initial state. Analytical parameter choices are typically conservative and instance-agnostic, which can lead to suboptimal behavior on specific problem instances. In this work, we propose a general framework for machine-learning-assisted parameterization of quantum walk algorithms, in which classical learning is used to adapt algorithmic parameters without modifying the underlying quantum decision logic. The machine learning component op erates exclusively as a classical control layer, preserving correctness guarantees while improving average-case performance. We demonstrate the framework through an application to the s–t connectivity problem, a canonical benchmark in graph algorithms and complexity theory. Classical simulations of discrete-time quantum walks on randomly generated sparse graphs show that ML-assisted pa rameter selection substantially improves success probability compared to fixed-parameter base lines, yielding multiplicative gains in average performance. These improvements are achieved despite only coarse prediction accuracy, highlighting the robustness of the approach. The results suggest a principled role for machine learning as an adaptive optimization layer in quantum algorithms, offering a practical path toward hybrid quantum–classical methods that enhance performance while maintaining theoretical soundness

•Dec 23, 2025•0 citations

Bosonic Random Walk Networks for Graph Learning

Shiv Shankar Shankar, Don Towsley

The development of Graph Neural Networks (GNNs) has led to great progress in machine learning on graph-structured data. These networks operate via diffusing information across the graph nodes while capturing the structure of the graph. Recently there has also seen tremendous progress in quantum computing techniques. In this work, we explore applications of multi-particle quantum walks on diffusing information across graphs. Our model is based on learning the operators that govern the dynamics of quantum random walkers on graphs. We demonstrate the effectiveness of our method on classification and regression tasks.

arXiv:2101.00082•Dec 31, 2020•1 citation

On the hitting times of quantum versus random walks

Frédéric Magniez, Ashwin Nayak, Peter C. Richter +1 more

The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of -- or equivalently, to find -- a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case.Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem [19] for the 2D grid. Extending his result, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.

Symposium on Discrete Algorithms•Jan 4, 2009•19 citations
We study hitting times of quantum walks on graphs from a machine learning perspective. Given a graph it is difficult to decide if quantum walks give an advantage relative to classical random walks. It was shown that machine learning can help to detect quantum advantage even though quantum walk and random walk dynamics on the graph has never been simulated. Here we describe the procedure by which training data is generated for the machine learning approach, and discuss possible future improvements.
We explore the use of machine-learning techniques to detect quantum speedup in random walks on graphs. Specifically, we investigate the performance of three different neural-network architectures (variations on fully connected and convolutional neural networks) for identifying linear, cyclic, and random graphs that yield quantum speedups in terms of the hitting time for reaching a target node after starting in another node of the graph. Our results indicate that carefully building the data set for training can improve the performance of the neural networks, but all architectures we test struggle to classify large random graphs and generalize from training on one graph size to testing on another. If classification accuracy can be improved further, valuable insights about quantum advantage may be gleaned from these neural networks, not only for random walks, but more generally for quantum computing and quantum transport.
Abstract Quantum walks are at the heart of modern quantum technologies. They allow to deal with quantum transport phenomena and are an advanced tool for constructing novel quantum algorithms. Quantum walks on graphs are fundamentally different from classical random walks analogs, in particular, they walk faster than classical ones on certain graphs, enabling in these cases quantum algorithmic applications and quantum-enhanced energy transfer. However, little is known about the possible advantages on arbitrary graphs not having explicit symmetries. For these graphs one would need to perform simulations of classical and quantum walk dynamics to check if the speedup occurs, which could take a long computational time. Here we present a new approach for the solution of the quantum speedup problem, which is based on a machine learning algorithm that predicts the quantum advantage by just ‘looking’ at a graph. The convolutional neural network, which we designed specifically to learn from graphs, observes simulated examples and learns complex features of graphs that lead to a quantum advantage, allowing to identify graphs that exhibit quantum advantage without performing any quantum walk or random walk simulations. The performance of our approach is evaluated for line and random graphs, where classification was always better than random guess even for the most challenging cases. Our findings pave the way to an automated elaboration of novel large-scale quantum circuits utilizing quantum walk based algorithms, and to simulating high-efficiency energy transfer in biophotonics and material science.
Abstract Quantum effects are known to provide an advantage in particle transfer across networks. In order to achieve this advantage, requirements on both a graph type and a quantum system coherence must be found. Here, it is shown that the process of finding these requirements can be automated by learning from simulated examples. The automation is done by using a convolutional neural network of a particular type that learns to understand with which network and under which coherence requirements quantum advantage is possible. The machine learning approach is applied to study noisy quantum walks on cycle graphs of different sizes. It is found that it is possible to predict the existence of quantum advantage for the entire decoherence parameter range, even for graphs outside of the training set. The results are of importance for demonstration of advantage in quantum experiments and pave the way toward automating scientific research and discoveries.
Abstract Quantum walk algorithms constitute a central primitive in quantum computation, yet their practical performance often depends sensitively on the choice of execution parameters such as walk depth and initial state. Analytical parameter choices are typically conservative and instance-agnostic, which can lead to suboptimal behavior on specific problem instances. In this work, we propose a general framework for machine-learning-assisted parameterization of quantum walk algorithms, in which classical learning is used to adapt algorithmic parameters without modifying the underlying quantum decision logic. The machine learning component op erates exclusively as a classical control layer, preserving correctness guarantees while improving average-case performance. We demonstrate the framework through an application to the s–t connectivity problem, a canonical benchmark in graph algorithms and complexity theory. Classical simulations of discrete-time quantum walks on randomly generated sparse graphs show that ML-assisted pa rameter selection substantially improves success probability compared to fixed-parameter base lines, yielding multiplicative gains in average performance. These improvements are achieved despite only coarse prediction accuracy, highlighting the robustness of the approach. The results suggest a principled role for machine learning as an adaptive optimization layer in quantum algorithms, offering a practical path toward hybrid quantum–classical methods that enhance performance while maintaining theoretical soundness
The development of Graph Neural Networks (GNNs) has led to great progress in machine learning on graph-structured data. These networks operate via diffusing information across the graph nodes while capturing the structure of the graph. Recently there has also seen tremendous progress in quantum computing techniques. In this work, we explore applications of multi-particle quantum walks on diffusing information across graphs. Our model is based on learning the operators that govern the dynamics of quantum random walkers on graphs. We demonstrate the effectiveness of our method on classification and regression tasks.
The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of -- or equivalently, to find -- a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case.Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem [19] for the 2D grid. Extending his result, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.