Distributed Bernstein–Vazirani algorithm

Distributed quantum computation has been considered an alternative and beneficial application in the noisy intermediate-scale quantum (NISQ) era, which needs fewer qubits and quantum gates. In this paper, we consider the Bernstein–Vazirani (BV) problem that needs to identify the hidden string s∈{0,1}n of Boolean function fs(x)=〈s⋅x〉=∑i=0n−1si⋅ximod2:{0,1}n→{0,1}. In the first instance, we subtly generate t subfunctions fSnj(mj)=〈Snj⋅mj〉:{0,1}nj→{0,1} according to fs(x), where Snj∈{0,1}nj, ∑j=0t−1nj=n, and j∈{0,1,…,t−1}. After that, we propose a distributed Bernstein–Vazirani algorithm (DBVA) with 2≤t≤n computing nodes, which will exactly acquire s=Sn0Sn1⋯Snt−1∈{0,1}n. To be more specific, (1) the query complexity of DBVA is O(1) rather than O(n); (2) the circuit depth of DBVA is 2max(n0,n1,…,nt−1)+3 less than the circuit depth of the BV algorithm 2n+3; (3) we request neither auxiliary qubits nor further classical queries; (4) we explicate how DBVA decomposes a 6-qubit BV algorithm into two 3-qubit or three 2-qubit BV algorithms on MindQuantum (a quantum software), which validates the correctness and practicable of DBVA. Eventually, by simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithms have the superiority of resisting noise.