[llvm-dev] ScaffCC (A Framework for Compilation and Analysis of Quantum Computing Programs) migrated to LLVM 6.0

Thu Nov 2 21:24:15 PDT 2017

Hi ScaffCC and LLVM developers,

My sincere thanks goto:

* Yupan Liu https://github.com/climberpi he introduced ScaffCC to me, 
and he wrote some popular science introduce about quantum computing 
https://www.zhihu.com/people/climberpi/activities

* Ali JavadiAbhari https://github.com/ajavadia he is the core developer 
of ScaffCC, count (ajavadia + epiqc) contribution together :) 
https://github.com/epiqc/ScaffCC/graphs/contributors

* Adam Holmes https://github.com/ah744 he is also core developer and 
provided kind response to ScaffCC users recently 
https://github.com/epiqc/ScaffCC/issues/7#issuecomment-336499375

* Hal Finkel https://www.alcf.anl.gov/staff-directory/hal-finkel he 
taught me how to use Internalize and GlobalDCE PASS correctly but not 
monkey patch 
http://lists.llvm.org/pipermail/llvm-dev/2017-October/118495.html

* Michael Kruse https://github.com/Meinersbur he taught me how to 
workaround use LoopUnroll PASS 
http://lists.llvm.org/pipermail/llvm-dev/2017-October/118420.html

and others who give me kind responses for teaching me about qubit and 
quantum gate https://en.wikipedia.org/wiki/Quantum_gate

ScaffCC has been migrated to LLVM 6.0 https://github.com/ScaffCC and it 
is just able to simulate qubit and quantum gate now, for example:

$ cat cat_state.n04.scaffold (Scaffold is a high level, C-like 
programming language for expressing quantum algorithms)
qmodule catN(qbit *bit, const int n) {
   H(bit[0]);
   for (int i = 1; i < n; i++) {
     CNOT(bit[i], bit[i - 1]);
   }
}

qmodule unCatN(qbit *bit, const int n) {
   for (int i = n - 1; i > 0; i--) {
     CNOT(bit[i], bit[i - 1]);
   }
   H(bit[0]);
}

int main() {
   qbit bits[4];
   catN(bits, 4);
   return 0;
}

$ ./scaffold.sh -fkR Algorithms/Cat_State/cat_state.n04.scaffold (a easy 
to use helper shell script for clang and opt command)
[Scaffold.makefile] Compiling cat_state.n04_merged.scaffold ...
clang version 6.0.0 (git at github.com:llvm-mirror/clang.git 
b4d187902f12e2f8240beb2b50227db637a6d5ba) 
(git at github.com:llvm-mirror/llvm.git 
2653dfaeb3502fd81dc99fde001be69d62a67d13)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /data/project/ScaffCC/ScaffCC/./build/bin
Found candidate GCC installation: /usr/lib/gcc/x86_64-redhat-linux/6.3.1
Found candidate GCC installation: /usr/lib/gcc/x86_64-redhat-linux/6.4.1
Selected GCC installation: /usr/lib/gcc/x86_64-redhat-linux/6.4.1
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Selected multilib: .;@m64
Found CUDA installation: /usr/local/cuda, version 9.0
  "/data/project/ScaffCC/ScaffCC/build/bin/clang-6.0" -cc1 -triple 
x86_64-unknown-linux-gnu -emit-llvm -disable-free -main-file-name 
cat_state.n04_merged.scaffold -mrelocation-model static -mthread-model 
posix -mdisable-fp-elim -fmath-errno -masm-verbose -mconstructor-aliases 
-munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info 
-debugger-tuning=gdb -v -coverage-notes-file 
/data/project/ScaffCC/ScaffCC/cat_state.n04.gcno -resource-dir 
/data/project/ScaffCC/ScaffCC/build/lib/clang/6.0.0 -I 
Algorithms/Cat_State/ -internal-isystem /usr/local/include 
-internal-isystem 
/data/project/ScaffCC/ScaffCC/build/lib/clang/6.0.0/include 
-internal-externc-isystem /include -internal-externc-isystem 
/usr/include -fdebug-compilation-dir /data/project/ScaffCC/ScaffCC 
-ferror-limit 19 -fmessage-length 103 -fobjc-runtime=gcc 
-fdiagnostics-show-option -fcolor-diagnostics -disable-O0-optnone -o 
cat_state.n04.ll -x c cat_state.n04_merged.scaffold
clang -cc1 version 6.0.0 based upon LLVM 6.0.0svn default target 
x86_64-unknown-linux-gnu
ignoring nonexistent directory "/include"
#include "..." search starts here:
#include <...> search starts here:
  Algorithms/Cat_State
  /usr/local/include
  /data/project/ScaffCC/ScaffCC/build/lib/clang/6.0.0/include
  /usr/include
