The Quantum Fourier Transform

In the previously introduced algorithms, the Hadamard transform played an essential role in being able to created a certain superposition of states that was exploited in the various ways by the algorithms. Recall the action of the Hadamard transform \(H^{\otimes n}\) on an arbitrary basis state \(\left|\mathbf{x}\right>\in\mathcal{H}^{2^n}\):
\[H^{\otimes n}\left|\mathbf{x}\right>=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{y}}\left|\mathbf{y}\right>,\]
which can be thought of as effectively encoding the string \(\mathbf{x}\) into the relative paste factors present in the amplitudes of the states in the superposition. Since \(H^{\otimes n}\) is its own inverse appying applying \(H^{\otimes n}\) to the state \(H^{\otimes n}\left|\mathbf{x}\right>\) returns the state \(\left|\mathbf{x}\right>\):
\[(H^{\otimes n}\left(\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{y}}\left|\mathbf{y}\right>\right) =H^{\otimes n}H^{\otimes n}\left|\mathbf{x}\right>=\left|\mathbf{x}\right>/\]In this regard, the Hadamard transform can also be thought of as decoding the information of the string \(\mathbf{x}\) in the phase factors into the state \(\left|\mathbf{x}\right>\).

Notice that all of the amplitudes defining the superposition of states in the Hadamard transform are either \(\pm 1\). The quantum Fourier Transform will generalize the Hadamard transform by constructing certain weighted superpositions of basis states that possess more general phase factors of the form \(e^{i2\pi\omega}\), for some real number \(\omega\in(0,1)\subset\mathbb{R}\). In the case of the Hadamard transform, \(\omega=0\) and \(\omega=1/2\) making \(e^{i2\pi\omega}=\pm1\). The quantum Fourier Transform will allow certain specially weighted superposition of states to be constructed, which will then be used in algorithms that can perform faster than known classical approaches.

The Quantum Fourier Transform

Consider an \(N\)--tuple of \(N\) complex numbers \(x_j\in\mathbb{C}\), where \(j\in\{0,1, \dots, N-1\}\). The discrete \emph{classical} Fourier transform is a function \(\mathcal{F}\) that takes these \(N\) numbers and constructs \(N\) other complex numbers in terms of the \(x_j\):
\[\begin{array}{r c l}
\mathcal{F}:  \mathbb{C}^N &\rightarrow&\mathbb{C}^N \\
  (x_0, x_1, \dots, x_{N-1})& \mapsto &(y_0, y_1, \dots, y_{N-1}),
\end{array}\]
where each of the \(y_k\) complex numbers are given by
\[y_k=\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{j=0}^{N-1}e^{\frac{i2\pi jk}{N}}x_j.\]
The quantum Fourier transform has a related action on the \(N\) computational basis states \(\left|j\right>\in\mathcal{H}^{N}\). Here, the basis states are represented in the \emph{decimal representation} where each state is indexed by the integer \(j\in\{0,1,\dots, N-1\}\). The quantum Fourier transform, denoted by \(\mathbf{QFT}\), maps these computational basis states to another basis called the Fourier basis consisting of weighted superpositions of the computational basis states as
\[\begin{array}{r c l}
QFT:  \mathcal{H}^N &\rightarrow&\mathcal{H}^N \\
  \left|j\right>& \mapsto &\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}\left|k\right>.
\end{array}\]
In terms of the discrete classcical Fourier transform, the action of the \(QFT\) can be expressed more concisely as
\[\left|j\right> \mapsto \displaystyle \frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}y_k\left|k\right>.\]
Now, consider the action of the \(QFT\) on the \(n\) qubit basis state \(\left|0\right>\) where \(N=2^n\),
\[QFT\left|0\right>=\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k\cdot 0}{N}}\left|k\right>=\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}\left|k\right>=H^{\otimes n}\left|0\right>,\]
which is an equally weighted superposition of all \(N\) basis states and this precisely the same state produced  when Hadamard gates are applied to each qubit. Thus, in the case where \(\left|j\right>=\left|0\right>\), \(QFT\left|j\right>=H^{\otimes n}\left|j\right>\). In general though, \(QFT\left|j\right>\neq H^{\otimes n}\left|j\right>\). In this regard, The quantum Fourier transform can be seen as a generalization of the Hadamard transform.

