2
$\begingroup$

I have come through an interesting paper by Don Coppersmith (https://arxiv.org/pdf/quant-ph/0201067.pdf), and I was wondering what was your view on the $Q_{JK}$ ("twiddle") transformation, which is defined as:

$\omega^{2^{L-1-J+K}}$

How can the matrices be obtained on the basis of this definition? Substituting the terms in the equation itself is trivial, but determining the position inside the matrix is something more challenging, at least for me. Which kind of operation allow to obtain the matrix $P_1Q_{12}$ given the two initial matrices?

Thank you in advance for your time.

$\endgroup$
2
$\begingroup$

I think (but have not carefully checked) that the construction being described in this paper is essentially the same as the one from this blog post which has clearer figures:

multiplication

The structure of the recursion used above means that the phasing inside the recursive cases uses angles that are the square roots of angles used in the outer case (instead of angles that are merely twice as large). This allows truncating the phase gates to be done more aggressively.

enter image description here

I guess what I'm saying is that the operation they are describing is "phase by an amount proportional to the multiplication of two registers".

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, which is very interesting. I think it is not exactly the same algorithm, since Coppersmith uses Knuth's proposal, but it is certainly something interesting to think about. $\endgroup$ Feb 28 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.