20 citations · 60 across the 8 of their papers we have counts for
8 papers · 1 filter
Explicit Multiregister Measurements for Hidden Subgroup Problems
Cristopher Moore, Alexander Russell
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This en…
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
Cristopher Moore, Daniel Rockmore, Alexander Russell +1
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a Hidden Subgroup problem, in which an unknown subgroup H of a g…
For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
Cristopher Moore, Alexander Russell
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group D_n in the case where the hidd…
The Symmetric Group Defies Strong Fourier Sampling: Part I
Cristopher Moore, Alexander Russell, Leonard J. Schulman
We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric gro…
Generic Quantum Fourier Transforms
Cristopher Moore, Daniel Rockmore, Alexander Russell
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient…
Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation
Alexander Russell, Igor Shparlinski
We consider the problem of recovering a hidden monic polynomial f(X) of degree d > 0 over the finite field F of p elements given a black box which, for any x in F, evaluates the qu…