You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operati

You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operations, instead of a single run taking n^2 operations. This reduction can be implemented on a classical computer in polynomial time. They also require more qubits per run, n^1.5 instead of n but it is unclear to me whether this comes from n*sqrt(n), i.e., sqrt(n) paralel runs on n qubits, or that each run requires n^1.5 qubits. I would expect the first. So, the quantum part of the algorithm still requires n^2 gates, but the improvement is that it is split up (and non-adaptability). This means that it can be run in parallel, and that the individual runs will have less problems with errors stacking due to circuit depth. Note that the classical overhead for the reduction might be relatively high. Original paper: https://arxiv.org/pdf/2308.06572.pdf https://arxiv.org/pdf/2308.06572.pdf