NISQ (noisy intermediate-scale quantum) algorithms generated a lot of excitement and a lot of publications - the 2022 review has amassed almost 2000 citations! Nowadays the tone is more subdued, with many experts believing any useful practical applications of quantum processors will need quantum error correction. The new hot topics are understanding how to make useful error correction a reality, and what might be done with a few hundred logical qubits.
What then should a new student interested in applied quantum computing focus on?
Ryan Babbush and collaborators already argued in 2021 that algorithms with quadratic speedups won't be useful in practice. So sorry, but we won't be able to solve complex industry optimization problems using Grover search. However, their analysis indicated that quartic speedups and beyond could be practically useful. Which quantum algorithms have this property?
Consulting the excellent review article Quantum algorithms: A survey of applications and end-to-end complexities, there are only a few examples of known or suspected quartic or beyond end-to-end quantum speedups! They are:
Tensor principal component analysis (PCA). Ordinary
PCA is a data reduction step widely used in data analysis and machine
learning. It's not yet clear what tensor PCA might be useful for, but if
an application can be found quantum computers will probably give a
useful speedup.
On the classical computing side, quantum-inspired
tensor network methods are very promising for near-term applications.
There
are also other approaches (QAOA, quantum machine learning) which attracted a lot of interest since 2020
and are still being explored theoretically, but at least in their present formulations they seem unable to provide a useful speedup for classical problems, with
their most promising applications related to directly studying or
simulating certain quantum systems. Thus, interest has shifted from "beating" classical methods on carefully-selected problems to better understanding the
foundations of quantum machine learning. While this is a fascinating topic, it is at this stage it is more theoretical than applied research.