epiqc / scaffcc Goto Github PK

Compilation, analysis and optimization framework for the Scaffold quantum programming language.

License: BSD 2-Clause "Simplified" License

C 20.66% Makefile 0.01% C++ 74.55% CMake 0.34% Objective-C 1.75% Python 1.01% HTML 0.66% CSS 0.01% Objective-C++ 0.43% Cuda 0.21% Shell 0.08% M 0.01% LLVM 0.02% Perl 0.10% JavaScript 0.02% Emacs Lisp 0.01% OCaml 0.10% Assembly 0.02% Batchfile 0.01% Roff 0.01%

quantum-algorithms quantum-computing quantum-programming-language

scaffcc's People

Contributors

Stargazers

Watchers

scaffcc's Issues

Building braidflash is not working

Hello, I'd like to use ScaffCC in my research, but I found some problems when executing braidflash.

1

First of all, ScaffCC/braidflash/Makefile is not working because it contains argparse.cpp file as SOURCE, which is not existing on the directory.

2

So I tried erasing the argparse.cpp, leaving only braidflash.cpp as SOURCE. However I found another problems that ScaffCC/scripts/gen-lpfs.sh does not generate .lpfs and .cg file, which is necessary for executing braidflash.

3

Lastly, I tried to rename the files that are generated by the command
../scripts/gen-lpfs.sh ../Algorithms/Square Root/square root.n10.scaffold

to this.
square_root.n10.flat010k.simd.2.1024.leaves.local =====> square_root.n10.flat010k.lpfs
square_root.n10.flat010k.simd.2.1024.local.time ====> square_root.n10.flat010k.cg

but braidflash emits messages like Physical error rate is higher than the code threshold. Terminating.. which is quite suspicious.

Thank you for your awesome work. I hope my problems are treated soon.

Segmentation fault when generating QASM when file contains `cbit c = MeasZ(q);`

Running scaffold.sh -f for the following file:

int main() {
    qbit q[1];
    cbit c = MeasZ(q[0]);
    return 0;
}

causes Segmentation fault :

measure_qubit.scaffold                                                                                                                                                                                                                
[Scaffold.makefile] Compiling measure_qubit_merged.scaffold ...                                                                                                                                                                       
[Scaffold.makefile] Transforming cbits ...                                                                                                                                                                                            
[Scaffold.makefile] O1 optimizations ...                                                                                                                                                                                              
[Scaffold.makefile] Unrolling Loops (1) ...                                                                                                                                                                                           
[Scaffold.makefile] Cloning Functions (1) ...                                                                                                                                                                                         
Functions Cloned: 0                                                                                                                                                                                                                   
[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] Internalizing and Removing Unused Functions ...                                                                                                                                                                   
[Scaffold.makefile] Inserting Reverse Functions...                                                                                                                                                                                    
[Scaffold.makefile] Flattening modules ...                                                                                                                                                                                            
/bin/bash: line 1:    76 Segmentation fault      /root/ScaffCC/build/Release+Asserts/bin/opt -load /root/ScaffCC/build/Release+Asserts/lib/Scaffold.so -gen-qasm measure_qubit12.inlined.ll 2> measure_qubit.qasmh > /dev/null

Running scaffold.sh does not cause any problems. Above is a problem when running on epiqc/scaffcc Docker.

-o is not working for QFT

$ ./scaffold.sh -o Algorithms/QFT/qft.scaffold

/bin/bash: line 5: 104 Segmentation fault ./build/Release+Asserts/bin/opt -load ./build/Release+Asserts/lib/Scaffold.so -Optimize qft12.inlined.ll 2> qft_optimized.qasmf > /dev/null
[Scaffold.makefile] Optimized circuit written to qft_optimized.qasmf ...

[PASS] FlattenModule generated 6837+K sha1.n12812.inlined.ll

Hi ScaffCC developers,

based on LLVM release_31 before the commit 871865b

$ ./scaffold.sh -fkR Algorithms/SHA-1/sha1.n128.scaffold
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ...
[Scaffold.makefile] Unrolling Loops (1) ...
[Scaffold.makefile] Cloning Functions (1) ...
Functions Cloned: 0
[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] Internalizing and Removing Unused Functions ...
[Scaffold.makefile] Compiling RKQC Functions ...
[Scaffold.makefile] Toffoli Decomposition ...
[Scaffold.makefile] Inserting Reverse Functions...
[Scaffold.makefile] Flattening modules ...  <-- CPU 100%

Before FlattenModule PASS, sha1.n12812.ll is 222+K, but after FlattenModule, sha1.n12812.inlined.ll is 6837+K! then gen-gasm failed to transform such HUGE LLVM IR.

