2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.