Distributed exact Grover’s algorithm

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 \lfloor n/2\rfloor 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\text{mod}2)+9, which is less than the circuit depths of the original and modified Grover’s algorithms, 1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor and 9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor, 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

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

[2] P. Benioff. Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys., 1982, 29(3): 515

[3] D. Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 1985, 400(1818): 97

[4] D. Deutsch, R. Jozsa. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A, 1992, 439(1907): 553

[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

[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

[9] A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502

[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

[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

[15] Z. J. Diao. Exactness of the original Grover search algorithm. Phys. Rev. A, 2010, 82(4): 044301

[16] G. L. Long. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307

[17] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79

[18] J. I. Cirac, P. Zoller. Quantum computations with cold trapped ions. Phys. Rev. Lett., 1995, 74(20): 4091

[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

[20] Y. Makhlin, G. Schön, A. Shnirman. Quantum-state engineering with Josephson-junction devices. Rev. Mod. Phys., 2001, 73(2): 357

[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

[22] R. Hanson, D. D. Awschalom. Coherent manipulation of single spins in semiconductors. Nature, 2008, 453(7198): 1043

[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

[25] R. Beals, S. Brierley, O. Gray. . Efficient distributed quantum computing. Proc. R. Soc. A, 2013, 469(2153): 0120686

[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

[27] J. Avron, O. Casper, I. Rozen. Quantum advantage and noise reduction in distributed quantum computing. Phys. Rev. A, 2021, 104(5): 052404

[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

[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