@eddieschoute Please try @ajavadia latest commit 871865b it might be able to work for SHA-1 algorithm #7 (comment)

Regards,
Leslie Zhai

CMake Error

Hello, I have installed all the prerequisites and tried using docker as well but cannot get past this step. I'm using Ubuntu 20.04.

CMake Error at utils/benchmark/src/CMakeLists.txt:19 (add_library): No SOURCES given to target: benchmark CMake Generate step failed. Build files cannot be regenerated correctly.

output.txt

Segmentation fault when assigning several cbit values

The following code

int main() {
    qbit q[2];
    cbit mres[2];
    mres[0] = MeasZ(q[0]);
    mres[1] = MeasZ(q[1]);
    if( mres[0] == 1 ) { Z(q[0]); }
    if( mres[1] == 1) { X(q[1]); }
    return 0;
}

casues segementation fault when running both scaffold.sh and scaffold.sh -f on epiqc/scaffcc Docker image.

Dummy Issue

Issue Tracking Test

Test Issue

Test

[PASS] O1 optimizations wrongly use -loop-simplify

Hi ScaffCC developers,

-loop-simplify will produce the disable unroll meta data (!llvm.loop !2), for example:

$ cat cat_state.n044.ll
; ModuleID = 'cat_state.n045a.ll'
source_filename = "cat_state.n04_merged.scaffold"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: noinline nounwind uwtable
define void @catN(i16* %bit, i32 %n) local_unnamed_addr #0 {
entry:
   %0 = load i16, i16* %bit, align 2
   tail call void @llvm.H.i16(i16 %0)
   %cmp1 = icmp sgt i32 %n, 1
   br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
   %1 = add i32 %n, -1
   %2 = add i32 %n, -2
   %xtraiter = and i32 %1, 1
   %3 = icmp ult i32 %2, 1
   br i1 %3, label %for.cond.for.end_crit_edge.unr-lcssa, label 
%for.body.lr.ph.new

for.body.lr.ph.new:                               ; preds = %for.body.lr.ph
   %unroll_iter = sub i32 %1, %xtraiter
   br label %for.body

for.body:                                         ; preds = %for.body, 
%for.body.lr.ph.new
   %inc3 = phi i32 [ 1, %for.body.lr.ph.new ], [ %inc.1, %for.body ]
   %niter = phi i32 [ %unroll_iter, %for.body.lr.ph.new ], [ 
%niter.nsub.1, %for.body ]
   %idxprom = sext i32 %inc3 to i64
   %arrayidx1 = getelementptr inbounds i16, i16* %bit, i64 %idxprom
   %4 = load i16, i16* %arrayidx1, align 2
   %sub = add nsw i32 %inc3, -1
   %idxprom2 = sext i32 %sub to i64
   %arrayidx3 = getelementptr inbounds i16, i16* %bit, i64 %idxprom2
   %5 = load i16, i16* %arrayidx3, align 2
   tail call void @llvm.CNOT.i16.i16(i16 %4, i16 %5)
   %inc = add nsw i32 %inc3, 1
   %niter.nsub = sub i32 %niter, 1
   %idxprom.1 = sext i32 %inc to i64
   %arrayidx1.1 = getelementptr inbounds i16, i16* %bit, i64 %idxprom.1
   %6 = load i16, i16* %arrayidx1.1, align 2
   %idxprom2.1 = sext i32 %inc3 to i64
   %arrayidx3.1 = getelementptr inbounds i16, i16* %bit, i64 %idxprom2.1
   %7 = load i16, i16* %arrayidx3.1, align 2
   tail call void @llvm.CNOT.i16.i16(i16 %6, i16 %7)
   %inc.1 = add nsw i32 %inc, 1
   %niter.nsub.1 = sub i32 %niter.nsub, 1
   %niter.ncmp.1 = icmp ne i32 %niter.nsub.1, 0
   br i1 %niter.ncmp.1, label %for.body, label 
%for.cond.for.end_crit_edge.unr-lcssa

for.cond.for.end_crit_edge.unr-lcssa:             ; preds = %for.body, 
%for.body.lr.ph
   %inc3.unr = phi i32 [ 1, %for.body.lr.ph ], [ %inc.1, %for.body ]
   %lcmp.mod = icmp ne i32 %xtraiter, 0
   br i1 %lcmp.mod, label %for.body.epil, label %for.end

