Distributed quantum algorithm for Simon's problem

Limited by today's physical devices, quantum circuits with a long depth are usually noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we study Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The algorithm proposed by us has the advantage of exponential acceleration compared with classical distributed computing and has the advantage of square acceleration compared with the best distributed quantum algorithm proposed before in query complexity. In particular, the previous distributed quantum algorithm for Simon's problem cannot be extended to the case of more than two computing nodes (i.e., two subproblems), but our distributed quantum algorithm can be extended to the case of multiple computing nodes (i.e., multiple subproblems).

Figure 1

The circuit for the quantum part of the distributed quantum algorithm for finding $s_1$: two computing nodes.

Figure 2

The circuit for the quantum part of the distributed quantum algorithm for finding $s_1$: four computing nodes.

Figure 3

The circuit for the quantum part of the distributed quantum algorithm for finding $s_1$: eight computing nodes.

Figure 4

The circuit for the quantum part of the distributed quantum algorithm for finding $s_1$: $2^t$ computing nodes.