[amirhirsch]

Welcome to Hacker News Gil! I’m a big fan of your work in complexity theory and have thought long and hard on the entropy-influence conjecture revisiting it again recently after Hao Huang’s marvelous proof of the sensitivity conjecture.

To answer your question on why the hyped fantastic claim, as you must know, the people who provide the funds for quantum computing research almost certainly do not understand the research they are funding, and need as feedback a steady stream of fantastic “breakthroughs” to justify writing the checks.

This has made QC research ripe for applied physicists who are skilled in the art of bullshitting about Hilbert Spaces. While I don’t doubt the integrity of a plurality of the scientists involved, I can say with certainty that approximately all of the people working on Quantum Computing Research would not take me up on my bet of $2048 that RSA2048 will not be factored by 2048 —- and would happily accept $204,800,000 to make arrays of quantum-related artifacts. Investors require breakthroughs or the physicists will lose their budget for liquid gases — certainly exceeding $2048.

While there might be interesting science discovered along the way, I think of QC a little like alchemy: the promise of unlimited gold attracted both bullshitters and serious physicists (Newton included) for centuries, but the physical laws eventually emerged that it is not scalable to turn lead into gold. Similarly it would be useful to determine the scaling laws for Quantum Computers. How big of an RSA key is needed before even a QC exceeds the total number of particles in the universe to factor it in reasonable time? Is 2048 good enough that we can shelf all the peripheral number-theory research in post-quantum-cryptography? Let’s not forget the mathematicians too!

[tmvphil]

You are too certain. Polls of working quantum researchers put significant credence on breaking RSA within 20 years. https://globalriskinstitute.org/publication/2023-quantum-thr...

[light_hue_1]

You should not put any weight on surveys like this.

I'm an ML/AI researcher. I get similar surveys regularly. I don't reply, neither do my colleagues. The people who reply are a self selected group who are heavily biased toward thinking that AGI will happen soon. Or they have a financial interest in creating hype.

Most of the experts from that report have a direct financial benefit from claiming that this will happen really soon now.

[dxbydt]

> Most of the experts from that report have a direct financial benefit from claiming that this will happen

Rigetti $RGTI is up 400% this month. 135% this week alone. He’s right.

[sgt101]

I think Shor's scales lineally, if it's possible to do the fine grain control of the most significant bits. Some people don't think that's a problem, but if it is then growing keys will be an effective defense.

[amirhirsch]

The argument is that error correction doesn’t scale.

[sgt101]

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.

[Strilanc]

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

[adgjlsfhk1]

that's a tough argument given that there are already known algorithms to scale it. it's possibly QM is just broken, but it it's not, it's hard to see how error correction wouldn't work

[amirhirsch]

But we're literally having this discussion with Gil Kalai in the next room.