  Distributed quantum computing can give substantial noise reduction due to
shallower circuits. An experiment illustrates the advantages in the case of
Grover search. This motivates studying the quantum advantage of the distributed
version of the Simon and Deutsch-Jozsa algorithm. We show that the distributed
Simon algorithm retains the exponential advantage, but the complexity
deteriorates from O(n) to O(n^2), where n = log2(N). The distributed
Deutsch-Jozsa deteriorates to being probabilistic but retains a quantum
advantage over classical random sampling.
