Even if a quantum advantage can be established in some setting, I do not yet understand its scope. Could quantum computation help with every kind of problem, or only particular families?
I want to understand what structure an algorithm can exploit, how the size of a speedup is measured, and when preparing inputs or reading outputs changes the comparison. This asks where to look for an advantage, alongside the separate question of how to prove one.
Papers I am exploring
John Preskill’s Quantum Computing in the NISQ era and beyond puts this question in the setting of noisy hardware: what useful tasks remain possible when noise limits circuit size? It offers context for applications and limitations, rather than a general complexity-class separation.
His later perspective, Beyond NISQ: The Megaquop Machine, asks about potential uses of error-corrected machines capable of a million or more quantum operations. Together, these papers give me a way to ask how the prospect of useful quantum computation changes with the available hardware and error correction.
For the proof side, Wu’s thesis on Fourier growth is a separate lead on problem structure and provable advantages in query and communication models. I want to keep that distinction between a formal resource advantage and a useful application on a realizable machine clear.