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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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".

Improve this answer
$\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$
    – nicolopinci
    Feb 28, 2021 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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