Distributed exact Grover’s algorithm

doi:10.1007/s11467-023-1327-x

Front. Phys.

2023, Vol. 18

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

RESEARCH ARTICLE

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

Download: PDF(14522 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

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

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

About author:

^* These authors contributed equally to this work.

Issue Date: 29 August 2023

Cite this article:

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

URL:

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

Fig.1 Quantum circuit of Grover’s algorithm.

Fig.2 Visualization of Grover’s algorithm. In the two-dimensional plane space spanned by

{| x ~ ?, | τ ?}

, one iteration of

G

causes a rotation by an angle

2 θ

from the initial state

| h ?

to the target state

| τ ?

Fig.3 Quantum circuit of the modified Grover’s algorithm.

Fig.4 Visualization of the modified Grover’s algorithm. In the three-dimensional Bloch sphere spanned by

{| x ~ ?, | τ ?}

, the initial state

r i

rotate

ω

around axis

l

, and then

r f

is obtained, where

ω

is the desired rotation angle.

Fig.5 Quantum circuit of the distributed exact Grover’s algorithm (DEGA).

Fig.6 Equivalent quantum circuit of Toffoli gate (or

C 2 Z

gate), where

T

represent

π / 8

gate and

T †

represents the conjugate transpose of

T

Fig.7 The quantum circuit corresponding to the Oracle

U f (x)

Fig.8 The quantum circuit corresponding to the Oracle

U 0

Fig.9 The quantum circuit corresponding to the Oracle

R f (x)

Fig.10 The quantum circuit corresponding to the Oracle

R 0

Fig.11 Quantum circuit of the 2-qubit DEGA (target string

τ = 01

Fig.12 The sampling results of the 2-qubit DEGA (target string

τ = 01

Fig.13 Quantum circuit of the 3-qubit DEGA (target string

τ = 101

). The parameter in the circuit is

ϕ = 2 arcsin ? (sin ? (π 4 J + 6) / sin ? θ) = 2.1268800471555034 ≈ 2.1269

, where

J = ? (π / 2 − θ) / (2 θ) ?

and

θ = arcsin ? (1 / 23)

Fig.14 The sampling results of the 3-qubit DEGA (target string

τ = 101

Fig.15 Quantum circuit of the 4-qubit DEGA (target string

τ = 1001

Fig.16 The sampling results of the 4-qubit DEGA (target string

τ = 1001

Fig.17 Quantum circuit of the 4-qubit Grover’s algorithm (target string

τ = 1001

Fig.18 Quantum circuit of the 4-qubit modified Grover’s algorithm (target string

τ = 1001

). The parameter in the circuit is

ϕ = 2 arcsin ? (sin ? (π 4 J + 6) / sin ? θ) = 2.195057699090115 ≈ 2.1951

, where

J = ? (π / 2 − θ) / (2 θ) ?

and

θ = arcsin ? (1 / 24)

Fig.19 The sampling results of the 4-qubit Grover’s algorithm (target string

τ = 1001

Fig.20 The sampling results of the 4-qubit modified Grover’s algorithm (target string

τ = 1001

Fig.21 Quantum circuit of the 5-qubit DEGA (target string

τ = 01001

). The parameter in the circuit is

ϕ = 2 arcsin ? (sin ? (π 4 J + 6) / sin ? θ) = 2.1268800471555034 ≈ 2.1269

, where

J = ? (π / 2 − θ) / (2 θ) ?

and

θ = arcsin ? (1 / 23)

Fig.22 The sampling results of the 4-qubit DEGA (target string

τ = 01001

Fig.23 Quantum circuit of the 5-qubit Grover’s algorithm (target string

τ = 01001

Fig.24 Quantum circuit of the 5-qubit modified Grover’s algorithm (target string

τ = 01001

). The parameter in the circuit is

ϕ = 2 arcsin ? (sin ? (π 4 J + 6) / sin ? θ) = 2.764763603060391 ≈ 2.7648

, where

J = ? (π / 2 − θ) / (2 θ) ?

and

θ = arcsin ? (1 / 25)

Fig.25 The sampling results of the 5-qubit Grover’s algorithm (target string

τ = 01001

Fig.26 The sampling results of the 5-qubit modified Grover’s algorithm (target string

τ = 01001

Fig.27 The probability of obtaining the target string by different algorithms.

Fig.28 The number of quantum gates required by different algorithms.

Fig.29 The depth of quantum circuit of different algorithms.

Fig.30 Quantum circuit of the 5-qubit Grover’s algorithm (target string

τ = 01001

) in the depolarizing channel.

Fig.31 Quantum circuit of the 5-qubit modified Grover’s algorithm (target string

τ = 01001

) in the depolarizing channel. The parameter in the circuit is

ϕ = 2 arcsin ? (sin ? (π 4 J + 6) / sin ? θ) = 2.764763603060391 ≈ 2.7648

, where

J = ? (π / 2 − θ) / (2 θ) ?

and

θ = arcsin ? (1 / 25)

Fig.32 Quantum circuit of the 5-qubit DEGA (target string

τ = 01001

) in the depolarizing channel. The parameter in the circuit is

ϕ = 2 arcsin ? (sin ? (π 4 J + 6) / sin ? θ) = 2.1268800471555034 ≈ 2.1269

, where

J = ? (π / 2 − θ) / (2 θ) ?

and

θ = arcsin ? (1 / 23)

Fig.33 The sampling results of the 5-qubit Grover’s algorithm in the depolarizing channel. The noise parameter

p = 0.01

Fig.34 The sampling results of the 5-qubit modified Grover’s algorithm in the depolarizing channel. The noise parameter

p = 0.01

Fig.35 The sampling results of the 5-qubit DEGA in the depolarizing channel. The noise parameter

p = 0.01

Fig.36 The probability of obtaining

τ = 01001

by different algorithms.

Fig.37 The sampling results of the 5-qubit Grover’s algorithm in the depolarizing channel. The noise parameter

p = 0.07

Fig.38 The sampling results of the 5-qubit modified Grover’s algorithm in the depolarizing channel. The noise parameter

p = 0.07

Fig.39 The sampling results of the 5-qubit DEGA in the depolarizing channel. The noise parameter

p = 0.07

Fig.40 The sampling results of the 5-qubit Grover’s algorithm in the depolarizing channel. The noise parameter

p = 0.09

Fig.41 The sampling results of the 5-qubit modified Grover’s algorithm in the depolarizing channel. The noise parameter

p = 0.09

Fig.42 The sampling results of the 5-qubit DEGA in the depolarizing channel. The noise parameter

p = 0.09

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