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

International Conference on Natural Computation (ICNC)

Some quantum search algorithms for arbitrary initial amplitude distribution

Hiromi Miyajima, Noritaka Shigei, Keisuke Arima

Published Aug 1, 2010• 4 citations
Publisher

Abstract

For searching any item in an unsorted database with N items, Grover's quantum searching algorithm takes only O(√N) steps, which is much faster than O(N) steps required for a classical computer. However, it is known that Grover's algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform. On the other hand, Ventura has also proposed a quantum searching algorithm. The algorithm is effective only in the special case for the initial amplitude distribution. Therefore, we have proposed an effective quantum searching algorithm in another case in the previous paper. In this paper, we generalize the previous algorithm and propose several effective algorithms in several cases where initial amplitude distributions of dataset are non-uniform. Further, in order to show the effectiveness of the algorithms, we analyze their dynamics.

DOI
10.1109/icnc.2010.5583154

Related papers

A Proposal of a Quantum Search Algorithm

Keisuke Arima, Noritaka Shigei, Hiromi Miyajima

For searching an unsorted database with N items, a classical computer requires O(N) steps but Grover's quantum searching algorithm requires only O(¿N) steps. However, it is also known that Grover's algorithm is effective in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the non-uniform case. In this paper, we will consider the influence of initial amplitude distribution of dataset for Grover's and Ventura's algorithms. Further, in order to improve the performance of quantum searching, we propose a new algorithm and analyze its dynamics.

International Conference on Computer Sciences and Convergence Information Technology•Jan 1, 2009•11 citations

Data Search Algorithms based on Quantum Walk

Masataka Fujisaki, Hiromi Miyajima, Noritaka Shigei

For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.

Lecture notes in computer science•Jan 1, 2012•2 citations

Analysis of Quantum Search Algorithms for Arbitrary Amplitude Distribution

Huifang Li

The problem of Grover's and Ventura's algorithms are not effective in any arbitrary amplitude distribution are studied.First,combining with the characteristics of quantum computing,a new algorithm is proposed and its amplitude dynamics with recursive function are analyzed.Further,a simulation with Matlab to compare the performance of three algorithms are made.Finally,the conclusion that the proposed algorithm can make up for Grover's and Ventura's deficiencies.If the value of m in advance is known,the appropriate algorithm to increase the probability of success can be seected.

Science Technology and Engineering•Jan 1, 2011•0 citations

Generalized Grover Search Algorithm for Arbitrary Initial Amplitude Distribution

David Biron, Ofer Biham, Eli Biham +2 more

Grover's algorithm for quantum searching of a database is generalized to deal with arbitrary initial amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the r marked and N-r unmarked states. These equations are solved exactly. An expression for the optimal measurement time T \sim O(\sqrt{N/r}) is derived which is shown to depend only on the initial average amplitudes of the marked and unmarked states. A bound on the probability of measuring a marked state is derived, which depends only on the standard deviation of the initial amplitude distributions of the marked or unmarked states.

arXiv:quant-ph/9801066•Jan 28, 1998•3 citations

Quantum search algorithm by adiabatic evolution under a priori probability

Zhaohui Wei, Mingsheng Ying

Grover's algorithm is one of the most important quantum algorithms, which performs the task of searching an unsorted database without a priori probability. Recently the adiabatic evolution has been used to design and reproduce quantum algorithms, including Grover's algorithm. In this paper, we show that quantum search algorithm by adiabatic evolution has two properties that conventional quantum search algorithm doesn't have. Firstly, we show that in the initial state of the algorithm only the amplitude of the basis state corresponding to the solution affects the running time of the algorithm, while other amplitudes do not. Using this property, if we know a priori probability about the location of the solution before search, we can modify the adiabatic evolution to make the algorithm faster. Secondly, we show that by a factor for the initial and finial Hamiltonians we can reduce the running time of the algorithm arbitrarily. Especially, we can reduce the running time of adiabatic search algorithm to a constant time independent of the size of the database. The second property can be extended to other adiabatic algorithms.

