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:quant-ph/9712011 · Physical Review Letters

Quantum Computers Can Search Rapidly by Using Almost Any Transformation

Lov K. Grover

Published May 11, 1998• 617 citations
arXivHTMLPDF

Abstract

A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can adapt to available technology.

DOI
10.1103/physrevlett.80.4329

Related papers

A framework for fast quantum mechanical algorithms

Lov K. Grover

A framework is presented for the design and analysis of quantum mechanical algorithms, the 0( fi) step quantum search algorithm is an immediate consequence of this framework.It leads to several other search-type applications -an example is presented where the Walsh-Hadamard (W-H) transform of the quantum search algorithm is replaced by another transform tailored to the parameters of the problem.Also, it leads to quantum mechanical algorithms for problems not immediately connected with search -two such algorithms are presented for calculating the mean and median of statistical distributions.In order to classically estimate either the mean or median of a given distribution to a precision E , needs a(~-~) steps.The best known quantum mechanical algorithm for estimating the median takes O(E-') steps, and that for estimating the mean takes O(E -1.5 ) steps.This paper presents O(E-l) step algorithms for both problems (all bounds are upto polylogarithmic factors).Both algorithms are considerably simpler than known algorithms.

arXiv:quant-ph/9711043•ACM Symposium on Theory of Computing (STOC)•Jan 1, 1998•246 citations

Realization of generalized quantum searching using nuclear magnetic resonance

Jingfu Zhang, Zhiheng Lu, Shan Lu +1 more

According to the theoretical results, the quantum searching algorithm can be generalized by replacing the Walsh-Hadamard transform by almost any quantum-mechanical operation. We have implemented the generalized algorithm using nuclear magnetic resonance techniques with a solution of chloroform molecules. Experimental results show a good agreement between the theory and experiment.

arXiv:quant-ph/0110076•Physical Review A•Feb 4, 2002•19 citations

Quantum computing and a unified approach to fast unitary transforms

Sos С. Agaian, Andreas Klappenecker

A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.

arXiv:quant-ph/0201120•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 23, 2002•6 citations

QUANTUM SEARCH ALGORITHM CAN BE IMPROVED

Lov K. Grover

Quantum search is a quantum mechanical technique for searching N possibilities in only [Formula: see text] steps. This has been proved to be the best possible algorithm for the exhaustive search problem in the sense that the number of queries it requires cannot be reduced. However, as this paper shows, the number of non-query operations can be reduced by a third without a single increase in the number of queries.

International Journal of Quantum Information•Dec 17, 2004•3 citations

An extention of Grover's quantum search algorithm (Foundations of Computer Science)

Keisuke Tanaka

Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time $O(\sqrt{N})$ with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where $N=2^{n}$ , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is $\Omega(N)$ .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in $O(\sqrt{N})$ time.

数理解析研究所講究録•Apr 1, 2000•0 citations

The Semi-Quantum Computer

Reinaldo O. Vianna, WILSON Ricardo Matos Rabelo, Carlos Henrique Monken

We discuss the performance of the Search and Fourier Transform algorithms on a hybrid computer constituted of classical and quantum processors working together. We show that this semi-quantum computer would be an improvement over a pure classical architecture, no matter how few qubits are available and, therefore, it suggests an easier implementable technology than a pure quantum computer with arbitrary number of qubits.

International Journal of Quantum Information•Jun 1, 2003•1 citation
A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can adapt to available technology.
A framework is presented for the design and analysis of quantum mechanical algorithms, the 0( fi) step quantum search algorithm is an immediate consequence of this framework.It leads to several other search-type applications -an example is presented where the Walsh-Hadamard (W-H) transform of the quantum search algorithm is replaced by another transform tailored to the parameters of the problem.Also, it leads to quantum mechanical algorithms for problems not immediately connected with search -two such algorithms are presented for calculating the mean and median of statistical distributions.In order to classically estimate either the mean or median of a given distribution to a precision E , needs a(~-~) steps.The best known quantum mechanical algorithm for estimating the median takes O(E-') steps, and that for estimating the mean takes O(E -1.5 ) steps.This paper presents O(E-l) step algorithms for both problems (all bounds are upto polylogarithmic factors).Both algorithms are considerably simpler than known algorithms.
A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.
Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time O(N)O(\sqrt{N})O(N​) with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where N=2nN=2^{n}N=2n , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is Ω(N)\Omega(N)Ω(N) .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in O(N)O(\sqrt{N})O(N​) time.