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)
Questions tagged [hidden-subgroup-problem]
31 questions
19
votes
1 answer
Are all quantum algorithms hidden subgroup algorithms?
I am reading the paper "Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit" by Samuel Lomonaco and Louis Kauffman from the book, "Mathematics of Quantum Computation and Quantum Technology." See also, this arxiv link.
The authors suggest…
user2521987
- 371
- 1
- 9
14
votes
1 answer
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 \rtimes \mathbb{Z}_2$) for general $n$. What…
Root
- 519
- 2
- 11
10
votes
1 answer
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 the dihedral group and symmetric group often use…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
8
votes
1 answer
What is the complexity of hidden subgroup problems?
It is often stated that some of the "hidden subgroup problems" can be efficiently solved by quantum computers if the group is abelian, while no efficient algorithm is known for the non-abelian case. The problems of the first case include…
Doriano Brogioli
- 511
- 2
- 14
7
votes
2 answers
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 quantum model, as is often suggested, is due to…
Greenstick
- 1,086
- 8
- 23
6
votes
2 answers
Burnside Decomposition in Kuperberg's Hidden Shift
In "Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem" (arXiv), Kuperberg writes that $\mathbb{C}[G]$ has a "Burnside decomposition" of
$$\mathbb{C}[G]\cong \bigoplus_{V} V^*\otimes V$$
where each $V$ is an…
Sam Jaques
- 2,201
- 7
- 15
6
votes
1 answer
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.
The Wikipedia page also mentions how Simon's…
glS
- 27,510
- 7
- 37
- 125
6
votes
1 answer
How would HSP with $S_N$ work when the automorphism subgroup is (almost) equal to the symmetric group?
The graph isomorphism problem can be reduced to a case of the hidden subgroup problem, with the group $S_N$ and the function $f \colon \pi \mapsto \pi(G)$ where $G$ is some graph, and $\pi \in S_N$.
The hidden subgroup is the group $Aut(G)$; the…
Andrew Baker
- 299
- 1
- 9
6
votes
1 answer
What is the intuitive reason for why Abelian HSPs are much easier than Non-Abelian HSPs?
I think I roughly understand the quantum algorithm for the general Abelian Hidden Subgroup Problem (HSP). We begin by constructing a uniform superposition, calculating the function over that superposition in another register, then measure it to…
paulinho
- 251
- 1
- 4
5
votes
1 answer
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 Simon's problem.
The problem is the following:…
glS
- 27,510
- 7
- 37
- 125
5
votes
1 answer
Is it true that there is no circuit that solve the hidden subgroup problem for non-abelian groups?
This question is probably stupid since I have little information about the topic, but have we proved that it cannot be solved, or is it still an open problem?
Can you please provide me with the proof or with the recent results regarding it (if…
NotaChoice
- 281
- 1
- 7
5
votes
2 answers
Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?
The (classical) lower bound on Fast Fourier transform is still open question. The complexity of $\mathcal{O}(N\log(N))$ (due to Cooley-Tukey) is not known to be optimal. (Here, $N$ is the vector size.)
In the quantum counterpart, there is an…
108_mk
- 883
- 1
- 6
- 20
5
votes
1 answer
What is the hidden subgroup in Deutsch-Jozsa?
It is noted by several sources (e.g. this paper) that the problem solved by the Deutsch-Jozsa (DJ) algorithm is an instance of the Hidden Subgroup Problem (HSP). However, I fail to see this for $n>2$.
For DJ to be an instance of the HSP, we need the…
smitke6
- 216
- 1
- 4
5
votes
3 answers
Why does “discarding” a qubit register, in the Hidden Subgroup Problem, give a randomly chosen coset $|x+H\rangle$?
I am reading up on the Hidden Subgroup Problem (HSP), and found this resource by Professor Childs.
I am a bit confused at this part though:
Basically, he’s saying that removing the second register from
$$
\frac{1}{\sqrt{\left | G \right |}} \sum_{x…
TwentyCents
- 117
- 4
5
votes
2 answers
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
In the usual presentations (e.g. Nielsen and Chuang) Shor's algorithm (in its quantum part) is presented as a special case of phase estimation, meaning it uses a circuit of the form "generate superposition, apply function, apply $QFT^{-1}$,…
Gadi A
- 437
- 2
- 4