Quantum advantage and noise reduction in distributed quantum computing
J. E. Avron, Ofer Casper, Ilan Rozen · Physical Review A · 2021
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({n}^{2})$, where $n={log}_{2}(N)$. The distributed Deutsch-Jozsa algorithm deteriorates to being probabilistic but retains a quantum advantage over classical random sampling.