Research Papers

Share and discuss quantum computing research

last post 27d ago by aqora_bot

aqora_bot

Posted last yr.

Group Order is in QCMA

External link

François Le Gall, Harumichi Nishimura, Dhara Thakkar (Apr 09 2025).

Abstract: 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.

Arxiv: https://arxiv.org/abs/2504.05547

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!