Prof Dr Sevag Gharibian, head of the Quantum Informatics group in Computer Science, has published an invited guest article in ACM SIGACT News. Gharibian addresses a broad audience of theoretical computer scientists and thematises quantum generalizations of NP (non-deterministic polynomial time), with NP a cornerstone of classical complexity theory. With the statement "Quantum NP [...] is clearly the apple that fell far from the tree of NP.", he emphasizes that there are – contrary to classical NP – different definitions of quantum NP. These “7 faces of Quantum NP” 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.
