Speedup of iterated quantum search by parallel performance

Yuri Ozhigov

paper

Speedup of iterated quantum search by parallel performance

arXiv:quant-ph/9904039

Abstract

Given a sequence $f_{1} (x_{1}), f_{2} (x_{1}, x_{2}), ..., f_{k} (x_{1}, ..., x_{k})$ of Boolean functions, each of which $f_{i}$ takes the value 1 in a single point of the form $x_{1}^{0}, x_{2}^{0}, ..., x_{i}^{0}, i = 1, 2, ..., k$ . A length of all $x_{i}^{0}$ is $n, N = 2^{n}$ . It is shown how to find $x_{k}^{0} (k \geq 2)$ using \frac{kπ\sqrt{N}}{4\sqrt{2}} $s im u l t an eo u se v a l u a t i o n so f f u n c t i o n so f t h e f or m$ f_i, f_{i+1} $w i t han er r or p r o babi l i t y o f or d er$ k/\sqrt{N} $w hi c hi s$ \sqrt{2} $t im es a s f a s t a s b y t h e$ k $se q u e n t ia l a ppl i c a t i o n so f G r o v er a l g or i t hm f or t h e q u an t u m se a r c h . E v o l u t i o n so f am pl i t u d es in p a r a l l e l q u an t u m co m p u t a t i o n s a r e a pp r o x ima t e d b y sy s t e m so f l in e a r d i f f er e n t ia l e q u a t i o n s . S o m e a d v an t a g eo f s im u l t an eo u se v a l u a t i o n so f a l l$ f_1 ,... f_k$ are discussed.

Latex, 21 pages, no figures, simplification of the proof

Speedup of iterated quantum search by parallel performance

Abstract

References in corpus (20)

Cited by in corpus (2)