Degradation of Grover’s search under collective phase flips in queries to the oracle

doi:10.1007/s11467-018-0825-8

Frontiers of Physics

2018, Vol. 13

Issue (5): 130318 https://doi.org/10.1007/s11467-018-0825-8

本期目录

Degradation of Grover’s search under collective phase flips in queries to the oracle

Alexey E. Rastegin(

)

Department of Theoretical Physics, Irkutsk State University, Irkutsk, Russia

全文: PDF(323 KB)

Abstract：

We address the case in which querying the oracle in Grover’s algorithm is exposed to noise including phase distortions. The oracle-box wires can be altered by an opposing party that tries to prevent reception of correct data from the oracle. This situation reflects an experienced truth that any access to prophetic knowledge cannot be common and direct. To study this problem, we introduce a simple model of collective phase distortions on the basis of a phase-damping channel. In the model, the probability of success is not altered via the oracle-box wires per se. Phase distortions of the considered type can hardly be detected via any one-time query to the oracle. However, the probability of success is significantly changed when such errors are introduced as an intermediate step in the Grover iteration. We investigate the probability of success with respect to variations of the parameter that characterizes the amount of phase errors. It turns out that the probability of success decreases significantly even if the error is not very high. Moreover, this probability quickly reduces to the value of one half, which corresponds to the completely mixed state. We also study trade-off relations between quantum coherence and the probability of success in the presence of noise of the considered type.

Key words： Grover’s algorithm phase noise relative entropy of coherence

收稿日期: 2018-02-04 出版日期: 2018-09-10

Corresponding Author(s): Alexey E. Rastegin

引用本文:

. [J]. Frontiers of Physics, 2018, 13(5): 130318.
Alexey E. Rastegin. Degradation of Grover’s search under collective phase flips in queries to the oracle. Front. Phys. , 2018, 13(5): 130318.

链接本文:

https://academic.hep.com.cn/fop/CN/10.1007/s11467-018-0825-8
https://academic.hep.com.cn/fop/CN/Y2018/V13/I5/130318

