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.

  • 2
    $\begingroup$ 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) $\endgroup$
    – C. Kang
    Dec 21, 2020 at 20:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.