Authors: Artur Scherer, Siun-Chuon Mau, Benoît Valiron

An implementation of the quantum linear system algorithm. The algorithm finds the solution to a sparse system of linear equations Ax=b, with a scaling exponentially better than the best known classical algorithms. Here, A is an N × N sparse matrix, b an N × 1 vector of known values, and x is the solution.

Huge sparse linear systems are common in applied sciences and engineering, such as those resulting from solving partial differential equations by means of Finite Element Method (FEM).

The example analyzed in this program is the scattering of electromagnetic waves off a 2D metallic region, where the FEM allows to convert Maxwell’s equations into a sparse linear system.

The QLS algorithm is based on two main techniques:

• Quantum Phase Estimation, which uses the Quantum Fourier Transform and Hamiltonian Simulation, which makes frequent queries to the oracle for matrix A;
• Quantum Amplitude Estimation, based on Grover’s search technique.

The algorithm is described in:

• Aram W. Harrow, Avinatan Hassidim, Seth Lloyd. Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett. vol. 15, no. 103, pp. 150502 (2009).
• B. D. Clader, B. C. Jacobs, C. R. Sprouse. Quantum algorithm to calculate electromagnetic scattering cross sections. http://arxiv.org/abs/1301.2340.

The present implementation is based on detailed algorithm and oracle specifications that were provided to us by the IARPA QCS program and written by B. David Clader and Bryan C. Jacobs.

Modules:

• Quipper.Algorithms.QLS.Main: Command line interface.
• Quipper.Algorithms.QLS.QSignedInt: An implementation of signed integers.
• Quipper.Algorithms.QLS.QSignedIntAux: Helper module.
• Quipper.Algorithms.QLS.QDouble: An implementation of real numbers, using fixed-point notation.
• Quipper.Algorithms.QLS.RealFunc: Implementation of various analytic functions, for use with the automated circuit generation tool.
• Quipper.Algorithms.QLS.Utils: Helper module.
• Quipper.Algorithms.QLS.QLS: The implementation of the main algorithm.
• Quipper.Algorithms.QLS.CircLiftingImport: Helper module.
• Quipper.Algorithms.QLS.TemplateOracle: Implementation of the oracle, in regular Haskell, together with the "build_circuit" keyword to allow automated circuit generation.

This module provides a command line interface for the Quantum Linear System algorithm. This allows the user, for example, to plug in different oracles, select a gate base, control boxing of subcircuits, and select different output formats.