1,721,094 research outputs found
Variable time amplitude amplification and quantum algorithms for linear algebra problems
Full text linkQuantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times.
We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. Our second algorithm tests whether a matrix A is singular or far from singular, faster then the previously known algorithms
Quantum search with variable times
Full text linkSince Grover's seminal work, quantum search has been studied in
great detail. In the usual search problem, we have a collection of
items and we would like to find .
We consider a new variant of this problem in which evaluating
for different may take a different number of time steps.
Let be the number of time steps required to evaluate .
If the numbers 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 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
Quantum Algorithms for Computational Geometry Problems
Full text linkWe study quantum algorithms for problems in computational geometry, such as Point-On-3-Lines problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. Point-On-3-Lines and many other computational geometry problems are known to be 3Sum-Hard. That is, solving them classically requires time Ω(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum problem (in which we are given a set S of n integers and have to determine if there are a, b, c ∈ S such that a + b + c = 0). Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search algorithm. This leads to a question: can we solve Point-On-3-Lines and other 3Sum-Hard problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard geometrical problems
The Power and the Limits of Quantum Automata and Search Algorithms
No full textANOTĀCIJA
Kvantu skaitļošana ir nozare, kas pēta uz kvantu mehānikas likumiem balstīto
skaitļošanas modeļu īpašības. Disertācija ir veltīta kvantu skaitļošanas
algoritmiskiem aspektiem. Piedāvāti rezultāti trijos virzienos:
Kvantu galīgi automāti
Analizēta stāvokļu efektivitāte kvantu vienvirziena galīgam automātam.
Uzlabota labāka zināmā eksponenciālā atšķirība [AF98] starp
kvantu un klasiskajiem galīgajiem automātiem.
Grovera algoritma analīze
Pētīta Grovera algoritma noturība pret kļūdām. Vispārināts [RS08]
loģisko kļūdu modelis un piedāvāti vairāki jauni rezultāti.
Kvantu klejošana
Pētīta meklēšana 2D režģī izmantojot kvantu klejošanu. Paātrināts
[AKR05] kvantu klejošanas meklēšanas algoritms.
Atslēgas vārdi: Kvantu galīgi automāti, eksponenciālā atšķirība, Grovera
algoritms, noturība pret kļūdām, kvantu klejošana
LITERATŪRA
[AF98] A. Ambainis, R. Freivalds.
1-way quantum finite automata: strengths, weaknesses and generalizations.
Proceedings of the 39th IEEE Conference on Foundations of
Computer Science, 332-341, 1998.
arXiv:quant-ph/9802062v3
[AKR05] A. Ambainis, J. Kempe, A. Rivosh.
Coins make quantum walks faster.
Proceedings of SODA’05, 1099-1108, 2005.
[RS08] O. Regev, L. Schiff. Impossibility of a Quantum Speed-up with
a Faulty Oracle.
Proceedings of ICALP’2008, Lecture Notes in Computer Science,
5125:773-781, 2008.ABSTRACT
Quantum computation is the eld that investigates properties of models of
computation based on the laws of the quantum mechanics. The thesis is ded-
icated to algorithmic aspects of quantum computation and provides results
in three directions:
Quantum nite automata
We study space-eciency of one-way quantum nite automata. We
improve best known exponential separation [AF98] between quantum
and classical one-way nite automata.
Analysis of Grover's algorithm
We study fault-tolerance of Grover's algorithm. We generalize the
model of logical faults by [RS08] and present several new results.
Quantum walks
We study search by quantum walks on two-dimensional grid. We im-
prove (speed-up) quantum walk search algorithm by [AKR05].
Keywords: Quantum nite automata, exponential separation, Grover's al-
gorithm, fault-tolerance, quantum walks
BIBLIOGRAPHY
[AF98] A. Ambainis, R. Freivalds.
1-way quantum nite automata: strengths, weaknesses and gen-
eralizations.
Proceedings of the 39th IEEE Conference on Foundations of
Computer Science, 332-341, 1998.
arXiv:quant-ph/9802062v3
[AKR05] A. Ambainis, J. Kempe, A. Rivosh.
Coins make quantum walks faster.
Proceedings of SODA'05, 1099-1108, 2005.
[RS08] O. Regev, L. Schi. Impossibility of a Quantum Speed-up with
a Faulty Oracle.
Proceedings of ICALP'2008, Lecture Notes in Computer
Science, 5125:773-781, 2008
The power of procrastination in inductive inference: How it depends on used ordinal notations
No full text
- …
