Group Order is in QCMA
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918297326321664 |
|---|---|
| author | Gall, François Le Nishimura, Harumichi Thakkar, Dhara |
| author_facet | Gall, François Le Nishimura, Harumichi Thakkar, Dhara |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05547 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Group Order is in QCMA Gall, François Le Nishimura, Harumichi Thakkar, Dhara Quantum Physics Computational Complexity Group Theory 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. |
| title | Group Order is in QCMA |
| topic | Quantum Physics Computational Complexity Group Theory |
| url | https://arxiv.org/abs/2504.05547 |