Predicting quantum advantage by quantum walk with convolutional neural networks

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.

10 pages, 5 figures

References in corpus (38)

• Quantum Machine Learning
• An efficient, multiple range random walk algorithm to calculate the density of states
• The scaling laws of human travel
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Adiabatic Quantum Computing
• Machine learning phases of matter
• Quantum random walks - an introductory overview
• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum algorithms: an overview
• Universal computation by quantum walk
• Quantum walks: a comprehensive review
• Random walks and diffusion on networks
• Photonic quantum information processing: a review
• Defining and detecting quantum speedup
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Universal computation by multi-particle quantum walk
• Reinforcement Learning in Different Phases of Quantum Control
• Active learning machine learns to create new quantum experiments
• Search via Quantum Walk
• Machine Learning Phases of Strongly Correlated Fermions
• Reinforcement Learning with Neural Networks for Quantum Feedback
• Quantum speedup for active learning agents
• Spatial search by quantum walk is optimal for almost all graphs
• Optimizing Quantum Error Correction Codes with Reinforcement Learning
• Efficient and coherent excitation transfer across disordered molecular networks
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Hitting time for quantum walks on the hypercube
• Heat transport through lattices of quantum harmonic oscillators in arbitrary dimensions
• Machine learning for long-distance quantum communication
• Quantum transport efficiency and Fourier's law
• Continuous-time Quantum Walks on a Cycle Graph
• Computational speedups using small quantum devices
• Quantum walks of interacting fermions on a cycle graph
• Open system quantum annealing in mean field models with exponential degeneracy
• Quantum walks on embedded hypercubes
• Hybrid annealing using a quantum simulator coupled to a classical computer
• Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases

Cited by in corpus (12)

• Machine learning for long-distance quantum communication
• Quantum Machine Learning: from physics to software engineering
• A Reinforcement Learning approach for Quantum State Engineering
• Quantum machine learning and quantum biomimetics: A perspective
• Setting up experimental Bell test with reinforcement learning
• Machine learning transfer efficiencies for noisy quantum walks
• Quantum reinforcement learning in the presence of thermal dissipation
• Quantum walk processes in quantum devices
• Benchmarking quantum tomography completeness and fidelity with machine learning
• Quantum walks as thermalizations, with application to fullerene graphs
• Recurrence in discrete-time quantum stochastic walks
• Characterization of anomalous diffusion in one-dimensional quantum walks