 |
|
| Science Forum Index » Physics - Research Forum » Proposed quantum algorithm for inverting one-way... |
|
Page 1 of 1 |
|
| Author |
Message |
| Lou Pagnucco... |
 Posted: Thu Oct 15, 2009 9:41 pm |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
|
|
| Lou Pagnucco... |
| Posted: Sun Oct 18, 2009 8:23 am |
|
|
|
Guest
|
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... at (no spam) htdconnect.com> wrote:
[quote:2789e1e379]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.[/quote:2789e1e379] |
|
|
| Back to top |
|
|
|
| Lou Pagnucco... |
| Posted: Sun Oct 18, 2009 9:31 pm |
|
|
|
Guest
|
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... at (no spam) htdconnect.com> wrote:
[quote]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.
[...][/quote] |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Nov 28, 2009 9:27 am
|
|