#### Problem
Setup:
* We have a blackbox function $f$.
* Its input is a $n$ bit binary
(an integer number with range $0\le x \le 2^n-1$)
* Output $f(x)$ is either 0 or 1.
* It can be one of these function:
* A constant function, where $f(x)=C$ all the time. $C$ can be 0 or 1 but is constant given any input.
* A balanced function, where $f(x)=0$ for half set of the input and $f(x)=1$ for the other half. We don't know which half an input belongs to.
Question: Determine whether $f(x)$ is a balanced function or constant function.
#### Solution
1. Initialize the system with an anncilla bit:
$$\ket{\psi_0}=\ket{0}^{\otimes n}\otimes\ket{1} $$
2. Intro superposition:
$$H^{\otimes n}\ket{\psi_0} =\ket{\psi_1} = (\sum_x{\ket{x}})\otimes\ket{-} $$
3. Apply the [oracle](http://shaofanlai.com/post/102#oracle) to kick the $f(x)$ to be the phase of $\ket{x}$
$$
\begin{aligned}
\ket{\psi_2} &= U(\psi_1) \\
&= \sum_x{U(\ket{x}\otimes\ket{-}}) \\
&= \sum_x{(-1)^{f(x)}\ket{x-}} \\
&= \left(
\begin{cases}
\sum_x{\ket{x}} & \text{if $f(x)$ is constant and $C=0$} \\
\sum_x{-\ket{x}} & \text{if $f(x)$ is constant and $C=1$} \\
\sum_{x\in S}{\ket{x}}- \sum_{x\in S'}{\ket{x} } & \text{balanced, if $f(x)=0$ for set $S$ and $f(x)=1$ for set $S'$}
\end{cases}
\right) \otimes \ket{-}
\end{aligned}
$$
We will only focus on the non-ancilla part (i.e. $\ket{\psi_2}_x$ ) in the follwing discussion
4. Interference
We will apply H gate to all registers and focus on the amplitude of state $\ket{0}^{\otimes n}$.
For constant case, we will get :
$$
H(\ket{\psi_2}_x) = \begin{cases}
H(\sum_x{\ket{x}}) = H(\ket{+}^{\otimes n}) = \ket{0}^{\otimes n} & C=0 \\
H(\sum_x{-\ket{x}}) = -H(\ket{+}^{\otimes n}) = -\ket{0}^{\otimes n} & C=1 \\
\end{cases}
$$
when measured, we have $100\%$ chance to get a $\ket{0}^{\otimes n}$ .
For balanced case, we will prove that we have $0\%$ to get a $\ket{0}^{\otimes n}$:
We can write the n-bit H gate in this away:
$$
H^{\otimes n} \ket{x} = \sum_{u} (-1)^{x \cdot u} |u\rangle
$$
So the system will be:
$$
\begin{aligned}
H\ket{\psi_2}_x &=
\left(\sum_{x\in S}{H\ket{x}}\right)
- \left(\sum_{x\in S'}{H\ket{x}}\right)\\
&= \left(\sum_{x\in S}\sum_u(-1)^{x\cdot u}\ket{u}\right)
- \left(\sum_{x\in S'}\sum_u(-1)^{x\cdot u}\ket{u}\right) \\
&= \sum_u\left( \sum_{x\in S}(-1)^{x\cdot u}-\sum_{x\in S'}(-1)^{x\cdot u}\right) \ket{u}
\end{aligned}
$$
When we only focusing on $u=\ket{0}^{\otimes n}$, the amplitude (coefficient) is
$$
\begin{aligned}
A_0 &= \sum_{x\in S}(-1)^{x\cdot \ket{0}}-\sum_{x\in S'}(-1)^{x\cdot \ket{0}} \\
&= \sum_{x\in S}1-\sum_{x\in S'}1 \\
&= |S| - |S'| = 0 \\
\end{aligned}
$$
#### Why it's quick?
The oracle $U$ only calls the black box function $f$ once. In the classicial way, we need to call $f$ at least $O(2^n)$ times.
#### Takeaways:
* Oracle trick (with phase kickback). Send the result from multiverse to the phase.
* The interference on a perticular state. Aggregate results from multiverse.
#### Follow-ups:
* What if $f(x) = s \cdot x \pmod 2$ and we want to find $s$?
* Bernstein-Vazirani Algorithm. mentioned in [this post](http://shaofanlai.com/post/103).
* Why we need to set ancilla bit to $\ket{-}$ at first?
* To trigger a phase kickback. Why we need a kickbase?
* Otherwise, the info is encoded in the ancilla bit rather than the input bits.
* deeper!
* where the info is encoded?
* case1: to the ancilla amplitude ( $U\ket{x}\ket{0}$ ). In this case, the ancilla bit is **entangled** with the input bit. When we try to interference the input for different outputs, it will fail because bit $\ket{0}_{ancilla}$ and $\ket{1}_{ancilla}$ is **Orthogonal**.
* case2: to the phase of the input. in this case, we can interference the input (since their ancilla bit is the same).
* why we need interference?
* To get a global look. To aggregate the result into to the interference result. Otherwise, we need $O(2^n)$ measurement. There is no benefit of using QC.
* What if the function is partially balanced?
* We will have larger probabilty to get $\ket{0}$ if the function is closer to constant. $P(\ket{0}^{\otimes n}) = \left( 1 - \frac{2*\text{\#unbalanced}}{2^n} \right)^2$
* Constant -> Constructive Interference; Balanced -> Destructive Interference; Not Balanced -> Partial Interference.
* If only one input out of $2^n$ is different, it will be hard to detect, we need amplitude amplification in this case (e.g. grover).