© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1901.10632 · New Journal of Physics

Predicting quantum advantage by quantum walk with convolutional neural networks

Alexey A. Melnikov, Leonid Evgenevich Fedichkin, Alexander Alodjants

Published Nov 27, 2019• 45 citations

Abstract

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.

DOI: 10.1088/1367-2630/ab5c5e

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

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•21 citations

Supervised graph classification for chiral quantum walks

Artem Kryukov, Roman Abramov, Leonid Evgenevich Fedichkin +2 more

Particle transport in quantum systems, which can be modeled by quantum walks on graphs, demonstrates a faster propagation advantage over the corresponding transport in classical systems. As known from several graph examples, achieving further advantages is possible by adding directional control in quantum walks. One way to introduce directional bias is via time-reversal symmetry breaking that can be achieved with chiral quantum walks, where complex phases are added to the edge weights. However, it is not known for which complex phases values and on which graphs quantum transport can be enhanced. Therefore, the classification of graph properties remains an open problem. Here we tackle this graph classification problem with a graph convolutional neural network trained on a set of simulated examples. We find that chiral quantum-walk dynamics leads to almost always faster transport on hypercubes compared to nonchiral dynamics. We connect our paper to physical implementations of quantum walks in superconducting qubits and optical waveguides. Our results open the possibility and flexibility of experimental implementations in demonstrating quantum-walk advantage.

Physical Review A•Feb 14, 2022•9 citations

Hybrid Quantum-Classical Graph Convolutional Network

Samuel Yen-Chi Chen, Tzu-Chieh Wei, Zhang, Chao +2 more

The high energy physics (HEP) community has a long history of dealing with large-scale datasets. To manage such voluminous data, classical machine learning and deep learning techniques have been employed to accelerate physics discovery. Recent advances in quantum machine learning (QML) have indicated the potential of applying these techniques in HEP. However, there are only limited results in QML applications currently available. In particular, the challenge of processing sparse data, common in HEP datasets, has not been extensively studied in QML models. This research provides a hybrid quantum-classical graph convolutional network (QGCNN) for learning HEP data. The proposed framework demonstrates an advantage over classical multilayer perceptron and convolutional neural networks in the aspect of number of parameters. Moreover, in terms of testing accuracy, the QGCNN shows comparable performance to a quantum convolutional neural network on the same HEP dataset while requiring less than $50\%$ of the parameters. Based on numerical simulation results, studying the application of graph convolutional operations and other QML models may prove promising in advancing HEP research and other scientific fields.

arXiv:2101.06189•Jan 15, 2021•21 citations

Graph Neural Networks on Quantum Computers

Yidong Liao, Xiao‐Ming Zhang, Christopher Ferrie

Graph Neural Networks (GNNs) are powerful machine learning models that excel at analyzing structured data represented as graphs, demonstrating remarkable performance in applications like social network analysis and recommendation systems. However, classical GNNs face scalability challenges when dealing with large-scale graphs. This paper proposes frameworks for implementing GNNs on quantum computers to potentially address the challenges. We devise quantum algorithms corresponding to the three fundamental types of classical GNNs: Graph Convolutional Networks, Graph Attention Networks, and Message-Passing GNNs. A complexity analysis of our quantum implementation of the Simplified Graph Convolutional (SGC) Network shows potential quantum advantages over its classical counterpart, with significant improvements in time and space complexities. Our complexities can have trade-offs between the two: when optimizing for minimal circuit depth, our quantum SGC achieves logarithmic time complexity in the input sizes (albeit at the cost of linear space complexity). When optimizing for minimal qubit usage, the quantum SGC exhibits space complexity logarithmic in the input sizes, offering an exponential reduction compared to classical SGCs, while still maintaining better time complexity. These results suggest our Quantum GNN frameworks could efficiently process large-scale graphs. This work paves the way for implementing more advanced Graph Neural Network models on quantum computers, opening new possibilities in quantum machine learning for analyzing graph-structured data.

arXiv:2405.17060•May 27, 2024•2 citations

Quantum Walk to Train a Classical Artificial Neural Network

Luciano S. de Souza, Jonathan H. A. de Carvalho, Tiago A. E. Ferreira

