Skip to main content

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
5 votes
2 answers
238 views

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.)...
Manish Kumar's user avatar
2 votes
0 answers
39 views

Create a superposition among the basis states of G for the hidden subgroup problem, implementing $\frac{1}{\sqrt{|G|}}\sum_{g\in G} | g,0\rangle$

I’ve been studying Simon’s problem and developing simulation models using Mathematica to extend the problem to other abelian groups and hidden subgroups of order $\geq 2$. I can now obtain the $h^\...
Phillip Dukes's user avatar
1 vote
0 answers
81 views

The hidden subgroup problem for finite Abelian groups when $|G| \neq 2^n$

I’ve been studying Simon’s problem and developing simulation models using Mathematica to extend the problem to other abelian groups and hidden subgroups of order $\geq 2$. I can now deduce any “hidden”...
Phillip Dukes's user avatar
3 votes
0 answers
41 views

Intuition for failure of strong Fourier sampling for the symmetric group

I am trying to read and understand the following two papers: The Symmetric Group Defies Strong Fourier Sampling: Part I The Symmetric Group Defies Strong Fourier Sampling: Part II I have a pretty good ...
Jackson Walters's user avatar
5 votes
1 answer
166 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>...
smitke6's user avatar
  • 116
0 votes
0 answers
29 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, $...
Andrew Baker's user avatar
3 votes
1 answer
78 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 ...
Andrew Baker's user avatar
2 votes
0 answers
43 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’...
Andrew Baker's user avatar
6 votes
1 answer
194 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$. ...
Andrew Baker's user avatar
1 vote
1 answer
71 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,...
Andrew Baker's user avatar
5 votes
3 answers
206 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 ...
TwentyCents's user avatar
4 votes
1 answer
142 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-...
user8622655's user avatar
5 votes
2 answers
133 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 ...
Gadi A's user avatar
  • 437
17 votes
1 answer
595 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 ...
user2521987's user avatar
4 votes
1 answer
215 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\...
Doriano Brogioli's user avatar
7 votes
1 answer
686 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-...
Doriano Brogioli's user avatar
3 votes
1 answer
211 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 ...
roydiptajit's user avatar
6 votes
1 answer
371 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 ...
paulinho's user avatar
  • 241
4 votes
0 answers
111 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 ...
dylan7's user avatar
  • 324
3 votes
1 answer
179 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 ...
dylan7's user avatar
  • 324
6 votes
2 answers
262 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 ...
Greenstick's user avatar
  • 1,076
14 votes
1 answer
279 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 ...
Root's user avatar
  • 499
10 votes
1 answer
822 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 ...
Sanchayan Dutta's user avatar
4 votes
0 answers
149 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 ...
Root's user avatar
  • 499
5 votes
2 answers
170 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}...
Sam Jaques's user avatar
  • 2,044
6 votes
1 answer
744 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's user avatar
  • 25k
4 votes
1 answer
356 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's user avatar
  • 25k