Lov K. Grover
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Lov K. Grover has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Anirvan M. Sengupta
Bell Laboratories, Lucent Technologies, 600-700 Mountain Avenue, Murray Hill, New Jersey 07974
2 shared publications - Apoorva Patel
Centre for High Energy Physics Indian Institute of Science 560012 Bangalore Karnataka India
2 shared publications - Tathagat Tulsi
Department of Physics Indian Institute of Science Bangalore-560012 India
2 shared publications - Vladimir E. Korepin
Stony Brook University
2 shared publications Ben W. Reichardt
EECS Department, Computer Science Division, University of California, Berkeley, California 94720, USA
1 shared publication- Ben W. Reichardt
UC Berkeley
1 shared publication
Latest Publications
- Open Access
A new algorithm for fixed point quantum search
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-$\pi/3$ search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from $\epsilon$ to $\epsilon^{2q+1}$ using $q$ oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-$\pi/3$ search algorithm but much better average-case behavior. Furthermore the new algorithm gives $\epsilon^{2q+1}$ convergence for all integral $q$, whereas the Phase-$\pi/3$ search algorithm requires $q$ to be $(3^{n}-1)/2$ with $n$ a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing.Open AccessA new algorithm for fixed point quantum search
The standard quantum search lacks a feature, enjoyed by many classical algorithms, of having a fixed point, i.e. monotonic convergence towards the solution. Recently a fixed point quantum search algorithm has been discovered, referred to as the Phase-$\pi/3$ search algorithm, which gets around this limitation. While searching a database for a target state, this algorithm reduces the error probability from $\epsilon$ to $\epsilon^{2q+1}$ using $q$ oracle queries, which has since been proved to be asymptotically optimal. A different algorithm is presented here, which has the same worst-case behavior as the Phase-$\pi/3$ search algorithm but much better average-case behavior. Furthermore the new algorithm gives $\epsilon^{2q+1}$ convergence for all integral $q$, whereas the Phase-$\pi/3$ search algorithm requires $q$ to be $(3^{n}-1)/2$ with $n$ a positive integer. In the new algorithm, the operations are controlled by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations applied to these ancillas. It is an example of how measurement can allow us to bypass some restrictions imposed by unitarity on quantum computing. - Open Access
Quantum Algorithms with Fixed Points: The Case of Database Search
The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.Open AccessQuantum Algorithms with Fixed Points: The Case of Database Search
The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction. - 1 February 2006
- Published by Springer Nature in Quantum Information Processing
- Vol. 5 (1) , 5-10
Simple Algorithm for Partial Quantum Search
- 1 February 2006
- Published by Springer Nature in Quantum Information Processing
- Vol. 5 (1) , 5-10
Simple Algorithm for Partial Quantum Search
- 26 October 2005
- Published by American Physical Society (APS) in Physical Review A
- Vol. 72 (4) , 042326
Quantum error correction of systematic errors using a quantum search framework
Composite pulses are a quantum control technique for canceling out systematic control errors. We present a different composite pulse sequence inspired by quantum search. Our technique can correct a wider variety of systematic errors—including, for example, nonlinear over-rotational errors—than previous techniques. Concatenation of the pulse sequence can reduce a systematic error to an arbitrarily small level.
- 26 October 2005
- Published by American Physical Society (APS) in Physical Review A
- Vol. 72 (4) , 042326
Quantum error correction of systematic errors using a quantum search framework
Composite pulses are a quantum control technique for canceling out systematic control errors. We present a different composite pulse sequence inspired by quantum search. Our technique can correct a wider variety of systematic errors—including, for example, nonlinear over-rotational errors—than previous techniques. Concatenation of the pulse sequence can reduce a systematic error to an arbitrarily small level.
- 3 October 2005
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 95 (15) , 150501
Fixed-Point Quantum Search
The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size in only queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of , the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.- 3 October 2005
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 95 (15) , 150501
Fixed-Point Quantum Search
The quantum search algorithm consists of an iterative sequence of selective inversions and diffusion type operations, as a result of which it is able to find a state with desired properties (target state) in an unsorted database of size in only queries. This is achieved by designing the iterative transformations in a way that each iteration results in a small rotation of the state vector in a two-dimensional Hilbert space that includes the target state; if we choose the right number of iterative steps, we will stop just at the target state. This Letter shows that by replacing the selective inversions by selective phase shifts of , the algorithm preferentially converges to the target state irrespective of the step size or number of iterations. This feature leads to robust search algorithms and also to new schemes for quantum control and error correction.- Open Access
Quantum searching amidst uncertainty
Consider a database most of whose entries are marked but the precise fraction of marked entries is not known. What is known is that the fraction of marked entries is 1-X, where X is a random variable that is uniformly distributed in the range (0,X_0) (X_0 is a small number). The problem is to try to select a marked item from the database in a single query. If the algorithm selects a marked item, it succeeds, else if it selects an unmarked item, it makes an error. How low can we make the probability of error? The best possible classical algorithm can lower the probability of error to O((X_0)^2). The best known quantum algorithms for this problem could also only lower the probability of error to O((X_0)^2). Using a recently invented quantum search technique, this paper gives an algorithm that reduces the probability of error to O((X_0)^3). The algorithm is asymptotically optimal.
Open AccessQuantum searching amidst uncertainty
Consider a database most of whose entries are marked but the precise fraction of marked entries is not known. What is known is that the fraction of marked entries is 1-X, where X is a random variable that is uniformly distributed in the range (0,X_0) (X_0 is a small number). The problem is to try to select a marked item from the database in a single query. If the algorithm selects a marked item, it succeeds, else if it selects an unmarked item, it makes an error. How low can we make the probability of error? The best possible classical algorithm can lower the probability of error to O((X_0)^2). The best known quantum algorithms for this problem could also only lower the probability of error to O((X_0)^2). Using a recently invented quantum search technique, this paper gives an algorithm that reduces the probability of error to O((X_0)^3). The algorithm is asymptotically optimal.
- Open Access
Quantum error correction of systematic errors using a quantum search framework
Composite pulses are a quantum control technique for canceling out systematic control errors. We present a new composite pulse sequence inspired by quantum search. Our technique can correct a wider variety of systematic errors -- including, for example, nonlinear over-rotational errors -- than previous techniques. Concatenation of the pulse sequence can reduce a systematic error to an arbitrarily small level.
Open AccessQuantum error correction of systematic errors using a quantum search framework
Composite pulses are a quantum control technique for canceling out systematic control errors. We present a new composite pulse sequence inspired by quantum search. Our technique can correct a wider variety of systematic errors -- including, for example, nonlinear over-rotational errors -- than previous techniques. Concatenation of the pulse sequence can reduce a systematic error to an arbitrarily small level.
- Open Access
Simple Algorithm for Partial Quantum Search
Quite often in database search, we only need to extract portion of the information about the satisfying item. Recently Radhakrishnan & Grover [RG] considered this problem in the following form: the database of $N$ items was divided into $K$ equally sized blocks. The algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. [RG] invented a quantum algorithm for this problem of partial search that took about $0.33\sqrt{N/K}$ fewer iterations than the quantum search algorithm. They also proved that the best any quantum algorithm could do would be to save $0.78 \sqrt(N/K)$ iterations. The main limitation of the algorithm was that it involved complicated analysis as a result of which it has been inaccessible to most of the community. This paper gives a simple analysis of the algorithm. This analysis is based on three elementary observations about quantum search, does not require a single equation and takes less than 2 pages.Open AccessSimple Algorithm for Partial Quantum Search
Quite often in database search, we only need to extract portion of the information about the satisfying item. Recently Radhakrishnan & Grover [RG] considered this problem in the following form: the database of $N$ items was divided into $K$ equally sized blocks. The algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. [RG] invented a quantum algorithm for this problem of partial search that took about $0.33\sqrt{N/K}$ fewer iterations than the quantum search algorithm. They also proved that the best any quantum algorithm could do would be to save $0.78 \sqrt(N/K)$ iterations. The main limitation of the algorithm was that it involved complicated analysis as a result of which it has been inaccessible to most of the community. This paper gives a simple analysis of the algorithm. This analysis is based on three elementary observations about quantum search, does not require a single equation and takes less than 2 pages. - Open Access
A different kind of quantum search
The quantum search algorithm consists of an alternating sequence of selective inversions and diffusion type operations, as a result of which it can find a target state in an unsorted database of size N in only sqrt(N) queries. This paper shows that by replacing the selective inversions by selective phase shifts of Pi/3, the algorithm gets transformed into something similar to a classical search algorithm. Just like classical search algorithms this algorithm has a fixed point in state-space toward which it preferentially converges. In contrast, the original quantum search algorithm moves uniformly in a two-dimensional state space. This feature leads to robust search algorithms and also to conceptually new schemes for error correction.
Open AccessA different kind of quantum search
The quantum search algorithm consists of an alternating sequence of selective inversions and diffusion type operations, as a result of which it can find a target state in an unsorted database of size N in only sqrt(N) queries. This paper shows that by replacing the selective inversions by selective phase shifts of Pi/3, the algorithm gets transformed into something similar to a classical search algorithm. Just like classical search algorithms this algorithm has a fixed point in state-space toward which it preferentially converges. In contrast, the original quantum search algorithm moves uniformly in a two-dimensional state space. This feature leads to robust search algorithms and also to conceptually new schemes for error correction.
- Open Access
Is partial quantum search of a database any easier?
In this paper, we consider the partial database search problem where given a database on N items, we are required to determine the first k bits of an address x such that f(x)=1. We derive an algorithm and a lower bound for this problem in the quantum circuits model. Let q(k,N) be the minimum number of queries needed to find the first k bits of the required address x. We show that there exist constants c_k and d_k such that (pi/4) (1 - d_k/sqrt{K}) sqrt{N} <= q(k,n) <= (pi/4) (1 - c_k/sqrt{K}) sqrt{N}, where K=2^k. Thus, it is always easier to determine a few bits of the target address than to find the entire address, but as k becomes large this advantage reduces rapidly.
Open AccessIs partial quantum search of a database any easier?
In this paper, we consider the partial database search problem where given a database on N items, we are required to determine the first k bits of an address x such that f(x)=1. We derive an algorithm and a lower bound for this problem in the quantum circuits model. Let q(k,N) be the minimum number of queries needed to find the first k bits of the required address x. We show that there exist constants c_k and d_k such that (pi/4) (1 - d_k/sqrt{K}) sqrt{N} <= q(k,n) <= (pi/4) (1 - c_k/sqrt{K}) sqrt{N}, where K=2^k. Thus, it is always easier to determine a few bits of the target address than to find the entire address, but as k becomes large this advantage reduces rapidly.