for.body.epil:                                    ; preds = 
%for.cond.for.end_crit_edge.unr-lcssa
   %inc3.epil = phi i32 [ %inc3.unr, %for.cond.for.end_crit_edge.unr-lcssa ]
   %idxprom.epil = sext i32 %inc3.epil to i64
   %arrayidx1.epil = getelementptr inbounds i16, i16* %bit, i64 
%idxprom.epil
   %8 = load i16, i16* %arrayidx1.epil, align 2
   %sub.epil = add nsw i32 %inc3.epil, -1
   %idxprom2.epil = sext i32 %sub.epil to i64
   %arrayidx3.epil = getelementptr inbounds i16, i16* %bit, i64 
%idxprom2.epil
   %9 = load i16, i16* %arrayidx3.epil, align 2
   tail call void @llvm.CNOT.i16.i16(i16 %8, i16 %9)
   %inc.epil = add nsw i32 %inc3.epil, 1
   %cmp.epil = icmp slt i32 %inc.epil, %n
   br label %for.end

for.end:                                          ; preds = 
%for.body.epil, %for.cond.for.end_crit_edge.unr-lcssa, %entry
   ret void
}

; Function Attrs: nounwind
declare void @llvm.H.i16(i16) #1

; Function Attrs: nounwind
declare void @llvm.CNOT.i16.i16(i16, i16) #1

; Function Attrs: noinline nounwind uwtable
define void @unCatN(i16* %bit, i32 %n) local_unnamed_addr #0 {
entry:
   %storemerge1 = add nsw i32 %n, -1
   %cmp2 = icmp sgt i32 %n, 1
   br i1 %cmp2, label %for.body.peel, label %for.end

for.body.peel:                                    ; preds = %entry
   %idxprom.peel = sext i32 %storemerge1 to i64
   %arrayidx.peel = getelementptr inbounds i16, i16* %bit, i64 %idxprom.peel
   %0 = load i16, i16* %arrayidx.peel, align 2
   %sub1.peel = add nsw i32 %n, -2
   %idxprom2.peel = sext i32 %sub1.peel to i64
   %arrayidx3.peel = getelementptr inbounds i16, i16* %bit, i64 
%idxprom2.peel
   %1 = load i16, i16* %arrayidx3.peel, align 2
   tail call void @llvm.CNOT.i16.i16(i16 %0, i16 %1)
   %storemerge.peel = add nsw i32 %storemerge1, -1
   %cmp.peel = icmp sgt i32 %storemerge1, 1
   br i1 %cmp.peel, label %for.body.lr.ph.peel.newph, label %for.end

for.body.lr.ph.peel.newph:                        ; preds = %for.body.peel
   br label %for.body

for.body:                                         ; preds = %for.body, 
%for.body.lr.ph.peel.newph
   %storemerge5 = phi i32 [ %storemerge.peel, %for.body.lr.ph.peel.newph 
], [ %storemerge, %for.body ]
   %storemerge.in3 = phi i32 [ %storemerge1, %for.body.lr.ph.peel.newph 
], [ %storemerge5, %for.body ]
   %idxprom = sext i32 %storemerge5 to i64
   %arrayidx = getelementptr inbounds i16, i16* %bit, i64 %idxprom
   %2 = load i16, i16* %arrayidx, align 2
   %sub1 = add nsw i32 %storemerge.in3, -2
   %idxprom2 = sext i32 %sub1 to i64
   %arrayidx3 = getelementptr inbounds i16, i16* %bit, i64 %idxprom2
   %3 = load i16, i16* %arrayidx3, align 2
   tail call void @llvm.CNOT.i16.i16(i16 %2, i16 %3)
   %storemerge = add nsw i32 %storemerge5, -1
   %cmp = icmp sgt i32 %storemerge5, 1
   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !2

for.end:                                          ; preds = %for.body, 
%for.body.peel, %entry
   %.lcssa = phi i16* [ %bit, %entry ], [ %bit, %for.body.peel ], [ 
%bit, %for.body ]
   %4 = load i16, i16* %.lcssa, align 2
   tail call void @llvm.H.i16(i16 %4)
   ret void
}

; Function Attrs: noinline nounwind uwtable
define i32 @main() local_unnamed_addr #0 {
entry:
   %bits = alloca [4 x i16], align 2
   %arraydecay = getelementptr inbounds [4 x i16], [4 x i16]* %bits, i64 
0, i64 0
   call void @catN_IP4_IPx_IPx_IPx_DPx_DPx_DPx_DPx(i16* %arraydecay, i32 
undef)
   ret i32 0
}

