Detecting quantum speedup for random walks with artificial neural networks

Abstract: Random walks on graphs are an essential base for crucial algorithms for solving problems, like the boolean satisfiability problem. A speedup of random walks could improve these algorithms. The quantum version of the random walk, quantum walk, is faster than random walks in specific cases, e.g., on some linear graphs. An analysis of when the quantum walk is faster than the random walk can be accomplished analytically or by simulating both the walks on the graph. The problem arises when the graphs grow in size and connectivity. There are no known general rules for what an arbitrary graph not having explicit symmetries should exhibit to promote the quantum walk. Simulations will only answer the question for one single case, and will not provide any general rules for properties the graph should have. Using artificial neural networks (ANNs) as an aid for detecting when the quantum walk is faster on average than random walk on graphs, going from an initial node to a target node, has been done before. The quantum speedup may not be more than polynomial if the initial state of the quantum walk is purely in the initial node of the graph. We investigate starting the quantum walk in various superposition states, with an additional auxiliary node, to maybe achieve a larger quantum speedup. We suggest different ways to add the auxiliary node and select one of these schemes for use in this thesis. The superposition states examined are two stabiliser states and two magic states, inspired by the Gottesman-Knill theorem. According to this theorem, starting a quantum algorithm in a magic state may give an exponential speedup, but starting in a stabilizer state cannot give an exponential speedup, given that only gates from the Clifford group are used in the algorithm, as well as measurements are performed in the Pauli basis. We show that it is possible to train an ANN to classify graphs into what quantum walk was the fastest for various initial states of the quantum walk. The ANN classifies linear graphs and random graphs better than a random guess. We also show that a convolutional neural network (CNN) with a deeper architecture than earlier proposed for the task, is better at classifying the graphs than before. Our findings pave the way for automated research in novel quantum walk-based algorithms.