Distributed exact Grover’s algorithm
Xu Zhou, Daowen Qiu, Le Luo
Distributed exact Grover’s algorithm
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 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 , which is less than the circuit depths of the original and modified Grover’s algorithms, and , respectively. It only depends on the parity of , and it is not deepened as 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.
distributed quantum computation / search problem / distributed exact Grover’s algorithm (DEGA) / MindQuantum / the depolarization channel noise
[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,
|
[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.
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.
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,
|
[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,
|
[35] |
M.A. NielsenI.L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2002
|
/
〈 | 〉 |