Theory of Computing Systems

Quantum Search with Variable Times

Andris Ambainis

Published Jun 2, 2009• 40 citations

Abstract

Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x 1,…,x n and we would like to find i:x i =1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i . If the numbers t i are known in advance, we give an algorithm that solves the problem in $O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})$ steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

DOI: 10.1007/s00224-009-9219-1

Related papers

Quantum search with variable times

Andris Ambainis

arXiv:quant-ph/0609168Sep 21, 20061 citation

Improved Algorithm and Lower Bound for Variable Time Quantum Search

Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs

arXiv:2302.06749Leibniz international proceedings in informaticsJan 1, 20233 citations

Quantum search simulation with Wolfram Mathematica

Alexander N. Prokopenya

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIESep 28, 20160 citations

A Proposal of a Quantum Search Algorithm

Keisuke Arima, Noritaka Shigei, Hiromi Miyajima

International Conference on Computer Sciences and Convergence Information TechnologyJan 1, 200911 citations

Strength and Weakness in Grover's Quantum Search Algorithm

Ahmed Younes

arXiv:0811.4481Nov 27, 200817 citations

Analog analogue of a digital quantum computation

Edward Farhi, Sam Gutmann

Physical Review AApr 1, 1998382 citations

Theory of Computing Systems

Quantum Search with Variable Times

Andris Ambainis

Published Jun 2, 2009• 40 citations

Publisher

Abstract

O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})

steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

DOI: 10.1007/s00224-009-9219-1

Related papers

Quantum search with variable times

Andris Ambainis

Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. If the numbers t_i are known in advance, we give an algorithm that solves the problem in O(\sqrt{t_1^2+t_2^2+...+t_n^2}) steps. This is optimal, as we also show a matching lower bound. The case, when t_i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. If the numbers t_i are known in advance, we give an algorithm that solves the problem in O(\sqrt{t_1^2+t_2^2+...+t_n^2}) steps. This is optimal, as we also show a matching lower bound. The case, when t_i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

arXiv:quant-ph/0609168Sep 21, 20061 citation

Improved Algorithm and Lower Bound for Variable Time Quantum Search

Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs

We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$ denoting the time to check the $i$ -th item. Our second result is a quantum lower bound of $Ω(\sqrt{T\log T})$ . Both the algorithm and the lower bound improve over previously known results by a factor of $\sqrt{\log T}$ but the algorithm is also substantially simpler than the previously known quantum algorithms.We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$ denoting the time to check the $i$-th item. Our second result is a quantum lower bound of $Ω(\sqrt{T\log T})$. Both the algorithm and the lower bound improve over previously known results by a factor of $\sqrt{\log T}$ but the algorithm is also substantially simpler than the previously known quantum algorithms.

arXiv:2302.06749Leibniz international proceedings in informaticsJan 1, 20233 citations

Quantum search simulation with Wolfram Mathematica

Alexander N. Prokopenya

We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIESep 28, 20160 citations

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.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 TechnologyJan 1, 200911 citations

Strength and Weakness in Grover's Quantum Search Algorithm

Ahmed Younes

Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with $N$ records in $O(\sqrt{N})$ assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for $M>3N/4$ , where $M$ is the number of matches in the list.Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with $N$ records in $O(\sqrt{N})$ assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for $M>3N/4$, where $M$ is the number of matches in the list.

arXiv:0811.4481Nov 27, 200817 citations

Analog analogue of a digital quantum computation

Edward Farhi, Sam Gutmann

We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system with a Hamiltonian of the form $E|w〉〈w|$ where $|w〉$ is an unknown (normalized) state. The problem is to produce $|w〉$ by adding a Hamiltonian (independent of $|w〉)$ and evolving the system. If $|w〉$ is chosen uniformly at random we can (with high probability) produce $|w〉$ in a time proportional to ${N}^{1/2}/E$ . If $|w〉$ is instead chosen from a fixed, known orthonormal basis we can also produce $|w〉$ in a time proportional to ${N}^{1/2}/E$ and we show that this time is optimally short. This restricted problem is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer that locates a marked item from an unsorted list of $N$ items in a number of steps proportional to ${N}^{1/2}$ .We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system with a Hamiltonian of the form $E|w〉〈w|$ where $|w〉$ is an unknown (normalized) state. The problem is to produce $|w〉$ by adding a Hamiltonian (independent of $|w〉)$ and evolving the system. If $|w〉$ is chosen uniformly at random we can (with high probability) produce $|w〉$ in a time proportional to ${N}^{1/2}/E$. If $|w〉$ is instead chosen from a fixed, known orthonormal basis we can also produce $|w〉$ in a time proportional to ${N}^{1/2}/E$ and we show that this time is optimally short. This restricted problem is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer that locates a marked item from an unsorted list of $N$ items in a number of steps proportional to ${N}^{1/2}$.

Physical Review AApr 1, 1998382 citations

O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})

O(\sqrt{T}\log n)

where

T=\sum_{i=1}^n t_i^2

with

t_i

denoting the time to check the

i

-th item. Our second result is a quantum lower bound of

Ω(\sqrt{T\log T})

. Both the algorithm and the lower bound improve over previously known results by a factor of

\sqrt{\log T}

but the algorithm is also substantially simpler than the previously known quantum algorithms.

Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with

N

records in

O(\sqrt{N})

assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for

M>3N/4

, where

M

is the number of matches in the list.

We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system with a Hamiltonian of the form

E|w〉〈w|

where

|w〉

is an unknown (normalized) state. The problem is to produce

|w〉

by adding a Hamiltonian (independent of

|w〉)

and evolving the system. If

|w〉

is chosen uniformly at random we can (with high probability) produce

|w〉

in a time proportional to

{N}^{1/2}/E

. If

|w〉

is instead chosen from a fixed, known orthonormal basis we can also produce

|w〉

in a time proportional to

{N}^{1/2}/E

and we show that this time is optimally short. This restricted problem is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer that locates a marked item from an unsorted list of

N

items in a number of steps proportional to

{N}^{1/2}