It remains to be checked that the \(QFT\) is a unitary transformation, which will now be done by verifying that \(QFT^\dagger=QFT^{-1}\). To see that this is indeed the case, consider the matrix representation of \(QFT\) whose matrix coefficient \(q_{jk}\) contained in the \(j^{th}\) row and \(k^{th}\) column is given by \(q_{jk}= e^{ \frac{i2\pi jk}{N}}\). Then the conjugate transpose \(QFT^\dagger\) of \(QFT\) has  the corresponding matrix coefficient \(q'_{jk}=\overline{q_{kj}}=e^{ \frac{-i2\pi kj}{N}}\)
in its \(j^{th}\) row and \(k^{th}\) column.
Therefore, the action of \(QFT^\dagger\) on some basis state \(\left|k\right>\in\mathcal{H}^N\) is given as
\[\begin{array}{r c l}
QFT^\dagger:  \mathcal{H}^N &\rightarrow&\mathcal{H}^N \\

  \left|k\right>& \mapsto &\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{j=0}^{N-1}e^{\frac{-i2\pi kj}{N}}\left|j\right>.
\end{array}\]
Now consider what happens when the composition of \(QFT\) with \(QFT^\dagger\) acts on a basis state \(\left|j\right>\)
\[\begin{array}{r  l}
QFT^\dagger QFT\left|j\right>=&QFT^\dagger\left(\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}\left|k\right> \right) \\
=&\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}QFT^\dagger\left|k\right> \\
=& \displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}\left(\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{l=0}^{N-1}e^{\frac{-i2\pi kl}{N}}\left|l\right>\right) \\
=&\displaystyle\frac{1}{N}\displaystyle\sum\limits_{l=0}^{N-1}\left(\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}e^{\frac{-i2\pi kl}{N}}\right)\left|l\right> \\
&= \displaystyle\frac{1}{N}\displaystyle\sum\limits_{l=0}^{N-1}\left(\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(j-l)}{N}}\right)\left|l\right>.
\end{array}\]
Let \(\alpha_s\) denote the amplitude of the basis state \(\left|s\right>\) in this superposition.  Then assuming \(s\neq j\),
\[\alpha_s=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(j-s)}{N}}=\displaystyle\frac{1}{N}\displaystyle\frac{e^{\frac{i2\pi k(j-s)}{N}N}-1}{e^{\frac{i2\pi k(j-s)}{N}}-1}=\displaystyle\frac{1}{N}\displaystyle\frac{(1-1)}{e^{\frac{i2\pi k(j-s)}{N}}-1}=0,\]
where the formula for the geometric series
 \[\displaystyle\sum\limits_{k=0}^{N-1}z^{k}=\displaystyle \frac{z^{N}-1}{z-1}\]
 was used together with
\[z^N=e^{ \frac{i2\pi (j-s)}{N}N}=e^{i2\pi (j-s)}=1\]
since \(e^{i2\pi m}=1\) for any integer \(m\). This implies that all basis states \(\left|s\right>\neq\left|j\right>\) have \(\alpha_s=0\) amplitude and do not appear in the above superposition. Then examining the amplitude of the state \(\left|j\right>\) shows that
\[\alpha_j=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(j-j)}{N}}=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(0)}{N}}=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}1=\displaystyle\frac{N}{N}=1,\]
which shows that \(QFT^\dagger QFT\left|j\right>=\left|j\right>\). A similar argument also shows that \(QFT QFT^\dagger\left|j\right>=\left|j\right>\). This implies that \(QFT^\dagger=QFT^{-1}\) proving that \(QFT\) is indeed a unitary operator.

The proof just presented that the quantum Fourier transform \(QFT\) is a unitary operator shows that the \(QFT\) can be used to define transformations on quantum states. However, the proof does not provide a constructive means for actually implementing the \(QFT\), since unitarity was shown directly using the definition of the \(QFT\). In the next section, an explicit circuit using elementary quantum gates will be constructed. The existence of such a circuit will also provide proof that the \(QFT\) is unitary provided that all gates used in this construction are themselves unitary.

Simon's Problem and Algorithm

Let \(X\subseteq \{0,1\}^n \) be some subset and consider a function \(f: \{0,1\}^n\rightarrow X\) that satisfies the property that for all \(\mathbf{x}, \mathbf{y}\in \{0,1\}^n\), \(f(\mathbf{x})=f(\mathbf{y})\) if and only if \(\mathbf{x}=\mathbf{y}\) or \(\mathbf{x}=\mathbf{y}\oplus\mathbf{s}\), for some fixed \(\mathbf{s}\in\{0,1\}^n\). Suppose such a function is provided, but the string \(\mathbf{s}\) is unknown. Simon's problem, presented first in \cite{simon}, is concerned with determining the string \(\mathbf{s}\) by making queries to a black-box that evaluates the function \(f\).

Simon's Problem

Input:  A black-box that computes an unknown function \(f:\{0,1\}^n\rightarrow X\), where \(X\subseteq\{0,1\}\), such that there exists  some fixed \(\mathbf{s}\in\{0,1\}^n\) that satisfies  \(f(\mathbf{x})=f(\mathbf{y})\) if and only if \(\mathbf{x}=\mathbf{y}\) or \(\mathbf{x}=\mathbf{y}\oplus\mathbf{s}\).

Problem:  Determine the unknown string \(\mathbf{s}\in\{0,1\}^n\) by making queries to the black-box that evaluates \(f\).

A quantum algorithm for solving Simon's problem will be constructed in what follows, and it will be shown that this can be done by making exponentially fewer queries to \(f\) than what is needed in the classical case. Before presenting this algorithm, it is worthwhile to invest some detail pertaining to some properties of bitstrings in \(\{0,1\}^n\) and certain operations defined on them. The relevant details can be found in the previous post on orthogonal complements in the vector space \(\mathbb{Z}_2^n\). These consequences will be essential in the analysis of Simon's algorithm.

Simon's Algorithm

