Distributed exact generalized Grover’s algorithm

Abstract

Distributed quantum computation has garnered immense attention in the noisy intermediate-scale quantum (NISQ) era, where each computational node necessitates fewer qubits and quantum gates. In this paper, we focus on a generalized search problem involving multiple targets within an unordered database and propose a Distributed Exact Generalized Grover’s Algorithm (DEGGA) to address this challenge by decomposing it into arbitrary t components, where 2\le t\le n. Specifically, (1) our algorithm ensures accuracy, with a theoretical probability of identifying the target states at 100%; (2) if the number of targets is fixed, the pivotal factor influencing the circuit depth of DEGGA is the partitioning strategy, rather than the magnitude of n; (3) the maximum number of qubits required by our method at a single node is max\left(n_0,n_1,\dots ,n_{t-1}\right), where n_j represents the number of qubits for the jth node and satisfies {\sum }_{j=0}^{t-1}{n}_j=n, eliminating the need for auxiliary qubits; (4) we elucidate the resolutions (two-node and three-node) of a particular generalized search issue incorporating two goal strings (000000 and 111111) by applying DEGGA. The feasibility and effectiveness of our suggested approach is further demonstrated by executing the quantum circuits on MindSpore Quantum (a quantum simulation software). Eventually, through the decomposition of multi-qubit gates, DEGGA diminishes the utilization of quantum gates by 90.7% and decreases the circuit depth by 91.3% in comparison to the modified Grover’s algorithm by Long. It is increasingly evident that distributed quantum algorithms offer augmented practicality.

Graphical abstract

Keywords

distributed quantum computation / noisy intermediate scale quantum (NISQ) era / distributed exact generalized Grover’s algorithm (DEGGA) / MindSpore quantum / quantum simulation software

References

[1] Benioff P . The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 1980, 22( 5): 563–591

[2] Feynman R P. Simulating physics with computers. International Journal of Theoretical Physics, 1982, 21(6−7): 467−488

[3] Deutsch D . Quantum theory, the Church–Turing principle and the universal quantum computer. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1985, 400( 1818): 97–117

[4] Deutsch D, Jozsa R . Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992, 439( 1907): 553–558

[5] Bernstein E, Vazirani U . Quantum complexity theory. SIAM Journal on Computing, 1997, 26( 5): 1411–1473

[6] Simon D R . On the power of quantum computation. SIAM Journal on Computing, 1997, 26( 5): 1474–1483

[7] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994, 124−134

[8] Grover L K . Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 1997, 79( 2): 325–328

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

[10] Cerezo M, Arrasmith A, Babbush R, Benjamin S C, Endo S, Fujii K, McClean J R, Mitarai K, Yuan X, Cincio L, Coles P J . Variational quantum algorithms. Nature Reviews Physics, 2021, 3( 9): 625–644

[11] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A, O’brien J L . A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 2014, 5( 1): 4213

[12] Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm. 2014, arXiv preprint arXiv: 1411.4028

[13] Durr C, Hoyer P. A quantum algorithm for finding the minimum. 1996, arXiv preprint arXiv: quant-ph/9607014

[14] Ramesh H, Vinay V . String matching in O(n+m) quantum time. Journal of Discrete Algorithms, 2003, 1( 1): 103–110

[15] Ambainis A, Larka N. Quantum algorithms for computational geometry problems. In: Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography. 2020, 9

[16] Ambainis A, Balodis K, Iraids J, Kokainis M, Prūsis K, Vihrovs J. Quantum speedups for Exponential-Time dynamic programming algorithms. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. 2019, 1783−1793

[17] Montanaro A . Quantum-walk speedup of backtracking algorithms. Theory of Computing, 2018, 14( 1): 1–24

[18] Allcock J, Bao J, Belovs A, Lee T, Santha M. On the quantum time complexity of divide and conquer. 2023, arXiv preprint arXiv: 2311.16401

[19] Brassard G, Hoyer P, Mosca M, Tapp A. Quantum amplitude amplification and estimation. Contemporary Mathematics, 2002, 305: 53−74

[20] Diao Z J . Exactness of the original Grover search algorithm. Physical Review A, 2010, 82( 4): 044301

[21] Høyer P . Arbitrary phases in quantum amplitude amplification. Physical Review A, 2000, 62( 5): 052304

[22] Long G L . Grover algorithm with zero theoretical failure rate. Physical Review A, 2001, 64( 2): 022307

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

[24] Cirac J I, Zoller P . Quantum computations with cold trapped ions. Physical Review Letters, 1995, 74( 20): 4091–4094

