×

Grover’s search with local and total depolarizing channel errors: complexity analysis. (English) Zbl 1344.81060

Summary: In this paper, the effect of noise on Grover’s algorithm is analyzed, modeled as a total depolarizing channel (TDCh) and a local depolarizing channel (LDCh) in each qubit. The focus was not in error correction (e.g. by the fault-tolerant method), but to provide an insight to the kind of error, or degradation, that needs to be corrected. In the last years, analytical results regarding mainly the TDCh model have been obtained. In this paper, we extend these previous results to the local case, concluding that the degradation of Grover’s algorithm with the latter is worse than the former. It has been shown that for both cases with an \(N\)-dependent small enough error-width, smaller than \(1/\sqrt{N}\) for total error and \(1/\sqrt{N}\log_2N)\) for the local case, correction is not needed.

MSC:

81P68 Quantum computation
68P10 Searching and sorting
68Q12 Quantum algorithms and complexity in the theory of computing
94A40 Channel models (including quantum) in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 1. H. Azuma, Phys. Rev. A65 (2002) 042311. genRefLink(16, ’S021974991650009XBIB001’, ’10.1103
[2] 2. D. Shapira, S. Mozes and O. Biham, Phys. Rev. A67 (2003) 042301. genRefLink(16, ’S021974991650009XBIB002’, ’10.1103
[3] 3. P. J. Salas, Eur. Phys. J. D46 (2008) 365. genRefLink(16, ’S021974991650009XBIB003’, ’10.1140
[4] 4. P. Gawron, J. Klamka and R. Winiarczyk, Appl. Math. Comput. Sci.22 (2) (2012) 493.
[5] 5. A. Ambainis, A. Backurs, N. Nahimovs and A. Rivosh, Grovers algorithm with errors, Mathematical and Engineering Methods in Computer Science eds. A. Kucera, T. A. Henzinger, J. Nesetril, T. Vojnar and D. Antos, Lecture Notes in Computer Science, Vol. 7721 (Springer, Berlin, 2013), pp. 180-189.
[6] 6. D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error, Proc. Twenty-Ninth Annual ACM Symp. Theory of Computing, STOC ’97 (New York, 1997) pp. 176-188. · Zbl 0962.68065
[7] 7. D. Gottesman, Phys. Re. A57 (1998) 127. genRefLink(16, ’S021974991650009XBIB007’, ’10.1103
[8] 8. L. K. Grover, A fast quantum mechanical algorithm for database search, Proc 28th Annual ACM Symp Theory of Computing (1996), p. 212. · Zbl 0922.68044
[9] 9. L. K. Grover, Phys. Rev. Lett.79 (1997) 325. genRefLink(16, ’S021974991650009XBIB009’, ’10.1103
[10] 10. L. K. Grover, Am. J. Phys.69 (2001) 769. genRefLink(16, ’S021974991650009XBIB010’, ’10.1119
[11] 11. O. Regev and L. Schiff, Impossibility of a quantum speed-up with a faulty oracle, Automata, Languages and Programming, eds. L. Aceto, I. Damgrd, L. Goldberg, M. Halldrsson, A. Inglfsdttir and I. Walukiewicz, Lecture Notes in Computer Science, (Springer, Berlin, 2008), pp. 773-781. · Zbl 1153.68365
[12] 12. K. Temme, Phys. Rev. A90 (2014) 022310. genRefLink(16, ’S021974991650009XBIB012’, ’10.1103
[13] 13. J. Chen, D. Kaszlikowski, L. C. Kwek and C. H. Oh, Phys. Lett. A306 (2003) 296. genRefLink(16, ’S021974991650009XBIB013’, ’10.1016
[14] 14. P. Vrana, D. Reeb, D. Reitzner and M. M. Wolf, New J. Phys.16 (2014) 073033. genRefLink(16, ’S021974991650009XBIB014’, ’10.1088
[15] 15. R. Demkowicz-Dobrzaski and M. Markiewicz, Phys. Rev. A91 (2015) 062322. genRefLink(16, ’S021974991650009XBIB015’, ’10.1103
[16] 16. C. Zalka, Phys. Rev. A60 (1999) 2746. genRefLink(16, ’S021974991650009XBIB016’, ’10.1103
[17] 17. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.