Degradation of Grover’s search under collective phase flips in queries to the oracle
Alexey E. Rastegin
Degradation of Grover’s search under collective phase flips in queries to the oracle
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.
Grover’s algorithm / phase noise / relative entropy of coherence
[1] |
A. Galindo and M. A. Martin-Delgado, Information and computation: Classical and quantum aspects, Rev. Mod. Phys. 74(2), 347 (2002)
CrossRef
ADS
Google scholar
|
[2] |
P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26(5), 1484 (1997)
CrossRef
ADS
Google scholar
|
[3] |
D. Haase and H. Maier, Quantum algorithms for number fields, Fortschr. Phys. 54(8–10), 866 (2006)
CrossRef
ADS
Google scholar
|
[4] |
S. Hallgren, Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem, J. Assoc. Comput. Mach. 54(1), 1 (2007)
CrossRef
ADS
Google scholar
|
[5] |
A. M. Childs and W. van Dam, Quantum algorithms for algebraic problems, Rev. Mod. Phys. 82(1), 1 (2010)
CrossRef
ADS
Google scholar
|
[6] |
L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79(2), 325 (1997)
CrossRef
ADS
Google scholar
|
[7] |
L. K. Grover, Quantum computers can search arbitrarily large databases by a single query, Phys. Rev. Lett. 79(23), 4709 (1997)
CrossRef
ADS
Google scholar
|
[8] |
L. K. Grover, Quantum computers can search rapidly by using almost any transformation, Phys. Rev. Lett. 80(19), 4329 (1998)
CrossRef
ADS
Google scholar
|
[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
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[11] |
C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput. 26(5), 1510 (1997)
CrossRef
ADS
Google scholar
|
[12] |
C. Zalka, Grover’s quantum searching algorithm is optimal, Phys. Rev. A 60(4), 2746 (1999)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[14] |
A. Galindo and M. A. Martin-Delgado, Family of Grover’s quantum-searching algorithms, Phys. Rev. A 62(6), 062303 (2000)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[16] |
E. Biham and D. Kenigsberg, Grover’s quantum search algorithm for an arbitrary initial mixed state, Phys. Rev. A 66(6), 062301 (2002)
CrossRef
ADS
Google scholar
|
[17] |
J. Watrous, The Theory of Quantum Information, Cambridge: Cambridge University Press, 2018
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[22] |
T. Baumgratz, M. Cramer, and M. B. Plenio, Quantifying coherence, Phys. Rev. Lett. 113(14), 140401 (2014)
CrossRef
ADS
Google scholar
|
[23] |
A. Streltsov, G. Adesso, and M. B. Plenio, Quantum coherence as a resource, Rev. Mod. Phys. 89(4), 041003 (2017)
CrossRef
ADS
Google scholar
|
[24] |
G. Adesso, T. R. Bromley, and M. Cianciaruso, Measures and applications of quantum correlations, J. Phys. A Math. Theor. 49(47), 473001 (2016)
CrossRef
ADS
Google scholar
|
[25] |
M. L. Hu and H. Fan, Relative quantum coherence, incompatibility, and quantum correlations of states, Phys. Rev. A 95(5), 052106 (2017)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[28] |
A. E. Rastegin, Quantum-coherence quantifiers based on the Tsallis relative a entropies, Phys. Rev. A 93(3), 032136 (2016)
CrossRef
ADS
Google scholar
|
[29] |
E. Chitambar and G. Gour, Comparison of incoherent operations and measures of coherence, Phys. Rev. A 94(5), 052336 (2016)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[33] |
S. Rana, P. Parashar, and M. Lewenstein, Tracedistance measure of coherence, Phys. Rev. A 93(1), 012110 (2016)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[35] |
S. Cheng and M. J. W. Hall, Complementarity relations for quantum coherence, Phys. Rev. A 92(4), 042101 (2015)
CrossRef
ADS
Google scholar
|
[36] |
U. Singh, A. K. Pati, and M. N. Bera, Uncertainty relations for quantum coherence, Mathematics 4(3), 47 (2016)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[39] |
A. E. Rastegin, Uncertainty relations for quantum coherence with respect to mutually unbiased bases, Front. Phys. 13(1), 130304 (2018)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[42] |
T. Qureshi and M. A. Siddiqui, Wave-particle duality in N-path interference, Ann. Phys. 385, 598 (2017)
CrossRef
ADS
Google scholar
|
[43] |
M. Hillery, Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation, Phys. Rev. A 93(1), 012111 (2016)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
[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)
CrossRef
ADS
Google scholar
|
/
〈 | 〉 |