[kirrent]

'I suspect that any speedup imparted by clever uses of entanglement will be counteracted by the fundamental need for error correction and averaging over several runs.'

Perhaps you don't understand what people mean when they say scalable quantum computing? They mean that it scales with the error correction included. Needing to average over several runs is already factored into the complexity of quantum algorithms.

Also, whether you can make a scalable quantum computer isn't beside the point. It's the entire point Kalai's trying to make. If you can make a scalable quantum computer we already know that there are applications it will outperform a classical computer on performance and cost.

[smaddox]

Perhaps I don't, but your description doesn't seem to contradict my point that scalability is distinct from competitive with classical computing. Perhaps people also implicitly mean "scales faster than a classical computer", in which case I did indeed misunderstand.

On the topic of whether or not the need for averaging is already accounted for in algorithmic complexity, my understanding is that it is not. This [1] preprint from 2006 seems to support my understanding. If you have evidence to the contrary, I would greatly appreciate a link.

[1] https://arxiv.org/pdf/quant-ph/0612077

[kirrent]

Shor's original paper discusses the fundamental need for several runs and gives the time complexity.

https://arxiv.org/pdf/quant-ph/9508027.pdf

The paper you linked to is just saying that the need for several runs and 2006 readout error rates together led to awful scaling (though still better than classical factorisation). That isn't surprising. Error rates in all parts of even modern quantum computers are still too high to scale well. Especially when repetition is called for.

Ultimately, complexity is calculated using logical qbits. Kalai doesn't think that even with error correction codes we can get close enough. Most other people think we can. That paper you linked to is just making the point that we're definitely not there yet. When we do, algorithms in BQP will still need several runs on many algorithms (the exact same way as algorithms in BPP do) but that should already be incorporated into those algorithm's complexity.

[kirrent]

*Kalai doesn't think that even with error correction codes we can get sufficiently close to a logical qbit.