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

DOI10.2478/V10006-012-0037-2zbMATH Open1285.81012arXiv1108.1915OpenAlexW2079714474WikidataQ62582396 ScholiaQ62582396MaRDI QIDQ5403382FDOQ5403382

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometry of Quantum States
• Title not available (Why is that?)

Cited In (21)

• 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
• Matrix algebra for quantum search algorithm: non unitary symmetries and entanglement

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)