Distributed exact Grover’s algorithm

doi:10.1007/s11467-023-1327-x

Frontiers of Physics

2023, Vol. 18

Issue (5): 51305 https://doi.org/10.1007/s11467-023-1327-x

本期目录

Distributed exact Grover’s algorithm

Xu Zhou^1,^2,^3,⁴(

), Daowen Qiu^1,^2,⁴(

), Le Luo^3,⁴(

)

¹. Institute of Quantum Computing and Computer Theory, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
². The Guangdong Key Laboratory of Information Security Technology, Sun Yat-sen University, Guangzhou 510006, China
³. School of Physics and Astronomy, Sun Yat-sen University, Zhuhai 519082, China
⁴. QUDOOR Co, Ltd., Beijing 100089, China

全文: PDF(14522 KB) HTML

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 (n mod 2) + 9$ , which is less than the circuit depths of the original and modified Grover’s algorithms, $1 + 8 ⌊ π 4 2 n ⌋$ and $9 + 8 ⌊ π 4 2 n − 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.

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

收稿日期: 2023-03-16 出版日期: 2023-08-29

Corresponding Author(s): Xu Zhou,Daowen Qiu,Le Luo

引用本文:

. [J]. Frontiers of Physics, 2023, 18(5): 51305.
Xu Zhou, Daowen Qiu, Le Luo. Distributed exact Grover’s algorithm. Front. Phys. , 2023, 18(5): 51305.

链接本文:

https://academic.hep.com.cn/fop/CN/10.1007/s11467-023-1327-x
https://academic.hep.com.cn/fop/CN/Y2023/V18/I5/51305

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

Fig.19

Fig.20

Fig.21

Fig.22

Fig.23

Fig.24

Fig.25

Fig.26

Fig.27

Fig.28

Fig.29

Fig.30

Fig.31

Fig.32

Fig.33

Fig.34

Fig.35

Fig.36

Fig.37

Fig.38

Fig.39

Fig.40

Fig.41

Fig.42

1	Benioff P.. 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 https://doi.org/10.1007/BF01011339
2	Benioff P.. Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys., 1982, 29(3): 515 https://doi.org/10.1007/BF01342185
3	Deutsch D.. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 1985, 400(1818): 97 https://doi.org/10.1098/rspa.1985.0070
4	Deutsch D., Jozsa R.. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A, 1992, 439(1907): 553 https://doi.org/10.1098/rspa.1992.0167
5	Bernstein E.Vazirani U., Quantum complexity theory, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC’93), 1993, pp 11–20
6	R. Simon D.. On the power of quantum computation. SIAM J. Comput., 1997, 26(5): 1474 https://doi.org/10.1137/S0097539796298637
7	W. Shor P., Algorithms for quantum computation: Discrete logarithms and factoring, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp 124–134
8	K. Grover L.. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 1997, 79(2): 325 https://doi.org/10.1103/PhysRevLett.79.325
9	W. Harrow A., Hassidim A., Lloyd S.. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502 https://doi.org/10.1103/PhysRevLett.103.150502
10	Christoph D.Peter H., A quantum algorithm for finding the minimum, arXiv: quant-ph/9607014v2 (1996)
11	Ramesh H., Vinay V.. String matching in O~(n+m) quantum time. J. Discrete Algorithms, 2003, 1(1): 103 https://doi.org/10.1016/S1570-8667(03)00010-8
12	Ambainis A.Balodis K.Iraids J., et al.., 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	Andris A.Nikita L., Quantum algorithms for computational geometry problems, in: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2020
14	Brassard G., Hoyer P., Mosca M.. et al.. Quantum amplitude amplification and estimation. Contemp. Math., 2002, 305: 53 https://doi.org/10.1090/conm/305/05215
15	J. Diao Z.. Exactness of the original Grover search algorithm. Phys. Rev. A, 2010, 82(4): 044301 https://doi.org/10.1103/PhysRevA.82.044301
16	L. Long G.. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307 https://doi.org/10.1103/PhysRevA.64.022307
17	Preskill J.. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79 https://doi.org/10.22331/q-2018-08-06-79
18	I. Cirac J., Zoller P.. Quantum computations with cold trapped ions. Phys. Rev. Lett., 1995, 74(20): 4091 https://doi.org/10.1103/PhysRevLett.74.4091
19	Y. Lu C., Q. Zhou X., Guhne O., B. Gao W., Zhang J., S. Yuan Z., Goebel A., Yang T., W. Pan J.. Experimental entanglement of six photons in graph states. Nat. Phys., 2007, 3(2): 91 https://doi.org/10.1038/nphys507
20	Makhlin Y., Schön G., Shnirman A.. Quantum-state engineering with Josephson-junction devices. Rev. Mod. Phys., 2001, 73(2): 357 https://doi.org/10.1103/RevModPhys.73.357
21	Berezovsky J., H. Mikkelsen M., G. Stoltz N., A. Coldren L., D. Awschalom D.. Picosecond coherent optical manipulation of a single electron spin in a quantum dot. Science, 2008, 320(5874): 349 https://doi.org/10.1126/science.1154798
22	Hanson R., D. Awschalom D.. Coherent manipulation of single spins in semiconductors. Nature, 2008, 453(7198): 1043 https://doi.org/10.1038/nature07129
23	Buhrman H.Röhrig H., Distributed quantum computing, in: Mathematical Foundations of Computer Science 2003: 28th International Symposium, Berlin Heidelberg, Springer, 2003, pp 1–20
24	Yimsiriwattan A., Lomonaco Jr. Distributed quantum computing: A distributed Shor algorithm. Quantum Inf. Comput. II., 2004, 5436: 360 https://doi.org/10.1117/12.546504
25	Beals R., Brierley S., Gray O.. et al.. Efficient distributed quantum computing. Proc. R. Soc. A, 2013, 469(2153): 0120686 https://doi.org/10.1098/rspa.2012.0686
26	Li K., W. Qiu D., Li L., Zheng S., Rong Z.. Application of distributed semiquantum computing model in phase estimation. Inf. Process. Lett., 2017, 120: 23 https://doi.org/10.1016/j.ipl.2016.12.002
27	Avron J., Casper O., Rozen I.. Quantum advantage and noise reduction in distributed quantum computing. Phys. Rev. A, 2021, 104(5): 052404 https://doi.org/10.1103/PhysRevA.104.052404
28	W. Qiu D.Luo L.G. Xiao L., Distributed Grover’s algorithm, arXiv: 2204.10487v3 (2022)
29	W. Tan J., G. Xiao L., W. Qiu D., Luo L., Mateus P.. Distributed quantum algorithm for Simon’s problem. Phys. Rev. A, 2022, 106(3): 032417 https://doi.org/10.1103/PhysRevA.106.032417
30	G. Xiao L.W. Qiu D.Luo L.Mateus P., Distributed Shor’s algorithm, Quantum Inf. Comput. 23(1&2), 27 (2023)
31	G. Xiao L.W. Qiu D.Luo L., et al.., Distributed quantum−classical hybrid Shor’s algorithm, arXiv: 2304.12100 (2023)
32	Zhou X.W. Qiu D.Luo L., Distributed exact quantum algorithms for Bernstein−Vazirani and search problems, arXiv: 2303.10670 (2023)
33	Li H.W. Qiu D. Luo L., Distributed exact quantum algorithms for Deutsch−Jozsa problem, arXiv: 2303.10663 (2023)
34	MindQuantum, , 2021
35	A. Nielsen M.L. Chuang I., Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2002

Viewed

Full text

Abstract

Cited

Shared

Discussed