This file is part of Quipper. Copyright (C) 2011-2016. Please see the file COPYRIGHT for a list of authors, copyright holders, licensing, and other details. All rights reserved. ====================================================================== This is Quipper. Copyright, License, and Disclaimers =================================== See the file COPYRIGHT. Installing the necessary components =================================== For installing on Linux, Mac OS X, and other Unix-like systems: please first see the instructions in INSTALLING, then continue to read below. For installing on Windows: please first see the instructions in INSTALLING.windows, then continue to read below. Configuring the software environment ===================================== Before you can compile Quipper, you have to install some Haskell libraries: * random >= 1.0.1.1 * mtl >= 2.1.2 * primes >= 0.2.1.0 * Lattices >= 0.0.1 (note: "Lattices" must be capitalized) * zlib >= 0.5.4.1 * easyrender >= 0.1.0.0 * fixedprec >= 0.2.1.0 * newsynth >= 0.3.0.1 * containers >= 0.5.2.1 * set-monad >= 0.1.0.0 * QuickCheck >= 2.6 This can be done using Cabal. On the command line, use the following commands: cabal update then: cabal install random cabal install mtl cabal install primes cabal install Lattices cabal install zlib cabal install easyrender cabal install fixedprec cabal install newsynth cabal install containers cabal install set-monad cabal install QuickCheck Note: When upgrading from a previous version of Quipper, please ensure that the fixedprec library is version 0.2.1.0 or newer; Quipper 0.6 will not work with earlier versions of fixedprec. Also ensure that the newsynth library has been compiled against the same version of fixedprec as Quipper. If you get strange error messages related to fixedprec, try cabal install fixedprec cabal install newsynth --reinstall You now have all the necessary Haskell libraries. Special note for GHC 7.4.2: =========================== The combination of GHC 7.4.2 and Template Haskell 2.8.0.0 is not possible, because it triggers a GHC bug. If you get a compilation error of the form: "ghc: panic! (the 'impossible' happened)", follow these steps: # Remove Template Haskell 2.8.0.0: ghc-pkg unregister --force template-haskell-2.8.0.0 # Reinstall QuickCheck (because of a broken dependency). This will # also install template-haskell-2.7.0.0: cabal install QuickCheck Special note for GHC 7.10.*: ============================ Quipper will not work with ghc 7.10. Please use ghc 7.8 or earlier, or ghc 8.0 or later. Browsing the documentation and source code ========================================== While it is possible the browse the Quipper source code in a text editor, it is much nicer to browse the documented source by pointing your web browser to doc/frames.html in this Quipper distribution. The documented source is fully cross-referenced and indexed, with links to color-coded raw source files. Building the documentation ========================== Please note: our documentation uses special mark-up and requires custom tools to be built. Therefore it is not currently possible for users to re-build the documentation. Building the included algorithms and programs ============================================= Compilation, and execution of generated code, are done from the command line interface. The code can be built with "make" from the main directory. This will build an executable file in each Algorithm subdirectory, 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= output format for circuits (default: preview) -g --gatebase= type of gates to decompose into (default: logical) -o select oracle to use (default: orthodox) -n --height= set tree height (positive; default 5) -c --color= color to use with --oracle (0..3, default 0) -s --repeats= set parameter s (iteration count; default 1) -l --large set large problem size: n=300, s=336960 -t
--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= which part of the circuit to use (default: whole) -o --oracle= which oracle to use (default: small) -m --moves= which moves have already been made (default: []) -f --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= 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= output format for circuits (default: ASCII) -g --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 --sub= 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 --delta= discriminant Δ (a.k.a. D) (default: 28) -s --ss= estimated bound on period S, for stage 1 (default: 2) -i estimated bound on log_2 S, for stage 1 (default: 1) -r --rr= approximate regulator R, for stage 4 (default: 12.345) -q The parameter q, for stage 4 (default: 4) -k The parameter k, for stage 4 (default: 3) -n The parameter n, for stage 4 (default: 3) -m The parameter m, for stage 4 (default: 5) --seed= 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 --template= output a particular circuit template -f --format= output format for circuits (default: Preview) -g --gatebase= gates to decompose into (default: Logical) -m --orbitals= number of orbitals (default: 4) -o --occupied= number of occupied orbitals (default: 2) -b --precision= number of precision qubits (default: 3) -D --delta_e= energy range (default: 6.5536) -E --e_max= maximum energy (default: -3876.941) --n0= 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= filename for one-electron data (default: "h_1e_ascii") --h2= filename for two-electron data (default: "h_2e_ascii") -d --datadir= 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 --oracle= output only the oracle (default: r) -f --format= output format for circuits (default: gatecount) -g --gatebase= type of gates to decompose into (default: logical) -o select oracle implementation to use (default: blackbox) -p --param= choose a set of parameters (default: dummy). -P --peel= peel 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= output format for circuits (default: preview) -g --gatebase= type of gates to decompose into (default: logical) -l --l= parameter l (default: 4) -n --n= parameter n (default: 3) -r --r= parameter r (default: 2) -C --QWTFP output the whole circuit (default) -O --oracle output only the oracle -s --subroutine= output the chosen subroutine (default: adder) -Q use alternative qRAM implementation -o 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= output format for circuits (default: eps) -g --gatebase= type of gates to decompose into (default: logical) -n --n= parameter n (default: 5) -b --b= parameter b (default: 5X5 with entries = 1) -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. Invoking the Quipper compiler ============================= The Quipper compiler is called "quipper", and is located in the directory quipper/scripts. The easiest way to use it is to add the "scripts" directory to the environment variable PATH. If you move the quipper script around, make sure to keep the other scripts in the same directory as the quipper script, and to update QUIPPER_BASE in the "quipper" and "quipperi" scripts to point to the directory where the Quipper sources are located. On the Windows operating system, you should use "quipper.bat"; on all other operating systems, just "quipper" will do. In reality, the "quipper" script is a wrapper around the GHC Haskell compiler, providing some pre-processing and setting required compilation options. There is also a "quipperi" script for an interactive version of the compiler, which is akin to "ghci". To try this out, the directory "tests" contains various small stand-alone programs that can be compiled with Quipper, and are useful for demonstrating the basic Quipper idiom. Each program can be compiled and run like this: For example: # to compile and run on Unix (or on Unix with the MSYS/bash): quipper And_gate.hs ./And_gate # to compile and run on Windows with cmd.exe: quipper.bat And_gate.hs And_gate Note that there is also a Makefile, so "make" can be used to build the programs as well. If the previewer is working properly, the circuit should show up in Acrobat Reader. If not, either change "Preview" to "EPS" in the file (for PostScript output), or trouble-shoot the previewer installation (if you are on Windows, see INSTALLING) and/or contact Benoit Valiron or Peter Selinger for help. The naming of built-in gates and many operators can be found out by looking at the documentation of the "Quipper" module (the main public interface of the Quipper system). Troubleshooting Guidelines ========================== In case of problems, please contact * Benoit Valiron * Peter Selinger