Tutte seminar - Andrew Childs

One-More Discrete Logarithm Problems

Abstract:

Given an undirected graph G, the continuous-time quantum walk on G is defined as the solution of the Schrodinger equation with the Hamiltonian given by the adjacency matrix of G. Such quantum analogs of classical Markov processes have recently proven to be useful tools for quantum algorithms. In this talk, I will show that even a restricted model of quantum walk captures the full power of quantum computers: in particular, any quantum circuit can be simulated by a continuous-time quantum walk on a low-degree, unweighted graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.