Status of our algorithm

[Lior Eldar]

Peter Shor and myself would like to share the status of our proposed algorithm:

Our algorithm to solve BDD(L,v) consists of 3 main components:

(1) Reduction of L* (dual of L) to systematic normal form ==> L'

(2) Generating a quantum super-position of small variance around a random dual point of L'

(3) Applying a Hadamard test on the super-position w.r.t. a phase-shift by the input vector v .

Having simplified step (3) significantly (thanks to Oded Regev for this) it is apparent that in its current form

the algorithm is completely classical.  Furthermore, we can even show that if v is in L^* it will even return

an answer that is independent of the input. Thus in it's current form, as a classical algorithm, our proposed method cannot work.

However, we are not nearly as sure about its behavior when used in conjunction with techniques that are "crucially quantum".

While we are still investigating such techniques, we plan to post soon a version summarizing the other techniques we are confident about, 

as well as some unpublished result about a special lattice-preserving quantum Fourier transform on SysNF lattices, that may

come in handy for a quantum algorithm.