2.5 KiB
Deutsch’s algorithm is the first algorithm exploring quantum parallelism. It uses two qubits (only one in the economical version) and has a very modest gain, but it has inspired the construction of several new quantum algorithms that are more efficient than their classical counterpart.
Regardless of f, the quantum computer does not go through an entangled state during the execution of Deutsch’s algorithm because each state |ψii for i from 1 to 3 is a tensor product of 1-qubit pure states. The qubits are unentangled all the time. This means that Deutsch’s algorithm is faster than classical algorithms making use of quantum parallelism only.
This is a rule of the game. Deutsch’s algorithm applies Uf only once and the classical algorithm needs to evaluate f two times. Then, Deutsch’s is faster.
Note that the analysis of Deutsch’s algorithm shows that f is evaluated at two distinct points in the domain simultaneously. This is not possible to be carried out using a sequential classical algorithm. However, it is possible to be carried out in a classical computer with parallel processors if the number of simultaneous threads does not scale up. Since Deutsch’s algorithm uses a fixed number of qubits, we cannot scale it up and it is not possible to perform an asymptotic analysis. In terms of time complexity, the quantum version has no gain. The importance of Deutsch’s algorithm lies in the fact that it stimulated the search for generalizations, such as the Deutsch-Jozsa, Bernstein-Vazirani, and Simon algorithms, which inspired Shor in the elab- oration of a quantum algorithm for factoring composite integers and a quantum algorithm for calculating discrete logarithms.
Last but not least, we remark that it is not up to us to implement the oracle. It is someone else’s job. Without this understanding, we face a contradiction—we have to know the answer before even starting to implement the algorithm that will find the answer. It is allowed to query function f implemented by someone without looking at its implementation details. We are given what is called a black box quantum computer with Uf already implemented, which we can use,add new gates, but cannot see inside. To add new gates is allowed by the rules of the game for oracle-based algorithms.
Deutsch-Jozsa Algorithm (came afterwards)
The Deutsch-Jozsa algorithm is a deterministic quantum algorithm, a generalization of Deutsch’s algorithm, and the first example that is exponentially faster than its equivalent classical deter- ministic algorithm.