define void @catN_IP4_IPx_IPx_IPx_DPx_DPx_DPx_DPx(i16* %bit, i32 %n) {
entry.:
   %0 = load i16, i16* %bit, align 2
   tail call void @llvm.H.i16(i16 %0)
   %arrayidx1. = getelementptr inbounds i16, i16* %bit, i64 1
   %1 = load i16, i16* %arrayidx1., align 2
   %2 = load i16, i16* %bit, align 2
   tail call void @llvm.CNOT.i16.i16(i16 %1, i16 %2)
   %arrayidx1.1. = getelementptr inbounds i16, i16* %bit, i64 2
   %3 = load i16, i16* %arrayidx1.1., align 2
   %arrayidx3.1. = getelementptr inbounds i16, i16* %bit, i64 1
   %4 = load i16, i16* %arrayidx3.1., align 2
   tail call void @llvm.CNOT.i16.i16(i16 %3, i16 %4)
   %arrayidx1.epil. = getelementptr inbounds i16, i16* %bit, i64 3
   %5 = load i16, i16* %arrayidx1.epil., align 2
   %arrayidx3.epil. = getelementptr inbounds i16, i16* %bit, i64 2
   %6 = load i16, i16* %arrayidx3.epil., align 2
   tail call void @llvm.CNOT.i16.i16(i16 %5, i16 %6)
   ret void
}

attributes #0 = { noinline nounwind uwtable 
"correctly-rounded-divide-sqrt-fp-math"="false" 
"disable-tail-calls"="false" "less-precise-fpmad"="false" 
"no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" 
"no-infs-fp-math"="false" "no-jump-tables"="false" 
"no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" 
"no-trapping-math"="false" "stack-protector-buffer-size"="8" 
"target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" 
"unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 6.0.0 (git at github.com:llvm-mirror/clang.git 
0aed123216ad4a38a9c2b16f1783895fd5cb1a04) 
(git at github.com:llvm-mirror/llvm.git 
d209b37aec1e392dabbf9b5324ea4a60c36fbc55)"}
!2 = distinct !{!2, !3}
!3 = !{!"llvm.loop.unroll.disable"}

Then it failed to Unroll:

$(OPT) -S cat_state.n044.ll -mem2reg -loops -loop-simplify -loop-rotate 
-lcssa -loop-unroll -unroll-threshold=100000000 -sccp -simplifycfg -o 
cat_state.n045.ll

There are still for-loops in the cat_state.n045.ll, although it is able to workaround use -internalize -globaldce to remove unCatN and catN DeadFunction which including for-loops :)

Regards,
Leslie Zhai

About the CTQG part in the paper

Is the CTQG(CLASSICAL-TO-QUANTUMGATE CONVERSION) part proposed in the paper available now? I want to transform some simple classical functions into the quantum circuit but do not find doc for the CTQG. The example code in the paper

