Deutsch-Jozsa Problem and Quantum Parallelism

1. The Deutsch-Jozsa Problem: A Promise-Based Challenge

Imagine you are given a "black box," or oracle, that computes a function $f$. This function takes an $n$-bit binary string as input and produces a single bit (0 or 1) as output. So, $f:\{0,1{\}}^n\to \{0,1\}$.

You don't know the inner workings of the function, but you have a promise: the function is guaranteed to be either constant or balanced.

• A constant function always returns the same value, either 0 for all inputs or 1 for all inputs.
• A balanced function returns 0 for exactly half of its possible inputs and 1 for the other half.

The Deutsch-Jozsa Problem: Your task is to determine whether the function in the oracle is constant or balanced, using the minimum number of queries to the oracle.

The Classical Approach

How would you solve this with a classical computer? You would have to query the oracle with different input strings.

• Best case: You get lucky. Your first query is, say, f(00...0) = 0, and your second is f(11...1) = 1. You've seen two different outputs, so you know instantly the function must be balanced. This took two queries.
• Worst case: You query the function and keep getting the same output. For an n-bit input, there are $2^n$ possible input strings. If you've checked half of them ($2^{n-1}$ queries) and they all produced, say, 0, you still can't be 100% certain. It's possible you've just happened to pick all the inputs that give 0 for a balanced function. To be absolutely sure the function is constant, you need to check one more input, for a total of $2^{n-1}+1$ queries.

For even a moderate number of bits, like $n=50$, this number is astronomically large. The following video provides a clear explanation of this problem and the limitations of the classical strategy.

As you can see, the classical approach is inefficient. This is where quantum computing offers a dramatic speedup.

2. The Quantum Solution: Harnessing Parallelism and Interference

A quantum computer can solve this problem with just one single query, regardless of the size of $n$. This provides an exponential speedup over the classical method. This is achieved by combining two fundamental quantum principles: quantum parallelism and quantum interference.

Quantum Parallelism: Doing Many Things at Once

Thanks to superposition, we can prepare an input register of $n$ qubits to be in an equal superposition of all $2^n$ possible classical states. By feeding this superposition into the quantum oracle, we can compute the function value $f(x)$ for all $2^n$ values of $x$ simultaneously. This powerful capability is known as quantum parallelism.

However, quantum parallelism on its own is not a magic bullet. The problem arises when we try to get the information out. If we were to measure the state right after the oracle, the superposition would collapse to a single random result, $|x,f(x)⟩$, destroying all the other computations.

The following reading from IBM's Qiskit documentation explains this limitation very clearly.

So, if we can't just "read out" all the results, how does the algorithm work? The answer lies in orchestrating interference to reveal a global property of the function.

The Secret Sauce: Phase Kickback and Interference

Instead of trying to learn individual values of $f(x)$, the Deutsch-Jozsa algorithm uses a clever trick called phase kickback. The oracle is set up in such a way that it doesn't write the output to the ancilla qubit. Instead, it "kicks back" a phase of $(-1{)}^{f(x)}$ to the corresponding state $|x⟩$ in the input register's superposition.

• If $f(x)=0$, the phase is $(-1{)}^0=+1$ (no change).
• If $f(x)=1$, the phase is $(-1{)}^1=-1$ (a phase flip).

After the oracle applies these phases, a final set of Hadamard gates is applied to the input register. This step causes all the states in the superposition to interfere with each other.

The outcome of this interference depends entirely on the phases applied by the oracle:

1. If the function is constant: All $f(x)$ values are the same. This means every state $|x⟩$ in the superposition receives the exact same phase (either all +1 or all -1). The final interference is perfectly constructive, and the input register is transformed back to the all-zeroes state, $|00...0⟩$.
2. If the function is balanced: Half of the states get a +1 phase, and the other half get a -1 phase. This leads to destructive interference for the all-zeroes state $|00...0⟩$. The probability of measuring all zeroes becomes zero.

Therefore, by measuring the input register just once:

• If the result is 00...0, the function is constant.
• If the result is any other bitstring, the function is balanced.

The following video from the Qiskit team provides an excellent, intuitive explanation of this process, starting with the simpler 1-qubit case (Deutsch's Algorithm) and building up to the full Deutsch-Jozsa algorithm.

Conclusion

In this lesson, we have dissected one of the first and most illustrative quantum algorithms. You've seen how it cleverly sidesteps the limitations of classical computation to achieve an exponential speedup on a specific problem.

Key Takeaways:

• The Deutsch-Jozsa problem is to determine if a promised function is constant or balanced.
• Classically, solving this problem requires up to $2^{n-1}+1$ queries in the worst case.
• The quantum solution uses quantum parallelism to evaluate the function for all possible inputs in a single step by preparing the input qubits in a full superposition.
• The key to the algorithm is phase kickback, which encodes the function's outputs into the phases of the superposition, and interference, which makes this global property measurable.
• The Deutsch-Jozsa algorithm can determine if the function is constant or balanced with 100% certainty in a single query.

This algorithm, while not solving a practically useful problem on its own, was a crucial proof of principle. It demonstrated for the first time that quantum computers could solve certain problems fundamentally faster than classical ones and laid the groundwork for more powerful algorithms to come.

Preview of the Next Lesson:
Now that you have a solid conceptual understanding of how the Deutsch-Jozsa algorithm works, our next step will be to bring it to life. In the next lesson, you will implement the Deutsch-Jozsa algorithm in Qiskit for a given oracle, putting the theory you learned today into practice.