#import "qcs.typ": *
#set page(
  paper: "a4",
  header: align(center)[
    QCS - DM6 : Decide satisfiability - Augustin LUCAS
  ],
)


#question("Assignment Q1", [
  Using Grover's algorithm, design a quantum circuit deciding with probability $>= 2/3$ SATISFIABILITY,
  having size $O(2^(n/2) "poly"(abs(phi)))$, where $n$ is the number of variables of $phi$.

  SATISFIABILITY:
  - INPUT: Boolean formula $phi$
  - OUTPUT: 1 if $exists sigma : {x_1, dots, x_n} -> {0, dots, 1}$ satisfying $phi$; 0 otherwise
])

Let $f : x in {0, 1}^n |-> phi(x) in {0, 1}$.

Let $Z_f$ be a circuit of size $"poly"(abs(phi))$ such that $Z_f ket(x) = (-1)^(f(x)) ket(x)$

Applying Grover's algorithm with $Z_f$ consists of the following circuit :

#{
  import "@preview/quill:0.5.0": *

  quantum-circuit(
  setwire(0), lstick(align(center)[$n$ qubits], n: 4, pad: 10.5pt), 
    lstick($|0〉$), setwire(1), $H$, mqgate($G$, n:4), mqgate($G$, n:4), mqgate($G$, n:4),
    midstick($ dots $), mqgate($G$, n:4), 1, meter(), setwire(2), 1, [\ ],
  setwire(0), 1, lstick($|0〉$), setwire(1), $H$, 3, midstick($ dots $), 2, meter(), setwire(2), 1, [\ ],
  setwire(0), 1, lstick($|0〉$), setwire(1), $H$, 3, midstick($ dots $), 2, meter(), setwire(2), 1, [\ ],
  setwire(0), 1, lstick($|0〉$), setwire(1), $H$, 3, midstick($ dots $), 2, meter(), setwire(2), 1,
  )
}

Let $y$ be the final measurement. After that, we check if it is a solution to $f$. If it is a solution
to $f$, it it a solution to $phi$ too, and $phi$ is satisfiable.

As we need to apply the $G$ gate $O(2^(n/2))$ times, there are $O(2^(n/2))$ uses of $Z_f$ in this circuit. Then,
the complexity of the circuit is $O(2^(n/2) "poly"(abs(phi)))$.


We now need to design a circuit $Z_f$, such that $Z_f ket(x) = (-1)^(f(x)) ket(x)$.
We may need the following gates:
- $Z_1 ket(x_1 x_2 y) = ket(x_1 x_2 ((x_1 and x_2) xor y))$
- $Z_2 ket(x_1 x_2 y) = ket(x_1 x_2 ((x_1 or x_2) xor y))$
- $Z_3 ket(x y) = ket(x (not x xor y))$

Using these gates, we can build $Y_phi$ such that $Y_phi ket(x_1 dots x_n) ket(0^p) ket(b) = ket(x_1 dots x_n (b xor phi(x_1, dots, x_n)))$, using $p$ ancilla qubits.
We then restore these $p$ ancilla qubits to their original state by applying the operations in reverse order.



#question("Bonus Question", [
  There is a box with 2 possibilities:
  - There is no bomb, the box replicates identity
  - There is a bomb, if we measure in basis ${ket(0), ket(1)}$:
    + outcome $ket(0)$ : it outputs $ket(0)$
    + outcome $ket(1)$ : EXPLOSION

  For any $epsilon > 0$, determine if there is a bomb without getting an explosion.
  You are allowed for an error or an explosion with probability $<= epsilon$
])