Prev: Difference between an array, list, vector, and a tuple.
Next: ATT/TEL=FIBER
From: Lou Pagnucco on 16 Oct 2009 03:41


I would like to modify a framework for structured quantum search
first suggested by Kastella-Freeling (preprint quant-ph/0109087),
perhaps correcting a flaw in their approach.

The algorithm inverts one-way permutations in apparent poly-time
(and, with modification, some other one-way functions). Since
this is pretty implausible, it probably includes a stage requiring
exp-time I've overlooked. I would appreciate help finding it.


OBJECTIVE: Given a poly-time computable one-way permutation f:S-->S
=========
S = {0,1,2,...,(2^n)-1} the n-bit binary numbers < 2^n = N

Find the unique marked item 'Z' such that f(Z) = N-1

Our Hilbert space = span{|0>,|1>,...,|N-1>} (normalized kets)


ALGORITHM
=========
Define:

bit(k,x) = bit weighted by 2^k in binary bit expansion of x

I = NxN identity matrix

D(k) = NxN diagonal matrix for which D(k)[j,j] = bit(k,f(j))

d(k) = D(k)*D(k-1)*...*D(1)*D(0)

|u> = (|0>+|1>+...+|N-1>)/sqrt(N) uniform superposition

U = |u><u|

[A,B] = A*B - B*A the matrix commutator

M(0) = U
M(k+1) = M(k) - [[M(k),D(k)],D(k)] for k = 0,1,...,n-2

Q(k) = [(2^(k+1))*M(k) - (1+i)*I]/sqrt(2)
F(k) = I + (i-1)*d(k)

CLAIM: |z> = Q(n-1)*F(n-1)*...*Q(1)*F(1)*Q(0)*F(0)*|u>


NOTES
=====

(1) The amplitude of the |z> component doubles each iteration.

(2) Q(k)*F(k) are "sure-success" quantum search unitaries for
the case when fraction of "marked states" = 1/2. See
"A family of sure-success quantum algorithms for solving a
generalized Grover search problem" (arXiv:quant-ph/0210201)

(3) Each M(k) is the sum of weighted orthogonal projectors, each
with dimension = N/(2^k). Each projector in M(k) is
orthogonally split in M(k+1).

(4) All diagonal matrices above are clearly poly-time simulatable.

(5) If A and B are poly-time simulatable hamiltonians, then A+B and
[A,B] are also. So the Q(k), F(k) unitaries should be poly-time.

(6) Assuming "f(z)=N-1" does not cost any generality.

(7) This approach appears to work for some other one-way functions
(with restricted distributions) if the Q(k)*F(k) pairs are
replaced with poly-time simulatable adiabatic evolutions.


From: Lou Pagnucco on 18 Oct 2009 14:23
I withdraw this question.

While the commutation operation in the recursion preserves poly-time
computability, the entire recursion clearly requires an exponential
numbers of steps.

On Oct 16, 3:41�am, Lou Pagnucco <pagnu...(a)htdconnect.com> wrote:
> I would like to modify a framework for structured quantum search
> first suggested by Kastella-Freeling (preprint �quant-ph/0109087),
> perhaps correcting a flaw in their approach.
>
> The algorithm inverts one-way permutations in apparent poly-time
> (and, with modification, some other one-way functions). �Since
> this is pretty implausible, it probably includes a stage requiring
> exp-time I've overlooked. � I would appreciate help finding it.
From: Lou Pagnucco on 19 Oct 2009 03:31

An obvious point at which exp-time is required that I overlooked
is in the recursion - so it is clear this algorithm does not
provide speed up.

On Oct 16, 3:41�am, Lou Pagnucco <pagnu...(a)htdconnect.com> wrote:
> I would like to modify a framework for structured quantum search
> first suggested by Kastella-Freeling (preprint �quant-ph/0109087),
> perhaps correcting a flaw in their approach.
>
> The algorithm inverts one-way permutations in apparent poly-time
> (and, with modification, some other one-way functions). �Since
> this is pretty implausible, it probably includes a stage requiring
> exp-time I've overlooked. � I would appreciate help finding it.
>
[...]


 | 
Pages: 1
Prev: Difference between an array, list, vector, and a tuple.
Next: ATT/TEL=FIBER