We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.
Quantum computers are expected to be able to outperform classical computers. In fact, some computational problems such as integer factorization can be solved on quantum computers substantially faster than classical computers. Interestingly, these problems can be cast in a framework of the hidden symmetry subgroup problem. However, only a few of quantum algorithms for efficiently solving this problem have been known, and the approaches used in all previous results can be applied to particular groups with specific group actions. In this paper, we introduce new technique for solving the hidden symmetry subgroup problem which can be applicable for any groups and any group actions with a certain condition. In addition, we define the continuous hidden symmetry subgroup problem on a group by employing a continuous oracle function, and prove that if the group is a metric space and the group action satisfies some condition, then the continuous hidden symmetry subgroup problem can be efficiently reduced to the continuous hidden subgroup problem. In particular, we show that there exists an efficient quantum algorithm to solve the continuous hidden symmetry subgroup problem on
Rn, while it has not yet been shown that the original hidden symmetry subgroup problem on
Rncan be efficiently solved by a quantum computer.