The Quipper System

Algorithms.QLS.Main

Description

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:

Synopsis

# Command line interface

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.

# Option processing

An enumeration type for determining what the main function should do.

Constructors

 Circuit Show the whole circuit. Oracle Show only an oracle.

Instances

 # MethodsshowList :: [WhatToShow] -> ShowS #

An enumeration type for selecting an oracle implementation.

Constructors

 Matlab The oracle, implemented with Template Haskell. Blackbox A blackbox oracle.

Instances

 # MethodsshowList :: [OracleSelect] -> ShowS #

An enumeration type for selecting an oracle to print.

Constructors

 OracleR Oracle r. OracleB Oracle b. OracleA Int Bool Oracle A, with selected band and boolean parameter.

Instances

 # MethodsshowList :: [WhichOracle] -> ShowS #

data Options Source #

A data type to hold values set by command line options.

Constructors

 Options Fieldswhat :: WhatToShowWhat kind of thing to output.format :: FormatThe output format.gatebase :: GateBaseWhat kind of gates to decompose into.oracle :: OracleSelectWhich oracle implementation to use.whichoracle :: WhichOracleWhich oracle to output.param :: RunTimeParamRun time parameters.peel :: Intnumber of layers of subroutines to peel away.

Instances

 # MethodsshowList :: [Options] -> ShowS #

The default options.

The list of command line options, in the format required by getOpt.

An enumeration of available oracles and their names.

dopts :: [String] -> IO Options Source #

Process argv-style command line options into an Options structure.

usage :: IO () Source #

Print usage message to stdout.

# The QLS main function

main :: IO () Source #