Skip to main content
Share Your Experience: Take the 2024 Developer Survey
9 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}^\...
Adam Zalcman's user avatar
  • 22.9k
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 ...
David Bar Moshe's user avatar
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, ...
Greg Kuperberg's user avatar
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 ...
Craig Gidney's user avatar
  • 37.7k
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 ...
Adam Zalcman's user avatar
  • 22.9k
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 ...
MartinQuantum's user avatar
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 ...
Craig Gidney's user avatar
  • 37.7k
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 ...
benrg's user avatar
  • 878
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 &...
Abdullah Khalid's user avatar
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 ...
Manish Kumar's user avatar
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 ...
Condo's user avatar
  • 2,048
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 ...
dabacon's user avatar
  • 745
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

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 ...
Adam Zalcman's user avatar
  • 22.9k
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 ...
Stefan S's user avatar
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 ...
Mark Spinelli's user avatar
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 ...
AHusain's user avatar
  • 3,643
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 ...
Sam Jaques's user avatar
  • 2,066
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 ...
Sam Jaques's user avatar
  • 2,066
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 ...
Mark Spinelli's user avatar
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 ...
Mark Spinelli's user avatar
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 ...
MartinQuantum's user avatar
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....
Mark Spinelli's user avatar
2 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 ...
Mark Spinelli's user avatar
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 ...
Mark Spinelli's user avatar
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$ ...
Mark Spinelli's user avatar
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 ...
Condo's user avatar
  • 2,048

Only top scored, non community-wiki answers of a minimum length are eligible