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?
$\begingroup$
$\endgroup$
4
-
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 ♦Commented Feb 12, 2019 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$– ahelwerCommented Feb 12, 2019 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. ChopinCommented Feb 13, 2019 at 18:00
-
1$\begingroup$ I think you mean "will factoring research remain solely in the classical world..." $\endgroup$– Mark SpinelliCommented Feb 21, 2019 at 13:16
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
-
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$ Commented Feb 23, 2019 at 15:27
-
$\begingroup$ @SamJaques If we have classical $TC^0$ circuits for modular exponentiation, what would be the impact for quantum computing? $\endgroup$– TurboCommented Jun 15, 2023 at 17:37
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered May 5, 2019 at 14:01