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/0609168

Quantum search with variable times

Andris Ambainis

Published Sep 21, 2006• 1 citation
arXivHTMLPDF

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 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.

DOI
10.48550/arxiv.quant-ph/0609168

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 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.

Theory of Computing Systems•Jun 2, 2009•40 citations

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.

arXiv:2302.06749•Leibniz international proceedings in informatics•Jan 1, 2023•3 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.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Sep 28, 2016•0 citations

An 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 described by an N dimensional Hilbert space with a Hamiltonian of the form $E |w >< w|$ where $| w>$ is an unknown (normalized) state. We show how to discover $| w >$ by adding a Hamiltonian (independent of $| w >$) and evolving for a time proportional to $N^{1/2}/E$. We show that this time is optimally short. This process is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer which locates a marked item from an unsorted list of N items in a number of steps proportional to $N^{1/2}$.

arXiv:quant-ph/9612026•Dec 6, 1996•15 citations

A Grover-based quantum search of optimal order for an unknown number of marked elements

Christof Zalka

We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.

arXiv:quant-ph/9902049•Feb 12, 1999•9 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}$.

Physical Review A•Apr 1, 1998•382 citations
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 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(t12+t22+…+tn2)O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})O(t12​+t22​+…+tn2​​) 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.
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(Tlog⁡n)O(\sqrt{T}\log n)O(T​logn) where T=∑i=1nti2T=\sum_{i=1}^n t_i^2T=∑i=1n​ti2​ with tit_iti​ denoting the time to check the iii-th item. Our second result is a quantum lower bound of Ω(Tlog⁡T)Ω(\sqrt{T\log T})Ω(TlogT​). Both the algorithm and the lower bound improve over previously known results by a factor of log⁡T\sqrt{\log T}logT​ but the algorithm is also substantially simpler than the previously known quantum algorithms.
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 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 described by an N dimensional Hilbert space with a Hamiltonian of the form E∣w><w∣E |w >< w|E∣w><w∣ where ∣w>| w>∣w> is an unknown (normalized) state. We show how to discover ∣w>| w >∣w> by adding a Hamiltonian (independent of ∣w>| w >∣w>) and evolving for a time proportional to N1/2/EN^{1/2}/EN1/2/E. We show that this time is optimally short. This process is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer which locates a marked item from an unsorted list of N items in a number of steps proportional to N1/2N^{1/2}N1/2.
We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.
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∣E|w〉〈w|E∣w〉〈w∣ where ∣w〉|w〉∣w〉 is an unknown (normalized) state. The problem is to produce ∣w〉|w〉∣w〉 by adding a Hamiltonian (independent of ∣w〉)|w〉)∣w〉) and evolving the system. If ∣w〉|w〉∣w〉 is chosen uniformly at random we can (with high probability) produce ∣w〉|w〉∣w〉 in a time proportional to N1/2/E{N}^{1/2}/EN1/2/E. If ∣w〉|w〉∣w〉 is instead chosen from a fixed, known orthonormal basis we can also produce ∣w〉|w〉∣w〉 in a time proportional to N1/2/E{N}^{1/2}/EN1/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 NNN items in a number of steps proportional to N1/2{N}^{1/2}N1/2.