For Simons problem we are provided with a black-box that computes an unknown function \(f: \{0,1\}^n\rightarrow X\) such that there exists  some fixed \(\mathbf{s}\in\{0,1\}^n\) that satisfies  \(f(\mathbf{x})=f(\mathbf{y})\) if and only if \(\mathbf{x}=\mathbf{y}\) or \(\mathbf{x}=\mathbf{y}\oplus\mathbf{s}\). This black-box can be implemented as the controlled\(-U_f\) gate \[\begin{array}{r l}
c-U_f: &\mathcal{H}^{2^n}\otimes\mathcal{H}^{2^n}\rightarrow \mathcal{H}^{2^n}\otimes \mathcal{H}^{2^n}, \\
& \left|\mathbf{x}\right>\left|\mathbf{y}\right>\mapsto \left|\mathbf{x}\right>\left|\mathbf{y}\oplus f(\mathbf{x})\right>,
\end{array}\]
where the first register serves as a \(n\) qubit control register and the second register acts as a \(n\) qubit target.


(A circuit used to solve Simon's problem consisting of two \(n\) qubit registers. Simon's algorithm runs the circuit multiple times making a single query to the black-box \(c-U_f\) each time the circuit is applied. First, Hadamard gates are applied to the first \(n\) qubits in the control register of the state \(\left|\psi_0\right>\) creating an equally weighted superposition of basis states in the control register. Then by applying the \(c-U_f\) gate to \(\left|\psi_1\right>\) an entangled state \(\left|\psi_2\right>\) is produced that contains the value of each \(f(\mathbf{x})\) in the target register. Measuring the target register of \(\left|\psi_2\right>\), leaves the control register in a state which produces a superposition \(\left|\psi_4\right>\) of states in the orthogonal complement \(\mathbf{s}^ {\bot}\) after the last set of Hadamard gates is applied to the control register. A final measurement of the control register then produces a state \(\left|\psi_5\right>\) in \(\mathbf{s}^ {\bot}\). After this procedure is iterated a sufficient amount of times the states obtained after the measurement can be used to determine \(\mathbf{s}\).)


Simon's algorithm makes use of the circuit displayed in the figure above, and begins with the input state \(\left|\psi_0\right>=\left|\mathbf{0}\right>\left|\mathbf{0}\right>\). First, a Hadamard gate is applied to every qubit in the control yielding
\[\left|\psi_1\right>=H^{\otimes n}\left|\mathbf{0}\right>\left|\mathbf{0}\right>=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\left|\mathbf{0}\right>,\]
which has an equally weighted superposition of all \(2^n\) basis states in the control register. Next, by making a single query with \(c-U_f\) to the state \(\left|\psi_1\right>\), a superposition of states is formed that contains the value of \(f(\mathbf{x})\) for every \(\mathbf{x}\in\{0,1\}^n\) in the target register
\[\begin{array}{r l}
\left|\psi_2\right>=c-U_f\left|\psi_1\right> &=\displaystyle\frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}c-U_f(\left|\mathbf{x}\right>\left|\mathbf{0}\right>) \\
&=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\left|f(\mathbf{x})\right>.
\end{array}\]
 Notice that this state \(\left|\psi_2\right>\) is actually an entangled state. If all the qubits in the target register were to be measured at this point, a particular computational basis state \(\left|f(\mathbf{x})\right>\in\mathcal{H}^{2^n}\) will be observed.

To see what state the control register will be left in after a measurement is made to the target, recall the definition of the function \(f\): f(\mathbf{x})=f(\mathbf{y})\) if and only if \(\mathbf{x}=\mathbf{y}\) or \(\mathbf{y}=\mathbf{x}\oplus\mathbf{s}\). Observe that if \(\mathbf{s}\neq\mathbf{0}\) then the function \(f\) is two-to-one. This means that for every value \(f(\mathbf{x})\) there are precisely two bitstrings in \(\{0,1\}^n\) that both share the same value \(f(\mathbf{x})\)---namely, the strings \(\mathbf{x}\) and \(\mathbf{y}=\mathbf{x}\oplus\mathbf{s}\). Therefore, consider a partition of the \(2^n\) bitstrings of \(\{0,1\}^n\) into \(2^{n-1}\) disjoint sets  where each set is of the form \(\{\mathbf{x},\mathbf{x}\oplus\mathbf{s}\}\). Moreover, let \(I\) be the index set that contains \(2^{N-1}\) bitstrings \(\mathbf{x}\) that represent each of the sets \(\{\mathbf{x},\mathbf{x}\oplus\mathbf{s}\}\). In this way, the  entangled state \(\left|\psi_2\right>\) can be expressed as
\[\left|\psi_2\right>=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\left|f(\mathbf{x})\right>=\displaystyle \frac{1}{\sqrt{2^{n-1}}}\displaystyle\sum\limits_{\mathbf{x}\in I}\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right)\left|f(\mathbf{x})\right>,\] where now the sum only runs over the indexed states of \(I\).


