Follow

Well this seems like a big deal. Quantum algorithm to factor integers using resources (both qubit # and gate depth) that scale sub-linearly! For comparison Shor's algorithm requires O(n) qubits and a gate depth of O(n³).

So claim is RSA-2048 can be broken with 372 qubits and a gate depth of ~1000

@punk_physicist if this is right, it's a big enough deal that I'm kinda shocked it was published!

Brandon Rodenburg, PhD@punk_physicist@qoto.orgSo far my biggest worry is the fact that the authors don't seem to address how many times you have to run the quantum circuit, especially as you scale to larger problem sizes.