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