This C++ implementation is based on the algorithm presented in the paper Optimal ancilla-free Clifford+T approximation of z-rotations. This program is developed as part of my study. Currenthly this program demonstrates notably poorer performance in comparison to the Haskell program GridSynth developed by the authors of the paper.
While GridSynth is distributed under the GPL license, my implementation has been developed independently without referencing the original code. Therefore, I am releasing this implementation under the MIT license.
To build this library, use Boost.Multiprecision, Boost.Program_options, and GoogleTest. Follow these commands:
$ cmake -S . -B build
$ cmake --build build
$ ctest --test-dir build- Optimal ancilla-free Clifford+T approximation of z-rotations
- Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates
- Representation of Quantum Circuits with Clifford and π/8 Gates
- Enhance Speed
- The prime factorization process currently consumes a significant amount of time
- Implement the Quadratic Sieve algorithm
- Use OpenMP
- Address numerical errors arising from floating-point calculations
The execution time of gridsynth_cpp is notably influenced by the success or failure of prime factorization.
- CPU: AMD Ryzen 7 3700X 8-Core Processor
$ time ./gridsynth_cpp pi/128 -d 10
TCount = 104
TSHTSHTHTHTHTSHTSHTSHTHTHTHTHTSHTHTSHTHTSHTSHTSHTHTHTSHTHTHTHTHTHTSHTSHTHTHTHTSHTSHTSHTHTHTSHTHTHTHTSHTSHTSHTHTHTHTSHTHTHTSHTSHTHTHTSHTSHTHTHTSHTSHTSHTSHTSHTSHTHTHTHTSHTSHTHTHTSHTSHTSHTSHTSHTSHTSHTHTSHTHTSHTHTHTSHTSHTSHTSHTSHTHTSHTSHTSHTHTSHTSHTSHTHTHTSHTSHTHTSHTSSSXS
real 0m0.288s
user 0m0.258s
sys 0m0.030s$ time ./gridsynth_cpp pi/128 -d 20
TCount = 202
THTSHTHTSHTHTSHTSHTSHTHTHTSHTHTSHTHTHTSHTSHTSHTHTHTHTSHTSHTHTHTSHTSHTHTSHTHTHTSHTHTHTHTSHTSHTSHTSHTSHTSHTSHTHTSHTSHTSHTHTSHTSHTHTSHTHTSHTHTHTSHTSHTHTHTHTSHTSHTHTHTSHTHTHTHTHTHTSHTHTHTHTSHTHTSHTHTSHTSHTHTHTSHTSHTHTSHTHTHTSHTHTSHTHTHTSHTHTHTHTSHTHTHTSHTSHTHTSHTHTSHTHTSHTHTSHTHTSHTSHTHTHTSHTHTSHTSHTHTSHTHTHTHTSHTHTSHTSHTSHTSHTSHTHTSHTSHTSHTHTSHTHTSHTHTSHTSHTSHTSHTSHTSHTHTHTHTSHTHTHTHTHTHTHTSHTHTSHTSHTHTSHTHTHTHTSHTHTHTSHTHTSHTSHTHTSHTHTHTHTSHTHTSHTHTHTSHTHTSHTSHTHTSHTHTHTSHTHTHTHTSHTSHTSHTHTSHTHTHTSHWWWWW
real 0m9.688s
user 0m9.688s
sys 0m0.000s$ time ./gridsynth_cpp pi/128 -d 30
TCount = 298
SHTSHTSHTSHTSHTHTHTHTHTHTSHTSHTSHTHTHTHTSHTSHTHTHTSHTSHTHTSHTSHTSHTSHTHTSHTSHTSHTHTSHTSHTHTSHTSHTHTHTSHTSHTHTSHTHTSHTHTHTHTHTSHTHTHTSHTHTSHTSHTSHTSHTHTSHTSHTSHTHTSHTHTSHTHTSHTHTHTHTHTSHTSHTSHTHTHTHTSHTSHTHTHTSHTSHTHTHTSHTSHTHTSHTHTSHTSHTSHTHTHTSHTSHTHTSHTHTHTHTHTHTSHTHTHTSHTSHTSHTSHTSHTSHTHTHTHTHTHTSHTSHTHTHTSHTHTHTSHTHTHTHTHTHTHTSHTSHTSHTHTSHTSHTSHTHTSHTSHTSHTHTSHTSHTSHTHTHTHTSHTSHTSHTHTSHTSHTSHTHTSHTSHTSHTSHTHTSHTSHTHTHTHTSHTHTSHTSHTSHTSHTSHTSHTSHTHTSHTHTSHTSHTHTHTSHTHTSHTHTSHTSHTSHTSHTHTSHTHTSHTHTHTHTHTSHTSHTSHTHTHTSHTSHTHTSHTSHTSHTSHTHTSHTHTHTSHTHTSHTHTSHTHTSHTHTHTHTHTSHTSHTHTSHTHTSHTHTSHTHTSHTSHTHTSHTSHTSHTHTHTHTHTSHTHTHTSHTHTSHTSHTHTSHTSHTHTSHTHTHTHTSHTHTSHTHTHTSHTSHTSHTHTSHTSHTHTSHTSHTSHTSHTHTSHTHTHTHTSHTHTHTHTHTSHTHTSHTHTHTHTSHTSHTHTSHTW
real 0m3.736s
user 0m3.726s
sys 0m0.010s$ time ./gridsynth_cpp pi/128 -d 40
TCount = 400
TSHTHTSHTSHTHTHTSHTSHTSHTSHTSHTSHTHTHTSHTHTHTHTHTHTHTHTSHTHTSHTSHTSHTHTSHTHTHTSHTSHTSHTHTHTSHTSHTSHTSHTSHTHTSHTHTSHTSHTHTSHTHTSHTSHTHTHTSHTHTHTSHTHTHTHTHTSHTSHTHTSHTSHTSHTSHTSHTSHTSHTHTHTSHTHTHTHTSHTSHTHTSHTHTSHTSHTSHTHTSHTHTHTHTHTSHTSHTHTSHTHTSHTSHTSHTSHTSHTSHTSHTHTHTHTSHTSHTSHTHTHTSHTSHTHTHTSHTHTHTHTSHTHTHTHTHTSHTSHTSHTSHTSHTSHTHTSHTSHTHTHTSHTHTHTHTHTHTHTSHTHTSHTHTSHTSHTSHTSHTHTSHTSHTSHTSHTHTSHTHTHTHTHTHTHTHTSHTHTHTHTSHTHTHTSHTSHTHTSHTSHTHTHTHTSHTHTHTHTSHTHTHTSHTHTSHTHTSHTSHTHTSHTSHTSHTHTSHTSHTHTHTHTSHTSHTSHTHTHTHTSHTSHTHTHTHTHTHTSHTSHTHTHTSHTSHTSHTSHTHTHTSHTSHTSHTHTSHTHTHTHTHTSHTHTSHTSHTSHTHTHTHTSHTSHTHTSHTHTHTHTSHTSHTHTSHTHTSHTSHTHTSHTSHTSHTHTHTHTSHTHTSHTHTSHTSHTSHTSHTSHTHTSHTSHTHTHTHTSHTHTHTSHTHTHTSHTHTSHTSHTSHTHTHTSHTSHTSHTSHTSHTHTSHTSHTHTHTHTSHTSHTHTSHTHTHTSHTHTSHTHTSHTSHTSHTHTSHTSHTHTHTSHTHTHTHTSHTSHTHTHTHTHTSHTHTHTHTSHTSHTSHTHTHTHTSHTHTSHTHTHTSHTHTHTHTSHTSHTSHTSHTHTSHTHTSHTHTSHTHTHTSHTHTSHTHTHTHTHTSHTHTHTHTHTHTHTSHTHTSHTHTSHTSHTHTHTSHTHTSHTHTSHTHTSHTSHTSHTSHTHTSHTHTHTSHTHTSXSSSXW
real 0m4.377s
user 0m4.355s
sys 0m0.020s$ time ./gridsynth_cpp pi/128 -d 50
TCount = 500
SHTHTHTHTSHTSHTSHTSHTSHTSHTSHTHTHTSHTSHTSHTHTHTHTHTSHTSHTHTSHTSHTSHTSHTSHTSHTSHTHTHTHTHTHTSHTSHTSHTSHTSHTHTSHTSHTSHTHTHTSHTSHTSHTHTHTSHTHTHTHTHTSHTSHTSHTHTSHTSHTSHTSHTSHTSHTHTHTHTSHTHTHTSHTSHTSHTSHTSHTHTSHTHTSHTHTSHTHTHTSHTSHTHTSHTSHTHTSHTHTSHTHTSHTSHTSHTSHTHTSHTSHTHTHTHTSHTHTSHTHTSHTSHTHTHTHTSHTHTSHTSHTHTHTSHTSHTHTSHTHTHTSHTSHTSHTHTSHTSHTSHTHTHTHTSHTSHTSHTSHTSHTSHTSHTHTSHTSHTSHTSHTSHTSHTHTHTHTHTHTHTSHTHTHTSHTHTHTSHTHTHTSHTHTHTSHTSHTSHTHTSHTHTSHTSHTSHTHTHTHTSHTHTSHTSHTHTHTHTHTSHTSHTSHTSHTSHTSHTHTSHTSHTHTHTHTSHTSHTSHTSHTHTHTHTSHTHTHTSHTHTSHTSHTSHTHTSHTHTHTHTHTHTSHTHTHTSHTSHTSHTHTSHTSHTHTHTHTHTHTHTHTSHTSHTHTHTSHTSHTSHTSHTSHTHTSHTHTHTHTHTSHTHTHTHTHTSHTHTSHTHTHTHTSHTHTHTHTHTSHTHTHTSHTSHTSHTSHTHTSHTHTHTSHTHTSHTSHTSHTHTHTSHTHTSHTHTSHTHTSHTSHTHTSHTHTSHTHTHTSHTSHTHTSHTHTHTSHTHTHTSHTSHTHTSHTHTSHTHTHTHTSHTSHTHTHTSHTSHTHTHTSHTSHTSHTSHTHTHTSHTSHTHTHTHTHTSHTHTHTSHTHTSHTSHTHTHTHTHTHTHTHTSHTHTHTHTSHTSHTHTHTHTHTSHTSHTHTSHTHTHTHTSHTSHTSHTHTHTHTSHTSHTHTHTSHTSHTSHTHTHTHTHTSHTHTSHTSHTSHTHTSHTSHTSHTHTHTSHTHTHTSHTHTSHTHTHTSHTSHTHTHTSHTHTSHTHTSHTHTSHTSHTSHTSHTSHTHTHTSHTHTSHTHTSHTHTSHTSHTHTHTHTSHTHTHTHTSHTHTSHTHTHTSHTSHTHTHTSHTSHTSHTSHTSHTSHTSHTHTSHTSHTHTHTHTHTSHTHTHTHTHTSHTSHTSHTHTHTSHTHTSHTHTHTSHTHTHTSHTHTHTSHTHTHTHTSHTHTSHTSHTHTHTSHTSHTHTHTSHTHTSHTSHTXSW
real 0m27.724s
user 0m27.724s
sys 0m0.000s$ time ./gridsynth_cpp pi/128 -d 60
TCount = 598
HTSHTHTSHTHTHTHTSHTSHTHTSHTHTHTSHTHTSHTSHTHTSHTSHTHTHTSHTSHTHTSHTHTSHTSHTSHTSHTSHTHTHTHTHTSHTHTHTHTHTHTSHTHTSHTHTSHTSHTHTSHTSHTSHTSHTSHTHTSHTHTSHTSHTSHTHTHTHTHTHTSHTHTHTSHTHTHTSHTSHTSHTHTHTHTSHTHTSHTSHTHTHTHTSHTSHTSHTHTSHTHTSHTHTHTHTSHTHTSHTHTHTSHTHTHTHTHTSHTSHTSHTSHTSHTHTHTHTHTSHTHTHTHTHTSHTHTHTHTSHTSHTHTSHTSHTHTSHTSHTHTHTSHTSHTHTHTHTSHTSHTHTSHTHTHTSHTHTSHTHTHTHTHTHTHTHTHTSHTHTHTSHTSHTSHTSHTHTHTHTHTHTSHTSHTSHTSHTHTSHTSHTSHTSHTHTSHTHTSHTSHTHTSHTHTHTSHTHTSHTSHTHTHTSHTSHTSHTSHTHTSHTSHTSHTHTHTHTHTSHTHTSHTSHTSHTHTSHTSHTSHTSHTSHTHTSHTSHTSHTHTSHTHTSHTHTSHTHTSHTSHTSHTHTHTHTSHTSHTSHTSHTHTSHTSHTHTHTSHTSHTHTSHTSHTHTSHTSHTHTSHTSHTSHTHTSHTSHTHTSHTSHTHTHTHTSHTSHTHTHTHTSHTSHTSHTHTSHTSHTSHTHTHTHTSHTHTHTSHTHTSHTHTSHTHTSHTSHTSHTSHTSHTHTSHTHTSHTHTSHTHTSHTHTHTSHTHTSHTHTSHTHTHTHTSHTHTSHTSHTSHTHTSHTHTHTHTSHTSHTSHTHTSHTSHTHTHTSHTHTHTHTSHTHTSHTSHTHTHTHTSHTHTHTSHTSHTSHTSHTHTSHTHTSHTHTSHTHTHTHTSHTSHTSHTSHTSHTSHTSHTSHTHTHTHTSHTHTSHTSHTSHTHTSHTHTSHTSHTHTSHTSHTHTHTHTHTSHTHTHTSHTHTHTHTHTHTSHTSHTHTHTSHTHTHTSHTSHTSHTHTSHTHTSHTHTSHTHTSHTHTSHTSHTSHTHTSHTSHTHTHTHTSHTSHTHTHTSHTHTHTHTSHTHTSHTHTHTHTHTHTHTHTSHTSHTSHTHTHTSHTHTHTSHTHTSHTHTHTHTSHTSHTSHTSHTHTHTHTHTHTSHTHTSHTHTSHTHTSHTHTSHTSHTSHTHTSHTHTSHTHTHTHTHTSHTHTSHTSHTSHTHTHTHTSHTSHTHTHTSHTSHTHTHTHTSHTSHTSHTHTHTHTHTSHTHTHTSHTSHTHTSHTHTHTSHTHTSHTSHTHTSHTHTHTSHTSHTSHTHTHTHTSHTHTHTHTSHTSHTSHTHTSHTHTHTSHTSHTSHTSHTHTHTHTSHTHTSHTHTSHTHTSHTSHTSHTHTSHTSHTSHTHTHTHTSHTSHTHTSHTSHTSHTSHTHTHTHTHTHTHTSHTSHTHTSHTHTSHTSHTSHTHTSHTSHTHTSHTHTSHTSHTHTHTHTSHTSHTHTHTSHTHTHTHTSHXSXW
real 0m11.066s
user 0m11.046s
sys 0m0.020s
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent