The Deutsch-Josza algorithm with n=1

Analysis

The Deutsch-Jozsa algorithm was expounded in 1992 by D. Deutsch and R. JozsaDavid Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 439, pages 553-558. The Royal Society, 1992.. Though it is widely acknowledged that the algorithm fills no real use cases, it is nevertheless regarded as one of the earliest demonstrations that a quantum system can in principle compute at least a non-zero set of decision problems in a way that is more efficient than any conceivable classical method. In the terminology of complexity theory, we would say that it provides a separation between the class P and EQP. I won’t go into detail about EQP, but the point is that this is not as powerful as the separation we would like, between BPP and BQP, because there are probabilistic classical algorithms that can solve this problem efficiently. However, the quantum solution is deterministic, rather than probabilistic, so it is still a significant discovery.

Here we will describe the Deutsch-Jozsa problem, and think about the resource costs of both the quantum and classical methods of solving it. We will see that no classical method can match the proposed quantum solution, even in principle.

1. Statement of the problem

The Deutsch-Jozsa circuit is an example of an oracle, which essentially means that it answers a yes/no question. This question is generally posed as a choice between two alternatives regarding a function \(f:\{0,1\}^n\rightarrow\{0,1\}\) which is encoded by a black box \(U_f\). This notation means that \(f\) maps binary strings of length \(n\) onto binary strings of length 1. The function is promised to possess exactly one of the following properties:

  1. the function \(f\) is constant, meaning all \(f(x)\) are equal, or
  2. the function \(f\) is balanced, meaning \(f\) has value 0 for exactly half of the inputs \(x\), and \(f\) has value 1 for the other half if inputs \(x\).

Notice that we know we can look at exactly half of the inputs since there are \(2^n\) elements in \(\{0,1\}^n\), and \(2^n\) is even. The quantum function \(U_f\), which we don’t explicitly define but promise it exists, is defined by a quantum circuit of the type shown in Figure 1. We will initially consider the case where \(n=1\) for ease of explanation – we will only need to consider two cases corresponding to \(f(0)\) and \(f(1)\). It is immediately clear that the only way to answer this question using deterministic classical means is to evaluate the function for each of the two input values, and the only way to do that is with two calls to the function. We will show that we can exploit superposition to solve this problem using only one call to \(U_f\) using a quantum computer.


Figure 1: A circuit showing the action of the quantum circuit \(U_f\) for the Deutsch-Jozsa problem with \(n=1\).

2. For the case \(n=1\)

I claim that the circuit presented in Figure 2 computes the solution for the Deutsch-Jozsa problem for \(n=1\) with certainty. That is, it tells us whether the mystery function \(U_f\) is balanced or constant. Notice that initially the first qubit is in the state \(|0\rangle\) and the second qubit is in the state \(\frac{1}{\sqrt 2}(|0\rangle-|1\rangle)\). This choice of first qubit seems perfectly natural since it’s ’empty’, and we will see later that there is good reason for the choice of the second qubit state. Let’s consider each step of the circuit systematically.


Figure 2: This circuit computes the solution to the Deutsch-Jozsa problem for \(n=1\).

  1. The input state is $$|\psi_0\rangle =|0\rangle\otimes\frac{1}{\sqrt 2}(|0\rangle-|1\rangle).$$
  2. After the first Hadamard gate on the first qubit we have the state $$|\psi_1\rangle = \frac{1}{2}(|0\rangle+|1\rangle)\otimes(|0\rangle-|1\rangle)=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle).$$
  3. Next we apply our quantum Boolean function through \(U_f\), recalling that it has the action \(U_f:|a,b\rangle\mapsto|a,b\oplus f(a)\rangle\). Our state becomes $$|\psi_2\rangle = \frac{1}{2}(|0, f(0)\rangle-|0,1\oplus f(0)\rangle+|1,f(1)\rangle-|1,1\oplus f(1)\rangle).$$
  4. Applying the second Hadamard gate produces $$|\psi_3\rangle = \frac{1}{2}(|0,f(0)\rangle+|1,f(0)\rangle-|0,1\oplus f(0)\rangle – |1,1\oplus f(0)\rangle\\ +|0,f(1)\rangle-|1,f(1)\rangle-|0,1\oplus f(1)\rangle+|1,1\oplus f(1)\rangle).$$
  5. If \(f\) is constant, that is if \(f(0)=f(1)=a\), then we have the following state: $$|\psi_4\rangle = \frac{1}{\sqrt 2}(|0,1\oplus a\rangle-|0,a\rangle),$$
  6. while if \(f\) is balanced so \(f(0)\neq f(1)\), our state becomes $$|\psi_4’\rangle = \frac{1}{\sqrt 2}(1,f(0)\rangle-|1,f(1)\rangle).$$

We’re done. The striking thing to notice in steps 5 and 6 is that if \(f(0)=f(1)=a\), we are certain to measure \(|0\rangle\) for the first qubit, and if \(f(0)\neq f(1)\) then we are certain to measure \(|1\rangle\) for the first qubit. Thus we have solved in exactly one step what classically must take at least two. The advantage comes from the parallelism provided by quantum superposition, enabling us to effectively check both inputs at once. Superposition is a resource that no classical algorithm, no matter how clever, can hope to exploit.