End of search list.
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ...
[Scaffold.makefile] Unrolling Loops (1) ...
[Scaffold.makefile] Cloning Functions (1) ...
Functions Cloned: 1
[Scaffold.makefile] Dead Argument Elimination (1) ...
[Scaffold.makefile] Unrolling Loops (2) ...
[Scaffold.makefile] Cloning Functions (2) ...
Functions Cloned: 0
[Scaffold.makefile] Dead Argument Elimination (2) ...
[Scaffold.makefile] Unrolling Loops (3) ...
[Scaffold.makefile] Cloning Functions (3) ...
Functions Cloned: 0
[Scaffold.makefile] Dead Argument Elimination (3) ...
[Scaffold.makefile] Internalizing and Removing Unused Functions ...
[Scaffold.makefile] Toffoli Decomposition ...
[Scaffold.makefile] Inserting Reverse Functions...
[Scaffold.makefile] Flattening modules ...
[Scaffold.makefile] Flat QASM written to cat_state.n04.qasmf ...

$ cat cat_state.n04.qasmf
qubit bits0
qubit bits1
qubit bits2
qubit bits3
H bits0
CNOT bits1,bits0
CNOT bits2,bits1
CNOT bits3,bits2

$ ./cat_state.n04_qasm
H bits0
CNOT bits1,bits0
CNOT bits2,bits1
CNOT bits3,bits2

$ ./scaffold.sh -s Algorithms/Cat_State/cat_state.n04.scaffold
$ ./qx_simulator_1.0.beta_linux_x86_64 cat_state.n04.qc

=======================================================================================================
_______
       /  ___   \   _  __      ____   ____   __  ___  __  __ __    ___   
______  ____    ___
      /  /   /  |  | |/_/     / __/  /  _/  /  |/  / / / / /  / / / _ | 
/_  __/ / __ \  / _ \
     /  /___/  /  _>  <      _\ \   _/ /   / /|_/ / / /_/ / / /__ / __ 
|  / /   / /_/ / / , _/
     \______/\__\ /_/|_|    /___/  /___/  /_/  /_/  \____/ /____//_/ |_| 
/_/    \____/ /_/|_|
[v0.1 beta]
_______________________________________________________________________________________________________
   [version 0.1 beta - Nader Khammassi - TU Delft, QuTech - 2016 - 
report bugs to: n.khammassi at tudelft.nl]
   [released under Apache License 2.0 terms, license copy at: 
http://www.apache.org/licenses/LICENSE-2.0]
======================================================================================================= 

[+] loading circuit from 'cat_state.n04.qc' ...
[-] loading quantum_code file 'cat_state.n04.qc'...
[+] code loaded successfully.
[+] initializing xpu...
[+] initialized.
[+] creating quantum register of 4 qubits...
[+] executing circuit 'default' (1 iter) ...
--------------[quantum state]--------------
    (+0.707107,+0.000000) |0000> +
    (+0.707107,+0.000000) |1111> +
-------------------------------------------
[>>] measurement prediction:  | X | X | X | X |
-------------------------------------------
[>>] measurement register  :  | 0 | 0 | 0 | 0 |
-------------------------------------------
[+] circuit execution time: +0.000396 sec.

QX: Quantum Computer Simulator 
https://qutech.nl/qx-quantum-computer-simulator/

About HACKING ScaffCC, just git checkout scaff-llvm release_31 branch 
https://github.com/ScaffCC/scaff-llvm/tree/release_31

Then

$ git diff 02b87df98afb03136a1f5076c042696c98524947

to see how ScaffCC modified the original LLVM release_31 branch, so it 
is able to:

* Add more quantum types 
https://github.com/ScaffCC/scaff-llvm/blob/master/include/llvm/IR/Intrinsics.td#L254

* Add more quantum gates 
https://github.com/ScaffCC/scaff-llvm/blob/master/include/llvm/IR/Intrinsics.td#L313

* Optimize Scaffold PASS 
https://github.com/ScaffCC/scaff-llvm/tree/master/lib/Transforms/Scaffold

Also checkout scaff-clang release_31 branch 
https://github.com/ScaffCC/scaff-clang/tree/release_31   to diff

WIP:

Quantum algorithm Shors 
https://github.com/ScaffCC/ScaffCC/tree/master/Algorithms/Shors is too 
heavy! it used up classical computer (my Thinkpad X220 notebook) 
resource https://github.com/ScaffCC/ScaffCC/issues/3 it needs to 
optimize Scaffold and LLVM PASS.

-- 
Regards,
Leslie Zhai -https://reviews.llvm.org/p/xiangzhai/