When the target register of \(\left|\psi_2\right>\) is measured, a state of the form
\[\left|\psi_3\right>=\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right)\left|f(\mathbf{x})\right>\]for a particular value of \(f(\mathbf{x})\) is observed with equal probability. Thus, the target register becomes the state \(\left|f(\mathbf{x})\right>\), and the control register is left in the state \[\displaystyle\frac{1}{\sqrt{2}}\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right)\] after measurement. Then as it was shown in the previous section, where \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right),\] applying Hadamard gates to the control register after a measurement on the target register has been made results in the state
\[\left|\psi_4\right>=H^{\otimes n}\left|\psi_3\right>=H^{\otimes n}\left|\psi\right>\left|f(\mathbf{x})\right>=\displaystyle\frac{1}{\sqrt{2^{n-1}}}\displaystyle\sum\limits_{\mathbf{z}\in\mathbf{s}^\bot}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>\left|f(\mathbf{x})\right>,\]
which has the control register in an equally weighted superposition of all basis states belonging to the orthogonal complement \(\mathbf{s}^ {\bot}\). Measuring the control register therefore yields some state \(\left|\psi_5\right>=\left|\mathbf{z}\right>\), such that \(\mathbf{z}\in\mathbf{s}^ {\bot}\), where each state is observed with equal probability.

Simon's algorithm solves the problem of determining \(\mathbf{s}\) by repeating the operation just described by the circuit in the figure shown above. By observing the control register after the final measurement is made in each iteration of this circuit, elements of \(\mathbf{s}^ {\bot}\) are effectively sampled uniformly at random. After a sufficient amount of samples are made from each iteration, the information obtained from the observed states \(\left|z_i\right>\) can be used to construct the matrix \(W\) whose rows consists of coefficients given by the strings \(\mathbf{z_i}\). This allows the string \(\mathbf{s}\) to be determined by finding the solutions to the matrix equation \(W\mathbf{x}^T=\mathbf{0}^T\).

    In regards to the query complexity of Simon's algorithm, it can be shown that the number of expected queries \(Q(n)\) made to the black-box \(c-U_f\), which is directly proportional to the number of iterations that need to be made to Simon's circuit, is less than \(n\). In addition, the amount of other steps \(S(n)\) needed to solve the matrix equation \(W\mathbf{x}^T=\mathbf{0}^T\) is in \(O(n^3)\).\cite{mosca}

     It is presumed that this latter part of this algorithm of solving the matrix equation is performed through classical means. Therefore, the total time complexity of Simon's algorithm is \(T(n)=Q(n)R(n)+S(n)=O(n)R(n)+O(n^3)\) for some function \(R(n)\) representing the time complexity of implementing the black box \(c-U_f\). Regardless, the total time complexity of Simon's algorithm is \(\Omega(n^3)\). In the probabilistic  classical case, at least \(\Omega(2^{n/3})\) queries must be made to some classical black box implementing the function \(f\) in order to solve Simon's problem with a probability of success at least \(2/3\). This requires resources exponentially larger than the quantum algorithm provided by Simon's. Thus, Simon's algorithm is our first example of an algorithm that can perform exponentially faster than any known classical algorithm.

Orthogonal complements in the vector space \(\mathbb{Z}_2^n\)

This section will review some mathematical preliminaries that will be useful in understanding Simin's algorithm.

The set \(\{0,1\}^n\) can be regarded as an \(n\)-dimensional vector space \(\mathbb{Z}_2^n\) over the field \(\mathbb{Z}_2\) where the addition of vectors, or bitstrings, \(\mathbf{x}=x_1x_2\dots x_n\) and \(\mathbf{y}=y_1y_2\dots y_n\) in \(\{0,1\}^n\) is given by \(\mathbf{x}\oplus\mathbf{y}=\mathbf{z}\). Let \(\mathbf{z}=z_1z_2\dots z_n\). Then this operation is just bitwise addition modulo \(2\) where \(z_i=(x_i+y_i)mod2\) for each \(i\). That is, \(z_i=1\) if and only if \(x_i\neq y_i\). An inner product on \(\mathbb{Z}_2^n\) is also defined for \(\mathbf{x}=x_1x_2\dots x_n\) and \(\mathbf{y}=y_1y_2\dots y_n\) in \(\mathbb{Z}_2^n\) as
\[\mathbf{x}\cdot\mathbf{y}=(x_1y_1+x_2y_2+\dots +x_ny_n)mod2=\left(\displaystyle\sum\limits_{i=1}^n x_iy_i\right)mod2,\] and so the product of two bitstrings is either \(0\) or \(1\).

 Consider some \(\mathbf{s}\in\mathbb{Z}_2^n\) and define the orthogonal complement of \(\mathbf{s}\) as the set \(\mathbf{s}^{ \bot}=\{\mathbf{x}\in\mathbb{Z}_2^n | \mathbf{x}\cdot\mathbf{s}=0\}\) consisting of all strings orthogonal to \(\mathbf{s}\). The orthogonal complement \(\mathbf{s}^{ \bot}\) of \(\mathbf{s}\) is actually a vector subspace of \(\mathbb{Z}_2^n\) that is orthogonal to the \(1\)-dimensional vector subspace \(\{\mathbf{0},\mathbf{s}\}\) provided that \(\mathbf{s}\neq\mathbf{0}\). Then since \(\mathbf{s}^{ \bot}\cup\{\mathbf{0},\mathbf{s}\}=\mathbb{Z}_2^n\), and \(\mathbb{Z}_2^n\) has dimension \(n\), \(\mathbf{s}^{ \bot}\) must be a subspace of dimension \(n-1\).

