Distributed exact Grover’s algorithm

Xu Zhou, Daowen Qiu, Le Luo

PDF(14522 KB)
PDF(14522 KB)
Front. Phys. ›› 2023, Vol. 18 ›› Issue (5) : 51305. DOI: 10.1007/s11467-023-1327-x
RESEARCH ARTICLE
RESEARCH ARTICLE

Distributed exact Grover’s algorithm

Author information +
History +

Abstract

Distributed quantum computation has gained extensive attention. In this paper, we consider a search problem that includes only one target item in the unordered database. After that, we propose a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into n/ 2 parts. Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is 8(nmod 2)+ 9, which is less than the circuit depths of the original and modified Grover’s algorithms, 1+ 8 π4 2n and 9+ 8 π42n 12, respectively. It only depends on the parity of n, and it is not deepened as n increases; (iii) we provide particular situations of the DEGA on MindQuantum (a quantum software) to demonstrate the practicality and validity of our method. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

Graphical abstract

Keywords

distributed quantum computation / search problem / distributed exact Grover’s algorithm (DEGA) / MindQuantum / the depolarization channel noise

Cite this article

Download citation ▾
Xu Zhou, Daowen Qiu, Le Luo. Distributed exact Grover’s algorithm. Front. Phys., 2023, 18(5): 51305 https://doi.org/10.1007/s11467-023-1327-x

References

[1]
P. Benioff. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J. Stat. Phys., 1980, 22(5): 563
CrossRef ADS Google scholar
[2]
P. Benioff. Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys., 1982, 29(3): 515
CrossRef ADS Google scholar
[3]
D. Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 1985, 400(1818): 97
CrossRef ADS Google scholar
[4]
D. Deutsch, R. Jozsa. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A, 1992, 439(1907): 553
CrossRef ADS Google scholar
[5]
E.BernsteinU. Vazirani, Quantum complexity theory, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC’93), 1993, pp 11–20
[6]
D. R. Simon. On the power of quantum computation. SIAM J. Comput., 1997, 26(5): 1474
CrossRef ADS Google scholar
[7]
P.W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp 124–134
[8]
L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 1997, 79(2): 325
CrossRef ADS Google scholar
[9]
A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502
CrossRef ADS Google scholar
[10]
D.ChristophH. Peter, A quantum algorithm for finding the minimum, arXiv: quant-ph/9607014v2 (1996)
[11]
H. Ramesh, V. Vinay. String matching in O~(n+m) quantum time. J. Discrete Algorithms, 2003, 1(1): 103
CrossRef ADS Google scholar
[12]
A.AmbainisK. BalodisJ.Iraids, ., Quantum speedups for exponential-time dynamic programming algorithms, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. San Diego: SIAM, 2019, pp 1783–1793
[13]
A.AndrisL. Nikita, Quantum algorithms for computational geometry problems, in: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2020
[14]
G. Brassard, P. Hoyer, M. Mosca. . Quantum amplitude amplification and estimation. Contemp. Math., 2002, 305: 53
CrossRef ADS Google scholar
[15]
Z. J. Diao. Exactness of the original Grover search algorithm. Phys. Rev. A, 2010, 82(4): 044301
CrossRef ADS Google scholar
[16]
G. L. Long. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307
CrossRef ADS Google scholar
[17]
J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79
CrossRef ADS Google scholar
[18]
J. I. Cirac, P. Zoller. Quantum computations with cold trapped ions. Phys. Rev. Lett., 1995, 74(20): 4091
CrossRef ADS Google scholar
[19]
C. Y. Lu, X. Q. Zhou, O. Guhne, W. B. Gao, J. Zhang, Z. S. Yuan, A. Goebel, T. Yang, J. W. Pan. Experimental entanglement of six photons in graph states. Nat. Phys., 2007, 3(2): 91
CrossRef ADS Google scholar
[20]
Y. Makhlin, G. Schön, A. Shnirman. Quantum-state engineering with Josephson-junction devices. Rev. Mod. Phys., 2001, 73(2): 357
CrossRef ADS Google scholar
[21]
J. Berezovsky, M. H. Mikkelsen, N. G. Stoltz, L. A. Coldren, D. D. Awschalom. Picosecond coherent optical manipulation of a single electron spin in a quantum dot. Science, 2008, 320(5874): 349
CrossRef ADS Google scholar
[22]
R. Hanson, D. D. Awschalom. Coherent manipulation of single spins in semiconductors. Nature, 2008, 453(7198): 1043
CrossRef ADS Google scholar
[23]
H.BuhrmanH. Röhrig, Distributed quantum computing, in: Mathematical Foundations of Computer Science 2003: 28th International Symposium, Berlin Heidelberg, Springer, 2003, pp 1–20
[24]
A. Yimsiriwattan, Jr Lomonaco. Distributed quantum computing: A distributed Shor algorithm. Quantum Inf. Comput. II., 2004, 5436: 360
CrossRef ADS Google scholar
[25]
R. Beals, S. Brierley, O. Gray. . Efficient distributed quantum computing. Proc. R. Soc. A, 2013, 469(2153): 0120686
CrossRef ADS Google scholar
[26]
K. Li, D. W. Qiu, L. Li, S. Zheng, Z. Rong. Application of distributed semiquantum computing model in phase estimation. Inf. Process. Lett., 2017, 120: 23
CrossRef ADS Google scholar
[27]
J. Avron, O. Casper, I. Rozen. Quantum advantage and noise reduction in distributed quantum computing. Phys. Rev. A, 2021, 104(5): 052404
CrossRef ADS Google scholar
[28]
D.W. QiuL. LuoL.G. Xiao, Distributed Grover’s algorithm, arXiv: 2204.10487v3 (2022)
[29]
J. W. Tan, L. G. Xiao, D. W. Qiu, L. Luo, P. Mateus. Distributed quantum algorithm for Simon’s problem. Phys. Rev. A, 2022, 106(3): 032417
CrossRef ADS Google scholar
[30]
L.G. XiaoD. W. QiuL.LuoP.Mateus, Distributed Shor’s algorithm, Quantum Inf. Comput. 23(1&2), 27 (2023)
[31]
L.G. XiaoD. W. QiuL.Luo, ., Distributed quantum−classical hybrid Shor’s algorithm, arXiv: 2304.12100 (2023)
[32]
X.ZhouD. W. QiuL.Luo, Distributed exact quantum algorithms for Bernstein−Vazirani and search problems, arXiv: 2303.10670 (2023)
[33]
H.LiD.W. Qiu L.Luo, Distributed exact quantum algorithms for Deutsch−Jozsa problem, arXiv: 2303.10663 (2023)
[34]
MindQuantum, URL: gitee.com/mindspore/mindquantum, 2021
[35]
M.A. NielsenI.L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2002

Declarations

The authors declare that they have no competing interests and there are no conflicts.

Data availability statement

No data associated in the manuscript.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61572532 and 61876195) and the Natural Science Foundation of Guangdong Province of China (No. 2017B030311011).

RIGHTS & PERMISSIONS

2023 Higher Education Press
AI Summary AI Mindmap
PDF(14522 KB)

Accesses

Citations

Detail

Sections
Recommended

/