#define M 100
scaff_module main_ctqg(qint[16] sum, qint[16] i, qint[16] n){
int control_i;
$ i := 1;
$ sum := 0;
for (control_i = 1; control_i <= M; control_i++) {
$if (i <= n)
$ sum += i;
$endif
$ i += 1;
}

cannot be compiled by current ScaffCC.

Regression Tests failing

I was able to build and download ScaffCC 3 days ago (170806)
However, there are some important steps missing in the README.
I found I had to do the following on my RedHat Linux:

yum install zlib-devel
yum install bzip2-devel
yum install m4

in order to get past the boost build and gmp builds
And even then I have a few remaining failures around thread support in boost.
All errors are similar to the two shown here:

gcc.compile.c++ bin.v2/libs/locale/build/gcc-4.8.3/release/threading-multi/shared/date_time.o
In file included from ./boost/thread/detail/platform.hpp:17:0,
from ./boost/thread/mutex.hpp:12,
from libs/locale/src/shared/date_time.cpp:11:
./boost/config/requires_threads.hpp:29:4: error: #error "Threading support unavaliable: it has been explicitly disabled with BOOST_DISABLE_THREADS"
error "Threading support unavaliable: it has been explicitly disabled with BOOST_DISABLE_THREADS"

libs/locale/src/shared/date_time.cpp:435:5: error: â mutexâ in namespace â boostâ does not name a type
boost::mutex &tz_mutex()
^
libs/locale/src/shared/date_time.cpp: In function â std::string boost::locale::time_zone::global()â :
libs/locale/src/shared/date_time.cpp:447:9: error: â unique_lockâ is not a member of â boostâ
boost::unique_lockboost::mutex lock(tz_mutex());

I was able , however, to perform the make at the top level
and it succeeds, with no reports of errors.

So, I ran the regression_test.sh script .
Several of the tests succeed, but I get 3 errors:

cat_state.n04_merged.scaffold fails with:

clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [cat_state.n04.qasmf] Error 1
cmp: *.qasmf: No such file or directory
[./../test_cases/Cat_State] Generating Flattened QASM Failed

Also get

clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [rkqc_test.n32.qasmf] Error 1
cmp: *.qasmf: No such file or directory
[./../test_cases/RKQC_Testing] Generating Flattened QASM Failed

and

clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [square_root.n10.qasmf] Error 1
cmp: *.qasmf: No such file or directory
[./../test_cases/Square_Root] Generating Flattened QASM Failed

**** Any ideas what might be causing these errors ?

Note: I am able to successfully run several of the Algorithms, such as Shors,
so much of scaffold appears to be working.

Ground State Estimation

Hello,
I have no problem about installation or running ScaffCC. However, I am not clear what the following application does.
ScaffCC/Algorithms/Ground_State_Estimation/
I want to calculate ground state energy of TiO2. Is it possible to calculate with this application. If it is, can you explain what term(s) needs to be updated.
Cheers...

Changing compiler syntax/core

Please make sure you don't make changes that affect a large part of the code, and if you do, make sure that you have taken care of all possible repercussions by running unit tests.

For example, I just did a whole bunch of debugging to realize that the gate names in LLVM have been changed from llvm.X to llvm.X.i16. This is a pretty low-level change that affects many things. Many passes are broken as a result, which I will try to fix.

BTW, what's the rationale behind that change?

[Algorithms] How to solve the NP-complete problem for Register Allocation?

Hi ScaffCC developers,

Is there some paper to research Register Allocation Algorithm? I am researching https://www.leetcode.cn/2017/11/quantum-register-allocation-algorithm.html please give me some hint, thanks a lot!

Regards,
Leslie Zhai

Build error (macOS 10.13)

I'm trying to build Scaffold on OSX High Sierra and am getting a build error.
I followed the installation instructions and am on the OSX branch. After following the OSX installation instruction, cmake was still missing so I installed that through brew.

During the make I get the following error:

[ 70%] Building CXX object tools/bugpoint/CMakeFiles/bugpoint.dir/ToolRunner.cpp.o
/Users/eddie/dev/ScaffCC/llvm/tools/bugpoint/ToolRunner.cpp:131:12: error: invalid operands to binary expression
      ('llvm::raw_ostream' and 'std::ostringstream' (aka 'basic_ostringstream<char>'))
    errs() << OS;
    ~~~~~~ ^  ~~
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:183:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'const void *' for 1st argument; take
      the address of the argument with &
  raw_ostream &operator<<(const void *P);
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/ADT/Twine.h:516:23: note: candidate function not viable: no known conversion
      from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'const llvm::Twine' for 2nd argument
  inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) {
                      ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:133:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'char' for 1st argument
  raw_ostream &operator<<(char C) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:140:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'unsigned char' for 1st argument
  raw_ostream &operator<<(unsigned char C) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:147:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'signed char' for 1st argument
  raw_ostream &operator<<(signed char C) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:154:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'llvm::StringRef' for 1st argument
  raw_ostream &operator<<(StringRef Str) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:167:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'const char *' for 1st argument
  raw_ostream &operator<<(const char *Str) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:174:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'const std::string' (aka 'const
      basic_string<char, char_traits<char>, allocator<char> >') for 1st argument
  raw_ostream &operator<<(const std::string &Str) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:179:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'unsigned long' for 1st argument
  raw_ostream &operator<<(unsigned long N);
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:180:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'long' for 1st argument
  raw_ostream &operator<<(long N);
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:181:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'unsigned long long' for 1st argument
  raw_ostream &operator<<(unsigned long long N);
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:182:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'long long' for 1st argument
  raw_ostream &operator<<(long long N);
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:184:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'unsigned int' for 1st argument
  raw_ostream &operator<<(unsigned int N) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:188:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'int' for 1st argument
  raw_ostream &operator<<(int N) {
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:192:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'double' for 1st argument
  raw_ostream &operator<<(double N);
               ^
/Users/eddie/dev/ScaffCC/llvm/include/llvm/Support/raw_ostream.h:205:16: note: candidate function not viable: no known
      conversion from 'std::ostringstream' (aka 'basic_ostringstream<char>') to 'const llvm::format_object_base' for 1st
      argument
  raw_ostream &operator<<(const format_object_base &Fmt);
               ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:750:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, _CharT __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:757:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, char __cn)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:790:1: note: 
      candidate template ignored: could not match 'basic_ostream<char, type-parameter-0-0>' against 'llvm::raw_ostream'
operator<<(basic_ostream<char, _Traits>& __os, char __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:797:1: note: 
      candidate template ignored: could not match 'basic_ostream<char, type-parameter-0-0>' against 'llvm::raw_ostream'
operator<<(basic_ostream<char, _Traits>& __os, signed char __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:804:1: note: 
      candidate template ignored: could not match 'basic_ostream<char, type-parameter-0-0>' against 'llvm::raw_ostream'
operator<<(basic_ostream<char, _Traits>& __os, unsigned char __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:811:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, const _CharT* __str)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:818:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, const char* __strn)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:864:1: note: 
      candidate template ignored: could not match 'basic_ostream<char, type-parameter-0-0>' against 'llvm::raw_ostream'
operator<<(basic_ostream<char, _Traits>& __os, const char* __str)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:871:1: note: 
      candidate template ignored: could not match 'basic_ostream<char, type-parameter-0-0>' against 'llvm::raw_ostream'
operator<<(basic_ostream<char, _Traits>& __os, const signed char* __str)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:879:1: note: 
      candidate template ignored: could not match 'basic_ostream<char, type-parameter-0-0>' against 'llvm::raw_ostream'
operator<<(basic_ostream<char, _Traits>& __os, const unsigned char* __str)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:1046:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os,
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:1054:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os,
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:1063:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, const error_code& __ec)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:1071:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, shared_ptr<_Yp> const& __p)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/ostream:1078:1: note: 
      candidate template ignored: could not match 'basic_ostream<type-parameter-0-0, type-parameter-0-1>' against
      'llvm::raw_ostream'
operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Size>& __x)
^
1 error generated.
make[3]: *** [tools/bugpoint/CMakeFiles/bugpoint.dir/ToolRunner.cpp.o] Error 1
make[2]: *** [tools/bugpoint/CMakeFiles/bugpoint.dir/all] Error 2
make[1]: *** [all] Error 2
make: *** [Clang] Error 2

