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

Time evolution of Grover's algorithm with imperfections

Pil Hun Song

Published Oct 21, 2000• 0 citations
OpenAlex

Abstract

We study imperfection effects on time evolution of Grover's algorithm on quantum computer. We introduce an effective two-level model with dissipation and stochasty, which is based upon the idea that ideal Grover's algorithm operates in 2 dimensional Hilbert space. The simulation results of both are compared and it is found that they are in good agreement for appropriately tuned parameters. It turns out that the main features of Grover's algorithm with imperfections can be understood in terms of two basic mechanisms, i.e., a diffusion of probability density into full Hilbert space and a stochastic rotation within the original 2 dimensional Hilbert space.

Related papers

Localization of two-dimensional quantum walks

Norio Inui, Yoshinao Konishi, Norio Konno

The Grover walk, which is related to Grover's search algorithm on a quantum computer, is one of the typical discrete time quantum walks. However, a localization of the two-dimensional Grover walk starting from a fixed point is strikingly different from other types of quantum walks. The present paper explains the reason why the walker who moves according to the degree-four Grover operator can remain at the starting point with a high probability. It is shown that the key factor for the localization is due to the degeneration of eigenvalues of the time evolution operator. In fact, the global time evolution of the quantum walk on a large lattice is mainly determined by the degree of degeneration. The dependence of the localization on the initial state is also considered by calculating the wave function analytically.

arXiv:quant-ph/0311118•Physical Review A•May 19, 2004•154 citations

Effects of stochastic noise on dynamical decoupling procedures

József Zsolt Bernád, Holger Frydrych

Dynamical decoupling is an important tool to counter decoherence and dissipation effects in quantum systems originating from environmental interactions. It has been used successfully in many experiments; however, there is still a gap between fidelity improvements achieved in practice compared to theoretical predictions. We propose a model for imperfect dynamical decoupling based on a stochastic Ito differential equation which could explain the observed gap. We discuss the impact of our model on the time evolution of various quantum systems in finite- and infinite-dimensional Hilbert spaces. Analytical results are given for the limit of continuous control, whereas we present numerical simulations and upper bounds for the case of finite control.

arXiv:1405.1852•Physical Review A•Jun 23, 2014•3 citations

Effects of decoherence and imperfections for quantum algorithms

A. A. Pomeransky, O. V. Zhirov, Dima L. Shepelyansky

We study effects of static inter-qubit interactions and random errors in quantum gates on the stability of various quantum algorithms including the Grover quantum search algorithm and the quantum chaos maps. For the Grover algorithm our numerical and analytical results show existence of regular and chaotic phases depending on the static imperfection strength $ε$. The critical border $ε_c$ between two phases drops polynomially with the number of qubits $n_q$ as $ε_c \sim n_q^{-3/2}$. In the regular phase $(ε< ε_c)$ the algorithm remains robust against imperfections showing the efficiency gain $ε_c / ε$ for $ε> 2^{-n_q/2}$. In the chaotic phase $(ε> ε_c)$ the algorithm is completely destroyed. The results for the Grover algorithm are compared with the imperfection effects for quantum algorithms of quantum chaos maps where the universal law for the fidelity decay is given by the Random Matrix Theory (RMT). We also discuss a new gyroscopic quantum error correction method which allows to reduce the effect of static imperfections. In spite of this decay GYQEC allows to obtain a significant gain in the accuracy of quantum computations.

arXiv:quant-ph/0407264•Jul 30, 2004•4 citations

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•52 citations

Quantum search algorithm

Lukáš Mejdrech

In this work we study Grover's algorithm for quantum computers. This algorithm promises to search in an unstructured database in time comparable with a square root of the number of objects. A description of basic quantum computer principles is followed by the original Grover's formulation and a proof of the algorithm, as well as a later geometrical description of the algorithm. We also mention their suitability for educational purposes. We also include a description of the Grover's algorithm in a programming language, which makes it possible to simulate a quantum computing on classical computers.

•Jan 1, 2007•0 citations

Localization in two-dimensional alternate quantum walks with periodic coin operations

Carlo D. Franco, Mauro Paternostro

