module Homework4 where
import System.Random
import Quipper
import Quipper.Libraries.Simulation

-- Problem 1.

-- Consider the following 1-bit Deutsch problem: 
-- A 1-bit function f is called "constant" if f(a) = f(b) for all a,b ∈ {0,1}.
-- A 1-bit function f is called "balance" if f(a) != f(b) for all a != b, where a, b ∈ {0,1}.
-- Usually, to test if a function f is balance or constant, we would need to run f at least twice.
-- But Deutsch algorithm gives an answer of balance or constant by just running f once. Here is
-- how Deutsch algorithm work:
-- 1. Giving a 1-bit classical function f :: Qubit -> Qubit, we 
-- find a reversible circuit for f, called U_f :: Qubit -> Qubit -> Circ(Qubit, Qubit) such that
-- U_f x y = (x, y ⊕ f(x)). 


-- 2. Then we define a higher-order function deutsch :: (Qubit -> Qubit -> Circ(Qubit, Qubit)) -> Circ (Qubit, Qubit)
-- such that: deutsch U_f = (H ⊗ H) (U_f |+⟩⊗|-⟩). Please define this function below. 
-- (2 points)
deutsch :: (Qubit -> Qubit -> Circ(Qubit, Qubit)) -> Circ (Qubit, Qubit)
deutsch = undefined

-- 3. When we measure the pair of qubits from (deutsch U_f) for a given U_f,
-- if the first bit is False, then we can deduce f is constant, otherwise f is balance. So
-- Deutsch's solution only requires running f once.  

-- The following u_f1 and u_f2 are reversible circuits for some 1-bit function. 
u_f1 :: Qubit -> Qubit -> Circ(Qubit, Qubit)
u_f1 x y = do
   (y, x) <- controlled_not y x
   return (x, y)

u_f2 :: Qubit -> Qubit -> Circ(Qubit, Qubit)
u_f2 x y = return (x, y)

-- Write a test case for u_f1. Your test case can use run_generic or sim_generic. But it has to print out
-- something like: "f1 is balance" or  "f1 is constant".
-- (1 point)
test1 :: IO ()
test1 = undefined

-- Write a test case for u_f2. Your test case can use run_generic or sim_generic. But it has to print out
-- something like: "f2 is balance" or  "f2 is constant".
-- (1 point)
test2 :: IO ()
test2 = undefined

-- Problem 2.
-- Define a n-fold controlled-not gate nfoldCX.
-- You can only use ancillas, controlled_not and toffoli (provided below) to define c_to_nX. 
-- If you use ancillas in your definition of nfoldCX, you must return them back to 0.  
-- (4 points)

toffoli :: Qubit -> Qubit  -> Qubit -> Circ (Qubit, Qubit, Qubit)
toffoli x y z = do
  z <- qnot z `controlled` (x, y)
  return (x, y, z)

-- We require the first argument to be the controlled wires and the second
-- argument to be the target. 
nfoldCX :: [Qubit] -> Qubit -> Circ ([Qubit], Qubit)
nfoldCX cs target = undefined

-- Problem 3.
-- Consider an n-qubit unitary operation U such that
-- U|x1 ... xn⟩ = |0 ... 0⟩ if x1 = ... xn = 0
-- U|x1 ... xn ⟩ = -|x1 ... xn ⟩ otherwise.
-- You can only use the gates/circuits we have learned so far to program U.
-- If you use ancillas, you must return them back to 0. 
-- (4 points)
u :: [Qubit] -> Circ [Qubit]
u = undefined



-- Problem 4 (Bonus problem)
-- Consider the following method for calculating binary multiplication.

--      1011   (this is binary for decimal 11)
--    × 1110   (this is binary for decimal 14)
--    ======
--      0000   (this is 1011 × 0)
--   + 10110   (this is 1011 × 1, shifted one position to the left)
--   =======
--     10110
--  + 101100   (this is 1011 × 1, shifted two positions to the left)
--  ========
--   1000010
-- + 1011000   (this is 1011 × 1, shifted three positions to the left)
-- =========
--  10011010   (this is binary for decimal 154)

-- Define a multiplication function based on the above method.
-- You may reuse the addition circuit we defined in the class. 
-- If you use ancillas, you must return them back to 0. 
-- (4 points)
mult :: [Qubit] -> [Qubit] -> Circ [Qubit]
mult = undefined