[home]
Exact and approximate synthesis of quantum circuits

Contents

Description

This package provides an easy-to-use executable program gridsynth that computes approximations of arbitrary z-rotations over the Clifford+T gate set, up to arbitrary ϵ. It achieves T-counts that are within O(log(log(1/ϵ))) of optimal. In the typical case, this means T-counts of 4log2(1/ϵ) + O(log(log(1/ϵ))). This compares favorably to the Solovay-Kitaev algorithm, which achieves T-count O(logc(1/ϵ)), for c > 3.

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.

Usage

The purpose of the gridsynth program is to approximate a z-rotation
up to arbitrary ϵ. It takes one argument, which is the angle θ. The angle can be specified symbolically, for example "pi/128"; the program will then automatically calculate π/128 to the required number of digits. To distinguish negative numbers from command line options, negative angles should be entered parenthesized and in quotes, for example, "(-0.1)". Typical usage is like this: 
     $ gridsynth pi/128
     SHTHTHTHTHTHTHTSHTHTHTHTSHTHTHTHTHTSHTSHTHTHTHTHTSHTHTHTSHTSHTHTSHTSHTSHTHTHTHTS
     HTHTHTHTHTSHTSHTHTSHTHTSHTSHTSHTSHTHTSHTSHTSHTSHTHTHTSHTSHTSHTHTHTHTSHTHTSHTHTHT
     SHTHTHTHTSHTHTSHTHTSHTSHTSHTHTHTHTHTHTHTSHTHTSHTHTHTSHTSHTHTHTSHTSHTSHTHTSHTHTHT
     HTSHTSHTSHSSSWWWWWWW
Here, "T", "S", "H", and "X" denote the usual quantum gates of the same names, and "W" denotes the scalar ω = eiπ/4. Operators are shown in matrix order, not circuit order. This means they are meant to be applied from right to left.

The default value for the precision is 10 decimal digits, i.e., ϵ = 10-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 pi/1024 rotation up to ϵ = 10-100: 

     $ gridsynth pi/1024 -d 100
You can see the output here.

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)

Library overview

The synthesis library includes implementations of a number of algorithms for approximate and exact synthesis over the Clifford+T gate set, but for single-qubit and multi-qubit quantum circuits. Currently, the following algorithms are provided:
  • 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.
The package also provides modules for computations with rings of quadratic and cyclotomic integers, Euclidean domains, symbolic real numbers, Euler angles, Clifford operators, a Diophantine equation solver, and a solver for one- and two-dimensional grid problems.

Library usage

The library is fully documented; please see the browseable online documentation.

News

  • 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.
For a more detailed list of changes, see the ChangeLog.

Downloading and installing

There are several options for downloading and installing the newsynth package.
  • 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.

Support and reporting bugs

For bug reports or support requests, please email me at selinger@mathstat.dal.ca.

Related work

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

Version

0.3.0.4

Authors

Peter Selinger
Neil J. Ross

License

Copyright (c) 2012-2018 Peter Selinger and Neil J. Ross.

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/.


To Peter Selinger's other Software.

Back to Peter Selinger's Homepage: [home]

Peter Selinger / selinger@mathstat.dal.ca