Solvable Problems

Gennaro Auletta

Stephen Fenner, Yong Zhang

We introduce two decision problems, STABILIZERD and TRANSLATING COSETD, and give quantum reductions from them to the problem ORBIT SUPERPOSITION, 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. We also show that GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP are in the complexity class SZK.

Ian Jauslin

Grigori Karlovich Giorgadze

In this paper, we investigate the problem of simulation of quantum-mechanical dynamical system with prescribed properties using of exactly solvable Hamiltonians. A method for solving time-dependent matrix Schrodinger equations in an explicit analytical form will be developed. It is based on exactly solvable time-independent problems, a certain choice of the initial conditions, and special time-dependent gauge transformations converting time-independent problems to time-dependent ones. An application of the exactly solvable time-dependent problems thus obtained to the construction of a universal set of gates for quantum computers is also presented.

John Watrous

In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.