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)
23
questions
3
votes
1
answer
106
views
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>...
- 96
0
votes
0
answers
28
views
How does the hardness of the HSP change when the hiding function is altered?
When talking about many (presumably) NP-intermediate problems, such as factoring and graph isomorphism, the HSP is brought up. The HSP, as a problem, is often paired with a group, $G$, and an oracle, $...
- 237
2
votes
1
answer
69
views
What is known about the 'structure' of the solution for Graph Isomorphism on quantum computers?
It is thought that Graph Isomorphism, at least the HSP with the symmetric group, is unsolvable on quantum computers. This is a case of the non-abelian HSP.
But if a solution to this problem were to ...
- 237
2
votes
0
answers
37
views
Does a solution to SAT solve the HSP for $S_N$, $D_{2N}$, or even the general case?
I often hear about the graph isomorphism problem reducing to the HSP with the symmetric group and a mapping $f \colon \pi \in S_N \mapsto \pi(G)$ with $G$ being some graph (the union of the graphs we’...
- 237
6
votes
1
answer
184
views
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$.
...
- 237
1
vote
1
answer
62
views
Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model
The HSP (Hidden Subgroup Problem) links many NP-intermediate problems, such as factoring, graph isomorphism, and shortest vector.
The brief problem statement is presented like so:
Given some group, G,...
- 237
5
votes
3
answers
133
views
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 ...
- 97
3
votes
1
answer
89
views
Is the phase-estimation a specific case of the Hidden Subgroup Problem?
I read Nielsen & Chuang and I have difficulties understanding the links between the Hidden Subgroup Problem and the Phase Estimation.
In Exercise 5.14 (Section 5.3.1 "Application: order-...
- 81
4
votes
2
answers
89
views
$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 ...
- 427
14
votes
0
answers
419
views
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 ...
- 317
4
votes
1
answer
187
views
Quantum algorithm for hidden subgroup problems: question on cosets
We have a group $G$ and a function $f$ which hides a subgroup $H$, and we want to find $H$. The quantum algorithm for solving the problem involves the use of two registers, initially at $\left|0,0\...
- 463
6
votes
1
answer
489
views
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-...
- 463
3
votes
1
answer
179
views
In the hidden subgroup problem for finite Abelian groups, where does the state $\frac{1}{\sqrt{|G|}}\sum_{g\in G} |g,0\rangle$ come from?
I am new to the concept of HSP. Previously, I saw how to solve hidden subgroup problem over $\mathbb{Z}_2^n$, which was Simon's algorithm. Over there the first step was to apply $H^{\otimes n}$, which ...
- 227
3
votes
1
answer
214
views
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 ...
- 211
3
votes
0
answers
99
views
Abelian Hidden Subgroup Problem for arbitrary cyclic p-Groups
I had asked a question similar to this one here regarding how to handle the HSP for groups whose cyclic decomposition contains factors whose order is not a power of two. I also had some prior ...
- 314
3
votes
1
answer
171
views
Constructing arbitrary functions for the Abelian HSP
My question might be similar to Hidden subgroup problem. However, I'm not exactly sure though. In addition, that question doesn't have an answer.
I'm trying to create some simple instances of the ...
- 314
6
votes
2
answers
229
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 ...
- 1,036
12
votes
0
answers
203
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 ...
- 469
9
votes
1
answer
728
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 ...
- 17.1k
4
votes
0
answers
144
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 ...
- 469
4
votes
2
answers
161
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}...
- 1,974
5
votes
1
answer
560
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.
...
glS♦
- 22.9k
4
votes
1
answer
338
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 ...
glS♦
- 22.9k