Discrete optimization : Limitations of existing quantum algorithms

We investigate the limitations of existing quantum algorithms to solve discrete optimization problems. First, we discuss the quantum counting algorithm of Brassard et al. (1998), and show that it has performance that is equivalent to that of a brute-force approach when approximating the number of valid solutions. In addition, we show that a straightforward application of Grover's algorithm (referred to as GUM by Creemers and Pérez (2023b)) dominates any quantum counting algorithm when verifying whether a valid solution exists. Next, we discuss the nested quantum search algorithm of Cerf et al. (2000), and show that it is dominated by a classical nested search that uses an approach such as GUM to find (partial) solutions to (nested) problems. Last but not least, we also discuss amplitude amplification (a procedure that generalizes Grover's algorithm), and show (once more) that it may not be possible to outperform GUM