Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1108.1915 · International Journal of Applied Mathematics and Computer Science

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

Piotr Gawron, Jerzy Klamka, R. Winiarczyk

Published Jun 1, 2012• 25 citations
arXivHTMLPDF

Abstract

Noise effects in the quantum search algorithm from the viewpoint of computational complexity 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.

DOI
10.2478/v10006-012-0037-2

Related papers

Quantum Noise and Information in Quantum Search Algorithm

Demosthenes Ellinas

External influences in the form of quantum noise on Grover’s search algorithm are investigated. The study shows that the algorithm can be robust under such external dissipation. The effect of noise is described by a completely positive trace preserving map, acting on an unsorted N‐dimensional database made of projective density matrices. To evaluate the efficiency of the algorithm two figures of merit are used, the radial fidelity giving the projection between the Bloch vectors of target and final density operators, and the cosine of angular fidelity between the same vectors. Explicitly we prove that the resulting search positive map depends on x, the strength of the coupling to the environment, and that there are infinitely many x values, named good x’s and bad x’s, for which search is successful after O(N) queries, or fails, respectively . Next we study the information theoretic aspects of the dissipative quantum search algorithm. To this end we view the initial state as a pure qubit signal entering through a cascade of quantum channels, each channel described by a completely positive map, and corresponds to the iterations of the algorithm. This map is identical to the dissipative search map of the algorithm for which the parameter x now characterizes the influence of the noisy channel exercised upon the incoming quantum signal. The process of searching is understood as transmission of the initial signal/item through the composite channel made by O(N) elementary channels. The quality of this transmission corresponds to the fidelity of targeting the wanted item in the quantum database, and is studied in terms of the majorization/quantum entropy of the input‐output density matrix, and by the entropy exchanged between the qubit signal/item and an external environment.

AIP conference proceedings•Jan 1, 2004•1 citation

Effect of unitary noise on Grover’s quantum search algorithm

Daniel Shapira, Shay Mozes, Ofer Biham

The effect of unitary noise on the performance of Grover's quantum search algorithm is studied. This type of noise may result from tiny fluctuations and drift in the parameters of the (quantum) components performing the computation. The resulting operations are still unitary, but not precisely those assumed in the design of the algorithm. Here we focus on the effect of such noise in the Hadamard gate W, which is an essential component in each iteration of the quantum search process. To this end W is replaced by a noisy Hadamard gate U. The parameters of U at each iteration are taken from an arbitrary probability distribution (e.g., a Gaussian distribution) and are characterized by their statistical moments around the parameters of W. For simplicity, we assume that the noise is unbiased and isotropic, namely, all noise variables in the parametrization we use have zero average and the same standard deviation $\ensuremath{\epsilon}.$ The noise terms at different calls to U are assumed to be uncorrelated. For a search space of size ${N=2}^{n}$ (where n is the number of qubits used to span this space) it is found that as long as $\ensuremath{\epsilon}<{O(n}^{\ensuremath{-}1/2}{N}^{\ensuremath{-}1/4})$ the algorithm maintains significant efficiency, while above this noise level its operation is hampered completely. It is also found that below this noise threshold, when the search fails, it is likely to provide a state that differs from the marked state by only a few bits. This feature can be used to search for the marked state by a classical postprocessing, even if the quantum search has failed, thus improving the success rate of the search process.

arXiv:quant-ph/0307142•Physical Review A•Apr 1, 2003•49 citations

Noisy Grover's search algorithm

Demosthenes Ellinas, Christos Konstadakis

External environment influences on Grover's search algorithm modeled by quantum noise are investigated. The algorithm is shown to be robust under that external dissipation. Explicitly we prove that the resulting search positive maps acting on unsorted N-dimensional database made of projective density matrices depend on x the strength of the environment, and that there are infinitely many x values for which search is successful after O(\sqrt{N}) queries. These algorithms are quantum entropy increasing.

arXiv:quant-ph/0110010•Oct 1, 2001•1 citation

Noisy Grovers searching algorithm

Demosthenes Ellinas, Christos Konstadakis

External environment influences on Grover’s search algorithm modeled by quantum noise are investigated. The algorithm is shown to be robust under that external dissipation. Explicitly we prove that the resulting search positive maps acting on unsorted N-dimensional database made of projective density matrices depend on x the strength of the environment, and that there are infinitely many x values for which search is successful O ( N ) after queries. These algorithms are quantum entropy increasing.

Optical Fiber Communication Conference•Jan 1, 2001•2 citations

Grover's algorithm on two-way quantum computer

Grzegorz Czelusta, Verma, Dev Rishi, Wanjalkar, Govind

Two-way quantum computing (2WQC) represents a novel approach to quantum computing that introduces a CPT version of state preparation. This paper analyses the influence of this approach on Grover's algorithm and compares the behaviour of typical Grover and its 2WQC version in the presence of noise in the system. Our findings indicate that, in an ideal scenario without noise, the 2WQC Grover algorithm exhibits a constant complexity of $\mathcal{O}(1)$. In the presence of noise, the 2WQC Grover algorithm demonstrates greater resilience to different noise models than the standard Grover's algorithm.

