> The precision in phase needed to perform an accurate QFT scales EXPONENTIALLY with the number of qubits you're trying to transform. This is false. The gates

> The precision in phase needed to perform an accurate QFT scales EXPONENTIALLY with the number of qubits you're trying to transform. This is false. The gates that appear in the textbook QFT circuit (such as the one shown on wikipedia [1]) do mention angles that are exponentially small in N (the number of qubits being operated upon). That may be what's confusing you. But it's well known that the tolerance on those rotations is high, meaning that simply skipping all the exponentially tiny rotations introduces negligible error [2][3]. Here's a simple model. Each time you get a rotation off by an angle of X, add X to the "total algorithm rotation error" R. The chance of an algorithm failing is at most R^2. For example, if R is less than 1 degree then the chance of algorithm failure will be less than 0.03%. That's an acceptable retry chance for Shor's algorithm. The QFT circuit on N qubits performs less than N^2 rotations. So, for R to be less than 1 degree, it's sufficient for each rotation's error X to be less than (1°)/N^2. Therefore the required precision only increases polynomially (like N^2) instead of exponentially (like 2^N). Note the required precision can be improved from O(1/N^2) to O(1/N) using techniques like the qubit recycling QFT [4]. Actually, even if the required precision scaled exponentially, that still wouldn't be an insurmountable problem. Quantum error correction achieves exponentially tighter tolerances from polynomially increasing resources. For example, Ross and Selinger proved that continuous rotations can be approximated to a target error of epsilon using O(log(1/epsilon)) gates from the discrete gate set Clifford+T [4]. And Clifford gates with error below epsilon can be achieved in the surface code using O(log(1/epsilon)^2) noisy qubits for O(log(1/epsilon)) time [5]. And T gates can be achieved by using those reliable Clifford gates to perform magic state distillation of log(1/epsilon)^O(1) T states [6]. Since everything scales polynomially in log(1/epsilon), making epsilon exponentially smaller adds polynomial resources. There is no part of Shor's algorithm that requires resources growing exponentially in n (the number of digits of the number being factored). The practical scaling is more like n^3: factoring a number that's twice as large can be done with ~two times as many qubits running for ~four times as long. Even if the qubits are noisy [7]. [1]: https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/media/File:Q_fourier_nqubits.png https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/med... [2]: https://arxiv.org/abs/quant-ph/0306018 https://arxiv.org/abs/quant-ph/0306018 [3]: https://arxiv.org/abs/quant-ph/9601018 https://arxiv.org/abs/quant-ph/9601018 [4]: https://arxiv.org/pdf/quant-ph/9903071#page=12 https://arxiv.org/pdf/quant-ph/9903071#page=12 [5]: https://arxiv.org/abs/1208.0928 https://arxiv.org/abs/1208.0928 [6]: https://arxiv.org/abs/1209.2426 https://arxiv.org/abs/1209.2426 [7]: https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749