The field of quantum computation and quantum simulation has been recently driven to a new rising edge by the experimental realization of quantum walks in various setups, highlighting that different physical systems can be adapted for the implementation of these models. In particular, optical systems have shown their full potential, allowing the experimental demonstration of two-dimensional quantum walks for the first time [1, 2], even if several further progresses will sur ely be obtained also in the other physical scenarios that have been already exploited for the one-dimensional case [3, 4]. From the theoretical point of view, the interest in twodimensional quantum walks has been boosted by the fact that, differently from the one-dimensional version, highe rdimensional schemes (i.e., walkers moving on structures with dimension larger than one) can be exploited for the efficient implementation of quantum search algorithms [5]. In particular, the Grover walk has been intensively studied due to its localization feature [6]. It has been proved that the non localized case of the Grover walk can be simulated by a walk where the requirement of a higher dimensionality of the coin space is substituted with the alternance of the directions i n which the walker can move [7]. In the quest for more feasible quantum walk models, an important step forward is presented in this paper: a strong localization-like effect can be indeed obtained in the modified version of the alternate quantum walk presented here, reducing the gap with the standard two-dimensional version. This result could pave the way for adapting this scheme to the realization of quantum algorithms, providing a clear advantage in terms of experimental resources. After a short introduct ion on the quantum walk studied here, we characterize it in terms of its relevant parameters and show that a proper choice can guarantee a non-negligible probability of finding the walke r at the origin even for large times. We then hint at a qualitative relation between the ability of the system to localize and th e behavior of coherences established in the state of the parti cles performing a two-particle equivalent scheme of the walk, which in turns provides information on the way correlations are set up between them. We discuss the robustness of this model to imperfections and its possible experimental realization with the current state-of-the-art settings in linear o ptics and cold-atom devices. Let us consider a quantum system with two degrees of freedom, and thus described by a vector in the composite Hilbert space H = HW ⊗ HC . The coin space HC is a two-dimensional Hilbert space spanned by {|0i,|1i} and the walker space HW is an infinite-dimensional Hilbert space spanned by {|x,yi}, with x and y assuming all possible integer values. We take as a basis of this space H the set {|x,y,ci}, with |x,y,ci= |x,yiW ⊗ |ciC ; x and y could denote, for instance, the position of a particle ( walker) along the x and y directions, respectively, while |ciC is an internal twolevel degree of freedom. From now on, we consider|0,0iW as the initial state of our walker, and |+yiC = (|0iC+i|1iC)/ √ 2 as the coin one. The evolution of the system is given by a sequence of conditional shift, coin operations, and phase gates. The effec t of the two different conditional shift operations

