# Can quantum computers speed up parsing?

Can quantum computers offer Grover-like speed ups in parsing of context-free languages? For instance, general CFLs can be parsed in $$O(n^3)$$ with standard algorithm like https://en.wikipedia.org/wiki/CYK_algorithm. Could Grover's algorithm be used to speed up the search at each level of the CYK table to produce an $$O(n^2)$$ algorithm?

It doesn't appear anyone has published anything on parsing speed-ups.

• Not a direct answer, but keep in mind that quantum algorithms are strong in compute-heavy, not data heavy, problems. By compute-heavy, the expected complexity is usually exponential or maybe high degree polynomial, but there usually isn't much value in a lower tiered reduction (at least at this stage of our understanding of quantum devices) – C. Kang Dec 21 '20 at 20:42