10
votes
Accepted
What is the complexity of hidden subgroup problems?
TL;DR: The general version of the Hidden Subgroup Problem (abelian or otherwise) is not in NP, because it is an oracle problem.
Background: $\text{NP}$
Recall that a language $L\subset \bigcup_{k=0}^\...
- 24.2k
8
votes
Accepted
Why does representation theory often arise in the context of quantum algorithms for the hidden subgroup problem?
Two classical texts for the representation theory of finite groups are the books of Hamermesh and Serre. These books however lack chapters on Fourier analysis needed for the quantum computation ...
- 2,585
8
votes
Burnside Decomposition in Kuperberg's Hidden Shift
In the paper I called it the Burnside decomposition, but it looks like the standard name is the Wedderburn decomposition. That might simply have been a mistake in terminology on my part.
Anyway, ...
- 1,436
6
votes
Accepted
How would HSP with $S_N$ work when the automorphism subgroup is (almost) equal to the symmetric group?
TL;DR: We do not need to inspect all the elements of the hidden subgroup ${\mathcal H}=Aut(G)$. We only need to inspect the elements of the generating set that HSP subroutine has found. An efficient ...
- 24.2k
6
votes
Accepted
Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?
Here's an $O(n \lg^2 n)$ construction of the QFT based on merging groups of phasing operations into multiplications:
You can verify the circuit works in Quirk.
The "reverse" gate reverses ...
- 40.8k
6
votes
Accepted
What is the hidden subgroup in Simon's problem?
To see that Simon's program is an instance of an (abelian) hidden subgroup problem, we have to identify the group $G$, the subgroup $H$, the set $X$ and the function $f : G \rightarrow X$. Note first ...
- 755
6
votes
Accepted
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
Note that $\text{QFT}^2$ is a permutation $|k\rangle \rightarrow |(-k) \bmod 2^n\rangle$. This is a classical operation. It can be applied in the post processing of the measurements, and in fact it ...
- 40.8k
6
votes
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
$\text{QFT}\big(|0\rangle^{\otimes n}\big) = \text{QFT}^{-1}\big(|0\rangle^{\otimes n}\big) = |{+}\rangle^{\otimes n}$, so a QFT, inverse QFT, or a column of Hadamard gates are all equivalent at the ...
- 888
5
votes
Accepted
Why does “discarding” a qubit register, in the Hidden Subgroup Problem, give a randomly chosen coset $|x+H\rangle$?
Let's start from the state (ignoring normalization)
$$
|\psi\rangle = \sum_{g \in G} | x\rangle |f(x)\rangle.
$$
There are two registers here: the "data" register that stores $x$ and the &...
- 1,903
5
votes
Accepted
Are all quantum algorithms hidden subgroup algorithms?
Currently, I am reviewing some literature on this topic. This is still an open problem if we talk about general Hidden subgroup problem (say, g-HSP), including both abelian and non-abelian cases.
An ...
- 831
5
votes
What is the intuitive reason for why Abelian HSPs are much easier than Non-Abelian HSPs?
I will begin by saying that first of all the HSP quantum algorithm works on any group, regardless of whether it is abelian or not. The problem is that when the group is not abelian (or the hidden ...
- 2,156
5
votes
Status of hidden shift and hidden subgroup problems
Here are some cases where there are polynomial time quantum algorithms for the hidden subgroup problems over non-ableian groups.
When the subgroups that are hidden are all normal. This is due to ...
- 745
5
votes
What are the ambient group $G$ and the hidden subgroup $H$ in Shor's order finding algorithm?
TL;DR: There are a few slightly different ways to cast period-finding as a Hidden Subgroup Problem (HSP). The conceptually simplest formulation uses $G=\mathbb{Z}$, but it is not practical from ...
- 24.2k
4
votes
What is known about the 'structure' of the solution for Graph Isomorphism on quantum computers?
I wouldn't necessarily say that Graph Isomorphism (GI) is thought to be unsolvable on quantum computers. The consensus among many computer scientists (see e.g. Scott Aaronson) seems to be that GI ...
- 41
4
votes
Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?
I think this is a good question. But the answers might depend on the precise meaning behind "exact" as even Coppersmith's improvement provides an approximate algorithm.
For example, Shor ...
- 13.6k
4
votes
Why does “discarding” a qubit register, in the Hidden Subgroup Problem, give a randomly chosen coset $|x+H\rangle$?
(Made CW as an expansion of some other other answers)
Understanding the answer to why quantum algorithms often ignore the second register is a bit of a pons asinorum test toward figuring out more of ...
4
votes
Accepted
Burnside Decomposition in Kuperberg's Hidden Shift
The second part of each tensor product serves as a multiplicity space. It might be more satisfying to write it as a full decomposition like your second one.
So you have $\bigoplus V_\lambda \otimes ...
- 3,683
4
votes
Accepted
Quantum algorithm for hidden subgroup problems: question on cosets
Consider that if we enumerate the cosets of $H$ as $g_0+H,g_1+H,\dots, g_n+H$, then every $g\in G$ can be written as $g_i+h$ for some $i$ and some $h\in H$, and this correspondence is 1-to-1. This ...
- 2,149
4
votes
Why does “discarding” a qubit register, in the Hidden Subgroup Problem, give a randomly chosen coset $|x+H\rangle$?
That description is a bit imprecise. "Discard" really means "measure this register and discard the result". It's impossible to just "discard" registers in quantum ...
- 2,149
3
votes
Is the phase-estimation a specific case of the Hidden Subgroup Problem?
I would say "No, the quantum phase-estimation algorithm (QPE), in all its glory, is not just an embodiment of, or should not be limited to, the hidden subgroup problem (HSP)", at least ...
- 13.6k
3
votes
Accepted
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?
With the Hidden Subgroup Problem, abelian or otherwise, we have a function $f$ from elements of $g\in G$ to an arbitrary set $X$, that is constant on cosets of $H\le G$ and is distinct on different ...
- 13.6k
3
votes
Accepted
Why does Fourier sampling allow to efficiently recover hidden subgroups?
The question is whether taking the Fourier transform $\operatorname{QFT}|gH\rangle$ followed by sampling allows to efficiently recover generators of the hidden subgroup $H\leq G$. While the problem is ...
- 755
3
votes
The relationship between problem structure and exponential speedups under the query model
Gilyén and Vazirani, building on the recent breakthrough of Hastings, give a (sub)-exponential separation for a quantum adiabatic algorithm with no sign problem. They design a graph that can be ...
- 13.6k
2
votes
Accepted
The relationship between problem structure and exponential speedups under the query model
The Aaronson-Ambainis (AA) conjecture implies that there must be some structure that's exploitable by a quantum algorithm to have any hope to achieve an exponential speedup for decision problems in NP....
- 13.6k
2
votes
What is the hidden subgroup in Deutsch-Jozsa?
Thinking about this some more, for the Deutsch-Jozsa problem I don't think the parent group $G$ is $n$ copies of $\mathbb Z_2$, but is rather $\mathbb Z/(2^n\mathbb Z)$. That is, the parent group is ...
- 13.6k
1
vote
What are the ambient group $G$ and the hidden subgroup $H$ in Shor's order finding algorithm?
The group is $G=(\{1,...,\phi(N)\},+)$, and the subgroup is $H=<r>$, where $r$ is the period of the function $f$.
- 170
1
vote
Accepted
Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model
What do you mean that we cannot "represent an input to this oracle as a bitstring"?
For example we could have the basis states in our Hilbert space be the adjacency matrices over $N$ ...
- 13.6k
1
vote
Constructing arbitrary functions for the Abelian HSP
I am not sure if this anwers your question but I think this all boils down to whether one can we efficiently implement $QFT_{\mathbb{Z}_N}$ when $N$ is not a power of $2$. In this case we can no ...
- 2,156
Only top scored, non community-wiki answers of a minimum length are eligible