Important Note: starting with version 4.0, the argument orders of CNOT and Toffoli have been changed and standardized to CNOT(control, target) and Toffoli(control1, control2, target) respectively. Previously, the target argument was first. All of the benchmarks (in Algorithms/) now conform to the new ordering. Also starting with version 4.0, rotation decomposition and Toffoli decomposition are disabled by default. They can be enabled with the -R and -T flags.

What Is ScaffCC?

ScaffCC is a compiler and scheduler for the Scaffold programing language. It is written using the LLVM open-source infrastructure. It is for the purpose of writing and analyzing code for quantum computing applications.

ScaffCC enables researchers to compile quantum applications written in Scaffold to a low-level quantum assembly format (QASM), apply error correction, and generate time and area metrics. It is written to be scalable up to problem sizes in which quantum algorithms outperform classical ones, and as such provide valuable insight into the overheads involved and possible optimizations for a realistic implementation on a future device technology.

If you use ScaffCC in your publications, please cite this work as follows:

Ali JavadiAbhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic Chong and Margaret Martonosi, ScaffCC: A Framework for Compilation and Analysis of Quantum Computing Programs, ACM International Conference on Computing Frontiers (CF 2014), Cagliari, Italy, May 2014

Release Information

Current Release

Version 5.0
Release Date: April 23, 2020

Supported Operating Systems

ScaffCC currently offers support for the following operating systems:

“Ubuntu"
“Red Hat"
"macOS"

This list will continue to grow in the future!

Installation

Note: if you have trouble setting up ScaffCC, you can use our Docker image instead. Simply install Docker and run docker pull epiqc/scaffcc.

Getting ScaffCC

Go to https://github.com/epiqc/ScaffCC

For the Mac and Unix build, download the repository:

   git clone https://github.com/epiqc/ScaffCC.git [dir]

Building ScaffCC

Prerequisites

For macOS build

If not already installed, Xcode command line tool is required in order to build ScaffCC.
```
    xcode-select --install
```
Python 2.7/3: Python is usually bundled with macOS. The built-in version should be sufficient.
CMake: Can be downloaded from https://cmake.org/install or installed via Homebrew
Ninja: for much faster builds: https://ninja-build.org

For Unix build

First you need to install the following dependencies. For each one, you can either install by building from source, or use the package manager of your system (“yum" on Red Hat or “apt-get" on Ubuntu). For ScaffCC only items 1 through 5 are required. For RKQC items 7 through 9 are required.

Static libraries for libstdc++ and glibc
- “Ubuntu": Install GNU gold linker
  
  You can check if you have this now by doing ‘ld -v’ and if it says ‘GNU gold’ you have it
```
    sudo apt-get install binutils-gold
    
```
- “Red Hat"
```
    sudo yum install libstdc++-static 
    sudo yum install glibc-static
    
```
GCC 4.5 or higher: if you need to preserve an older build, consider using ‘update-alternatives’ as system-wide method for preserving and maintaining these.
Clang++ 3.5 or higher
CMake
- “Ubuntu"
```
    sudo apt-get install cmake
    
```
- “Source Build"
  
  There are instructions for downloading and building CMake from source at: https://cmake.org/install
Python 2.7/3+
Ninja, for much faster builds: https://ninja-build.org

Boost 1.48

“Source Build": Boost installation instructions are here: http://www.boost.org/doc/libs/1_48_0/doc/html/bbv2/installation.html

    wget http://sourceforge.net/projects/boost/files/boost/1.48.0/boost_1_48_0.tar.gz
    tar zxf boost_1_48_0.tar.gz && cd boost_1_48_0/
    sudo ./bootstrap.sh
    sudo ./b2 install --prefix=/usr/local

Alternatively, Ubuntu users can install the current Boost version via:

    sudo apt-get install libboost-all-dev

The GNU Multiple Precision Arithmetic Library (gmp and gmpxx)

“Ubuntu": Use tab-completion to verify the correct packages

    sudo apt-get install libgmp-dev libgmpxx4ldbl

“Source Build"

    wget https://ftp.gnu.org/gnu/gmp/gmp-6.0.0a.tar.bz2
    sudo ./configure --disable-shared --enable-static --enable-cxx
    sudo make && sudo make check && sudo make install

