Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There's a specific view (as I understand it) that QFT's don't scale https://arxiv.org/abs/2306.10072 but some folks seem to dismiss this for reasons I just don't grok at all.


There are two major issues with the paper you linked.

First, it says if you can't do accurate rotations then you can't factor. But the premise is false. Quantum error correction allows you to do arbitrarily accurate rotations. Specifically, you can achieve arbitrarily accurate 45 degree rotations around the X and Z axes by using state distillation and gate teleportation [1], and all rotations can be approximated by a sequence of these 45 degree rotations with the error decreasing exponentially versus the length of the sequence [2]. The paper's justification for saying you can't do accurate rotations is that they think quantum mechanics will end up being wrong (see section 4).

Second, even if you assume for the sake of argument that rotations are inherently noisy, the conclusion doesn't actually follow. The mistake the paper makes is to assume the algorithm will use the textbook QFT circuit [3], which uses n^2/2 rotations for an n-qubit QFT, allowing large amounts of error to accumulate. But in practice, because this QFT is at the end of a circuit, you would use the qubit-recycling QFT which only performs n rotations [4]. Alternatively, if rotations were really such a problem, you could perform ~30 rotations to prepare what's known as a phase gradient state. You can then achieve later rotations via the phase kickback of adding a constant into the phase gradient controlled by the qubit you want to rotate [5]. In other words, the paper asserts you need millions of rotations to factor a 2048 bit number when actually you only need dozens. Everything else can be done with Clifford+Toffoli gates.

So yeah, this paper is not at all a convincing takedown of quantum factoring. The formal part focuses on the wrong cost and the informal justification is that they think quantum mechanics is wrong.

[1]: https://en.wikipedia.org/wiki/Magic_state_distillation

[2]: https://www.mathstat.dal.ca/~selinger/newsynth/

[3]: https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/med...

[4]: figure 3 of https://arxiv.org/pdf/1706.07884#page=5 is an example

[5]: https://arxiv.org/pdf/1709.06648#page=4




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: