群交

一组群论问题的量子算法*

摘要：本工作引入了两个决策问题，稳定器 D 和轨道陪集 D ，并给出了从它们到问题轨道叠加 (Friedl 等人，2003) 的量子简化，以及从两个群论问题群交和双陪集成员到它们的量子简化。基于这些简化，在黑箱群设置中获得针对群交和双陪集成员的有效量子算法。具体而言，对于可解群，如果其中一个底层可解群具有平滑可解的交换子群，则这为群交提供了有效的量子算法，如果其中一个底层可解群是平滑可解的，则这为双陪集成员提供了有效的量子算法。最后，证明了群交和双陪集成员属于复杂度类 SZK 。