10
$\begingroup$

In other words, will factoring research remain solely in the classical world or are there interesting research on-going in the quantum world related to factoring?

$\endgroup$
  • 1
    $\begingroup$ knowing one algorithm to solve the problem efficiently does not mean that there aren't other algorithms to be found that are better (either in general or in specific circumstances) $\endgroup$ – glS Feb 12 at 9:57
  • 2
    $\begingroup$ Are you asking whether Shor's algorithm has been proven optimal, or are you asking whether research into classical factoring algorithms is still useful? $\endgroup$ – ahelwer Feb 12 at 19:38
  • $\begingroup$ I'm asking the latter. I'm sure the search will continue in the classical world because nobody knows whether a fast solution there exists or not, but how about in quantum computing? Is everyone satisfied with Shor's algorithm to the point of going to other fields? $\endgroup$ – R. Chopin Feb 13 at 18:00
  • 1
    $\begingroup$ I think you mean "will factoring research remain solely in the classical world..." $\endgroup$ – Mark S Feb 21 at 13:16
7
$\begingroup$

Asymptotically, Shor's algorithm is really efficient. Basically it's just: superposition, modular exponentiation (the slowest step), and a fourier transform. Modular exponentiation is what you do to actually use the RSA cryptosystem. That means to a quantum computer, encrypting/decrypting RSA legitimately would be about the same speed as using Shor's algorithm to break the system. So I'm skeptical that there will be any improvements on the basic idea.

That said, any improvement to integer addition, integer multiplication, or the quantum fourier transform would improve Shor's algorithm, and those are all very general subroutines that people will almost certainly work on. A short search on Google Scholar shows lots of research on improving quantum arithmetic circuits.

I think there will be more research on classical/quantum trade-offs in Shor's algorithm. That is, if you have a small or noisy quantum computer, can you modify Shor's algorithm so that it still works, but maybe needs a lot more pre- and post-processing on a classical computer, or maybe has a lower probability of success, etc.? In this area there's Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. There's also the Quantum Number Field Sieve, an approach where a "small" quantum computer (too small to use Shor's algorithm directly) is used as a subroutine of the classical number field sieve, slightly improving the time complexity (though I am personally convinced that error correction for this will require more physical qubits than vanilla Shor's algorithm).

In short, I don't expect any radical new quantum factoring algorithms and I don't think anyone's working on it. But there are a lot of interesting tweaks to be made to fit specific use cases.

$\endgroup$
  • 1
    $\begingroup$ I believe you'll find Post-quantum RSA an interesting read. Thank you very much for the interesting references added in your answer. $\endgroup$ – R. Chopin Feb 23 at 15:27
2
$\begingroup$

As addition to the answer of Sam:

No, partly because Shor's approach is not the only way of factorizing numbers.

Factorization can also be written as an optimization problem.

This can be solved using the D-Wave machine, but also using a gate-based quantum computer.

$\endgroup$
1
$\begingroup$

As a reminder, Shor's algorithm is implemented in the gate model of computation.

As mentioned by @nippon, factoring is can also be described as an optimization problem, which may be solved with an adiabatic algorithm - e.g., by evolving a quantum state to a minimum of $(N-xy)^2$, $x$ and $y$ may be factors of $N$.

The adiabatic algorithm's runtime is, as I understand it, notoriously fickle to be determined, being based on spectral properties of the problem Hamiltonian.

Although numerical simulations have sometimes looked encouraging, I believe it is still an open question as to whether an adiabatic factoring algorithm really provides an exponential speedup over classical factoring.

See more details in this paper by Peng, Liao, Xu, Gan Qin, Zhou, Suter, and Du - their FIG. 3 simulations of the runtime suggest a quadratic fit; however; I'm not sure if any further research on proving such a fit, or providing more evidence of even a polynomial runtime, has taken place.

$\endgroup$

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.