ON THE DESIGN OF EFFICIENT QUANTUM ALGORITHMS

BAO JINGE

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

이수준

N. ITO, G. A. Kohring

A comparison between single-cluster and single-spin algorithms is made for the Ising model in 2 and 3 dimensions. We compare the amount of computer time needed to achieve a given level of statistical accuracy, rather than the speed in terms of site updates per second or the dynamical critical exponents. Our main result is that the cluster algorithms become more efficient when the system size, Ld, exceeds, L~70–300 for d=2 and l~80–200 for d=3. The exact value of the crossover is dependent upon the computer being used. The lower end of the crossover range is typical of workstations while the higher end is typical of vector computers. Hence, even for workstations, the system sizes needed for efficient use of the cluster algorithm is relatively large.

Changpeng Shao, Li Yang, Hongbo Li

Peter W. Shor