.. _compiler:


***************
Compiler
***************

.. _compiling_SK:

Compiling Quantum Gates
=============================

Most quantum algorithms require only single qubit gates and entangling two qubit gates, 
which are combined into complex circuits. However, physical implementation of quantum
computers can often only realize a limited set of gates reliably. Other gates, that
do not belong to this instruction set, have to be approximated by sequences of these
gates. The task of the quantum compiler is given an arbitrary gate to find a sequence
the approximates it within a small error.
The universal set of quantum gates that is used can be found (and changed) in the module
``instruction_sets.py`` :

  >>> from QuackQuack.compiler.instruction_sets import universal_gates
  >>> n = 2                  # compile single qubit gates
  >>> G = universal_gates[n] # Hadamard, pi/8-gate and complex conjugates

Solovay-Kitaev Algorithm
------------------------
The Solovay-Kitaev algorithm [1]_ can iteratively produce better approximations, but it needs
a crude initial approximation to the gate in order to converge. The program ``QuackQuack/compiler/basic_approximations.py``
generates basic approximations by simply enumerating all possible combintations of simple gates
up to a certain length::

  cd QuackQuack/compiler/
  python basic_approximations.py 2 12

This will generate a set of basic approximations for 2x2 matrices of up to 12 gates and store them
in a database in ``/tmp/gate_library/basic_approximations/U2x2/`` for later use. You can load
this basic approximation with the following commands:

  >>> from QuackQuack.compiler.basic_approximations import IdentityReduction, BasicApproximation, load_basic_approximation
  >>> cache = load_basic_approximation(n)

The loaded object allows to retrieve a basic approximation to some unitary 2x2 matrix U as a sequence of 
indeces into the set of universal gates ``G``.

  >>> from QuackQuack.compiler.NumImporter import *
  >>> from QuackQuack.compiler.basic_approximations import seq_to_matrix
  >>> from QuackQuack.compiler.Solovay_Kitaev import SU_distance
  >>> U = array([[1,0],[0,exp(1j*pi/5)]])
  >>> Useq = cache.approximate(U)
  >>> Useq                             # 0 -> G[0] ~ Hadamard, 1 -> G[1] ~ Hadamard^+, 2 -> G[2] ~ pi/8, 3 -> G[3] ~pi/8^+ 
  [0, 3, 1, 1, 3, 0, 3, 1, 1, 3, 1, 3]
  >>> Uapprox = seq_to_matrix(Useq, G) # multiply gate sequence to get a matrix
  >>> print "Error: %s" % SU_distance(U,Uapprox)
  Error: 0.111

The method might fail if no gate close enough is found. In this case you should increase the maximal length
of the initial sequences and regenerate the basic approximations. 

Now we can use the SK-algorithm to find a much better approximation to U. First we need to tell 
the constructor that the instruction set is in ``G`` and that the function ``cache.approximate`` provides the basic approximations. 
We run the SK-algorithm for 5 iterations:

  >>> from QuackQuack.compiler.Solovay_Kitaev import Solovay_Kitaev 
  >>> SK = Solovay_Kitaev(G,cache.approximate)
  >>> Useq = SK.approximate(U, 5)
  >>> Useq
  [1, 2, 2, 0, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 3, 0, ...many more indeces...]
  >>> Uapprox = seq_to_matrix(Useq, G)
  >>> print "Error: %s" % SU_distance(U,Uapprox)
  Error: 1.80e-05

``U`` and ``Uapprox`` might look quite distinct because they may differ by a global phase and still represent the same gate. 
``SU_distance`` removes the phase difference before comparison.

.. The same procedure applies to approximating 4x4 unitary matrices by setting ``n=4``, but generating the initial approximations will take much longer.

.. [1] Dawson and Nielsen, "The Solovay-Kitaev algorithm", http://arxiv.org/abs/quant-ph/0505030v2

Simplification of Gate Sequences
--------------------------------
The gate sequences might be unnecessarily long because some combation of gates can be simplified.
For instance applying the Hadamard gate (the 0th element of G) twice yields the identity, so the pattern [0,0,x] can be replaced by [x]. The class ``IdentityReduction`` finds all replacement rules and applies them to sequences to shorten them.

  >>> from QuackQuack.compiler.basic_approximations import IdentityReduction
  >>> IdRed = IdentityReduction(G, 3)       # find all patterns of length at most 3
  >>> Useq_red = IdRed.replace_identities(Useq)
  >>> print len(Useq), len(Useq_red)
  36842 33710