arXiv:2406.09450•Jun 12, 2024•0 citations

Fault-ignorant quantum search

Péter Vrana, David Reeb, Daniel Reitzner +1 more

We investigate the problem of quantum searching on a noisy quantum computer. Taking a fault-ignorant approach, we analyze quantum algorithms that solve the task for various different noise strengths, which are possibly unknown beforehand. We prove lower bounds on the runtime of such algorithms and thereby find that the quadratic speedup is necessarily lost (in our noise models). However, for low but constant noise levels the algorithms we provide (based on Groverʼs algorithm) still outperform the best noiseless classical search algorithm.

arXiv:1307.0771•New Journal of Physics•Jul 24, 2014•10 citations
Noise effects in the quantum search algorithm from the viewpoint of computational complexity 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.
External influences in the form of quantum noise on Grover’s search algorithm are investigated. The study shows that the algorithm can be robust under such external dissipation. The effect of noise is described by a completely positive trace preserving map, acting on an unsorted N‐dimensional database made of projective density matrices. To evaluate the efficiency of the algorithm two figures of merit are used, the radial fidelity giving the projection between the Bloch vectors of target and final density operators, and the cosine of angular fidelity between the same vectors. Explicitly we prove that the resulting search positive map depends on x, the strength of the coupling to the environment, and that there are infinitely many x values, named good x’s and bad x’s, for which search is successful after O(N) queries, or fails, respectively . Next we study the information theoretic aspects of the dissipative quantum search algorithm. To this end we view the initial state as a pure qubit signal entering through a cascade of quantum channels, each channel described by a completely positive map, and corresponds to the iterations of the algorithm. This map is identical to the dissipative search map of the algorithm for which the parameter x now characterizes the influence of the noisy channel exercised upon the incoming quantum signal. The process of searching is understood as transmission of the initial signal/item through the composite channel made by O(N) elementary channels. The quality of this transmission corresponds to the fidelity of targeting the wanted item in the quantum database, and is studied in terms of the majorization/quantum entropy of the input‐output density matrix, and by the entropy exchanged between the qubit signal/item and an external environment.
The effect of unitary noise on the performance of Grover's quantum search algorithm is studied. This type of noise may result from tiny fluctuations and drift in the parameters of the (quantum) components performing the computation. The resulting operations are still unitary, but not precisely those assumed in the design of the algorithm. Here we focus on the effect of such noise in the Hadamard gate W, which is an essential component in each iteration of the quantum search process. To this end W is replaced by a noisy Hadamard gate U. The parameters of U at each iteration are taken from an arbitrary probability distribution (e.g., a Gaussian distribution) and are characterized by their statistical moments around the parameters of W. For simplicity, we assume that the noise is unbiased and isotropic, namely, all noise variables in the parametrization we use have zero average and the same standard deviation $\ensuremath{\epsilon}.$ The noise terms at different calls to U are assumed to be uncorrelated. For a search space of size N=2n{N=2}^{n}N=2n (where n is the number of qubits used to span this space) it is found that as long as $\ensuremath{\epsilon}<{O(n}^{\ensuremath{-}1/2}{N}^{\ensuremath{-}1/4})$ the algorithm maintains significant efficiency, while above this noise level its operation is hampered completely. It is also found that below this noise threshold, when the search fails, it is likely to provide a state that differs from the marked state by only a few bits. This feature can be used to search for the marked state by a classical postprocessing, even if the quantum search has failed, thus improving the success rate of the search process.
External environment influences on Grover's search algorithm modeled by quantum noise are investigated. The algorithm is shown to be robust under that external dissipation. Explicitly we prove that the resulting search positive maps acting on unsorted N-dimensional database made of projective density matrices depend on x the strength of the environment, and that there are infinitely many x values for which search is successful after O(\sqrt{N}) queries. These algorithms are quantum entropy increasing.
External environment influences on Grover’s search algorithm modeled by quantum noise are investigated. The algorithm is shown to be robust under that external dissipation. Explicitly we prove that the resulting search positive maps acting on unsorted N-dimensional database made of projective density matrices depend on x the strength of the environment, and that there are infinitely many x values for which search is successful O ( N ) after queries. These algorithms are quantum entropy increasing.
Two-way quantum computing (2WQC) represents a novel approach to quantum computing that introduces a CPT version of state preparation. This paper analyses the influence of this approach on Grover's algorithm and compares the behaviour of typical Grover and its 2WQC version in the presence of noise in the system. Our findings indicate that, in an ideal scenario without noise, the 2WQC Grover algorithm exhibits a constant complexity of O(1)\mathcal{O}(1)O(1). In the presence of noise, the 2WQC Grover algorithm demonstrates greater resilience to different noise models than the standard Grover's algorithm.
We investigate the problem of quantum searching on a noisy quantum computer. Taking a fault-ignorant approach, we analyze quantum algorithms that solve the task for various different noise strengths, which are possibly unknown beforehand. We prove lower bounds on the runtime of such algorithms and thereby find that the quadratic speedup is necessarily lost (in our noise models). However, for low but constant noise levels the algorithms we provide (based on Groverʼs algorithm) still outperform the best noiseless classical search algorithm.