Effect of quantum decoherence on the Deutsch-Jozsa algorithm / Luis Gabriel Q. del Rosario, Henry N. Adorna.

Quantum computers have the potential to solve certain problems exponentially faster than classical computers, with one of the most simple examples being Deutsch and Jozsa’s black box algorithm for determining whether a function f : {0, 1}n → {0, 1} is constant or balanced. However, one major roadblock in the realization of the quantum computer is decoherence, or the loss of quantum information through coupling with the environment. Several methods have been proposed for incorporating decoherence in the study of quantum algorithms, one of which was introduced by Chuang et. al. and redefined by Brian De Jesus in 2014. This method, which had the characteristic of being easily applicable to different quantum algorithms, was used to find that the decoherence of
the Deutsch-Jozsa algorithm is bounded by 𝛼 < L/3L−1 , which for large L, shows it is more tolerant than Shor’s factoring algorithm and Grover’s unstructured search algorithm. Moreover, it was found that even if the algorithm were to return the wrong answer 50% of the time, it would still be more efficient than its classical counterpart.