Let me know how I can help debug the issue.

Toffoli decomposition not working (?)

I am unsure I am using the commands correctly so any help is appreciated.
For test_cases/All_Gates_Example/all_gates.scaffold, I am interesting in compiling into OpenQasm with all ccx gates decomposed.
all_gates.scaffold contains these lines of code which will contain cxx gates.

...
Toffoli ( q[0], q[1], q[2] );
Fredkin ( q[0], q[1], q[2] );

First, I run ./scaffold.sh -b all_gates.scaffold and the Toffoli and Fredkin gates are written as

...
cx q[0], q[1];
ccx q[0], q[1], q[2];
cx q[1], q[2];
ccx q[0], q[1], q[2];
cx q[1], q[2];

Next, I run ./scaffold.sh -b -T all_gates.scaffold and the Toffoli gate is decmoposed.

h q[2];
t q[0];
t q[1];
t q[2];
cx q[1], q[0];
cx q[2], q[1];
cx q[0], q[2];
tdg q[1];
t q[2];
cx q[0], q[1];
tdg q[0];
tdg q[1];
cx q[2], q[1];
cx q[0], q[2];
cx q[1], q[0];
h q[2];
cx q[1], q[2];
ccx q[0], q[1], q[2];
cx q[1], q[2];

Except I still have ccx gates from the Fredkin gate, so I change the level of recursion flag and run
./scaffold.sh -b -T -l 2 all_gates.qasm (I tested various levels of recursion between 2 and 10).

The inclusion of recursion does not eliminate the remaining ccx gates. The resulting .qasm code is exactly the same as from before without the recursion flag.

How I can I eliminate all ccx gates? I want to use ScaffCC and TriQ together, but TriQ does not allow for these gates.
Thanks

CTQG compilation example: controlled not

Hi,

I am new to ScaffCC so thank you for making the code available and apologies if I'm making obvious errors.

I am interested particularly in the CTQG functionality. I have written a simple CONTROLLED NOT module:

/* begin ctqg */
scaff_module my_c_not(qbit q[2])
{
        if (q[0] == 1) {
                X(q[1]);
        }
}
/* end ctqg */

int main() {
        qbit r[2];
        PrepZ(r[0], 0);
        PrepZ(r[1], 0);
        H(r[0]);
        my_c_not(r);
}

however the qasm produced by the scaffold compiler is

module my_c_not(qbit *q){
        X ( q[1] );
 }

module main(){
        qbit r[2];
        H ( r[0] );
        my_c_not ( r );
 }

which is simply a NOT instead of a CONTROLLED NOT. Note the first qubit has had a HADAMARD gate applied. Do I need to do something special to compile CTQG code? Is it correct to write

if (q[0] == 1)

Also is there a way to simulate my program? I'm running on a Linux box.

