标题： 群顺序属于QCMA 显示英文标题

标题： Group Order is in QCMA

摘要： 在本工作中，我们证明了验证作为黑盒给出的有限群的阶属于复杂度类QCMA。 这解决了Watrous在2000年在其关于量子证明的开创性论文中提出的一个开放问题，并直接表明Group Non-Membership问题也属于QCMA类，这进一步证明了Aaronson和Kuperberg在2006年提出的一个猜想。 我们的技术还对许多其他群论问题的复杂度给出了改进的量子上界，例如黑盒群的群同构问题。 显示英文摘要

摘要： In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his seminal paper on quantum proofs and directly implies that the Group Non-Membership problem is also in the class QCMA, which further proves a conjecture proposed by Aaronson and Kuperberg in 2006. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.