# Jacek's problem

Ile bramek 1/2 kubitowych potrzeba aby ze stanu $\lvert 0 \rangle$ przejść do zadanego $\lvert \psi \rangle$?

Tutaj jest $\mathcal{O}(n 2^n)$ (modulo oszustwo):
indukcja po $n$:
$n = 1$ lub $n=2$ -- jedna bramka; done
$n > 2$ -- zapisz $\lvert \psi \rangle = \sum_{b} \alpha_b \lvert b 0\rangle + \beta_b \lvert b 1 \rangle$ i niech $\gamma_b = \sqrt{|\alpha_b|^2 + |\beta_b|^2}$
z indukcji bierzesz obwód który 0 przekształca na $\sum_{b} \gamma_b \lvert b 0 \rangle$
teraz aplikujesz takiego cosia $U$ zdefiniowanego jako $U \lvert b 0 \rangle = \gamma_b^{-1}(\alpha_b \lvert 0 \rangle + \beta_b \lvert 1 \rangle)$
chyba $U$ implementujesz jako konkatenacja $2^{n-1}$ rotacji 1 qubitowych, gdzie każda z nich sprawdza, czy reszta rejestru to twoje ulubione $\lvert b \rangle$ (i taki check robisz w $\mathcal{O}(n)$ Toffolich)

in total, masz $T(n) = n 2^{n-1} + T(n-1)$ co się zwija do $T(n) \in \mathcal{O}(n2^n)$