content: 
  -- | This module provides an implementation of the Quantum Fourier Transform
  -- in QIO.
  module QIO.Qft where
  
  import Data.Monoid as Monoid
  import QIO.QioSyn
  import QIO.Qio
  import QIO.Qdata
  
  -- | Defines the unitary the represents appliying a Quantum Fourier Transform
  -- to the given quantum register.
  qft :: [Qbit] -> U
  qft qs = condQ qs (\bs -> qftAcu qs bs [])
  
  -- | The definition of the QFT unitary makes use of an accumulator, to repeatedly
  -- apply smaller QFTs to the tail of the given quantum register.
  qftAcu :: [Qbit] -> [Bool] -> [Bool] -> U
  qftAcu [] [] _ = mempty
  qftAcu (q:qs) (b:bs) cs = qftBase cs q `mappend` qftAcu qs bs (b:cs)
  
  -- | The \"base\" step involved in a QFT is a series of controlled rotations.
  qftBase :: [Bool] -> Qbit -> U
  qftBase bs q =  f' bs q 2
      where f' [] q _ = uhad q
            f' (b:bs) q x = if b then (rotK x q) `mappend` f' bs q (x+1) 
                    else f' bs q (x+1)
  
  --need to change this into a conQRec???
  -- e.g. qft [Qbit 0]
  -- = condQ [Qbit 0] (\(b:bs) -> uhad 0 `mappend` mempty)
  -- but gives  cond 0 (\x -> if x then uhad 0 else uhad 0) which is forbidden
  
  -- | The rotation used in the QFT is a phase rotation, parameterised by the 
  -- angle 1/(2^\k\)
  rotK :: Int -> Qbit -> U
  rotK k q = uphase q (1.0/(2.0^k))
  
  -- | A test of the QFT unitary, over a quantum integer initialised to \n\.
  tryQft :: Int -> QIO Int
  tryQft n = do 
    QInt qs <- mkQ n
    applyU(qft qs)
    x <- measQ (QInt qs)
    return x
  