00748nas a2200157   4500000000100000000000100001000000100002008004100003100001700044700001700061700002300078245009700101300001400198490000700212520037100219       2012                            d1 aPiotr Gawron1 aJerzy Klamka1 aRyszard Winiarczyk00aNoise effects in the quantum search algorithm from the viewpoint of computational complexity  a493–4990 v223 aWe 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 computational complexity of the quantum search algorithm. We show that only for small amounts of noise the quantum search algorithm is still more efficient than any classical algorithm.