Eigenvalue Estimation

This section will combine the technique deployed in the phase kick-back algorithms, and the method of phase estimation to solve a problem of a similar nature. Here, the objective will be to determine the eigenvalue of the form \(e^{i2\pi\omega}\) of a eigenvector \(\left|\phi\right>\) associated to a particular unitary operator \(U\). In the eigenvalue estimation problem, the details of the unitary operator \(U\) and eigenvector \(\left|\phi\right>\) are unknown and not of main concern. It is assumed that such a state is already provided as well as the means to operate on the state with a circuit that implements \(U\).

Eigenvalue Estimation Problem

Input: A quantum circuit implementing a unitary operator \(U\) with an eigenvector \(\left|\phi\right>\) and associated eigenvalue \(e^{i2\pi\omega}\).

Problem: Determine an estimate for the unknown parameter \(\omega\) which determines the eigenvalue.


 Since \(\left|\phi\right>\) is an eigenvector of \(U\) with eigenvalue \(e^{i2\pi\omega}\), then by definition \(U\left|\phi\right>=e^{i2\pi\omega}\left|\phi\right>\). Define a controlled\(-U\) operation, \(c-U\) where a single qubit is used as the control register.  Then if the target register is prepared in the state \(\left|\phi\right>\), the action of \(c-U\) is given by
\[\begin{array}{r l}
c-U\left|0\right>\left|\phi\right>=&\left|0\right>\left|\phi\right>, \\

c-U\left|1\right>\left|\phi\right>=&e^{i2\pi\omega}\left|1\right>\left|\phi\right>.
\end{array}.\]
Thus, the phase factor \(e^{i2\pi\omega}\) can be associating to the control qubit as in the phase kick-back algorithms. Now, denote the action of applying \(c-U\) \(m\) times as \(c-U^m\), and observe that \(c-U^m\) acts as follows
\[\begin{array}{r l}
c-U^m\left|0\right>\left|\phi\right>=&\left|0\right>\left|\phi\right>, \\

c-U^m\left|1\right>\left|\phi\right>=&e^{i2\pi\omega m}\left|1\right>\left|\phi\right>.
\end{array}.\]
This follows straight from the definition \(\left|\psi\right>\) being an eigenvector of \(U\) with eigenvalue \(e^{i2\pi\omega}\), and since a product of exponentials is equivalent to a single exponential whose argument is the sum of the arguments of the exponentials.

The ability to perform the action of \(c-U^m\) for various values of \(m\) is helpful in solving the eigenvalue estimation problem, because this will allow the value of \(\omega\) to be encoded into the relative phases of states. If the state
\[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right>,\]
can be prepared, then as done in the phase estimation algorithms the value of \(\omega\) can be estimated by applying the \(QFT^{-1}\) to the state \(\left|\psi\right>\). However, since the value of \(\omega\) is unknown this state cannot be prepared directly. Fortunately, the ability to perform \(c-U^m\) operations on the state \(\left|\phi\right>\), which is given, can be used to construct the state \(\left|\psi\right>\). Therefore, once this state \(\left|\psi\right>\) has been constructed and the phase estimation algorithm is performed by making use of \(QFT^{-1}\), information about \(\omega\) will be obtained enabling an estimate of the eigenvalue.