[25] Lu C Y, Zhou X Q, Gühne O, Gao W B, Zhang J, Yuan Z S, Goebel A, Yang T, Pan J W . Experimental entanglement of six photons in graph states. Nature Physics, 2007, 3( 2): 91–95

[26] Makhlin Y, Schön G, Shnirman A . Quantum-state engineering with Josephson-junction devices. Reviews of Modern Physics, 2001, 73( 2): 357–400

[27] Berezovsky J, Mikkelsen M H, Stoltz N G, Coldren L A, Awschalom D D . Picosecond coherent optical manipulation of a single electron spin in a quantum dot. Science, 2008, 320( 5874): 349–352

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

[29] Barral D, Cardama F J, Díaz-Camacho G, Faílde D, Llovo I F, Mussa-Juane M, Vázquez-Pérez J, Villasuso J, Piñeiro C, Costas N, Pichel J C, Pena T F, Gómez A . Review of distributed quantum computing: from single QPU to high performance quantum computing. Computer Science Review, 2025, 57: 100747

[30] Buhrman H, Röhrig H. Distributed quantum computing. In: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science 2003. 2003, 1−20

[31] Yimsiriwattana A, Lomonaco Jr S J. Distributed quantum computing: a distributed Shor algorithm. In: Proceedings of SPIE 5436, Quantum Information and Computation II. 2004, 360−372

[32] Beals R, Brierley S, Gray O, Harrow A W, Kutin S, Linden N, Shepherd D, Stather M . Efficient distributed quantum computing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 469( 2153): 20120686

[33] Li K, Qiu D, Li L, Zheng S, Rong Z . Application of distributed semi-quantum computing model in phase estimation. Information Processing Letters, 2017, 120: 23–29

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

[35] Qiu D, Luo L, Xiao L . Distributed Grover’s algorithm. Theoretical Computer Science, 2024, 993: 114461

[36] Zhou X, Qiu D, Luo L . Distributed exact Grover’s algorithm. Frontiers of Physics, 2023, 18( 5): 51305

[37] Tan J, Xiao L, Qiu D, Luo L, Mateus P . Distributed quantum algorithm for Simon’s problem. Physical Review A, 2022, 106( 3): 032417

[38] Li H, Qiu D, Luo L, Mateus P . Exact distributed quantum algorithm for generalized Simon’s problem. Acta Informatica, 2024, 61( 2): 131–159

[39] Zhou X, Wang Y, Tao W, Zhou Z, Luo L . Distributed quantum algorithm for the NISQ era: a novel approach to solving Simon’s problem with reduced resources. Advanced Quantum Technologies, 2025, 8( 5): 2500067

[40] Zhou X, Qiu D, Luo L . Distributed Bernstein-Vazirani algorithm. Physica A: Statistical Mechanics and its Applications, 2023, 629: 129209

[41] Li H, Qiu D, Luo L. Distributed exact quantum algorithms for Deutsch-Jozsa problem. 2023, arXiv preprint arXiv: 2303.10663

[42] Xiao L, Qiu D, Luo L, Mateus P. Distributed Shor’s algorithm. Quantum Information and Computation, 2023, 23(1−2): 27−44

[43] Xiao L, Qiu D, Luo L, Mateus P. Distributed quantum-classical hybrid Shor’s algorithm. 2023, arXiv preprint arXiv: 2304.12100

[44] Liu X, Hu X M, Zhu T X, Zhang C, Xiao Y X, Miao J L, Ou Z W, Li P Y, Liu B H, Zhou Z Q, Li C F, Guo G C . Nonlocal photonic quantum gates over 7. 0 km. Nature Communications, 2024, 15( 1): 8529

[45] Main D, Drmota P, Nadlinger D P, Ainley E M, Agrawal A, Nichol B C, Srinivas R, Araneda G, Lucas D M . Distributed quantum computing across an optical network link. Nature, 2025, 638( 8050): 383–388

[46] Gitee. MindSpore/mindquantum. See Gitee.com/mindspore/mindquantum website, 2021

[47] Xu X, Cui J, Cui Z, He R, Li Q, , . MindSpore Quantum: a user−friendly, high-performance, and AI−compatible quantum computing framework. 2024, arXiv preprint arXiv: 2406.17248

[48] Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A, Weinfurter H . Elementary gates for quantum computation. Physical Review A, 1995, 52( 5): 3457–3467

[49] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010

RIGHTS & PERMISSIONS

Higher Education Press