•Nov 8, 2013•0 citations
We study imperfection effects on time evolution of Grover's algorithm on quantum computer. We introduce an effective two-level model with dissipation and stochasty, which is based upon the idea that ideal Grover's algorithm operates in 2 dimensional Hilbert space. The simulation results of both are compared and it is found that they are in good agreement for appropriately tuned parameters. It turns out that the main features of Grover's algorithm with imperfections can be understood in terms of two basic mechanisms, i.e., a diffusion of probability density into full Hilbert space and a stochastic rotation within the original 2 dimensional Hilbert space.
The Grover walk, which is related to Grover's search algorithm on a quantum computer, is one of the typical discrete time quantum walks. However, a localization of the two-dimensional Grover walk starting from a fixed point is strikingly different from other types of quantum walks. The present paper explains the reason why the walker who moves according to the degree-four Grover operator can remain at the starting point with a high probability. It is shown that the key factor for the localization is due to the degeneration of eigenvalues of the time evolution operator. In fact, the global time evolution of the quantum walk on a large lattice is mainly determined by the degree of degeneration. The dependence of the localization on the initial state is also considered by calculating the wave function analytically.
Dynamical decoupling is an important tool to counter decoherence and dissipation effects in quantum systems originating from environmental interactions. It has been used successfully in many experiments; however, there is still a gap between fidelity improvements achieved in practice compared to theoretical predictions. We propose a model for imperfect dynamical decoupling based on a stochastic Ito differential equation which could explain the observed gap. We discuss the impact of our model on the time evolution of various quantum systems in finite- and infinite-dimensional Hilbert spaces. Analytical results are given for the limit of continuous control, whereas we present numerical simulations and upper bounds for the case of finite control.
We study effects of static inter-qubit interactions and random errors in quantum gates on the stability of various quantum algorithms including the Grover quantum search algorithm and the quantum chaos maps. For the Grover algorithm our numerical and analytical results show existence of regular and chaotic phases depending on the static imperfection strength εεε. The critical border εcε_cεc​ between two phases drops polynomially with the number of qubits nqn_qnq​ as εc∼nq−3/2ε_c \sim n_q^{-3/2}εc​∼nq−3/2​. In the regular phase (ε<εc)(ε< ε_c)(ε<εc​) the algorithm remains robust against imperfections showing the efficiency gain εc/εε_c / εεc​/ε for ε>2−nq/2ε> 2^{-n_q/2}ε>2−nq​/2. In the chaotic phase (ε>εc)(ε> ε_c)(ε>εc​) the algorithm is completely destroyed. The results for the Grover algorithm are compared with the imperfection effects for quantum algorithms of quantum chaos maps where the universal law for the fidelity decay is given by the Random Matrix Theory (RMT). We also discuss a new gyroscopic quantum error correction method which allows to reduce the effect of static imperfections. In spite of this decay GYQEC allows to obtain a significant gain in the accuracy of quantum computations.
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.
In this work we study Grover's algorithm for quantum computers. This algorithm promises to search in an unstructured database in time comparable with a square root of the number of objects. A description of basic quantum computer principles is followed by the original Grover's formulation and a proof of the algorithm, as well as a later geometrical description of the algorithm. We also mention their suitability for educational purposes. We also include a description of the Grover's algorithm in a programming language, which makes it possible to simulate a quantum computing on classical computers.
The field of quantum computation and quantum simulation has been recently driven to a new rising edge by the experimental realization of quantum walks in various setups, highlighting that different physical systems can be adapted for the implementation of these models. In particular, optical systems have shown their full potential, allowing the experimental demonstration of two-dimensional quantum walks for the first time [1, 2], even if several further progresses will sur ely be obtained also in the other physical scenarios that have been already exploited for the one-dimensional case [3, 4]. From the theoretical point of view, the interest in twodimensional quantum walks has been boosted by the fact that, differently from the one-dimensional version, highe rdimensional schemes (i.e., walkers moving on structures with dimension larger than one) can be exploited for the efficient implementation of quantum search algorithms [5]. In particular, the Grover walk has been intensively studied due to its localization feature [6]. It has been proved that the non localized case of the Grover walk can be simulated by a walk where the requirement of a higher dimensionality of the coin space is substituted with the alternance of the directions i n which the walker can move [7]. In the quest for more feasible quantum walk models, an important step forward is presented in this paper: a strong localization-like effect can be indeed obtained in the modified version of the alternate quantum walk presented here, reducing the gap with the standard two-dimensional version. This result could pave the way for adapting this scheme to the realization of quantum algorithms, providing a clear advantage in terms of experimental resources. After a short introduct ion on the quantum walk studied here, we characterize it in terms of its relevant parameters and show that a proper choice can guarantee a non-negligible probability of finding the walke r at the origin even for large times. We then hint at a qualitative relation between the ability of the system to localize and th e behavior of coherences established in the state of the parti cles performing a two-particle equivalent scheme of the walk, which in turns provides information on the way correlations are set up between them. We discuss the robustness of this model to imperfections and its possible experimental realization with the current state-of-the-art settings in linear o ptics and cold-atom devices. Let us consider a quantum system with two degrees of freedom, and thus described by a vector in the composite Hilbert space H = HW ⊗ HC . The coin space HC is a two-dimensional Hilbert space spanned by {|0i,|1i} and the walker space HW is an infinite-dimensional Hilbert space spanned by {|x,yi}, with x and y assuming all possible integer values. We take as a basis of this space H the set {|x,y,ci}, with |x,y,ci= |x,yiW ⊗ |ciC ; x and y could denote, for instance, the position of a particle ( walker) along the x and y directions, respectively, while |ciC is an internal twolevel degree of freedom. From now on, we consider|0,0iW as the initial state of our walker, and |+yiC = (|0iC+i|1iC)/ √ 2 as the coin one. The evolution of the system is given by a sequence of conditional shift, coin operations, and phase gates. The effec t of the two different conditional shift operations