153 citations · 255 across the 5 of their papers we have counts for
5 papers
The quantum query complexity of the hidden subgroup problem is polynomial
Mark Ettinger, Peter Hoyer, Emanuel Knill
We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. Thi…
Quantum Time-Frequency Transforms
J. Mark Ettinger
Time-frequency transforms represent a signal as a mixture of its time domain representation and its frequency domain representation. We present efficient algorithms for the quantum…
Hidden Subgroup States are Almost Orthogonal
Mark Ettinger, Peter Hoyer, Emanuel Knill
It is well known that quantum computers can efficiently find a hidden subgroup of a finite Abelian group . This implies that after only a polynomial (in ) number o…
A Quantum Observable for the Graph Isomorphism Problem
Mark Ettinger, Peter Hoyer
Suppose we are given two graphs on vertices. We define an observable in the Hilbert space $\Co[(S_n \wr S_2)^m]$ which returns the answer ``yes'' with certainty if the graphs a…
On Quantum Algorithms for Noncommutative Hidden Subgroups
Mark Ettinger, Peter Hoyer
Quantum algorithms for factoring and discrete logarithm have previously been generalized to finding hidden subgroups of finite Abelian groups. This paper explores the possibility o…