67 lines
2.6 KiB
Plaintext
67 lines
2.6 KiB
Plaintext
|
#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$
|
||
|
|
])
|
||
|
|
|