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
4 votes
1 answer
124 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\...
user avatar
6 votes
1 answer
261 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-...
user avatar
3 votes
1 answer
126 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 ...
user avatar
3 votes
1 answer
85 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 ...
user avatar
  • 201
3 votes
0 answers
75 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 ...
user avatar
  • 294
3 votes
1 answer
159 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 ...
user avatar
  • 294
5 votes
1 answer
118 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 ...
user avatar
10 votes
0 answers
152 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 ...
user avatar
  • 439
7 votes
1 answer
408 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 ...
user avatar
4 votes
0 answers
122 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 ...
user avatar
  • 439
4 votes
2 answers
138 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}...
user avatar
  • 1,546
5 votes
1 answer
359 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. ...
user avatar
  • 18.2k
4 votes
1 answer
271 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 ...
user avatar
  • 18.2k