For some string \(\mathbf{x}=x_1x_2\dots x_n\in\{0,1\}^n\), denote by \(\mathbf{x}^T\) the column vector that has the coefficient \(x_i\) in row \(i\). Define a \(m\times n\) matrix \(W\) whose rows are given by \(m\) bitstrings \(\mathbf{w}_j\in\mathbf{s}^{ \bot}\) for some \(\mathbf{0}\neq\mathbf{s}\in\{0,1\}^n\). If the \(m\) bitstrings \(\mathbf{w}_i\) are chosen so that they span \(\mathbf{s}^{ \bot}\) entirely, then a nontrivial solution \(\mathbf{x}^T\) to the matrix equation \(W\mathbf{x}^T=\mathbf{0}^T\), where \(\mathbf{0}\in\{0,1\}^m\), will be a the unique solution \(\mathbf{x}^T=\mathbf{s}^T\) that determines exactly the bitstring \(\mathbf{s}\).

 Let \(\mathbf{x}, \mathbf{y}\in\{0,1\}^n\) and \(\mathbf{s}=\mathbf{x}\oplus\mathbf{y}\). Consider the quantum state \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{y}\right>)\in\mathcal{H}^{2^n}.\] Note that \(\mathbf{y}=\mathbf{x}\oplus\mathbf{s}\) implies \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>).\] Applying the Hadamard transform \(H^{\otimes n}\) to \(\left|\psi\right>\) gives
\[\begin{array}{r l}
H^{\otimes n}\left|\psi\right> &=\displaystyle\frac{1}{\sqrt{2}}\left(H^{\otimes n}\left|\mathbf{x}\right>+H^{\otimes n}\left|\mathbf{x}\oplus\mathbf{s}\right>\right) \\
&= \displaystyle\frac{1}{\sqrt{2}}\left(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>+\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}(-1)^{(\mathbf{x}\oplus\mathbf{s})\cdot\mathbf{z}}\left|\mathbf{z}\right>\right) \\
&= \displaystyle\frac{1}{\sqrt{2^{n+1}}}\left(\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}\left((-1)^{\mathbf{x}\cdot\mathbf{z}}+(-1)^{(\mathbf{x}\oplus\mathbf{s})\cdot\mathbf{z}}\right)\left|\mathbf{z}\right>\right)
\end{array}.\]
Now consider the amplitude \(\alpha_z\) of the state \(\left|\mathbf{z}\right>\) in this superposition:
\[\begin{array}{r l}
\alpha_z  & =(-1)^{\mathbf{x}\cdot\mathbf{z}}+(-1)^{(\mathbf{x}\oplus\mathbf{s})\cdot\mathbf{z}} \\
& = (-1)^{\mathbf{x}\cdot\mathbf{z}}+(-1)^{\mathbf{x}\cdot\mathbf{z}\oplus\mathbf{s}\cdot\mathbf{z}} \\
& = (-1)^{\mathbf{x}\cdot\mathbf{z}}\left(1+(-1)^{\mathbf{s}\cdot\mathbf{z}}\right)
\end{array}.\]
If \(\mathbf{z}\in\mathbf{s}^{ \bot}\), then \(\mathbf{s}\cdot\mathbf{z}=0\) and so \((-1)^{\mathbf{s}\cdot\mathbf{z}}=1\) which implies that \(\alpha_z=2(-1)^{\mathbf{x}\cdot\mathbf{z}}\). Thus, the state \(\left|\mathbf{z}\right>\) remains with a nonzero amplitude \(\alpha_z\) in the superposition \(H^{\otimes n}\left|\psi\right>\). Instead, suppose \(\mathbf{z}\notin\mathbf{s}^{ \bot}\) so that \(\mathbf{s}\cdot\mathbf{z}=1\), which implies that the amplitude of the state \(\left|\mathbf{z}\right>\) is \(\alpha_z=(-1)^{\mathbf{x}\cdot\mathbf{z}}\left(1+(-1)^1\right)=0\). Therefore, the state \(H^{\otimes n}\left|\psi\right>\) consists of a superposition of precisely those \(2^{n-1}\) states \(\left|\mathbf{z}\right>\in\{0,1\}^n\) such that \(\mathbf{z}\in\mathbf{s}^ { \bot}\), allowing the sum to be written as
\[H^{\otimes n}\left|\psi\right>=\displaystyle \frac{1}{\sqrt{2^{n-1}}}\displaystyle\sum\limits_{\mathbf{z}\in\mathbf{s}^{ \bot}}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>.\]
If a measurement were to be performed on the state \(H^{\otimes n}\left|\psi\right>\), where \[\left|\psi\right>=\displaystyle \frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>),\]  some computational basis state \(\left|\mathbf{z}\right>\) such that  \(\mathbf{z}\in\mathbf{s}^{ \bot}\) will be observed.

