Deutsch's algorithm is one of the simplest quantum algorithms, demonstrating the power of quantum parallelism and interference. It solves a specific problem—determining whether a function 𝑓(𝑥) is constant or balanced—more efficiently than any classical algorithm.
Given a function 𝑓(𝑥) where:
1. Initialize Qubits:
\( |\psi_0\rangle = |0\rangle \otimes |1\rangle \)
2. Apply Hadamard Gates:
\( H|0\rangle = \frac{1}{\sqrt{2}} ( |0\rangle + |1\rangle ) \)
\( H|1\rangle = \frac{1}{\sqrt{2}} ( |0\rangle - |1\rangle ) \)
\( |\psi_1\rangle
= \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)
\otimes
\frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)
\)
\( |\psi_1\rangle = |+\rangle |-\rangle \)
\( |\psi_1\rangle
= \frac{1}{\sqrt{2}} ( |0\rangle + |1\rangle ) |-\rangle
\)
3. Apply Oracle \( U_f \)
\( |\psi_2\rangle = U_f \frac{1}{\sqrt{2}} ( |0\rangle |-\rangle + |1\rangle |-\rangle ) \)
\( |\psi_2\rangle = \frac{1}{\sqrt{2}} ( U_f |0\rangle |-\rangle + U_f |1\rangle |-\rangle ) \)
\( |\psi_2\rangle
= \frac{1}{\sqrt{2}} \left( (-1)^{f(0)} |0\rangle |-\rangle
+ (-1)^{f(1)} |1\rangle |-\rangle \right) \)
\( |\psi_2\rangle
= \frac{1}{\sqrt{2}} \left( (-1)^{f(0)} |0\rangle
+ (-1)^{f(1)} |1\rangle \right) |-\rangle \)
\( |\psi_2\rangle =
\begin{cases}
\pm \frac{1}{\sqrt{2}} ( |0\rangle + |1\rangle ) |-\rangle = \pm |+\rangle |-\rangle , & f(0)=f(1) \\
\pm \frac{1}{\sqrt{2}} ( |0\rangle - |1\rangle ) |-\rangle = \pm |-\rangle |-\rangle , & f(0)\neq f(1)
\end{cases}
\)
4. Apply Hadamard Gate
\( |\psi_3\rangle =
\begin{cases}
\pm |0\rangle |-\rangle , & f(0)=f(1) \\
\pm |1\rangle |-\rangle , & f(0)\neq f(1)
\end{cases}
\)
If we measure 0 then the function is constant, since f(0)= f(1).
If we measure 1 then the function is constant, since f(0) ≠ f(1).