1	A. Galindo and M. A. Martin-Delgado, Information and computation: Classical and quantum aspects, Rev. Mod. Phys. 74(2), 347 (2002) https://doi.org/10.1103/RevModPhys.74.347
2	P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26(5), 1484 (1997) https://doi.org/10.1137/S0097539795293172
3	D. Haase and H. Maier, Quantum algorithms for number fields, Fortschr. Phys. 54(8–10), 866 (2006) https://doi.org/10.1002/prop.200610311
4	S. Hallgren, Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem, J. Assoc. Comput. Mach. 54(1), 1 (2007) https://doi.org/10.1145/1206035.1206039
5	A. M. Childs and W. van Dam, Quantum algorithms for algebraic problems, Rev. Mod. Phys. 82(1), 1 (2010) https://doi.org/10.1103/RevModPhys.82.1
6	L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79(2), 325 (1997) https://doi.org/10.1103/PhysRevLett.79.325
7	L. K. Grover, Quantum computers can search arbitrarily large databases by a single query, Phys. Rev. Lett. 79(23), 4709 (1997) https://doi.org/10.1103/PhysRevLett.79.4709
8	L. K. Grover, Quantum computers can search rapidly by using almost any transformation, Phys. Rev. Lett. 80(19), 4329 (1998) https://doi.org/10.1103/PhysRevLett.80.4329
9	A. D. Patel and L. K. Grover, Quantum search, in: M.- Y. Kao (Ed.), Encyclopedia of Algorithms, New York: Springer, 2016, pp 1707–1716 https://doi.org/10.1007/978-1-4939-2864-4_317
10	S. J. Jr Lomonaco and L. H. Kauffman, Is Grover’s algorithm a quantum hidden subgroup algorithm? Quantum Inform. Process. 6(6), 461 (2007) https://doi.org/10.1007/s11128-007-0066-1
11	C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput. 26(5), 1510 (1997) https://doi.org/10.1137/S0097539796300933
12	C. Zalka, Grover’s quantum searching algorithm is optimal, Phys. Rev. A 60(4), 2746 (1999) https://doi.org/10.1103/PhysRevA.60.2746
13	E. Biham, O. Biham, D. Biron, M. Grassl, and D. A. Lidar, Grover’s quantum search algorithm for an arbitrary initial amplitude distribution, Phys. Rev. A 60(4), 2742 (1999) https://doi.org/10.1103/PhysRevA.60.2742
14	A. Galindo and M. A. Martin-Delgado, Family of Grover’s quantum-searching algorithms, Phys. Rev. A 62(6), 062303 (2000) https://doi.org/10.1103/PhysRevA.62.062303
15	E. Biham, O. Biham, D. Biron, M. Grassl, D. A. Lidar, and D. Shapira, Analysis of generalized Grover quantum search algorithms using recursion equations, Phys. Rev. A 63(1), 012310 (2000) https://doi.org/10.1103/PhysRevA.63.012310
16	E. Biham and D. Kenigsberg, Grover’s quantum search algorithm for an arbitrary initial mixed state, Phys. Rev. A 66(6), 062301 (2002) https://doi.org/10.1103/PhysRevA.66.062301
17	J. Watrous, The Theory of Quantum Information, Cambridge: Cambridge University Press, 2018 https://doi.org/10.1017/9781316848142
18	D. Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proc. R. Soc. Lond. A 400(1818), 97 (1985)
19	M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2000
20	S. L. Braunstein and A. K. Pati, Speed-up and entanglement in quantum searching, Quantum Inf. Comput. 2, 399 (2002)
21	R. Jozsa and N. Linden, On the role of entanglement in quantum-computational speed-up, Proc. R. Soc. Lond. A 459(2036), 2011 (2003) https://doi.org/10.1098/rspa.2002.1097
22	T. Baumgratz, M. Cramer, and M. B. Plenio, Quantifying coherence, Phys. Rev. Lett. 113(14), 140401 (2014) https://doi.org/10.1103/PhysRevLett.113.140401
23	A. Streltsov, G. Adesso, and M. B. Plenio, Quantum coherence as a resource, Rev. Mod. Phys. 89(4), 041003 (2017) https://doi.org/10.1103/RevModPhys.89.041003
24	G. Adesso, T. R. Bromley, and M. Cianciaruso, Measures and applications of quantum correlations, J. Phys. A Math. Theor. 49(47), 473001 (2016) https://doi.org/10.1088/1751-8113/49/47/473001
25	M. L. Hu and H. Fan, Relative quantum coherence, incompatibility, and quantum correlations of states, Phys. Rev. A 95(5), 052106 (2017) https://doi.org/10.1103/PhysRevA.95.052106
26	M. L. Hu, X. Hu, Y. Peng, Y. R. Zhang, and H. Fan, Quantum coherence and quantum correlations, arXiv: 1703.01852 [quant-ph] (2017)
27	V. Vedral, The role of relative entropy in quantum information theory, Rev. Mod. Phys. 74(1), 197 (2002) https://doi.org/10.1103/RevModPhys.74.197
28	A. E. Rastegin, Quantum-coherence quantifiers based on the Tsallis relative a entropies, Phys. Rev. A 93(3), 032136 (2016) https://doi.org/10.1103/PhysRevA.93.032136
29	E. Chitambar and G. Gour, Comparison of incoherent operations and measures of coherence, Phys. Rev. A 94(5), 052336 (2016) https://doi.org/10.1103/PhysRevA.94.052336
30	L. H. Shao, Y. Li, Y. Luo, and Z. Xi, Quantum coherence quantifiers based on the Rényi a-relative entropy, Commum. Theor. Phys. 67(6), 631 (2017) https://doi.org/10.1088/0253-6102/67/6/631
31	A. Streltsov, H. Kampermann, S. Wölk, M. Gessner, and D. Bruß, Maximal coherence and the resource theory of purity, New J. Phys. 20(5), 053058 (2018) https://doi.org/10.1088/1367-2630/aac484
32	L. H. Shao, Z. Xi, H. Fan, and Y. Li, Fidelity and tracenorm distances for quantifying coherence, Phys. Rev. A 91(4), 042120 (2015) https://doi.org/10.1103/PhysRevA.91.042120
33	S. Rana, P. Parashar, and M. Lewenstein, Tracedistance measure of coherence, Phys. Rev. A 93(1), 012110 (2016) https://doi.org/10.1103/PhysRevA.93.012110
34	H. J. Zhang, B. Chen, M. Li, S. M. Fei, and G. L. Long, Estimation on geometric measure of quantum coherence, Commum. Theor. Phys. 67(2), 166 (2017) https://doi.org/10.1088/0253-6102/67/2/166
35	S. Cheng and M. J. W. Hall, Complementarity relations for quantum coherence, Phys. Rev. A 92(4), 042101 (2015) https://doi.org/10.1103/PhysRevA.92.042101
36	U. Singh, A. K. Pati, and M. N. Bera, Uncertainty relations for quantum coherence, Mathematics 4(3), 47 (2016) https://doi.org/10.3390/math4030047
37	Y. Peng, Y. R. Zhang, Z.Y. Fan, S. Liu, and H. Fan, Complementary relation of quantum coherence and quantum correlations in multiple measurements, arXiv: 1608.07950 [quant-ph] (2016)
38	X. Yuan, G. Bai, T. Peng, and X. Ma, Quantum uncertainty relation using coherence, Phys. Rev. A 96(3), 032313 (2017) https://doi.org/10.1103/PhysRevA.96.032313
39	A. E. Rastegin, Uncertainty relations for quantum coherence with respect to mutually unbiased bases, Front. Phys. 13(1), 130304 (2018) https://doi.org/10.1007/s11467-017-0713-7
40	M. N. Bera, T. Qureshi, M. A. Siddiqui, and A. K. Pati, Duality of quantum coherence and path distinguishability, Phys. Rev. A 92(1), 012118 (2015) https://doi.org/10.1103/PhysRevA.92.012118
41	E. Bagan, J. A. Bergou, S. S. Cottrell, and M. Hillery, Relations between coherence and path information, Phys. Rev. Lett. 116(16), 160406 (2016) https://doi.org/10.1103/PhysRevLett.116.160406
42	T. Qureshi and M. A. Siddiqui, Wave-particle duality in N-path interference, Ann. Phys. 385, 598 (2017) https://doi.org/10.1016/j.aop.2017.08.015
43	M. Hillery, Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation, Phys. Rev. A 93(1), 012111 (2016) https://doi.org/10.1103/PhysRevA.93.012111
44	H. L. Shi, S. Y. Liu, X. H. Wang, W. L. Yang, Z. Y. Yang, and H. Fan, Coherence depletion in the Grover quantum search algorithm, Phys. Rev. A 95(3), 032307 (2017) https://doi.org/10.1103/PhysRevA.95.032307
45	N. Anand and A. K. Pati, Coherence and entanglement monogamy in the discrete analogue of analog Grover search, arXiv: 1611.04542 [quant-ph] (2016)
46	A. E. Rastegin, On the role of dealing with quantum coherence in amplitude amplification, Quantum Inf. Progress 17(7), 179 (2018) https://doi.org/10.1007/s11128-018-1946-2
47	D. Reitzner and M. Hillery, Grover search under localized dephasing, arXiv: 1712.06558 [quant-ph] (2017)
48	M. Hillery, J. Bergou, and E. Feldman, Quantum walks based on an interferometric analogy, Phys. Rev. A 68(3), 032314 (2003) https://doi.org/10.1103/PhysRevA.68.032314

Viewed

Full text

Abstract

Cited

Shared

Discussed