Noise effects in the quantum search algorithm from the viewpoint of computational complexity

DOI10.2478/V10006-012-0037-2MaRDI QIDQ5403382zbMATH OpenOpenAlexWikidataFDO

Authors Piotr Gawron, Jerzy Klamka, Ryszard Winiarczyk

Publication date 26 March 2014

Published in International Journal of Applied Mathematics and Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.1915

zbMATH Keywords

quantum algorithmsalgorithm complexityquantum noise

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: 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 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.

Recommendations

• Fault-ignorant quantum search
• On quantum algorithm for binary search and its computational complexity
• Grover's search with local and total depolarizing channel errors: complexity analysis
• Quantum search degeneration under amplitude noise in queries to the oracle
• Searching a database under decoherence

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1775388 (Why is no real title available?)
• scientific article; zbMATH DE number 1393316 (Why is no real title available?)
• Geometry of Quantum States

Cited in

(21)

• Matrix algebra for quantum search algorithm: non unitary symmetries and entanglement
• The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
• An efficient algorithm for estimating the parameters of superimposed exponential signals in multiplicative and additive noise
• Quantum search degeneration under amplitude noise in queries to the oracle
• A classical limit of Grover's algorithm induced by dephasing: coherence versus entanglement
• Performance of Grover's search algorithm with diagonalizable collective noises
• Quantum computational complexity in curved spacetime
• Search via quantum walks with intermediate measurements
• Qubit flip game on a Heisenberg spin chain
• Noisy Effect on Nonlinear Quantum Search Algorithm
• Fault-ignorant quantum search
• Performance analysis of the hardware-efficient quantum search algorithm
• Noise resistance of adiabatic quantum computation using random matrix theory
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Parametric quantum search algorithm as quantum walk: a quantum simulation
• Noise analysis for the sorkin and Peres tests performed on a quantum computer
• A model for quantum queue
• Characterizing error propagation in quantum circuits: the isotropic index
• Grover's search with local and total depolarizing channel errors: complexity analysis
• Decoherence in Grover search algorithm
• Searching a database under decoherence

This page was built for publication: Noise effects in the quantum search algorithm from the viewpoint of computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5403382)