The Deutsch-Jozsa Algorithm Explained

When learning quantum computing algorithms from a textbook, there is usually a progression from the earliest, simplest algorithms to the later, more complex algorithms. Among the first of these textbook algorithms to be presented is often the Deutsch-Jozsa algorithm, whose small size and seeming simplicity belie its importance.

What is the Deutsch-Jozsa algorithm?

Using the Deutsch-Jozsa approach, it is possible to determine if a given Boolean function is constant or balanced. Consider a function that takes input values of 0 and 1, and outputs values of 0 or 1. The function is considered constant only if all outputs are 0 or all outputs are 1. When exactly half of the inputs are zeroes and exactly half of the inputs are ones, we refer to the function as balanced.

How does the Deutsch-Jozsa work?

There are a few different implementations for the Deutsch-Jozsa algorithm, but they all share the same 5-step process. In the first step, quantum registers and input states are prepared. In the second step, the qubits are organized into the Hadamard Basis. This means that each qubit has a 50% chance of being 0 and a 50% chance of being 1. The third step is the oracle, which encodes the function that determines whether the outputs are constant or balanced via quantum entanglement. The fourth step returns the qubits to the measurement basis in order to find the answer. In the last step, the qubits are measured to obtain the solution.

The various implementation approaches vary little between the first and third steps, the main difference being the implementation of the oracle. One of the most common implementations for the oracle uses a CX gate to initialize a second quantum register with a single ancilla qubit, also referred to as a "work qubit." Normal initialization for qubits is 0; however, the ancilla qubit in this case is set to 1. The oracle then uses a process called phase kickback to assess whether the function is constant or balanced. If the function is balanced, phase kickback will add a negative phase to half of the quantum states.

How does the Deutsch-Jozsa algorithm compare?

The Deutsch-Jozsa algorithm determines if the Boolean function is constant or balanced. For today's error-prone quantum computers, this circuit must be run several times to determine whether the function is likely constant or likely balanced. However, future quantum computers will be able to make this judgment with 100% accuracy on the first attempt.

In contrast, the corresponding classical technique requires a minimum of two attempts. It requires a number of attempts equal to 1+N, where N is the number of inputs. A minimum of two attempts is required to see a zero and a one and, thus, determining if the function is balanced. For a larger number of inputs, if half of the inputs are zeros, for instance, there is still a chance that the other half are all ones, and the function might still be balanced. However, if half plus one of the inputs are zeroes - and a balanced function must contain exactly half zeros and half ones - then it can be determined that the function is constant.

The distinction between quantum and conventional techniques may look inconsequential due to the fact that textbook examples always demonstrate extremely minor issues. Imagine, however, a problem with one million inputs. The ideal classical approach would need to examine 500,001 inputs in the worst-case scenario. In contrast, the Deutsch-Jozsa algorithm would simultaneously examine all inputs and produce an accurate answer after a single attempt.

Why is the Deutsch-Jozsa algorithm important?

The Deutsch-Jozsa algorithm, which was discovered three decades ago in 1992, is significant for three reasons. In the first place, it was the first quantum algorithm to show a separation between the quantum and classical difficulty of a problem. While it was not the first quantum algorithm to promise a potential speedup, it was the first to demonstrate a scenario where a quantum computer is capable of outperforming a classical one. Second, the Deutsch-Jozsa method highlights the utility of employing negative amplitudes, which classical computing cannot achieve. Thirdly, the algorithm was a stepping stone for the development of much more significant quantum algorithms.

Regarding this final aspect, the Deutsch-Jozsa algorithm was significant in the history and development of quantum algorithms. It followed the discovery of Deutsch's problem and led to the discovery of later algorithms such as the Bernstein-Vazirani algorithm. The 1985 Deutsch problem is extremely similar to the Deutsch-Jozsa algorithm, with the exception that it is confined to functions with only a single input bit. David Deutsch, the discoverer of Deutsch's problem, later collaborated with Richard Jozsa to jointly develop the Deutsch-Jozsa algorithm, which expanded the algorithm to include functions with multiple input bits. Although this is a concise explanation of the Deutsch-Jozsa algorithm, at the time of their discovery it demonstrated the potential for quantum computers to tackle certain problems more quickly than classical computers. Unfortunately, it had no practical applications.

Is the Deutsch-Jozsa algorithm practical?

The Deutsch-Jozsa algorithm has no known application in the real world, but this was never its original purpose. The algorithm was designed to be simple for quantum computers to solve but difficult for classical computers. Nonetheless, it illustrates that there are issues that quantum computers may be able to address more effectively than their conventional equivalents. The eventual discovery of Grover's algorithm led to the understanding that realistic application speedups are indeed attainable. However, Grover's algorithm also led to the revelation that building quantum oracles for more than a handful of qubits is extremely difficult.

With the use of cutting-edge software development tools for quantum computing, such as the Classiq Platform, this offspring of the Deutsch-Jozsa algorithm is made user-friendly through circuit automation. The Classiq Platform is a quantum software design automation platform that can automatically synthesize quantum circuits from high-level user inputs. To use the Classiq Platform to create an oracle, you simply specify the expression you want the oracle to explore, and our circuit synthesis engine will generate the oracle automatically. Creating a quantum oracle was formerly a difficult process, but is today a piece of cake with Classiq.

To learn more about Classiq and our quantum circuit design automation platform, visit: www.classiq.io