The cache with basic approximations already contains an instance, so that the same effect is achieved by:

  >>> Useq_red = cache.IdRed.replace_identities(Useq)

Basic Approximations Supplied by a Server
-----------------------------------------
Loading the database with basic approximations and building a search tree can take up a considerable amount of time.
Also the database might be too large to fit into memory. For this reason the program ``approx_server.py`` allows
you to keep the database on a seperate computer with lots of memory and took communicate with that server to 
get approximations without reloading the database everytime you restart client.
First you need to generate a database of basic approximations as above::

  cd QuackQuack/compiler/
  python basic_approximations.py 2 12
  
Then start the server (which will listen on "localhost" at port 9999)::
  
  python QuackQuack/compiler/approx_server.py 2

You can then (possibly on another computer) get the instruction set and basic approximations with the following code:

  >>> from QuackQuack.compiler.approx_server import fetch_approximation, fetch_instruction_set
  >>> n = 2
  >>> G = fetch_instruction_set(n)
  >>> Useq = fetch_approximation(U)
  >>> Useq
  [1, 3, 0, 0, 3, 0, 3, 0, 0, 3, 0, 3]
  
.. Precision (associated code contains some BUG!)
.. ----------------------------------------------
.. Rounding errors limit the accuracy of the Solovay-Kitaev algorithm to about 1.e-7. By orthogonalizing the columns of supposedly unitary matrices using the Gram-Schmidt procedure from time to time, the accuracy can be improved a little bit. For a number of iterations ``n > 7`` the error does not decrease any further. If you need better approximations you can enable the arbitrary precision library mpmath_ for floating point operations instead of numpy_.

.. .. _mpmath: http://code.google.com/p/mpmath/
.. .. _numpy: http://www.numpy.org/

.. That can be done in the following way: Before importing anything from ``QuackQuack`` set the global variable ``numlib`` to "mpmath":

..  >>> numlib = "mpmath"
..  >>> from QuackQuack.compiler.NumImporter import *
..  >>> set_mpmath_precision(23)

.. This causes all calculations to be performed with a precision of approximatey 23 decimal places. You cannot change the precision later on.

Controlled Gates
----------------
This implementation of the SK-algorithm can only approximate 2x2 special unitary matrices. To implement many quantum algorithms
such as quantum Fourier transform or phase estimation we only require in addition controlled two-qubit gates. If the CNOT gate is available the results in [2]_ guarantee that we can compile any controlled gate

.. math::

   C(W) = \left( \begin{matrix} Id & 0 \\ 0 & W \end{matrix} \right)

by compiling single qubit gates A,B and C that satisfy

.. math::
   A \cdot B \cdot C &= Id \\
   A \cdot \sigma_X \cdot B \cdot \sigma_X \cdot C &= W

The circuit that implements the controlled W gate then looks like this:

.. image:: controlled_gate_ABC.png
   :scale: 200%
..   -------o-------o-------     
..          |       |       
..   ---A---+---B---+---C---

As an example let us compile a controlled pi/10 gate. First start the approximation server::
  
  python QuackQuack/compiler/approx_server.py 2

Define the pi/10 gate:

  >>> PI10 = array([[exp(-1j*pi/10),0],[0,exp(1j*pi/10)]])
  >>> controlled_PI10 = block_diag(identity(2,dtype=complex), PI10)

Setup the Solovay-Kitaev algorithm for requesting basic approximations from the server:

  >>> from QuackQuack.compiler.approx_server import fetch_approximation, fetch_instruction_set, fetch_simplification
  >>> G = fetch_instruction_set(2)
  >>> SK = Solovay_Kitaev(G, fetch_approximation)
  >>> fetch_simplification.dim=2

Now compile the gates A,B and C and compare with the ideal controlled gate:

  >>> from QuackQuack.compiler.basic_approximations import seq_to_matrix_controlled
  >>> Aseq,Bseq,Cseq = SK.approximate_controlled(PI10, 5, fetch_simplification)
  >>> controlled_PI10_approx = seq_to_matrix_controlled(Aseq,Bseq,Cseq, cache.G)
  >>> error = SU_distance(controlled_PI10, controlled_PI10_approx)
  >>> print "error = %s" % error    
  error = 3.933e-05

.. [2]  Adriano Bernco et.al., "Elementary gates in quantum computation" (1995), Lemma 5.1