{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T11:58:15Z","timestamp":1719316695625},"reference-count":17,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,6,1]]},"abstract":"<jats:title>Noise effects in the quantum search algorithm from the viewpoint of computational complexity<\/jats:title><jats:p>We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search algorithm. We show that it is only for small amounts of noise that the quantum search algorithm is still more efficient than any classical algorithm.<\/jats:p>","DOI":"10.2478\/v10006-012-0037-2","type":"journal-article","created":{"date-parts":[[2012,6,29]],"date-time":"2012-06-29T14:49:17Z","timestamp":1340981357000},"page":"493-499","source":"Crossref","is-referenced-by-count":18,"title":["Noise effects in the quantum search algorithm from the viewpoint of computational complexity"],"prefix":"10.61822","volume":"22","author":[{"given":"Piotr","family":"Gawron","sequence":"first","affiliation":[]},{"given":"Jerzy","family":"Klamka","sequence":"additional","affiliation":[]},{"given":"Ryszard","family":"Winiarczyk","sequence":"additional","affiliation":[]}],"member":"37438","reference":[{"issue":"4","key":"1","doi-asserted-by":"crossref","first-page":"42305","DOI":"10.1103\/PhysRevA.72.042305","article-title":"Higher-order perturbation theory for decoherence in Grover's algorithm","volume":"72","author":"H. Azuma","year":"2005","journal-title":"Physical Review A"},{"issue":"6","key":"2","doi-asserted-by":"crossref","first-page":"4363","DOI":"10.1103\/PhysRevA.60.4363","article-title":"Decoherence and programmable quantum computation","volume":"60","author":"J. Barnes","year":"1999","journal-title":"Physical Review A"},{"key":"3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511535048","volume-title":"Geometry of Quantum States. An Introduction to Quantum Entanglement","author":"I. Bengtsson","year":"2006"},{"key":"4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04209-0","volume-title":"The Physics of Quantum Information: Quantum Cryptography, Quantum Teleportation, Quantum Computation","author":"D. Bouwmeester","year":"2000"},{"issue":"2","key":"5","first-page":"143","article-title":"Quantum search","volume":"13","author":"S. Bugajski","year":"2001","journal-title":"Archiwum Informatyki Teoretycznej i Stosowanej"},{"issue":"1","key":"6","doi-asserted-by":"crossref","first-page":"77","DOI":"10.2478\/v10175-010-0008-4","article-title":"Extending scientific computing system with structural quantum programming capabilities","volume":"58","author":"P. Gawron","year":"2010","journal-title":"Bulletin of the Polish Academy of Sciences: Technical Sciences"},{"key":"7","first-page":"212","article-title":"A fast quantum mechanical algorithm for database search","author":"L. Grover","year":"1996"},{"issue":"2","key":"8","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","article-title":"Quantum mechanics helps in searching for a needle in a haystack","volume":"79","author":"L. Grover","year":"1997","journal-title":"Physical Review Letters"},{"key":"9","first-page":"53","article-title":"A framework for fast quantum mechanical algorithms","author":"L. Grover","year":"1998"},{"key":"10","volume-title":"Noisy Grover's Searching Algorithm","author":"C. Konstadakis","year":"2001"},{"issue":"4","key":"11","doi-asserted-by":"crossref","first-page":"42305","DOI":"10.1103\/PhysRevA.61.042305","article-title":"Dominant gate imperfection in Grover's quantum search algorithm","volume":"61","author":"G. Long","year":"2000","journal-title":"Physical Review A"},{"key":"12","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"1999"},{"issue":"1","key":"13","doi-asserted-by":"crossref","first-page":"12301","DOI":"10.1103\/PhysRevA.61.012301","article-title":"Noise in Grover's quantum search algorithm","volume":"61","author":"B. Pablo-Norman","year":"1999","journal-title":"Physical Review A"},{"issue":"2","key":"14","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1140\/epjd\/e2007-00295-1","article-title":"Noise effect on Grover algorithm","volume":"46","author":"P. Salas","year":"2008","journal-title":"The European Physical Journal D"},{"issue":"4","key":"15","doi-asserted-by":"crossref","first-page":"42301","DOI":"10.1103\/PhysRevA.67.042301","article-title":"Effect of unitary noise on Grover's quantum search algorithm","volume":"67","author":"D. Shapira","year":"2003","journal-title":"Physical Review A"},{"issue":"5","key":"16","doi-asserted-by":"crossref","first-page":"52313","DOI":"10.1103\/PhysRevA.68.052313","article-title":"Effects of a random noisy oracle on search algorithm complexity","volume":"68","author":"N. Shenvi","year":"2003","journal-title":"Physical Review A"},{"issue":"2","key":"17","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1140\/epjd\/e2006-00046-x","article-title":"Dissipative decoherence in the Grover algorithm","volume":"38","author":"O. Zhirov","year":"2006","journal-title":"The European Physical Journal D"}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/22\/2\/article-p493.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/view\/j\/amcs.2012.22.issue-2\/v10006-012-0037-2\/v10006-012-0037-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:27:25Z","timestamp":1709202445000},"score":1,"resource":{"primary":{"URL":"https:\/\/content.sciendo.com\/doi\/10.2478\/v10006-012-0037-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,1]]},"references-count":17,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.2478\/v10006-012-0037-2","relation":{},"ISSN":["1641-876X"],"issn-type":[{"value":"1641-876X","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6,1]]}}}