Abstract
We show that one can implement the Deutsch-Josza algorithm, one of the first and simplest quantum algorithms, in a fault-tolerant manner using the smallest quantum error-detecting code -- the code -- without any ancillae. We implemented the algorithm on a trapped-ion quantum computer with and without fault-tolerant encoding and compared the results. With approximately confidence, we found that the fault-tolerant implementation provided a noise reduction for all oracles. Averaged across all oracles, the reduction in error rate was nearly .