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!
@elilevensonfalk @punk_physicist From the conclusion: “It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.” 🤔🤔🤔
@Colinvparker @elilevensonfalk that's where my skepticism of this result lies, i.e. the number of times you have to sample grows too fast to be useful/show advantage
So 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.