article
Guest Column: The 7 faces of quantum NP
published
Sevag
Gharibian
author 715410000-0002-9992-3379
When it comes to NP, its natural definition, its wide applicability across scientific disciplines, and its timeless relevance, the writing is on the wall: There can be only one. Quantum NP, on the other hand, is clearly the apple that fell far from the tree of NP. Two decades since the first definitions of quantum NP started rolling in, quantum complexity theorists face a stark reality: There's QMA, QCMA, QMA1, QMA(2), StoqMA, and NQP. In this article aimed at a general theoretical computer science audience, I survey these various definitions of quantum NP, their strengths and weaknesses, and why most of them, for better or worse, actually appear to fit naturally into the complexity zoo.
2024
eng
ACM SIGACT News
54454-91
https://dl.acm.org/doi/abs/10.1145/3639528.3639535
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” <i>ACM SIGACT News</i> 54, no. 4 (2024): 54–91.
@article{Gharibian_2024, title={Guest Column: The 7 faces of quantum NP}, volume={54}, number={4}, journal={ACM SIGACT News}, author={Gharibian, Sevag}, year={2024}, pages={54–91} }
Gharibian, S. (2024). Guest Column: The 7 faces of quantum NP. <i>ACM SIGACT News</i>, <i>54</i>(4), 54–91.
S. Gharibian, “Guest Column: The 7 faces of quantum NP,” <i>ACM SIGACT News</i>, vol. 54, no. 4, pp. 54–91, 2024.
Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” <i>ACM SIGACT News</i>, vol. 54, no. 4, 2024, pp. 54–91.
Gharibian S. Guest Column: The 7 faces of quantum NP. <i>ACM SIGACT News</i>. 2024;54(4):54-91.
485442023-10-30T12:19:11Z2024-01-07T18:16:36Z