  Quantum computers offer a new paradigm of computing with the potential to
vastly outperform any imagineable classical computer. This has caused a gold
rush towards new quantum algorithms and hardware. In light of the growing
expectations and hype surrounding quantum computing we ask the question which
are the promising applications to realize quantum advantage. We argue that
small data problems and quantum algorithms with super-quadratic speedups are
essential to make quantum computers useful in practice. With these guidelines
one can separate promising applications for quantum computing from those where
classical solutions should be pursued. While most of the proposed quantum
algorithms and applications do not achieve the necessary speedups to be
considered practical, we already see a huge potential in material science and
chemistry. We expect further applications to be developed based on our
guidelines.
