Questions tagged [hidden-subgroup-problem]

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. (Wikipedia)

Filter by
Sorted by
Tagged with
4
votes
0answers
44 views

The relationship between problem structure and exponential speedups under the query model

What problem structure(s) are required to admit an exponential speedup in the universal quantum model of computation under the query model? Intuitively, it would seem that much of the benefit of the ...
6
votes
0answers
53 views

Status of hidden shift and hidden subgroup problems

We know that solving a hidden subgroup problem over a non-commutative group is a long standing problem in quantum computing even for groups like $D_{2n}$ (alternatively can be written as $\mathbb{Z}_n ...
5
votes
1answer
79 views

Why does representation theory often arise in the context of quantum algorithms for the hidden subgroup problem?

I noticed that approaches for finding quantum algorithms the hidden subgroup problem for both Abelian groups ($(\Bbb Z_n\times \Bbb Z_n, +)$, $(\Bbb R, +)$, etc.) and non-Abelian finite groups like ...
4
votes
2answers
99 views

Burnside Decomposition in Kuperberg's Hidden Shift

In "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem", Kuperberg writes that $\mathbb{C}[G]$ has a "Burnside decomposition" of $$\mathbb{C}[G]\cong \bigoplus_{V}...
4
votes
0answers
82 views

Hidden subgroup problem

Let $H$ be a hidden subgroup of $G_1$ that is indistinguishable from subgroup $H^{\prime}$ by quantum Fourier sampling. Now take a larger group $G_2$ such that it contains $G_1$. Now if I do quantum ...
5
votes
1answer
168 views

What is the hidden subgroup in Simon's problem?

Given access to an oracle for a function $f:\{0,1\}^n\to\{0,1\}^n$ such that $f(x)=f(y)$ iff $x\oplus y\in\{0,s\}$, Simon's algorithm allows to recover $s$ in $\mathcal O(n)$ queries to the oracle. ...
4
votes
1answer
127 views

Why does Fourier sampling allow to efficiently recover hidden subgroups?

The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and ...