Prof. Dr. Sevag Gharibian, head of the Quantum Informatics group, has published a guest article in the ACM SIGACT News. Gharibian addresses a broad audience of theoretical computer scientists and uses NP (non-deterministic polynomial time) as a cornerstone of complexity theory. With the statement "Quantum NP [...] is clearly the apple that has fallen far from the tree of NP." [He makes it clear that there are different definitions of quantum NP compared to classical NP. These are discussed in his essay.
The Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) has been publishing the ACM SIGACT News quarterly since 1969. Gharibian's guest article was published in December 2023 and is available here.
(Translate with DeepL)
