|
related topics |
{let, theorem, proof} |
{algorithm, log, probability} |
{operator, operators, space} |
{state, algorithm, problem} |
{classical, space, random} |
{qubit, qubits, gate} |
{cos, sin, state} |
|
Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule
Mario Szegedy
abstract: We introduce quantized bipartite walks, compute their spectra, generalize the
algorithms of Grover \cite{g} and Ambainis \cite{amb03} and interpret them as
quantum walks with memory. We compare the performance of walk based classical
and quantum algorithms and show that the latter run much quicker in general.
Let $P$ be a symmetric Markov chain with transition probabilities $P[i,j]$, $(i
,j\in [n])$. Some elements of the state space are marked. We are promised that
the set of marked elements has size either zero or at least $\epsilon n$. The
goal is to find out with great certainty which of the above two cases holds.
Our model is a black box that can answer certain yes/no questions and can
generate random elements picked from certain distributions. More specifically,
by request the black box can give us a uniformly distributed random element for
the cost of $\wp_{0}$. Also, when ``inserting'' an element $i$ into the black
box we can obtain a random element $j$, where $j$ is distributed according to
$P[i,j]$. The cost of the latter operation is $\wp_{1}$. Finally, we can use
the black box to test if an element $i$ is marked, and this costs us $\wp_{2}$.
If $\delta$ is the eigenvalue gap of $P$, there is a simple classical algorithm
with cost $O(\wp_{0} + (\wp_{1}+\wp_{2})/\delta\epsilon)$ that solves the above
promise problem. (The algorithm is efficient if $\wp_{0}$ is much larger than
$\wp_{1}+\wp_{2}$.) In contrast,we show that for the ``quantized'' version of
the algorithm it costs only $O(\wp_{0} +
(\wp_{1}+\wp_{2})/\sqrt{\delta\epsilon})$ to solve the problem. We refer to
this as the $\sqrt{\delta\epsilon}$ rule. Among the technical contributions we
give a formula for the spectrum of the product of two general reflections.
- oai_identifier:
- oai:arXiv.org:quant-ph/0401053
- categories:
- quant-ph
- comments:
- 27pages
- arxiv_id:
- quant-ph/0401053
- created:
- 2004-01-09
Full article ▸
|
|
related documents |
0610235v2 |
0308151v2 |
0605090v1 |
9711062v1 |
0109038v1 |
0003070v1 |
0603206v1 |
0503159v2 |
0212096v1 |
0406072v1 |
0302022v1 |
0702212v1 |
0701037v2 |
0410229v1 |
0606077v1 |
0604091v1 |
0411027v1 |
0407179v1 |
0502040v2 |
0406226v1 |
0412157v1 |
0506062v2 |
0404051v4 |
0407227v3 |
0609220v1 |
|