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

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.

Show thread

@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

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.