Implementation of a digitally encoded multigrid algorithm on a quantum computer

Abstract

Multigrid has become a popular method for solving some of the most challenging real-world computational problems, such as computational fluid dynamics (CFD). The reason for this is the very good scaling properties of multigrid, which is often linear, or close to linear, with respect to problem size. In this paper a method is presented, which can be used to implement a quantum version of the multigrid algorithm. The method relies upon a quantum state that is maintained in a equal superposition throughout the calculation, and where information is encoded digitally in the qubits in a way more similar to a classical computer. This differs from many existing quantum algorithms where information is encoded in the amplitudes of the quantum states in the superposition. At the core of the method is an algorithm for sharing information between the states in the superposition. An exponential speedup is provided for classes of problems where the solution vector can be compressed efficiently, and where a quantum compiler can reduce the quantum circuit depth efficiently.