View Related Documents

Abstract

This work introduces two decision problems, Stabilizer D and Orbit Coset D , and gives quantum reductions from them to the problem Orbit Superposition (Friedl et al., 2003), as well as quantum reductions to them from two group theoretic problems Group Intersection and Double Coset Membership. Based on these reductions, efficient quantum algorithms are obtained for Group Intersection and Double Coset Membership in the setting of black-box groups. Specifically, for solvable groups, this gives efficient quantum algorithms for Group Intersection if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for Double Coset Membership if one of the underlying solvable groups is smoothly solvable. Finally, it is shown that Group Intersection and Double Coset Membership are in the complexity class SZK.
This work was supported in part by the National Security Agency (NSA) and Advanced Research and Development Activity (ARDA) under Army Research Office (ARO) contract number DAAD 190210048.

Fulltext Preview

Image of the first page of the fulltext document