A circuit can be constructed using \(c-U^m\) gates that takes some basis state, say \(\left|\mathbf{0}\right>\in\mathcal{H}^{2^n}\), and produces the state
\[\begin{array}{r l}
\left|\psi\right>=&\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{j=0}^{2^n-1}e^{i2\pi \omega j}\left|j\right> \\
= &\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{n-1}}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{n-2}}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi \omega2^{0}}\left|1\right>}{\sqrt{2}}\right) \\
=&\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>.
\end{array}.\]
To accomplish this, first observe the action of \(c-U^m\) on a qubit in an equally weighted superposition in the control register, and the eigenstate \(\left|\phi\right>\) in the target register
\[c-U^m\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left(\displaystyle\frac{\left|0\right>+e^{i2\pi\omega m}\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>.\]
Then by setting \(m=2^n-k\) for integers \(1\leq n\leq n\), it follows that
\[c-U^{2^{n-k}}\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left(\displaystyle\frac{\left|0\right>+e^{i2\pi\omega 2^{n-k}}\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>=\left|\psi_k\right>,\]
which is the state of the \(k^{th}\) qubit in the register of the state \(\left|\psi\right>\).

Therefore, first take a control register in the basis state \(\left|\mathbf{0}\right>\in\mathcal{H}^{2^n}\) and apply the Hadamard gate to each qubit putting putting the register in an equally weighted superposition
\[H^{\otimes n}\left|\mathbf{0}\right>=\displaystyle\bigotimes\limits_{k=1}^{n}\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right).\] Then by applying a \(c-U^{2^{n-k}}\) multiple times, for \(1\leq k\leq n\), each time controlled by the \(k^{th}\) qubit in the control register the state \(\left|\psi\right>\) is produced:
\[\displaystyle\bigotimes\limits_{k=1}^{n}\left[\left(\displaystyle\frac{\left|0\right>+\left|1\right>}{\sqrt{2}}\right)\left|\phi\right>\right]=\displaystyle\bigotimes\limits_{k=1}^{n}\left|\psi_k\right>\left|\phi\right>=\left|\psi\right>.\]


(The circuit on the left implements the series of \(c-U^{2^{n-k}}\) gates controlled by the \(n\) qubits in the control register, where each is in the superposition \( \frac{1}{\sqrt{2}}\left(\left|0\right>+\left|1\right>\right)\) and the target register in the eigenstate \(\left|\phi\right>\), producing the state \(\left|\psi\right>\) as output in the control register. The controlled gate labelled by \(U^x\) in the circuit shown below is the shorthand symbol that represents the circuit above.)




Before giving a complete construction of a circuit that solves the eigenvalue estimation problem, consider the circuit shown that represents just the sequence of \(c-U^m\) gates acting on the states described above. As a notational convenience, this entire circuit will be represented in shorthand by the controlled\(-U^x\) gate also shown above. Then the output \(\left|\psi\right>\) provided in the control register after the controlled\(-U^x\) is applied to \(H^{\otimes n}\left|\mathbf{0}\right>\left|\phi\right>\) can be used as the input to the phase estimation algorithm. This is done by applying \(QFT^{-1}\) to the control register, which produces some state \(\left|x\right>\) such that \(x/2^m=\tilde{\omega}\) is an estimate of the phase parameter  \(\omega\) in the state \(\left|\psi\right>\). This estimate can then be used to determine an estimate \(e^{i2\pi\tilde{\omega}}\) of the eigenvalue. The circuit solving the eigenvalue estimation problem is shown in the figure below. Notice that the first gate is given by a \(QFT\) acting on the control register, since this gate's action is equivalent to the action of \(H^{\otimes n}\) on a control register where every qubit is in the state \(\left|0\right>\). By doing this, a certain symmetry in the circuit and algorithm is highlighted that is similar to many of the previously introduced algorithms. In this case, it is seen that the \(QFT\) plays an analogous role of the Hadamard gate \(H^{\otimes n}\) in its use to encode and decode information after some controlled gate is applied.

(A circuit for the eigenvalue estimation algorithm. The \(n\) qubit control register begins in the state \(\left|\mathbf{0}\right>\) and the target register in the eigenstate \(\left|\phi\right>\). First, the \(QFT\) is applied to the control register, followed by the controlled\(-U^x\) gate, and then the \(QFT^{-1}\) is applied to the control register. This produces some basis state \(\left|x\right>\) in the control register, which can then be used to estimate the eigenvalue through the phase parameter \(    \tilde{\omega}=x/2^n\).)

Since the \(QFT\) and \(QFT^{-1}\) can be implemented efficiently on a quantum computer, then provided with an eigenstate \(\left|\phi\right>\) and an efficient means to implement the controlled\(-U^x\), the eigenvalue estimation algorithm can solve the problem of estimating an eigenvalue efficiently.  The eigenvalue estimation problem is of a very general nature. After all, every unitary operator  acting on qubits has at least two eigenvalue/eigenvector pairs. Although this problem may still seem  of a somewhat contrived variety, the next section will reveal a remarkable application of the eigenvalue estimation algorithm to the problem of factoring integers efficiently.

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.

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.

Phase 'Kick-back' Algorithms

Consider some black-box that encodes some function \(f\) that is implemented as a controlled\(-U_f\)  gate acting on the state space \(\mathcal{H}_A\otimes\mathcal{H}_B\) consisting of two registers \(A\) and \(B\) of qubits. Generally, when a controlled\(-U_f\) gate is applied it is thought of as only affecting the target register \(B\) leaving the control register \(A\) unchanged. Therefore, the action of the \(c-U_f\) gate is of the form
\[c-U_f: \left|x\right>\left|\phi\right>\mapsto \left|x\right>\left|\phi'\right>,\]
For some state \(\left|\phi'\right>\in\mathcal{H}_B\). Suppose some state \(\left|\psi\right>\in\mathcal{H}_B\) is chosen to satisfy
\[c-U_f(\left|x\right>\left|\psi\right>)= v_x\left|x\right>\left|\psi\right>,\]
where  \(v_x\) is some complex number that could depends on \(x\). In this case, the state \(\left|x\right>\left|\psi\right>\) is called an eigenstate of the operator \(c-U_f\),  and \(v_x\) is called the eigenvalue of the eigenstate. Moreover, the state \(\left|\psi\right>\) may also satisfy
\[c-U_f(\left|y\right>\left|\psi\right>)= v_y\left|y\right>\left|\psi\right>,\]
for some other state \(\left|y\right>\in\mathcal{H}_B\) and eigenvalue \(v_y\).

 This situation is more interesting when the control register is in some superposition of states such as \(\alpha\left|x\right>+\beta\left|y\right>\in\mathcal{H}_A\). Then
\[\begin{array}{r l}
c-U_f\big((\alpha\left|x\right>+\beta\left|y\right>)\left|\psi\right>\big) & =c-U_f(\alpha\left|x\right>\left|\psi\right>)+c-U_f(\beta\left|y\right>\left|\psi\right>) \\
 &= v_x\alpha\left|x\right>\left|\psi\right>+v_y\beta\left|y\right>\left|\psi\right> \\
 &=\big(v_x\alpha\left|x\right>+v_y\beta\left|y\right>\big)\left|\psi\right>,
\end{array}\]
and depending on the eigenvalues the state in the control register may contain a relative phase factor between the states \(\left|x\right>\) and \(\left|y\right>\). In this context, by associating the eigenvalue to the state in the control register, the action of the controlled\(-U_f\) gate can effectively be thought of as changing the state in the control register instead of the target register. Then by performing a measurement on the states, the existence of this phase factor may contain relevant information about the function \(f\) encoded in the black box.
 
   This technique of preparing the input in an eigenstate of a controlled\(-U\) gate, and then associating the eigenvalue to the control register is referred to as phase kick-back. A whole class of quantum algorithms exploits this technique in order to learn some property of a function \(f\) encoded in a black-box with fewer queries than would be needed in the classical case.