Classical limits of quantum algorithms

Fault-tolerant quantum computing promises to solve some computational tasks that turn out to be hard on classical computing machines. There are algorithms like Grover's algorithm that have proven speedup against any classical algorithm. Unfortunately, truly fault-tolerant quantum computers have not been realized yet. The potential to achieve quantum advantage with quantum algorithms that run on today's noisy intermediate scale quantum (NISQ) devices remains an open question to date. Here, we propose a systematic strategy to benchmark given NISQ-algorithms for their potential of quantum advantage by comparing these algorithms to their own classical limits.