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.” 🤔🤔🤔
Follow
@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
