6
$\begingroup$

In this paper,May and Schlieper claim that one can find the period of a function $f()$ by embedding $h \circ f = h(f(x))$ for input $x$. This would have the immediate consequence of reducing the number of output qubits. What's more, they say that even a one-bit hash function would be enough to run Shor's algorithm and get reasonably good results. This is at the price of performance.

My questions are, how reasonable are these claims? What is the impact on post-quantum RSA security? Post-quantum RSA security is considered by some people as not that worrisome since it requires a non-negligible number of qubits to be practically broken.

$\endgroup$
4
$\begingroup$

My questions are, how reasonable are these claims?

Sounds fairly reasonable; they suggest an alternative factoring algorithm where they trade-off circuit depth to reduce the number of qubits required.

Would this trade-off be a good thing in practice? We don't know. We don't have a large scale quantum computer in front of us, and so we don't know the relative cost of different things, such as how expensive qubits are compared to a longer time to complete the computation (and if your logical qubits aren't perfect, a longer computation implies a larger probability of an intermediate error somewhere).

On the other hand:

What is the impact on post-quantum RSA security? Post-quantum RSA security is considered by some people as not that worrisome since it requires a non-negligible number of qubits to be practically broken.

Even if the number of qubits were the major cost factor in quantum algorithms, this algorithm doesn't reduce them all that much overall. After all, I don't believe we have that good of a view about the size of a quantum computer an adversary might have when they get one; if they did have a 2k logical qubit computer (and so could use this algorithm to factor a 2048 bit number), they could plausibly have a 4k qubit (and so could use standard Shor's). Our ignorance of the size of a quantum computer someone might have is far greater than just a factor of 2.

$\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.