  In the last couple of decades, the world has seen several stunning instances
of quantum algorithms that provably outperform the best classical algorithms.
For most problems, however, it is currently unknown whether quantum algorithms
can provide an advantage, and if so by how much, or how to design quantum
algorithms that realize such advantages. Many of the most challenging
computational problems arising in the practical world are tackled today by
heuristic algorithms that have not been mathematically proven to outperform
other approaches but have been shown to be effective empirically. While quantum
heuristic algorithms have been proposed, empirical testing becomes possible
only as quantum computation hardware is built. The next few years will be
exciting as empirical testing of quantum heuristic algorithms becomes more and
more feasible. While large-scale universal quantum computers are likely decades
away, special-purpose quantum computational hardware has begun to emerge that
will become more powerful over time, as well as some small-scale universal
quantum computers.
