The most famous problem in quantum computing is the hidden subgroup problem. In the hidden subgroup problem you are given access to an oracle which computers a function f. This function is a function from a group G to some set with a promise on the function. The promise is that f is constant and distinct on left cosets of some subgroup H of G. The goal of the hidden subgroup problem is, by querring the function, to determine a generating set for the subgroup H. We say that an algorithm for the hidden subgroup problem is efficient if it uses resources proportional to a polynomial in the logarithm of the size of the group.
The reason the hidden subgroup problem is famous is threefold. The first reason is that when G is Abelian, efficiently solving the hidden subgroup problem leads to an efficient algorithm for factoring integers and for the discrete logarithm problem, i.e. to Shor’s algorithm(s). The second reason is that efficiently solving the hidden subgroup problem when G is the symmetric group would lead to an efficient algorithm for the graph isomorphism problem. The third reason is that efficiently solving the hidden subgroup problem when G is the dihedral group would lead to an efficient algorithm for certain shortest vector in a lattice problems. The first of these reasons is a concrete reason: a quantum algorithm worked! But for the second and third, no efficient quantum algorithm is known.
Now what I find interesting, is that for the second of these reasons, for graph isomorphism, one can get by with solving a much more restricted version of the hidden subgroup problem than the full hidden subgroup problem over the symmetric group. The way to do this is to modify the problem to a problem I call the hidden subgroup conjugacy problem. Call two subgroups, H and K conjugate to each other if there exists an element g of the group G such that gHg^{-1}=K. In the hidden subgroup conjugacy problem, instead of identifying the subgroup (by returning a set of generators, for example) we require that you only identify which conjugacy the subgroup belongs to, i.e. the setup is the same: you are given an f which hides a subgroup H, but now instead of identifying the subgroup you only want to know which conjugacy class the subgroup belongs to. It is easy to see that for the Ableian case, this reduces to the hidden subgroup problem: gHg^{-1}=H for all g in this case. For graph isomorphism, the standard reduction to the hidden subgroup problem reduces to distinguishing between the subgroup being a trivial subgroup and the subgroup being a order two subgroup. So efficiently solving the hidden subgroup conjugacy problem would lead to an efficient algorithm for graph isomorphism. Interesting, the same does not seem to be true for the reduction from the hidden subgroup to certain shortest vector in a lattice problems, although I haven’t thought hard about this.
So the question I ask is, did we overgeneralize the hidden subgroup problem? Did we generalize ourselves into a problem which is just too hard, while efficiently solving a smaller variant would lead to interesting new quantum algorithms? I leave history to judge.
O brave new quantum world!
[snark mode on] Thanks for the upper Tucci. Bringing down others doesn’t raise one up, it lowers one down.[snark mode off]
On the last question you ask “which unitary matrices can be compiled efficiently and which cannot”…well you’re basically asking for something which we don’t even have an answer for in the classical case (“what can be computed efficiently with polynomial sized classical circuits”.) I’m not saying it’s not possible to make progess here, but I’m just stating that the analogous question in the classical world has been though about by a lot of very smart people and most of them have declared that it is a very very difficult problem.
Obviously, mathematically speaking the generalization from Abelian to non-Abelian is not trivial and the most general thing you could do with groups. If that is minor, so is quantum physics as a minor non-commutative generalization of classical mechanics.
And the fact that it is equivalent to the graph isomorphism, shows that it is interesting…
I am not sure if I understand the word overgeneralization? Mathematicians would never use this words 🙂
Btw, is your RSS fixed now?
You can tell I’m not a mathematician, eh?
The problem is that one needs to be careful in computer science when going from some problem which has an efficient algorithm to some generalization of this problem. If you generalize too far you often end up with too hard of a problem. This is what I’m suggesting might happen here…the hidden subgroup problem might not be efficiently solvable on a quantum computer, but the hidden subgroup conjugacy problem might be efficiently solvable on a quantum computer. Since both of these can be used to solve the graph isomorphism problem, it makes a big deal: if you work on the hidden subgroup problem you are doomed, but if you work on the hidden subgroup conjugacy problem, you have a chance!
I think my RSS is fixed. Joe Renes sent me an email about how to fix it. Let me know if it is still wacked (bloglines seems to like it now!)
In my opinion, the problem is that you guys have not generalized enough. Shor proposed his algorithm more than 10 years ago, the Hidden Subgroup Problem (HSP) is a fairly minor, conservative generalization of Shor’s algorithm from abelian to non-abelian G. Despite this, you guys have failed miserably to find efficient algorithms for HSP except for a few, very specialized groups.
Meanwhile, one of the fundamental questions of quantum computing, which unitary matrices can be compiled efficiently and which cannot, remains unanswered.
You could say that the relevant dihedral problem is the opposite extreme of the HSP; it’s about fixing a conjugacy class and finding out which conjugate you have.
I’m not sure why this characterization is useful, though.
At first I thought I’d agree that the generalization from the Abelian to the non-Abelian case wasn’t broad enough, but then I thought about it a bit and it’s not at all clear to me.
The reason for this is as follows. What type of problem do we expect a quantum computer to be able to solve? Suppose we are not ready to believe that quantum computers can solve NP-complete problems. Well, what kind of problems are then solvable by a quantum computer? Well there are problems like factoring which are in NP intersect co-NP. But we really don’t known many of these problems. And many of the ones we do know (graph isomorphism, a certain range of shortest vector in a lattice problems) are exactly the problems which a hidden subgroup algorithm would solve. So from this point of view, the hidden subgroup problem is THE game in town. Sure there are a few other problems in NP intersect coNP, but not many that we know.
Of course it may be that quantum computers can solve some very strange class of problems: perhaps even problems that lie outside of the polynomial heirarchy (someone please correct me if this has been shown to be impossible.) So, I’m inclined to agree with you.
I’d also say that an efficient algorithm for graph isomorphism would be slightly more important than you suggest. Perhaps if nothing more than showing that there is more hope for quantum computers than just factoring numbers, but also, I think, because this problem has a fairly large set of polynomial equivalent problems.
An interesting spin off of this is the question of whether the hidden subgroup problem is BQP-complete. Or maybe one should just go one direction and show that solving the hidden subgroup problem allows one to efficiently classically simulate any quantum circuit? What is the power of BPP^{HSP}?
[snark mode on] Thanks for the upper Tucci. Bringing down others doesn’t raise one up, it lowers one down.[snark mode off]
I didn’t mean any adhominens. I was merely expressing
my physics opinions.
Since you’ve worked in other quantum computing subjects
besides HSP, and will no
doubt work on other QC subjects in the future,
it’s not like your entire life depends on the outcome of that
particular avenue of research, which I still believe is not
that fruitful.
Obviously, mathematically speaking the generalization from Abelian to non-Abelian is not trivial and the most general thing you could do with groups. If that is minor, so is quantum physics as a minor non-commutative generalization of classical mechanics.
And the fact that it is equivalent to the graph isomorphism, shows that it is interesting…
I think if you take a very general theory like Newtonian Mechanics and replace abelianess by non-abelianess,
then you are bound to get something very powerful. But if your departure point (Shor’s algorithm) is not very general, then replacing abelianess by non-abelianess may not add much value.
I think that equivalence to the graph isomorphism problem, which is a very special pattern recognition problem, perhaps shows that HSP is not general enough.
i have some partial results on BPP^HSP.
it’s kind of hard to define this class, but if you do it carefully to avoid polynomial blowups, then i can show that access to a HSP-solving oracle doesn’t give the grover speedup – in fact, it speeds up unstructured search by a constant factor (between 2 and 4).
i strongly suspect that BPP^HSP cannot solve the “childs et al welded tree exponential speedup via quantum walk” problem in sub-exponential time. and can prove this given a somewhat unsatisfactory definition of BPP^HSP, but a) not in a more natural definition (though i still believe it’s possible) and b) of course this is only separation relative to an oracle. but of course we can’t really hope for separations w/o oracles.
Alright, alright, alright. Firstly, as far as I know HSP is *not* known to be equivalent to GI. After all, Approximate Shortest Vector also reduces to HSP, but there’s no known reduction from Approximate Shortest Vector to GI, right?
Secondly, we definitely don’t know whether BQP is in the polynomial hierarchy. That’s one of the biggest enchiladas out there. We can’t even give an oracle relative to which BQP is not in AM (MA is as far as we get). I’ll give BQP a 70% chance of not being in PH.
Scott: oops, I didn’t think I said HSP is equivalent to GI.
I wonder if there is a reduction from the shortest vector problems to graph isomoprhism which uses the symmetric group representation of the dihedral group?
One intermediate problem between GI and HSP is group intersection: Given two subgroups H and K of a group G, find a set of generators for their intersection. Let Gamma be a graph on n vertices. Let G be the group of permutations of all (n choose 2) edges of the complete graph, let H be subgroup given by vertex permutations, and let K be the subgroup given by separate permutations of edges and non-edges of Gamma. Then H cap K = Aut(Gamma).
In the abelian case, if G is explicit and H and K are given by generators, group intersection is in P. If G isn’t explicit then it looks as hard as abelian HSP.
To solve GI, in fact all you need is the “Order of Hidden Subgroup Problem:” input is the same as the HSP, output is the order of the hidden subgroup. Getting within a factor of \sqrt{2} in the order is even enough for GI. But I seem to recall that for the dihedral case, part of the question is which subgroup of order 2 is hidden, so the Order-HSP wouldn’t help much for the dihedral application to shortest vector.
(FYI, distinguishing between trivial and order 2 for GI is only for *rigid* graphs. Now, most graphs are rigid. But even for general graphs, you still just need to be able to compute the order of Aut(G) to within a factor better than \sqrt{2} to solve GI.)