Fault-Tolerant Implementation of the Deutsch-Jozsa Algorithm

The Deutch-Josza algorithm is one of the first and simplest quantum algorithms. Like many other quantum algorithms that provide a speedup via a reduction in oracle queries, implementation of the Deutch-Josza algorithm requires only Clifford gates and is therefore a natural candidate for small fault-tolerance experiments using currently-available quantum computers. We show that one can implement the Deutch-Josza algorithm in a fault-tolerant manner, by encoding in the $[[4,2,2]]$ quantum error-detecting code. We implemented the algorithm on a ion-trap based quantum computer with and without fault-tolerant encoding. We compared resulting error-rates, and we found that the fault-tolerant implementation of the Deutch-Josza algorithm provides a noise reduction compared with the non-fault-tolerant implementation, with approximately $99 \%$ confidence, for all oracles.