If multiple quantum states of the form \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>)\] can be constructed and then measured, the set of observed states can be used to construct the matrix \(W\) whose rows consist of elements in \(\mathbf{s}{ \bot}\). Furthermore, if these observed states \(\left|\mathbf{w}_j\right>\) happen to correspond to elements that span \(\mathbf{s}^ { \bot}\), then the string \(\mathbf{s}\) can be uniquely determined by solving the system \(W\mathbf{x}^T=\mathbf{0}^T\). Simon's algorithm provides a way to construct such a state by making queries to the a black-box.

The Deutsch-Jozca Algorithm

The Deutsch problem concerned itself with a function \(f:\{0,1\}\rightarrow \{0,1\}\) defined on a single bit. Instead, consider the function \(f:\{0,1\}^n\rightarrow \{0,1\}\) defined on bitstrings of length \(n\). Moreover, suppose this function is either constant if \(f(\mathbf{x})=c\) for all \(\mathbf{x}\in\{0,1\}^n\) and a fixed \(c\in\{0,1\}\), or balanced if \(f(\mathbf{x})=0\) for precisely half of the bitstrings \(\mathbf{x}\in\{0,1\}^n\) and \(f(\mathbf{x})=1\) for the remaining half of the bitstrings \(\mathbf{x}\in\{0,1\}^n\). This time, the problem of determining whether or not \(f\) is constant or balanced is tricker. In the classical context, suppose \(2^{n-1}\) queries are made to \(f\) for half of the possible bitstrings, and each of these queries returned the value \(0\). Then without making at least one more query to \(f\) it is impossible to determine with certainty whether or not \(f\) is constant or balanced since this next query could return a value of either \(0\) or \(1\). Thus, in the worst case \(2^{n-1}+1\) queries would be necessary to determine if \(f\) is constant or balanced. In the quantum case, the Deutsch-Jozsa algorithm, originally presented in \cite{jozsa}, is able to determine with certainty whether or not \(f\) is constant or balanced by making only a single query.

The Deutsch-Jozsa Problem

Input: A black-box that computes an unknown function \(f:\{0,1\}^n\rightarrow \{0,1\}\) which is guaranteed to be either constant or balanced.

Problem:  Determine wether or not the function is constant or balanced by making queries to the black-box.


Define a black-box encoding a function \(f:\{0,1\}^n\rightarrow \{0,1\}\) as the following controlled gate that acts on a \(n\) qubit control register and single qubit target register

\[\begin{array}{r l}
c-U_f: &\mathcal{H}^{2^n}\otimes\mathcal{H}^2\rightarrow \mathcal{H}^{2^n}\otimes \mathcal{H}^2, \\
& \left|\mathbf{x}\right>\left|y\right>\mapsto \left|\mathbf{x}\right>\left|y\oplus f(\mathbf{x})\right>.
\end{array}\]
Consider the circuit displayed in the figure below which takes as input the state \(\left|\psi_0\right>=\left|\mathbf{0}\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}} \big)\), where the first register represents the \(n\) qubit control and the second register represents the single qubit target. Notice that the overall action of this circuit is a generalization of the circuit for the Deutsch algorithm, where now the control register consists of \(n\) qubits instead of just one.

 

(A circuit solving the Deutsch-Jozsa problem by making a single query to the black-box \(c-U_f\). Applying Hadamard gates to the first \(n\) qubitis in the control register of the state 

\[\left|\psi_0\right>=\left|\mathbf{0}\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\] yields the state \(\left|\psi_2\right>\) which is in some superposition of  eigenstates of the \(c-U_f\) gate. Applying the second set of Hadamard gates ensures that state \[\left|\psi_4\right>=\left|\mathbf{0}\right>\] will only be observed upon measurement of the control register of \(\left|\psi_3\right>\) if the function \(f\) is constant. Otherwise some basis state \(\left|\psi_4\right>
\neq\left|\mathbf{0}\right>\) will be observed after measurement if the function \(f\) is balanced.)


After the Hadamard gate is applied to each qubit in the control the state becomes

\[\left|\psi_1\right>=(H^{\otimes n}\otimes I)\left|\psi_0\right>=H^{\otimes n}\left|\mathbf{0}\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)= \big(\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).\]
Then applying the \(c-U_f\) gate to \(\left|\psi_1\right>\) gives

\[\left|\psi_2\right>=(c-U_f)\left|\psi_1\right>= \big(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}\left|\mathbf{x}\right>\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),\]
and after the second set of Hadamard gates is applied to the control register the state becomes
\[\begin{array}{r l}
\left|\psi_3\right>=(H^{\otimes n}\otimes I)\left|\psi_2\right> &= \big(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}\big(\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>\big)\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
&= \big(\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}\big(
\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})+\mathbf{x}\cdot\mathbf{z}}\big)\left|\mathbf{z}\right>
\big)(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)
\end{array}.\]

Let \(\left|\psi_4\right>\) represent the state of the control register after a measurement is performed on the control register of \(\left|\psi_3\right>\). In order analyze what state will be observed when the control register of \(\left|\psi_3\right>\) is measured, consider the amplitude \(\alpha_0\)  of the state \(\left|\mathbf{z}\right>=\left|\mathbf{0}\right>\) in the control register of \(\left|\psi_3\right>\):
\[\alpha_0= \displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})+\mathbf{x}\cdot\mathbf{0}}=\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}.\]
Suppose the function \(f\) is constant. Then there are two cases with either \(f(\mathbf{x})=0\) for all \(\mathbf{x}\in\{0,1\}^n\) or \(f(\mathbf{x})=1\) for all \(\mathbf{x}\in\{0,1\}^n\), but either way