arXiv:quant-ph/0412117•Dec 15, 2004•3 citations

Grover’s quantum search algorithm for an arbitrary initial amplitude distribution

Eli Biham, Ofer Biham, David Biron +2 more

Grover's algorithm for quantum searching is generalized to deal with arbitrary initial complex amplitude distributions. First-order linear difference equations are found for the time evolution of the amplitudes of the marked and unmarked states. These equations are solved exactly. New expressions are derived for the optimal time of measurement and the maximal probability of success. They are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments. Our results imply that Grover's algorithm is robust against modest noise in the amplitude initialization procedure.

arXiv:quant-ph/9807027•Physical Review A•Oct 1, 1999•119 citations
For searching any item in an unsorted database with N items, Grover's quantum searching algorithm takes only O(√N) steps, which is much faster than O(N) steps required for a classical computer. However, it is known that Grover's algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform. On the other hand, Ventura has also proposed a quantum searching algorithm. The algorithm is effective only in the special case for the initial amplitude distribution. Therefore, we have proposed an effective quantum searching algorithm in another case in the previous paper. In this paper, we generalize the previous algorithm and propose several effective algorithms in several cases where initial amplitude distributions of dataset are non-uniform. Further, in order to show the effectiveness of the algorithms, we analyze their dynamics.
For searching an unsorted database with N items, a classical computer requires O(N) steps but Grover's quantum searching algorithm requires only O(¿N) steps. However, it is also known that Grover's algorithm is effective in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the non-uniform case. In this paper, we will consider the influence of initial amplitude distribution of dataset for Grover's and Ventura's algorithms. Further, in order to improve the performance of quantum searching, we propose a new algorithm and analyze its dynamics.
For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.
The problem of Grover's and Ventura's algorithms are not effective in any arbitrary amplitude distribution are studied.First,combining with the characteristics of quantum computing,a new algorithm is proposed and its amplitude dynamics with recursive function are analyzed.Further,a simulation with Matlab to compare the performance of three algorithms are made.Finally,the conclusion that the proposed algorithm can make up for Grover's and Ventura's deficiencies.If the value of m in advance is known,the appropriate algorithm to increase the probability of success can be seected.
Grover's algorithm for quantum searching of a database is generalized to deal with arbitrary initial amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the r marked and N-r unmarked states. These equations are solved exactly. An expression for the optimal measurement time T \sim O(\sqrt{N/r}) is derived which is shown to depend only on the initial average amplitudes of the marked and unmarked states. A bound on the probability of measuring a marked state is derived, which depends only on the standard deviation of the initial amplitude distributions of the marked or unmarked states.
Grover's algorithm is one of the most important quantum algorithms, which performs the task of searching an unsorted database without a priori probability. Recently the adiabatic evolution has been used to design and reproduce quantum algorithms, including Grover's algorithm. In this paper, we show that quantum search algorithm by adiabatic evolution has two properties that conventional quantum search algorithm doesn't have. Firstly, we show that in the initial state of the algorithm only the amplitude of the basis state corresponding to the solution affects the running time of the algorithm, while other amplitudes do not. Using this property, if we know a priori probability about the location of the solution before search, we can modify the adiabatic evolution to make the algorithm faster. Secondly, we show that by a factor for the initial and finial Hamiltonians we can reduce the running time of the algorithm arbitrarily. Especially, we can reduce the running time of adiabatic search algorithm to a constant time independent of the size of the database. The second property can be extended to other adiabatic algorithms.
Grover's algorithm for quantum searching is generalized to deal with arbitrary initial complex amplitude distributions. First-order linear difference equations are found for the time evolution of the amplitudes of the marked and unmarked states. These equations are solved exactly. New expressions are derived for the optimal time of measurement and the maximal probability of success. They are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments. Our results imply that Grover's algorithm is robust against modest noise in the amplitude initialization procedure.