Distributed Bernstein–Vazirani algorithm

Xu Zhou, Daowen Qiu and Le Luo

Physica A: Statistical Mechanics and its Applications, 2023, vol. 629, issue C

Abstract: 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.

Keywords: Distributed quantum computation; Noisy intermediate-scale quantum (NISQ) era; Distributed Bernstein–Vazirani algorithm (DBVA); MindQuantum; The depolarized channel (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437123007641
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:629:y:2023:i:c:s0378437123007641

DOI: 10.1016/j.physa.2023.129209

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().