This work proposes a computational procedure that uses a quantum walk in a complete graph to train classical artificial neural networks. The idea is to apply the quantum walk to search the weight set values. However, it is necessary to simulate a quantum machine to execute the quantum walk. In this way, to minimize the computational cost, the methodology employed to train the neural network will adjust the synaptic weights of the output layer, not altering the weights of the hidden layer, inspired in the method of Extreme Learning Machine. The quantum walk algorithm as a search algorithm is quadratically faster than its classic analog. The quantum walk variance is O(t) while the variance of its classic analog is O(√t), where t is the time or iteration. In addition to computational gain, another advantage of the proposed procedure is to be possible to know a priori the number of iterations required to obtain the solutions, unlike the classical training algorithms based on gradient descendent.

arXiv:2109.00128•Brazilian Conference on Intelligent Systems•Oct 1, 2019•9 citations

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.

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 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.

Particle transport in quantum systems, which can be modeled by quantum walks on graphs, demonstrates a faster propagation advantage over the corresponding transport in classical systems. As known from several graph examples, achieving further advantages is possible by adding directional control in quantum walks. One way to introduce directional bias is via time-reversal symmetry breaking that can be achieved with chiral quantum walks, where complex phases are added to the edge weights. However, it is not known for which complex phases values and on which graphs quantum transport can be enhanced. Therefore, the classification of graph properties remains an open problem. Here we tackle this graph classification problem with a graph convolutional neural network trained on a set of simulated examples. We find that chiral quantum-walk dynamics leads to almost always faster transport on hypercubes compared to nonchiral dynamics. We connect our paper to physical implementations of quantum walks in superconducting qubits and optical waveguides. Our results open the possibility and flexibility of experimental implementations in demonstrating quantum-walk advantage.

The high energy physics (HEP) community has a long history of dealing with large-scale datasets. To manage such voluminous data, classical machine learning and deep learning techniques have been employed to accelerate physics discovery. Recent advances in quantum machine learning (QML) have indicated the potential of applying these techniques in HEP. However, there are only limited results in QML applications currently available. In particular, the challenge of processing sparse data, common in HEP datasets, has not been extensively studied in QML models. This research provides a hybrid quantum-classical graph convolutional network (QGCNN) for learning HEP data. The proposed framework demonstrates an advantage over classical multilayer perceptron and convolutional neural networks in the aspect of number of parameters. Moreover, in terms of testing accuracy, the QGCNN shows comparable performance to a quantum convolutional neural network on the same HEP dataset while requiring less than

50\%

of the parameters. Based on numerical simulation results, studying the application of graph convolutional operations and other QML models may prove promising in advancing HEP research and other scientific fields.

Graph Neural Networks (GNNs) are powerful machine learning models that excel at analyzing structured data represented as graphs, demonstrating remarkable performance in applications like social network analysis and recommendation systems. However, classical GNNs face scalability challenges when dealing with large-scale graphs. This paper proposes frameworks for implementing GNNs on quantum computers to potentially address the challenges. We devise quantum algorithms corresponding to the three fundamental types of classical GNNs: Graph Convolutional Networks, Graph Attention Networks, and Message-Passing GNNs. A complexity analysis of our quantum implementation of the Simplified Graph Convolutional (SGC) Network shows potential quantum advantages over its classical counterpart, with significant improvements in time and space complexities. Our complexities can have trade-offs between the two: when optimizing for minimal circuit depth, our quantum SGC achieves logarithmic time complexity in the input sizes (albeit at the cost of linear space complexity). When optimizing for minimal qubit usage, the quantum SGC exhibits space complexity logarithmic in the input sizes, offering an exponential reduction compared to classical SGCs, while still maintaining better time complexity. These results suggest our Quantum GNN frameworks could efficiently process large-scale graphs. This work paves the way for implementing more advanced Graph Neural Network models on quantum computers, opening new possibilities in quantum machine learning for analyzing graph-structured data.

This work proposes a computational procedure that uses a quantum walk in a complete graph to train classical artificial neural networks. The idea is to apply the quantum walk to search the weight set values. However, it is necessary to simulate a quantum machine to execute the quantum walk. In this way, to minimize the computational cost, the methodology employed to train the neural network will adjust the synaptic weights of the output layer, not altering the weights of the hidden layer, inspired in the method of Extreme Learning Machine. The quantum walk algorithm as a search algorithm is quadratically faster than its classic analog. The quantum walk variance is O(t) while the variance of its classic analog is O(√t), where t is the time or iteration. In addition to computational gain, another advantage of the proposed procedure is to be possible to know a priori the number of iterations required to obtain the solutions, unlike the classical training algorithms based on gradient descendent.