The GNU MPFR Library (mpfr)

“Ubuntu"

    sudo apt-get install libmpfr-dev

“Source Build"

    wget http://www.mpfr.org/mpfr-current/mpfr-3.1.4.tar.bz2
    sudo ./configure --disable-shared --enable-static
    sudo make && sudo make check && sudo make install

Installing

Once you have all of the required libraries, simply run ./build.sh at the root of the repository.

Then run ninja llvm-headers followed by ninja opt clang LLVMScaffold in build to build the most necessary components.

Verifying Installation

Included with ScaffCC is a suite of tests designed to verify the integrity of new installations. To access these tests and verify that the installation process completed successfully:

Enter the scripts/ directory:
```
        cd scripts/
    
```
Run the Regression Test Suite:
```
        ./regression_test.sh
    
```

This invocation will compile three small benchmarks, and verify that the generated files match those precompiled on an existing system, which are included in the test cases directory. If the three tests complete with a “Succeeded", the installation was successful.

Using ScaffCC

Types

In programming a quantum algorithm, the Scaffold programming language now offers three distinct data types to the user: qubit, abit, and cbit. The first of these is the traditional qubit, for use in computation and throughout applications. Abit types are specifically "ancilla qubits", or those qubits that are used as intermediary steps in computation. To this end, the function afree() has been provided, which allows for ancilla bits (abits) to be freed explicitly by the programmer. This allows programmers to explicitly conserve usage of ancilla bits throughout their algorithm. The last of these is cbit, for the classical bit of information.

Running the Compiler

To run the compiler, simply use the scaffold.sh script in the main directory, with the name of the program and optional compiler flags.

Compiler Options

To see a list of compiler options which can be passed as flags, run:

./scaffold.sh -h

Usage: ./scaffold.sh [-hv] [-rqfRFckdso] [-l #] [-P #] <filename>.scaffold
    -r   Generate resource estimate (default)
    -q   Generate QASM
    -f   Generate flattened QASM
    -b   Generate OpenQASM
    -R   Enable rotation decomposition
    -T   Enable Toffoli decomposition
    -l   Levels of recursion to run (default=1)
    -P   Set precision of rotation decomposition in decimal digits (default=10)
    -F   Force running all steps
    -c   Clean all files (no other actions)
    -k   Keep all intermediate files (default only keeps specified output,
         but requires recompilation for any new output)
    -d   Dry-run; show all commands to be run, but do not execute
    -s   Generate QX Simulator input file 
    -o   Generate optimized QASM
    -v   Show current ScaffCC version

Basic Example:

The command below runs the compiler with default options on the Binary Welded Tree algorithm, with n=100 and s=100 as problem sizes. The default compiler option is to generate resource estimations (number of qubits and gates).

./scaffold.sh Algorithms/Binary_Welded_Tree/binary_welded_tree.n100s100.scaffold

Sample Scripts

This section describes some of the example scripts contained in the ‘scripts/’ directory. They are written to test the various functionalities of ScaffCC, as detailed below. Each of them automates the process of running multiple compiler passes on an input file to perform the required analysis or optimization.

1. Generating LLVM Intermediate Format: ./gen-ll.sh

Lowers .scaffold source file to .ll file (intermediary LLVM format). Creates <algorithm>.ll The .ll file is the main file in LLVM on which all transformations, optimizations and analysis are performed.

2. Critical Path Estimation: ./gen-cp.sh

Finds critical path information for several different flattening thresholds by doing the following:

Finding module sizes using the ResourceCount2 pass.
Flattening modules based on the found module sizes and the requested threshold.
Finds length of critical path, in terms of number of operations on it. Look for the number in front of “main” in the output.

flattening_thresh.py

Divides modules into different buckets based on their size, to be used for flattening decision purposes.

3. Module Call Frequency Estimation: ./gen-freq-estimate.sh

Generates an estimate of how many times each module is called, which can guide flattening decisions.

4. Generate Longest-Path-First-Schedule (LPFS): ./gen-lpfs.sh

Generates LPFS schedules wit

ScaffCC

Install / Use

README