The Quipper System

Safe HaskellNone

Algorithms.QLS.Main

Contents

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

data WhatToShow Source #

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

Constructors

Circuit

Show the whole circuit.

Oracle

Show only an oracle.

data OracleSelect Source #

An enumeration type for selecting an oracle implementation.

Constructors

Matlab

The oracle, implemented with Template Haskell.

Blackbox

A blackbox oracle.

data WhichOracle Source #

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.

data Options Source #

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

Constructors

Options 

Fields

Instances

defaultOptions :: Options Source #

The default options.

options :: [OptDescr (Options -> IO Options)] Source #

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

oracle_enum :: [(String, OracleSelect)] Source #

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 #

Main function: read options, then execute the appropriate task.