$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$
Deutsch-Jozsa Algorithm¶
First created in September 2018
Ref:
[1] Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667
Basics¶
Deutsch-Jozsa Algorithm demonstrates that a problem that would take a classical computer $2n+1$ runs (iterations) to solve can be solved by a quantum computer in one (a single run).
It is largely a "toy algorithm" that yet to find an application, but it illustrates that the power of quantum computing is real.
In the following diagram, the top line represents the query register, which serves as the input to the function $f(x)$. The bottom line is the answer register, which is the output of $f(x)$.
That said, the measurement is in fact on the query register (the input). This is because of the phase kickback from the answer register, as phase is relative.
$\Ket{\psi_0}=\Ket0^{\otimes n}\Ket1.$
$\displaystyle \Ket{\psi_1} =\left(H^{\otimes n}\otimes H\right)\Ket{\psi_0} =\big(H\Ket0\big)^{\otimes n}\otimes\big(H\Ket 1\big) =\left(\prod_{k=1}^{\otimes n}\frac{\Ket0+\Ket1}{\sqrt2}\right)\left(\frac{\Ket0-\Ket1}{\sqrt2}\right) =\sum_{x\in\{0,1\}^{\otimes n}}{\frac{\Ket x}{\sqrt{2^n}}}\left(\frac{\Ket0-\Ket1}{\sqrt2}\right) .$
$\displaystyle U_f=\Ket{x,y}\mapsto\Ket{x,y\oplus f(x)}.~~ U_f\Ket{\psi_1} =\sum_{x\in\{0,1\}^{\otimes n}}{\frac{\Ket x}{\sqrt{2^n}}}\left(\frac{\Ket{f(x)}-\Ket{1\oplus f(x)}}{\sqrt2}\right) .$
Note: $\oplus$ is XOR. Given $\displaystyle y=\left(\frac{\Ket0-\Ket1}{\sqrt2}\right),~~ y\oplus f(x) =\frac{\Ket{0\oplus f(x)}-\Ket{1\oplus f(x)}}{\sqrt2} =\frac{\Ket{f(x)}-\Ket{1\oplus f(x)}}{\sqrt2} .$
$\displaystyle \because \Ket{f(x)}-\Ket{1\oplus f(x)} =\left\{\begin{matrix}\Ket0-\Ket1&\text{when}~~f(x)=0,\\\Ket1-\Ket0&\text{when}~~f(x)=1.\end{matrix}\right.~~ \therefore y\oplus f(x) =\left(\frac{(-1)^{f(x)}\big(\Ket0-\Ket1\big)}{\sqrt 2}\right) .$
$\displaystyle \Ket{\psi_2} =U_f\Ket{\psi_1} =\sum_{x\in\{0,1\}^{\otimes n}}{\frac{\Ket x}{\sqrt{2^n}}}\left(\frac{(-1)^{f(x)}\big(\Ket0-\Ket1\big)}{\sqrt2}\right) =\sum_{x\in\{0,1\}^{\otimes n}}{\frac{(-1)^{f(x)}\Ket x}{\sqrt{2^n}}}\left(\frac{\Ket0-\Ket1}{\sqrt2}\right) .$
Note: The phase factor $(-1)^{f(x)}$ was on the answer register being transferred to the query register (phase kickback).
Consider $\displaystyle \Ket x=\prod_{k=1}^{\otimes n}\Ket{x_k},~~~ H^{\otimes n}\Ket x =\Rsr{2^n}\prod_{k=1}^{\otimes n}\big(\Ket{0_k}+(-1)^{x_k}\Ket{1_k}\big) =\Rsr{2^n}\sum_{z\in\{0,1\}^{\otimes n}}\big({-1}\big)^{x\cdot z}\Ket z,~$ where $x\cdot z=\sum_{k=1}^nx_kz_k$.
To illustrate the phase $x\cdot z$, let $\displaystyle \Ket z=\Ket{z_1z_2\ldots z_n}.~$ The phase each qubit contributes is $\displaystyle \left\{ \begin{array}{ll} -1&\text{when }x_k=1\text{ and }z_k=1,\\ 1&\text{otherwise}. \end{array} \right.$
In other words, each qubit contributes a phase of $(-1)^{x_kz_k}.$ Therefore, all qubits in $\Ket z$ give a phase of $x\cdot z=\sum_{k=1}^nx_kz_k.$
Note: $x\cdot z\ne\Braket{x\Verti z}.$ e.g. $0\cdot 0=0$ but $\Braket{0\Verti 0}=1.$
For example, $\displaystyle H\otimes H\otimes H\Ket{101} =\Rsr{2^3}\big(\Ket 0-\Ket 1\big)\big(\Ket 0+\Ket 1\big)\big(\Ket 0-\Ket 1\big) .$
$\displaystyle =\Rsr{2^3}\big(\Ket{000}-\Ket{001}+\Ket{010}-\Ket{011}-\Ket{100}+\Ket{101}-\Ket{110}+\Ket{111}\big) .$
The bitwise dot product of $\Ket x$ and $\Ket z$ gives the sign.
e.g. $\Ket{101}\cdot\Ket{010}=0~(+),~\Ket{101}\cdot\Ket{110}=1~(-),~\Ket{101}\cdot\Ket{101}=2~(+),$ etc.
Making use of $H^{\otimes n}\Ket x=\Rsr{2^n}\sum_z(-1)^{x\cdot z}\Ket z,$ we have
$\displaystyle \Ket{\psi_3} =(H^{\otimes n}\otimes I)\Ket{\psi_2} =\left(\sum_{x\in\{0,1\}^{\otimes n}}{\frac{(-1)^{f(x)}H^{\otimes n}\Ket x}{\sqrt{2^n}}}\right)\otimes \left(\frac{\Ket0-\Ket1}{\sqrt2}\right)$
$\displaystyle =\left( \sum_{x\in\{0,1\}^{\otimes n}}\frac{(-1)^{f(x)}}{\sqrt{2^n}} \left(\Rsr{2^n}\sum_{z\in\{0,1\}^{\otimes n}}\big({-1}\big)^{x\cdot z}\Ket z\right) \right)\otimes\left(\frac{\Ket0-\Ket1}{\sqrt2}\right) ={\frac{1}{2^n}}\sum_{x,z}(-1)^{x\cdot z+f(x)}\Ket z\left(\frac{\Ket0-\Ket1}{\sqrt2}\right) .$
For the query register without the answer $\Ket{\psi_3'}={\frac{1}{2^n}}\sum_{x,z}(-1)^{x\cdot z+f(x)}\Ket z$, the amplitude of $z=0$ or $\Ket z=\Ket0^{\otimes n}$ is $\phi_0={\frac{1}{2^n}}\sum_x(-1)^{f(x)}\Ket0^{\otimes n}$.
If $f(x)$ is constant, the amplitude is either all $+1$ or all $-1$. $\phi_0={\frac{1}{2^n}}2^n\times\pm1=\pm1$, with unity probability $\left|\phi_0\right|^2=1$. The measurement will return all $\Ket0$.
If $f(x)$ is balanced, half of $(-1)^{f(x)}$ are $+1$ and half $-1$, cancelling each other, $\left|\phi_0\right|^2=0$, leaving no amplitude for $\Ket0^{\otimes n}$. That means there will be at least one qubit measuring $\Ket1$.
In the above ellaboration, $\left|\phi_0\right|^2$ is either $0$ or $1$. What if $f(x)$ is neither constant nor balanced (e.g. returning 40% $0$ and 60% $1$), $0<\left|\phi_0\right|^2<1$?
That means measuring all zeros is not a certainty but still a possibility. So when an all-zero result shows up, you cannot conclude that $f(x)$ is constant.
This is when the Deutsch-Jozsa algorithm will break down, unable to determine the configuration of $f(x)$.
In other words, $f(x)$ is required to be either constant or balanced for Deutsch-Jozsa algorithm to be valid.