\[\alpha_0=\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}=\displaystyle\frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\pm 1=\displaystyle\frac{\pm2^n}{2^n}=\pm 1.\]
Therefore the state of the control register after the measurement will be in the state \(\left|\psi_4\right>=\left|\mathbf{0}\right>\) with certainty, implying that the function \(f\) is constant.

On the other hand suppose instead that the function \(f\) is balanced so that \(f(\mathbf{x})=0\) for exactly half of the states \(\left|\mathbf{x}\right>\) for \(\mathbf{x}\in\{0,1\}^n\) and \(f(\mathbf{x})=1\) for the remaining half. It then follows that
\[\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}=0,\]
since exactly half of the contributing terms in the sum will be \(1\) while the other half will be \(-1\) so that the total sums to \(0\). Now recall the amplitude \(\alpha_0\) of the state \(\left|\mathbf{z}\right>=\left|0\right>\) in the control register of \(\left|\psi_3\right>\) in this case:
\[\alpha_0=\displaystyle \frac{1}{2^n}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}(-1)^{f(\mathbf{x})}=0\].
This implies that there is zero probability in observing the state \(\left|0\right>\) when a measurement is performed on the control register of \(\left|\psi_3\right>\). Instead, some computational basis state \( \left|\psi_4\right>=\left|\mathbf{z}\right>\) with \(\mathbf{z}\in\{0,1\}^n\) such that \(\mathbf{z}\neq\mathbf{0}\) will be observed with nonzero probability.

The Deutsch-Jozsa algorithm shows that its possible to determine in a single query whether or not some function \(f:\{0,1\}^n\rightarrow \{0,1\}\) is constant or balanced provided that the function \(f\) is guaranteed to have one of these two properties. It was previously argued that the deterministic classical algorithm for solving the related problem must make at least \(2^{n-1}+1\) queries in the worst case to establish with certainty wether or not the function \(f\) is constant or balanced. Hence, the Deutsch-Jozsa algorithm gives an exponential speed up in the query complexity of the problem when compared to its deterministic classical analog.

However, it is worth mentioning that a probabilistic classical algorithm can actually solve the problem making only \(2\) queries to some black-box  if allowed to error with a probability at most \(p= \frac{1}{3}\). To decrease this probability of error to \(p<\frac{1}{2^n}\) only \(n+1\) queries need to be made. Therefore, when comparing the query complexity of the problem in the quantum case to the probabilistic classical case, the Deutsch-Jozsa algorithm only solves the problem by making one less query if the classical algorithm is allowed a constant probability of error, but the classical algorithm must make \(O(n)\) queries if exponentially small error probabilities are desired.

The Deutsch Problem and Algorithm

Let \(f: \{0,1\}\rightarrow \{0,1\}\) be some function encoded in a black-box which takes as input some \(x\in\{0,1\}\) and returns the value \(f(x)\in\{0,1\}\). There are only \(4\) different functions that can be defined in this case:
\[\begin{array}{r l l}
f_{00}:& 0 \mapsto 0,& 1\mapsto 0, \\
f_{11}:& 0 \mapsto 1,& 1\mapsto 1, \\
f_{01}:& 0 \mapsto 0,& 1\mapsto 1, \\
f_{10}:& 0 \mapsto 1,& 1\mapsto 0 .\end{array}\]
Notice that two of these functions, \(f_{00}\) and \(f_{11}\) are constant, where \(f(x)=c\) for some fixed \(c\in\{0,1\}\). The other two functions, \(f_{01}\) and \(f_{10}\), are balanced since \(f(x)=0\) for half of the possible inputs \(x\) and \(f(y)=1\) for the other half of remaining inputs \(y\).

The Deutsch problem, originally formulated and solved in \cite{deutsch}, and is the problem of determining whether or not some unknown function \(f: \{0,1\}\rightarrow \{0,1\}\) is constant or balanced by making queries to the function \(f\). Observe that the property of being constant or balanced can be determined by simply evaluating the sum \(f(0)\oplus f(1)\), since \(f(0)\oplus f(1)=0\) if and only if \(f\) is constant and \(f(0)\oplus f(1)=1\) if and only if \(f\) is balanced.



The Deutsch Problem

Input: A black-box that computes an unknown function \(f:\{0,1\}\rightarrow \{0,1\}\)

Problem: Determine whether or not the function is constant or balanced, or equivalently the value of \(f(0)\oplus f(1)\), by making queries to the black-box.


Trivially, making two queries to the black-box for the values of \(f(0)\) and \(f(1)\) is enough to completely determine the function $f$. The question then becomes whether or not the Deutsch problem can be solved by making only a single query. Classically, only a single query will never be enough to completely determine whether or not the function in constant or balanced, because provided with only a single value of say $f(0)$ the function may still be any two of the four possible functions described above. One of these possibilities is a constant function and the other is a balanced function so the Deutsch problem remains undetermined with only a single query in the classical case. The quantum algorithm described below shows that its possible to solve the Deutsch problem by making only a single query.

