| Title | : | Group Order and Group Non-Membership is in QCMA |
| Speaker | : | Dhara Thakkar (Nagoya University, Japan) |
| Details | : | Fri, Feb 6, 2026 11:30 AM, @ SSB 334 |
| Abstract | : | In this talk, I will discuss recent progress on the role of
classical proofs in quantum complexity theory, focusing on
group-theoretic problems in the black-box model. In particular, I
will present QCMA protocols for two long-standing open questions in
this area. First, we show that the Group Non-Membership problem--known
to lie in QMA but not in MA--is in fact in QCMA, settling a 2006
conjecture by Aaronson and Kuperberg. This result follows from a more
general result that the Group Order Verification problem lies in QCMA,
answering an open question posed by Watrous in 2000. 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 settings. This talk is based on the joint work with François Le Gall and Harumichi Nishimura. |