Under the typical computational complexity conjectures, quantum computers are strictly more powerful than classical computers: this fact motivates continued research in quantum algorithms and implementations of quantum computers. However, this is a nuanced notion. For example, it presumes that the quantum computer can operate coherently for as long as necessary, which does not correspond to the state of the art in in practical implementations, wherein the presence of noise forces stopping coherent computation after some time. There is, then, a natural follow-up question: are limited quantum computers (for some rigorous notion of "limited") strictly more powerful than classical computers? The answer to this is also a nuanced yes: adopting a query complexity perspective, one may show that, at least for some problems, a computer that can perform more queries coherently is more powerful than one that cannot, at a fixed trade-off. We re-derive this result using Quantum Singular Value Transformations, a recently introduced theoretical tool, simplifying its proof, and outlining a systematic procedure to generate quantum-classical algorithms.
Organized by: Paulo Brás, Paulo Silva, Jaime Silva