Thanks for your help,
Kevin.

Changing compiler syntax/core

Please make sure you don't make changes that affect a large part of the code, and if you do, make sure that you have taken care of all possible repercussions by running unit tests.

BTW, what's the rationale behind that change?

Publish Dockerfile

I'm building ScaffCC for NixOS, only to hit several build issues.
It would be helpful if you could upload your Dockerfile to the repo.

ScaffCC does not compile with C++11

When trying to compile with C++11 on ubuntu 18.0.4, G++ 7.4.0 and cmake 3.13.3, there is an error at the following stage,

llvm[3]: Compiling ToolRunner.cpp for Release+Asserts build
/home/project/ScaffCC/llvm/tools/bugpoint/ToolRunner.cpp:131:12: error: invalid operands to
binary expression ('llvm::raw_ostream' and 'std::ostringstream' (aka
'basic_ostringstream'))
errs() << OS;

A potential fix might be found here https://stackoverflow.com/questions/18448846/c11-invalid-operands-to-binary-expression-ostream-and-ostringstream

module was occupied by C++ modules TS keywords

Hi ScaffCC developers,

So it needs to rename module to qmodule, thoughts?

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

ScaffCC does not compile with Python 3.4, but does with Python 2.7

ScaffCC's README states that a version of Python 2.7 or greater is required.

But when compiling with Python version 3.4

(my_py34_venv) ttomesh@cafe:[~/scrap/ScaffCC]: python --version
Python 3.4.9

Compilation will fail with a fatal error:

/home/ttomesh/scrap/ScaffCC/llvm/tools/llvm-config/llvm-config.cpp:45:10: fatal error: 'LibraryDependencies.inc' file
      not found
#include "LibraryDependencies.inc"
         ^
1 error generated.

But probably more concerning are these ImportErrors found throughout the compilation output:

llvm[2]: Constructing LLVMBuild project information.
Traceback (most recent call last):
  File "/home/ttomesh/scrap/ScaffCC/llvm/utils/llvm-build/llvm-build", line 3, in <module>
    import llvmbuild
  File "/home/ttomesh/scrap/ScaffCC/llvm/utils/llvm-build/llvmbuild/__init__.py", line 1, in <module>
    from main import main
ImportError: No module named 'main'

I then tried switching to Python 2.7 and ScaffCC compiled just fine.

[Algorithms] Shors is too heavy! use up classical computer's resource

Hi ScaffCC developers,

