2005 | OriginalPaper | Buchkapitel
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
verfasst von : Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The hidden subgroup problem (HSP) offers a unified framework to study problems of group-theoretical nature in quantum computing such as order finding and the discrete logarithm problem. While it is known that Fourier sampling provides an efficient solution in the abelian case, not much is known for general non-abelian groups. Recently, some authors raised the question as to whether post-processing the Fourier spectrum by measuring in a random orthonormal basis helps for solving the HSP. Several negative results on the shortcomings of this
random strong
method are known. In this paper however, we show that the random strong method can be quite powerful under certain conditions on the group
G
. We define a parameter
r
(
G
) and show that
O
((log |
G
| /
r
(
G
))
2
) iterations of the random strong method give enough classical information to solve the HSP. We illustrate the power of the random strong method via a concrete example of the HSP over finite Heisenberg groups. We show that
r
(
G
) = Ω(1) for these groups; hence the HSP can be solved using polynomially many random strong Fourier samplings followed by a possibly exponential classical post-processing without further queries. The quantum part of our algorithm consists of a polynomial computation followed by measuring in a random orthonormal basis. As an interesting by-product of our work, we get an algorithm for solving the
state identification problem
for a set of nearly orthogonal pure quantum states.