quipper-algorithms: A set of algorithms implemented in Quipper.

[ bsd3, library, program, quipper ] [ Propose Tags ]

This package provides seven algorithms that have been implemented in Quipper. They are: BF - Boolean formula algorithm, BWT - Binary welded tree algorithm, CL - Class number algorithm, GSE - Ground state estimation algorithm, QLS - Quantum linear systems algorithm, TF - Triangle finding algorithm, USV - Unique shortest vector algorithm.


[Skip to Readme]
Versions [faq] 0.9.0.0
Change log ChangeLog
Dependencies array (>=0.5), base (>=4.5 && <5), containers (>=0.5.2.1), deepseq (>=1.4), easyrender (>=0.1.0.0), filepath (>=1.4), Lattices (>=0.0.1), mtl (>=2.1.2), newsynth (>=0.3.0.1), primes (>=0.2.1.0), QuickCheck (>=2.6), quipper-algorithms, quipper-language (>=0.9.0.0), quipper-libraries (>=0.9.0.0), quipper-utils (>=0.9.0.0), random (>=1.0.1.1) [details]
License BSD-3-Clause
Copyright Copyright (c) 2011-2019. All rights reserved.
Author Alexander S. Green, Keith Kim, Peter LeFanu Lumsdaine, Siun-Chuon Mau, Neil J. Ross, Artur Scherer, Peter Selinger, Benoît Valiron, Alexandr Virodov
Maintainer selinger@mathstat.dal.ca
Category Quipper
Home page http://www.mathstat.dal.ca/~selinger/quipper/
Uploaded by PeterSelinger at Mon Dec 30 05:32:08 UTC 2019
Distributions NixOS:0.9.0.0
Executables usv, tf, qls, gse, cl, bwt, bf
Downloads 91 total (48 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-12-30 [all 1 reports]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for quipper-algorithms-0.9.0.0

[back to package description]
Running the included algorithms
===============================

Each algorithm builds an executable file, which can be run with
various command line parameters to do different things. Run each
command with option --help to see a summary of the usage information.

In the following, we describe the set of options for the algorithms
that were implemented.


Running the bwt program
=======================

Usage for Binary Welded Tree algorithm:
---------------------------------------

Usage: bwt [OPTION...]
  -h             --help                 print usage info and exit
  -C             --circuit              output the whole circuit (default)
  -O             --oracle               output only the oracle
  -K             --oraclec              output the "classical" oracle as a classical circuit
  -G             --graph                print colored graph computed from oracle
  -S             --simulate             run simulations of some circuit fragments for tree height n
  -f <format>    --format=<format>      output format for circuits (default: preview)
  -g <gatebase>  --gatebase=<gatebase>  type of gates to decompose into (default: logical)
  -o <oracle>                           select oracle to use (default: orthodox)
  -n <n>         --height=<n>           set tree height (positive; default 5)
  -c <c>         --color=<c>            color to use with --oracle (0..3, default 0)
  -s <s>         --repeats=<s>          set parameter s (iteration count; default 1)
  -l             --large                set large problem size: n=300, s=336960
  -t <dt>        --dt=<dt>              set parameter dt (simulation time step; default pi/180)
Possible values for format are: eps, pdf, ps, postscript, ascii, preview, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.
Possible values for oracle are: orthodox, simple, blackbox, classical, template, optimized.

Examples of command line options:
---------------------------------

* Show the complete circuit for the BWT algorithm using the
  "orthodox" (official GFI) oracle, with n=5 and s=1:

  ./bwt -C -o orthodox -n 5 -s 1

  (One can point out the different parts of the algorithm: 8 oracle
  calls, and 4 very short diffusion steps).

* Show the same, using the "Template Haskell" oracle: this oracle is
  much larger, but automatically generated from classical code (and
  completely unoptimized):

  ./bwt -C -o template -n 5 -s 1

  The "template oracle" is defined in BWT/Template.hs. See the
  documentation of the module Quipper/CircLifting for how it works.

* Show the graph of the BWT algorithm, which is obtained by
  simulating the orthodox oracle (and therefore offers some evidence
  for the correctness of the oracle implementation):

  ./bwt -G -o orthodox -n 5

* Show the orthodox oracle for n=300. Note that this will result in a
  big file. One has to zoom in substantially to see gates. 

  ./bwt -O -o orthodox -n 300

* Show the complete circuit for the BWT algorithm, but decompose
  everything into binary gates:

  ./bwt -C -o orthodox -n 5 -s 1 -g binary 

* Show the oracle from Figure 1a (alternate oracle).

  ./bwt -C -o figure1a

* The same, decomposed into binary+Toffoli gates, or binary gates
  only, respectively:

  ./bwt -C -o figure1a -g toffoli
  ./bwt -C -o figure1a -g binary

* Show gate counts for BWT algorithm with n=300 and s=1, using
  "orthodox" oracle:

  ./bwt -C -o orthodox -n 300 -s 1 -f gatecount

* Show gate counts for same, after decomposition to binary gates:

  ./bwt -C -o orthodox -n 300 -s 1 -f gatecount -g binary 

Obviously, most other combinations of command line options are also
possible, for example: decompose to toffoli gates and then simulate
and show the graph. Some other combinations are not legal: for
example, decomposing to binary gates and then simulating. (The
classical simulator will complain that the circuit is not boolean; it
contains "V" gates).

* Similarly, one can run demos for the triangle finding
  algorithm using various command line options. 

Note that the triangle finding algorithm is not a deliverable; it is a
work in progress. The only implemented algorithm that is officially a
deliverable is the "orthodox" BWT implementation in BWT.BWT.

Running the bf program
======================

Usage for the Boolean Formula algorithm:
----------------------------------------

Usage: bf [OPTION...]
  -C             --circuit              output the whole circuit (default)
  -D             --demo                 run a demo of the circuit
  -H             --hexboard             output a representation of the initial state of the given oracle, i.e. the game played so far
  -p <part>      --part=<part>          which part of the circuit to use (default: whole)
  -o <oracle>    --oracle=<oracle>      which oracle to use (default: small)
  -m <moves>     --moves=<moves>        which moves have already been made (default: [])
  -f <format>    --format=<format>      output format for circuits (default: _preview)
  -d             --dummy                set to only use a dummy HEX gate instead of the full hex circuit
  -h             --help                 print usage info and exit
  -g <gatebase>  --gatebase=<gatebase>  type of gates to decompose the output circuit into (default: logical)
Possible values for part are: whole, u, oracle, hex, checkwin_red, diffuse, walk, undo_oracle.
Possible values for oracle are: 9by7, small, custom x y t.
Possible values for format are: eps, pdf, ps, postscript, ascii, preview, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.

Running the cl program
======================

Usage for the Class Number algorithm:
-------------------------------------

Usage: cl [OPTION...]
  -h               --help                 print usage info and exit
  -f <format>      --format=<format>      output format for circuits        (default: ASCII)
  -g <gatebase>    --gatebase=<gatebase>  gates to decompose into           (default: Logical)
  -1                                      output the circuit for stage 1 of the algorithm (default)
  -4                                      output the circuit for stage 4 of the algorithm
  -S <subroutine>  --sub=<subroutine>     output the circuit for a specific subroutine
  -R               --regulator            classically, find the regulator, given Δ
  -F                                      classically, find the fundamental unit, given Δ
  -P                                      classically, find the fundamental solution of Pell’s equation, given Δ
  -d <N>           --delta=<N>            discriminant Δ (a.k.a. D)                 (default: 28)
  -s <N>           --ss=<N>               estimated bound on period S, for stage 1 (default: 2)
  -i <N>                                  estimated bound on log_2 S, for stage 1 (default: 1)
  -r <N>           --rr=<N>               approximate regulator R, for stage 4  (default: 12.345)
  -q <N>                                  The parameter q, for stage 4        (default: 4)
  -k <N>                                  The parameter k, for stage 4        (default: 3)
  -n <N>                                  The parameter n, for stage 4        (default: 3)
  -m <N>                                  The parameter m, for stage 4        (default: 5)
                   --seed=<N>             Random seed (0 for seed from time)(default: 1)
Possible values for format are: eps, pdf, ps, postscript, ascii, preview, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.
Possible values for subroutine are: rho, rhoinv, normalize, dotprod, starprod, fn.

Running the gse program
=======================

Usage for Ground State Estimation algorithm:
--------------------------------------------

Usage: gse [OPTION...]
  -h             --help                 print usage info and exit
  -C             --circuit              output the whole circuit (default)
  -T <indices>   --template=<indices>   output a particular circuit template
  -f <format>    --format=<format>      output format for circuits (default: Preview)
  -g <gatebase>  --gatebase=<gatebase>  gates to decompose into (default: Logical)
  -m <N>         --orbitals=<N>         number of orbitals (default: 4)
  -o <N>         --occupied=<N>         number of occupied orbitals (default: 2)
  -b <N>         --precision=<N>        number of precision qubits (default: 3)
  -D <energy>    --delta_e=<energy>     energy range (default: 6.5536)
  -E <energy>    --e_max=<energy>       maximum energy (default: -3876.941)
                 --n0=<N>               use N_k = n0 * 2^k (default: N_k = 1)
  -l             --large                set large problem size (m=208, o=84, b=12, n0=100)
  -x             --orthodox             use the Coulomb operator of Whitman et al.
                 --h1=<file>            filename for one-electron data (default: "h_1e_ascii")
                 --h2=<file>            filename for two-electron data (default: "h_2e_ascii")
  -d <file>      --datadir=<file>       directory for one- and two-electron data (default: current)
Possible values for format are: eps, pdf, ps, postscript, ascii, preview, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.
Indices can be specified as p,q or p,q,r,s (with no spaces)

Running the qls program
=======================

Usage for Quantum Linear Systems algorithm:
-------------------------------------------

Usage: qls [OPTION...]
  -h             --help                 print usage info and exit
  -C             --circuit              output the whole circuit (default)
  -O <name>      --oracle=<name>        output only the oracle <name> (default: r) 
  -f <format>    --format=<format>      output format for circuits (default: gatecount)
  -g <gatebase>  --gatebase=<gatebase>  type of gates to decompose into (default: logical)
  -o <oracle>                           select oracle implementation to use (default: blackbox)
  -p <param>     --param=<param>        choose a set of parameters (default: dummy).
  -P <n>         --peel=<n>             peel <n> layers of boxed subroutines (default: 0).
Possible values for format are: ascii, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.
Possible values for oracle implementation are: matlab, blackbox.
Possible values for param are: dummy, small, large.
Possible values for oracle are: r, b, A[band][t|f]. E.g. "-OA1t" asks for band 1 with boolean argument True. For all three oracles, the factors are set up to 1.0.

Running the tf program
======================

Usage for Triangle Finding algorithm:
-------------------------------------

Usage: tf [OPTION...]
  -h               --help                     print usage info and exit
  -f <format>      --format=<format>          output format for circuits (default: preview)
  -g <gatebase>    --gatebase=<gatebase>      type of gates to decompose into (default: logical)
  -l <l>           --l=<l>                    parameter l (default: 4)
  -n <n>           --n=<n>                    parameter n (default: 3)
  -r <r>           --r=<r>                    parameter r (default: 2)
  -C               --QWTFP                    output the whole circuit (default)
  -O               --oracle                   output only the oracle
  -s <subroutine>  --subroutine=<subroutine>  output the chosen subroutine (default: adder)
  -Q                                          use alternative qRAM implementation
  -o <oracle>                                 select oracle to use (default: blackbox)
  -A               --arith                    test/simulate the arithmetic routines
  -T               --oracletest               test/simulate the oracle
Possible values for format are: eps, pdf, ps, postscript, ascii, preview, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.
Possible values for oracle are: orthodox, blackbox.
Possible values for subroutine are: zero, initialize, hadamard, setup, qwsh, diffuse, fetcht, storet, fetchstoret, fetche, fetchstoree, update, swap, a15, a16, a17, a18, gcqwalk, gcqwstep, convertnode, testequal, pow17, mod3, sub, add, mult.

Running the usv program
=======================

Usage for Unique Shortest Vector algorithm:
-------------------------------------------

Usage: usv [OPTION...]
  -h             --help                 print usage info and exit
  -f <format>    --format=<format>      output format for circuits (default: eps)
  -g <gatebase>  --gatebase=<gatebase>  type of gates to decompose into (default: logical)
  -n <n>         --n=<n>                parameter n (default: 5)
  -b <b>         --b=<b>                parameter b (default: 5X5 with entries = 1)
  -s <s>         --s=<s>                Random number generator seed s (default: 1)
  -F                                    output subroutine f (depends on b).
  -G                                    output subroutine g (depends on b).
  -H                                    output subroutine h (depends on n).
  -U                                    output algorithm 1 (depends on b).
  -Q                                    output algorithm 2 (depends on b).
  -R                                    output algorithm 3 (depends on b).
  -T                                    output algorithm 4 (depends on n).
  -S                                    output sieving subroutine (depends on n).
  -D                                    output algorithm 5 (depends on n).
  -t                                    test subroutine h (depends on n).
Possible values for format are: eps, pdf, ps, postscript, ascii, preview, gatecount.
Possible values for gatebase are: logical, binary, toffoli, cliffordt_old, cliffordt, cliffordt_keepphase, standard, strict, approximate, approximate_keepphase, exact, trimcontrols.