$ ./build/Release+Asserts/bin/clang --version
clang version 3.1 (tags/RELEASE_31/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix

$ ./build/Release+Asserts/bin/opt --version
LLVM (http://llvm.org/):
  LLVM version 3.1
  Optimized build with assertions.
  Built Oct 23 2017 (16:22:51).
  Default target: x86_64-unknown-linux-gnu
  Host CPU: corei7-avx

$ ./scaffold.sh -fkR Algorithms/Shors/shors.n512.scaffold 
[Scaffold.makefile] Compiling shors.n512_merged.scaffold ...
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ... <-- CPU boiled
[Scaffold.makefile] Unrolling Loops (1) ... <-- press POWER to restart my computer

Perform loop unrolling until completely unrolled, then remove dead code is not able to work for Shors, but able to work for QFT:

$ ./scaffold.sh -fkR Algorithms/QFT/qft.n05.scaffold 
[Scaffold.makefile] Compiling qft.n05_merged.scaffold ...
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ...
[Scaffold.makefile] Unrolling Loops (1) ...
[Scaffold.makefile] Cloning Functions (1) ...
Functions Cloned: 2
[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] Internalizing and Removing Unused Functions ...
[Scaffold.makefile] Toffoli Decomposition ...
[Scaffold.makefile] Inserting Reverse Functions...
[Scaffold.makefile] Flattening modules ...
[Scaffold.makefile] Flat QASM written to qft.n05.qasmf ...

$ ./qft.n05_qasm 
PrepZ reg0
PrepZ reg1
PrepZ reg2
PrepZ reg3
PrepZ reg4
H reg0
T reg0
Rz reg1,0.785398
CNOT reg1,reg0
Rz reg1,-0.785398
CNOT reg1,reg0
H reg1
Rz reg0,0.392699
Rz reg2,0.392699
CNOT reg2,reg0
Rz reg2,-0.392699
CNOT reg2,reg0
T reg1
Rz reg2,0.785398
CNOT reg2,reg1
Rz reg2,-0.785398
CNOT reg2,reg1
H reg2
Rz reg3,-0.196350
CNOT reg3,reg0
Rz reg3,0.196350
CNOT reg3,reg0
Rz reg1,0.392699
Rz reg3,0.392699
CNOT reg3,reg1
Rz reg3,-0.392699
CNOT reg3,reg1
T reg2
Rz reg3,0.785398
CNOT reg3,reg2
Rz reg3,-0.785398
CNOT reg3,reg2
H reg3
Rz reg4,-0.098150
CNOT reg4,reg0
Rz reg4,0.098150
CNOT reg4,reg0
Rz reg4,-0.196350
CNOT reg4,reg1
Rz reg4,0.196350
CNOT reg4,reg1
Rz reg2,0.392699
Rz reg4,0.392699
CNOT reg4,reg2
Rz reg4,-0.392699
CNOT reg4,reg2
T reg3
Rz reg4,0.785398
CNOT reg4,reg3
Rz reg4,-0.785398
CNOT reg4,reg3
H reg4
H reg0
MeasZ reg0
H reg1
MeasZ reg1
H reg2
MeasZ reg2
H reg3
MeasZ reg3
H reg4
MeasZ reg4

I am also testing with scaff-llvm based on LLVM 6.0 to compile Shors :)

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

Can't find math.h and other headers

I'm using OSX. I've tried tracking this down, but have spent way too much time trying to figure out where the pre-processor is called, and how to resolve this.

Unitive-MacBook-Pro-1598:scaffcc gonzo$ ./scaffold.sh Algorithms/Binary_Welded_Tree/binary_welded_tree.n100s100.scaffold
Algorithms/Binary_Welded_Tree/binary_welded_tree.n100s100.scaffold
[Scaffold.makefile] Compiling binary_welded_tree.n100s100_merged.scaffold ...
binary_welded_tree.n100s100_merged.scaffold:14:10: fatal error: 'math.h' file not found
#include <math.h>
^
1 error generated.
make: *** [binary_welded_tree.n100s100.ll] Error 1

I assume the standard C++ headers are used. If that's true, these are installed and used in my C++ code. For the record, I can go to the scripts dir and run regression_tests.sh. 12 of 20 run fine... only the ones requiring headers math.h or stdio.h fail.

But I argue that it is better to take place of sqct in ScaffCC, because sqct uses GPL https://github.com/epiqc/ScaffCC/blob/master/Rotations/sqct/COPYING gridsynth is the same issue http://www.mathstat.dal.ca/~selinger/newsynth/#license

I supports ScaffCC uses BSD LICENSE, it is commercial friendly, just like LLVM would switch to Apache too http://lists.llvm.org/pipermail/llvm-dev/2017-August/116266.html

And I prefer to use LLVM Toolchain to build ScaffCC https://github.com/ScaffCC/ScaffCC/commit/f111ce2ba3040730279fbbac3378b8fb241f1260 I tested to build for Fedora 25, but sqct might not depends on OpenMP?

Regards,
Leslie Zhai

Version not alligned

./scaffold.sh -v still shows "Release 4.1 (June 28, 2018)"

Wrong QASM output for Teleportation circuit

The code below

// Prepares (|00> + |11>)/Sqrt(2) given input qubits are both |0>
module PrepareEntangledPair( qbit a, qbit b ) {
    H(a);
    CNOT(a,b);
}

// Un-prepares (|00> + |11>)/Sqrt(2) given input qubits are both |0>
module PrepareEntangledPairAdjoint( qbit a, qbit b ) {
    CNOT(a,b);
    H(a);
}

module Teleport( qbit msg, qbit here, qbit there ) {
    PrepareEntangledPair(here,there);
    PrepareEntangledPairAdjoint(msg,here);
    if( MeasZ(msg) ) { Z(there); }
    if( MeasZ(here) ) { X(there); }
}

int main() {
    // We assume that newly allocated qubits are in |0> state
    qbit q[3];

    // Set the first qubit to |+>
    PrepX(q[0], 0);
    Teleport(q[0],q[1],q[2]);
    
    // Measure third qubit in X basis
    if( MeasX(q[2]) ) { return 1; } else { return 0; }
}

Produces the following QASM file :

qubit q0
qubit q1
qubit q2
PrepX q0
H q1
CNOT q1,q2
CNOT q0,q1
H q0
MeasZ q0
Z q2
MeasZ q1
X q2
MeasX q2

The QASM was obtained by running scaffold.sh -f teleport.scaffold on epiqc/scaffcc Docker image.

epiqc / scaffcc Goto Github PK

scaffcc's People

Contributors

Stargazers

Watchers

Forkers

scaffcc's Issues

1

2

3

Recommend Projects

Recommend Topics

Recommend Org