Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

Question

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is the preferred method. Modular exponentiation is also prominently featured in the quantum factoring algorithm, and it is expensive there as well.

So: why isn't Montgomery modular exponentiation apparently present in current detailed subroutines for quantum factoring?

The only thing I can imagine is that there's a high qubit overhead for some non-obvious reason.

Running montgomery quantum "modular exponentiation" through Google Scholar yields no useful results. I am aware of work by Van Meter and others on quantum addition and modular exponentiation, but examining their references (I have yet to read this work) shows no indication that Montgomery methods are considered there.

The single reference I have found that appears to discuss this is in Japanese, which lamentably I cannot read, though apparently it is from a 2002 conference proceedings. A machine translation yields nuggets appended below that indicate there might be something useful. However, I can't find any indication that this has been followed up, which makes me think that the idea has been a) considered and then b) discarded.

Quantum circuit in performing arithmetic Noboru Kunihiro

...In this study, but requires relatively large qubit, we propose a modular exponentiation circuit quantum computation time is short. Montgomery Reduction [8] and right binary method [9] Combined, they constitute a circuit Ru. Reduction Montgomery is, m randomly chosen as a natural number, mod 2m by the operation, perform the remainder operation If, mod n operations in eliminating. This will lead to reduction of computation time...

Application of 3.2 Montgomery Reduction Montgomery Reduction [8] is formulated as follows...This algorithm can return the correct values can be easily confirmed. M R (Y) he asks for a law 2m Polynomials with 2m points are important and only requires division by. In addition, Montgomery Reduction in, there are different calculation methods....In general, Reduction Montgomery is not one-to-one function...

...The proposed method uses a right binary method, Montgomery Reducton has a feature that is adopted. Than the conventional method, characterized by a small component of the circuit Have. qubit fault that is required to have a lot of expectations can be computed in less computational time Be. The future, Montgomery Reduction and control circuitry specifically NOT described by the qubit really needed Evaluate the number is expected to evaluate the computation time. In addition, each taking advantage of research findings, more than modular exponentiation Non-arithmetic (Euclid mutual division, etc.) also with respect to the planned configuration of an efficient quantum circuit.

...[8] PL Montgomery, "Modular Multiplication Without Trial Division," Mathematics of Computation, 44, 170, pp. 519-521, 1985...

Answer 1

Could you post the original Japanese title/reference?

Also, you might consider just writing to the author - assuming it's the same guy he is a professor at the University of Tokyo:

http://www.it.k.u-tokyo.ac.jp/~kunihiro/

and almost certainly would reply.

Sorry to post this as an answer, it should be a comment but I don't have the rep for that yet apparently...

EDIT: So, I took a look at the original Japanese. As a preface, I am currently a PhD student in the EE department at U. Tokyo, originally from the U.S., and I do technical JA->EN translation as a part-time job. However, this topic area is well outside my comfort zone so please take my opinion with a grain of salt!

Basically the conclusion (4) says:

べき乗剰余演算を行う量子回路を提案した。提案方式は、右向きbinary methodを採用し、Montgomery Reductionを採用するという特徴を持っている。従来の方式よりも、回路の構成要素が少ないという特徴を持っている。qubitが多く必要となるという欠点は持つが、より少ない計算時間で計算ができると期待される。

[In this paper] We proposed a new quantum circuit for computing modular exponentiation. The proposed method utilizes an LR binary method, and is also characterized by use of the Montgomery Reduction. Compared with previous methods, the proposed method requires fewer components to construct the circuit. The proposed method does however, have the drawback of requiring a large number of qubits, but we are confident that it will be computationally efficient ( lit: require very little computation time ).

I tried searching for related follow-up papers in both English and Japanese but was unsuccessful. My guess is that the approach proved unsuccessful, or the professor got busy with something else (looks like this was around when he switched universities).

I think that your best bet at this point, assuming you want to follow up the rest of the way and get a concrete answer, is to write professor Kunihiro directly (in English!)

Answer 2

I also wondered about this question, since the current approaches to modular multiplication for quantum factoring use either a trial subtraction if there is an overflow after every addition, or a division/subtraction approach at the end. Both of these seem wasteful.

I am working on a quantum architecture for performing modexp using Montgomery multiplication right now. I don't think the space overhead should be any greater than previous approaches, but I see no need to use Karatsuba multiplication currently.

Montgomery multiplication in binary is quite efficient (bit-shifting and addition). The addition of the modulus and the shifted sums depend on the least significant bit (LSB) at each step, so this seems to require before them serially, to get O(n) time.

However, you can parallelize this dependency on the LSB by using function tables and composing/narrowing them similar to carry-lookahead approaches or Kitaev's description of parallel finite automata in his book (Kitaev, Shen, Vyalyi 2002). This step almost certainly requires a lot of ancillae, but asymptotically it could be made O(log n)-depth.