Quantum advantage and noise reduction in distributed quantum computing

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

Automated summary

Distributed quantum computing can reduce noise and still exhibit quantum advantage in certain algorithms. However, some algorithms may have higher complexity in a distributed environment.