# Deutsch's algorithm


```python
import numpy as np

from qiskit import QuantumRegister, ClassicalRegister
from qiskit import QuantumCircuit
from qiskit import execute, BasicAer

import qiskit.tools.visualization as qvis

import warnings
warnings.filterwarnings("ignore", category=DeprecationWarning) 
```

Deutsch's algorithm allows us to perform a task using fewer queries quantumly than are needed classically.

Suppose we have some function $f$, that we know to be one of the 4 following functions:

| Function ($f$) |   $f$(0)    | $f$(1) |
| --- | -------- | -------- |
| `constant_zero`| 0 | 0|
| `constant_one` | 1| 1 |
| `balanced_id` | 0| 1 |
| `balanced_not`| 1 | 0 |

The two "constant" functions output the same value no matter the input, whereas the balanced functions output different values for each input.


## Our task

We are given a black box that we know implements one of: `constant_zero`, `constant_one`, `balanced_id`, `balanced_not`. We are allowed to query the box (i.e. ask for $f(x)$ for either $x= 0, 1$) as many times as we need. _How many queries are needed to determine with certainty which function the box implements_?

Let's choose one of the four functions randomly.


```python
function_names = ['constant_zero', 'constant_one', 'balanced_id', 'balanced_not']
oracle = function_names[np.random.randint(4)]
```

### Classical solution

We _must_ query twice. For example, if we query $f(0)$ and receive $0$, we know we must have `constant_zero` or `balanced_id`, but we still can't pin down the exact function without querying a second time.  

### Quantum solution

We can perform this task with only a _single_ query using two qubits.

Our oracle $U_f$ is going to implement the following transformation:
\begin{equation}
 U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x) \rangle
\end{equation}
where $f$ will be replaced with one of the four functions above, and $\oplus$ indicates addition modulo 2.

For example, if $f$ is `constant_one`,
\begin{eqnarray}
 U_f|00\rangle &=& |01\rangle \\
 U_f|01\rangle &=& |00\rangle \\
 U_f|10\rangle &=& |11\rangle \\
 U_f|11\rangle &=& |10\rangle
\end{eqnarray}

From this you can see that each function will produce a different permutation of the computational basis states. 

**Exercise**: Compute the unitary matrix associated with each function, and write out the quantum circuit that implements it. (The answers are shown further down because we need them for the demo, but you can still compute them yourself to understand how they work.)

To execute Deutsch's algorithm, we'll follow the steps as shown in class. We begin with the state 
\begin{equation} |+-\rangle =
 \left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) \otimes \left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right) = \frac{1}{2}\left(|00\rangle - |01\rangle + |10\rangle - |11\rangle \right)
\end{equation}

Let's set up the quantum and classical registers and prepare it:


```python
q = QuantumRegister(2)
c = ClassicalRegister(1)

circ = QuantumCircuit(q, c)
```


```python
# Prepares the state |+-> starting from |00>
circ.h(q[0])
circ.x(q[1])
circ.h(q[1]);
```

Let's now apply the oracle circuit:


```python
# Here are the quantum circuits for each of our functions
# If the circuit is 'constant_zero', we do nothing.
if oracle == 'constant_one':
    circ.x(q[1])
elif oracle == 'balanced_id':
    circ.cx(q[0], q[1])
elif oracle == 'balanced_not':
    circ.x(q[0])
    circ.cx(q[0], q[1])
```

We saw in the lectures that after calling the oracle, if the function is constant, we get a $|+\rangle$ on the first qubit, but when it is balanced, we get $|-\rangle$. We can combine all these results into a compact form:

\begin{equation}
 U_f|+\rangle |- \rangle =  \left( \frac{|0\rangle + (-1)^{f(0) \oplus f(1)}|1\rangle}{\sqrt{2}} \right) \otimes \left( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right)
 \end{equation}

We can then determine the value of $f(0) \oplus f(1)$, by applying a Hadamard to the first qubit to perform a basis change back to the computational basis, and then measuring. We should obtain:
\begin{equation}
 |f(0)\oplus f(1) \rangle \otimes |-\rangle
\end{equation}

If the function is constant, $f(0) \oplus f(1) = 0$ and so the first qubit will be in state $|0\rangle$. Similarly, if it is balanced, the first qubit will be in state $|1\rangle$. Does this work?


```python
# Convert the first qubit back to the computational basis and measure
circ.h(q[0])
circ.measure(q[0], c[0])

# Execute the circuit a single time to get the measurement outcome
backend = BasicAer.get_backend('qasm_simulator')
result = execute(circ, backend, shots = 1).result()
counts = result.get_counts()

if list(counts.keys())[0] == '0': # c[0] is a tuple of the register and the measurement value
    print("Measured first qubit in state |0>, function is constant.")
else:
    print("Measured first qubit in state |1>, function is balanced.")
```

Were we correct? Let's see which function the oracle had chosen to implement.


```python
print(f"The function implemented by the oracle is '{oracle}'")
```

Deutsch's algorithm can also be generalized to the Deutsch-Josza algorithm when $f$ is a function on $n$ bits. No matter the value of $n$, it is still possible to determine whether $f$ is constant or balanced with a single query.

91a78c1b33b00d10557950a464fcbfdf25b70b9a
ipynb
Jupyter Notebook
01-gate-model-theory/notebooks/Deutsch-Algorithm.ipynb
abhishekabhishek/Intro-QC-TRIUMF
9c780446988b327e32f62113d03b55d689876079
MIT
01-gate-model-theory/notebooks/Deutsch-Algorithm.ipynb
abhishekabhishek/Intro-QC-TRIUMF
9c780446988b327e32f62113d03b55d689876079
MIT
01-gate-model-theory/notebooks/Deutsch-Algorithm.ipynb
abhishekabhishek/Intro-QC-TRIUMF
9c780446988b327e32f62113d03b55d689876079
MIT
Qwen/Qwen-72B
1. YES
2. YES