```python
import cirq
```

We have already seen that quantum circuits can be used to transfer information efficiently. 
Now, we will see for the first time how we can use a quantum circuit to solve a problem in a more efficient way than it is possible with a classical probabilistic Turing machine. While the problem we will introduce below seems and also is a bit artificial, it demonstrates some essential concepts.

Reading Ch. 6, rspa.1992.0167

Before we state the problem and show the algorithm we want to briefly describe a process called phase kick-back, which quite nicely demonstrates the power of working with states that are superposed

To demonstrate the basic idea behind the phase kick-back we imagine a two qubit system, where the first qubit is im some arbitray superposition $a_0|0\rangle +a_1|1\rangle $ and the second qubit is in the following state $\frac{1}{\sqrt{2}}(|0\rangle -|1\rangle) = H|1\rangle$. Hence the system is in the follwoing state
\begin{equation}
|\psi\rangle = \left(a_0|0\rangle +a_1|1\rangle\right)\frac{1}{\sqrt{2}}(|0\rangle -|1\rangle)
\end{equation}
If we now look at the effect of a general unitary transformation $cU_{f(x)}$ where the first gate controls the transformation, i.e. $cU=|0\rangle\langle0| \otimes U_{f(0)} + |1\rangle\langle1| \otimes U_{f(1)}$, with $f:\{0,1\}\rightarrow \{0,1\}$ and $U_{f(x)}|y\rangle = |y\oplus f(x)\rangle $. It is now a simple exercise to apply $cU_{f(x)}$ to the initial state and we find
\begin{equation}
|\psi\rangle = \left((-1)^{f(0)}a_0|0\rangle +(-1)^{f(1)}a_1|1\rangle\right)\frac{1}{\sqrt{2}}(|0\rangle -|1\rangle)
\end{equation}
Surprisingly, we have, in fact not modified the target state but the control state, and its phase is changed by $\pi f(x)$, hence the name phase kick-back

We are now going to formulate the Deutsch problem and from there it should become clear, how one can use the phase kick-back idea to solve it 

\textbf{The Deutsch Problem} 
\begin{problem}
Let $f: \{0,1\} \rightarrow \{0,1\}$ be an unkown function.
Determine $f(0) \oplus f(1)$
\end{problem}

It is evident that with a classical computer, this problem can be solved using two queries. 
The Deutsch algorithm can solve this problem using a quantum circuit using a \textbf{single} query

This can be done using the phase kick-back.
Imagine we strart out in the state $|\psi\rangle = \frac{1}{2}\left(|0\rangle +1\rangle\right)(|0\rangle -|1\rangle)$ If we now apply $cU_{f(x)}$ we find 
\begin{equation}
|\psi_1\rangle =cU|\psi\rangle = \frac{(-1)^{f(0)}}{2}\left(|0\rangle +(-1)^{f(1)\oplus f(0)}|1\rangle\right)(|0\rangle -|1\rangle)
\end{equation}
One can now see that the state in the first bracket is the outcome of applying the Hadamard gate to $|0\rangle$ or ($|1\rangle$), when $f(1)\oplus f(0) =0$ ($f(1)\oplus f(0)=1$). Using that the Hadmard gate is self inverse, we find 
\begin{equation}
H|\psi_1\rangle = \frac{(-1)^{f(0)}}{\sqrt{2}}|0 (1)\rangle (|0\rangle -|1\rangle)
\end{equation}
telling us the value of $f(0) \oplus f(1)$

Before we implement the Deutsch cuircuit we have to construct a circuit, that implements $cU_{f(x)}$


```python
def f_cirquit(q0,q1, f0, f1):
    if f0:
        yield [cirq.X(q0),cirq.CNOT(q0,q1),cirq.X(q0)]
    if f1:
        yield cirq.CNOT(q0,q1)
```


```python
def deutsch_circuit(f0, f1):
    c = cirq.Circuit()
    q0,q1 = cirq.LineQubit.range(2)
    #create intial states
    c.append([cirq.H(q0),cirq.X(q1),cirq.H(q1)])
    #apply cU_f
    c.append(f_cirquit(q0,q1, f0, f1))
    #apply final H gate
    c.append(cirq.H(q0))
    #measure first qubit
    c.append(cirq.measure(q0))
    return c
```


```python
s=cirq.Simulator()
c = deutsch_circuit(1,0)
print(c)
```

    0: ───H───X───@───X───H───M───
                  │
    1: ───X───H───X───────────────



```python
x = s.simulate(c)
```


```python
x
```




    measurements: 0=1
    output vector: -0.707|10⟩ + 0.707|11⟩




```python
for f in [(0,0),(0,1),(1,0),(1,1)]:
    s=cirq.Simulator()
    c = deutsch_circuit(*f)
    x = s.simulate(c)
    assert (f[0] + f[1])%2 == x.measurements['0'][0]
```

3d52956a869085d58f9460e3c74b3b261424f735
ipynb
Jupyter Notebook
src/3. The Deutsch Algorithm.ipynb
phyjonas/QC
bbb3ace33dc7c5e64ba051c2908ea1fd2f88f4ee
MIT
src/3. The Deutsch Algorithm.ipynb
phyjonas/QC
bbb3ace33dc7c5e64ba051c2908ea1fd2f88f4ee
MIT
src/3. The Deutsch Algorithm.ipynb
phyjonas/QC
bbb3ace33dc7c5e64ba051c2908ea1fd2f88f4ee
MIT
Qwen/Qwen-72B
1. YES
2. YES