To represent the quantum black-box that encodes some unknown function \(f:\{0,1\}\rightarrow \{0,1\}\), define the following controlled gate acting on two qubits
\[\begin{array}{r l}
c-U_f: &\mathcal{H}^2\otimes\mathcal{H}^2\rightarrow \mathcal{H}^2\otimes \mathcal{H}^2, \\
& \left|x\right>\left|y\right>\mapsto \left|x\right>\left|y\oplus f(x)\right>.
\end{array}\]
Observe what happens when \(c-U_f\) acts on the state \(\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\) in the two cases where \(\left|x\right>=\left|0\right>\) or \(\left|x\right>\left|1\right>\):
\[\begin{array}{r l}
c-U_f\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) & =c-U_f\big(\displaystyle\frac{\left|x\right>\left|0\right>}{\sqrt{2}}\big)-c-U_f\big(\displaystyle\frac{\left|x\right>\left|1\right>}{\sqrt{2}}\big) \\
& = \big(\displaystyle\frac{\left|x\right>\left|0\oplus f(x)\right>}{\sqrt{2}}\big)-\big(\displaystyle\frac{\left|x\right>\left|1\oplus f(x)\right>}{\sqrt{2}}\big) \\
 & = (-1)^{f(x)}\left|x\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).
\end{array}\]
This we can consider the control register as picking up the phase factor \((-1)^{f(x)}\) which depends on the value of \(f(x)\). Now consider the circuit shown in the figure below.


(A circuit solving the Deutsch problem by making a single query to the black-box \(c-U_f\). Applying a Hadamard gate to the first qubit in the state \[\left|\psi_0\right>=\left|0\right>\big(\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\] yields the state \(\left|\psi_1\right>\) which is an equally weighted superposition of two eigenstates of the \(c-U_f\) gate. After one query is made with \(c-U_f\) the first qubit in the state  \(\left|\psi_2\right>\) has a relative phase factor that gets encoded into the state \(\left|\psi_3\right>\) after the Hadamard gate. The state then yields  \(\left|\psi_4\right>=\left|f(0)\oplus f(1)\right>\) when measured  which determins wether \(f\) is constant or balanced.)

The initial state of the input is \(\left|\psi_0\right>=\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\) and after the Hadamard gate is applied to the first qubit it is put into an equally weighted superposition
\[\left|\psi_1\right>=(H\otimes I)\left|\psi_0\right>=H\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)=\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).\]
Then after making one query to the black-box by applying the $c-U_f$ gate to$ \left|\psi_1\right>$ gives
\[\begin{array}{r l}
\left|\psi_2\right>=c-U_f\left|\psi_1\right> &=c-U_f\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
&= c-U_f\big(\displaystyle\frac{\left|0\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) +c-U_f\big(\displaystyle\frac{\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
  & = (-1)^{f(0)}\displaystyle\frac{\left|0\right>}{\sqrt{2}}\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)+(-1)^{f(1)}\displaystyle\frac{\left|1\right>}{\sqrt{2}}\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
  & = \big(\displaystyle\frac{(-1)^{f(0)}\left|0\right>+(-1)^{f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
    & = (-1)^{f(0)}\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),
 
\end{array}\]
where the factor \((-1)^{f(0)}\) has been factored out using \((-1)^{f(0)}(-1)^{f(1)}=(-1)^{f(0)\oplus f(1)}\).  The first qubit in \(\left|\psi_2\right>\) now has a relative phase factor of \((-1)^{f(0)\oplus f(1)}\), which contains the value of \(f(0)\oplus f(1)\). Applying a second Hadamard gate to the first qubit effectively decodes the value of \(f(0)\oplus f(1)\) after measurement. To see this, consider the state of the first qubit in  \(\left|\psi_3\right>$\)after the Hadamard gate is applied in the two cases where \(f(0)\oplus f(1)=0\) and \(f(0)\oplus f(1)=1\):

If \(f(0)\oplus f(1)=0\):
\[\begin{array}{r l}
\left|\psi_3\right> & = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\left|0\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big),

\end{array}\]

If \(f(0)\oplus f(1)=1\):
\[\begin{array}{r l}

\left|\psi_3\right> & = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>+(-1)^{f(0)\oplus f(1)}\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}H\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big)\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big) \\
& = (-1)^{f(0)}\left|1\right>\big(\displaystyle\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\big).

\end{array}\]
Note that the first qubit is in the state \(\left|0\right>\) if \(f(0)\oplus f(1)=0\) and is in the state \(\left|1\right>\) if \(f(0)\oplus f(1)=1\). Therefore, measuring the first qubit will return the state \(\left|\psi_4\right>=\left|0\right>\) with certainty if \(f\) is constant, and will instead return the state  \(\left|\psi_4\right>=\left|1\right>\) with certainty if \(f\) is balanced.

The circuit constructed solves the Deutsch problem by making only one query to the black-box, whereas \(2\) queries were necessary in the classical query complexity. Despite being a somewhat contrived example, this is the first example presented in the black-box model that exploits the phase kick-back technique where a quantum algorithm can solve the problem by making fewer queries than needed in the classical case.