The algorithm is described in:

• N. J. Ross and P. Selinger, "Optimal ancilla-free Clifford+T approximation of z-rotations", arXiv:1403.2975.

This package also provides a library of various algorithms for exact and approximate synthesis of quantum circuits over the Clifford+T gate set, written in Haskell.

     $ gridsynth pi/128
     SHTHTHTHTHTHTHTSHTHTHTHTSHTHTHTHTHTSHTSHTHTHTHTHTSHTHTHTSHTSHTHTSHTSHTSHTHTHTHTS
     HTHTHTHTHTSHTSHTHTSHTHTSHTSHTSHTSHTHTSHTSHTSHTSHTHTHTSHTSHTSHTHTHTHTSHTHTSHTHTHT
     SHTHTHTHTSHTHTSHTHTSHTSHTSHTHTHTHTHTHTHTSHTHTSHTHTHTSHTSHTHTHTSHTSHTSHTHTSHTHTHT
     HTSHTSHTSHSSSWWWWWWW

The default value for the precision is 10 decimal digits, i.e., ϵ = 10⁻¹⁰. The precision ϵ can also be specified by command line options: -d for decimal digits, -b for binary digits, or -e to specify ϵ directly. For example, to compute a π/1024 rotation up to ϵ = 10⁻¹⁰⁰:

     $ gridsynth pi/1024 -d 100

Note on phases: By default, gridsynth approximates the given z-rotation on the nose, i.e., not up to a phase. So if you give the angle θ = π/4, you will not get a single T-gate. Instead, you will get an approximation of \[ R_z({\pi}/{4}) = \left(\begin{array}{cc} e^{-i\pi/8} & 0 \\ 0 & e^{i\pi/8} \end{array}\right), \] which is not the same as \[ T = \left(\begin{array}{cc} 1 & 0 \\ 0 & \omega \end{array}\right). \] If you would like the approximation to be up to a phase, you must specify the --phase option. In that case, specifying θ = π/4 will give you a single T-gate as expected.

Here is the full list of command line options:

Usage: gridsynth [OPTION...] 
Arguments:
 theta                     z-rotation angle. May be symbolic, e.g. pi/128
Options:
  -h        --help          print usage info and exit
  -d n      --digits=n      set precision in decimal digits (default: 10)
  -b n      --bits=n        set precision in bits
  -e n      --epsilon=n     set precision as epsilon (default: 1e-10)
  -p        --phase         decompose up to a global phase (default: no)
  -f "n"    --effort="n"    how hard to try to factor (default: 25)
  -x        --hex           output hexadecimal coding (default: ASCII)
  -s        --stats         output statistics
  -l        --latex         use LaTeX output format
  -t        --table         generate the table of results for the article
  -c n      --count=n       repeat count for --table mode (default: 50)
  -r "s"    --rseed="s"     set optional random seed (default: random)

• Quantum.Synthesis.GridSynth: the efficient single-qubit approximate synthesis algorithm of N. J. Ross and P. Selinger, "Optimal ancilla-free Clifford+T approximation of z-rotations", arXiv:1403.2975. This is the algorithm used by the gridsynth program.

• Quantum.Synthesis.MultiQubitSynthesis: the multi-qubit exact synthesis algorithms of B. Giles and P. Selinger, "Exact synthesis of multiqubit Clifford+T circuits", Physical Review A 87, 032332, 2013, arXiv:1212.0506.

• Quantum.Synthesis.CliffordT: computation of Matsumoto-Amano normal forms for single-qubit Clifford+T operators. From K. Matsumoto and K. Amano, "Representation of Quantum Circuits with Clifford and π/8 Gates", arXiv:0806.3834.

• Quantum.Synthesis.RotationDecomposition: an algorithm for decomposing multi-qubit unitary operators into one- and two-level unitaries. See e.g. Section 4.5.1 of M. A. Nielsen and I. L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2002.

• 2018/11/05: Release 0.3.0.4. Fixed some compiler warnings and updated package constraints.
• 2016/07/27: Release 0.3.0.3. Relaxed package dependencies to accommodate older versions of ghc and base.
• 2015/08/15: Release 0.3.0.2. Relaxed dependencies and minor update for compiler compatibility.
• 2015/05/15: Release 0.3.0.1. Added a missing source file to the distribution.
• 2015/05/15: Release 0.3. Added a new --phase option to compute approximations up to a global phase. Fixed various bugs related to precision.
• 2014/10/08: Release 0.2.0.1. Fixed a bug where the actual T-count was output instead of the lower bound. Also updated dependencies to compile with newer version of Haskell libraries.
• 2014/03/12: Release 0.2. Added the new "gridsynth" algorithm, and removed the old "newsynth" algorithm (it can still be found in release 0.1.1.0 for reference). Various small improvements to other modules.
• 2014/02/05: Release 0.1.1.0. Improved asymptotic efficiency of various functions. Minor bug fixes. New functions euclid_divides and euclid_associates.
• 2013/12/14: Release 0.1.0.0. First release as a stand-alone Cabal package.
• 2013/09/02: Update released as part of Quipper 0.5.
• 2013/06/19: First public release, as part of Quipper 0.4.

• Using Cabal. First, you need a working Haskell Platform, which you can get from www.haskell.org. Then simply type

       cabal install newsynth
  

  This will automatically download, compile, and install the newest version of the newsynth package.

• From sources. You can download the newsynth package as a gzipped tar file from hackage.haskell.org/package/newsynth. You will still need the GHC Haskell compiler, which you can get from www.haskell.org.

• Pre-compiled binaries. If you just want to experiment with the gridsynth program without compiling or installing anything, here are some precompiled binaries. However, some of these are dynamically linked and depend on specific library versions, so they may not work for you.
  • For Linux (64 bit): gridsynth.
  • For Windows (64 bit): gridsynth.exe.
  • For Mac OS X (64 bit): gridsynth.

• PyGridsynth, by Shuntaro Yamamoto and Nobuyuki Yoshioka. A native Python implementation of the Gridsynth algorithm. (Added December 25, 2024).

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.