Let’s Dance, put on your red shoes and dance the blues.
That’s right, it’s the new paper dance! My new addition to that noise factory also known as the quant-ph arXiv: quant-ph/0612107.
How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
Authors: Dave Bacon
It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty-good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty-good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a vital new primitive in quantum algorithm design.
I’m looking forward to reading this interesting paper. But I can’t help but wonder… why didn’t you wait 2 weeks and try to be come the first paper of the new year in the new format? Maybe you have another paper up your sleeve?
I like the topic of this paper! It looks like, as promised, it simplifies the algorithm in Bacon, Childs, and van Dam.
In my paper, I have a lemma that the Clebsch-Gordan transform for any group can be computed using three QFTs. (Or rather, two inverse QFTs and one forward one.) I am having trouble finding this remark (which was later discovered independenty by Cris Moore, et al) in your new paper. You may already say it somewhere, but if not, it should be mentioned. The Clebsch-Gordan transform may be a right-thinking primitive in quantum algorithms (I certainly think so), but it is only sort-of “new”, in light of its universal reduction.
Also, although your bibliography is right-thinking with regard to arXiv citations, in other respects it could be better organized. In mathematics, the convention is to include both the title and full names of authors (at least when the cited paper has them), for both published and unpublished papers. We also usually alphabetize the bibliography. Computer scientists are similar. You use a less reasonable bibliography style which is common in condensed-matter physics.
Hey Greg, Could you point me to the part of your paper with Clebsch-Gordan transform? My reading, from what I recall in both your a Cris’s paper (and a similar result Aram Harrow and I had in our first Schur paper, but you have to dig back through the old arxiv versions), was that you have a transform which gets at the space where the irrep acts, but not at the multiplicity space?
In other words, for me the Clebsch-Gordan transform acts to change the basis where two irreps act |v> \otimes |w> into a basis where you have the irrep label |mu>, and two spaces, one with the multiplicity |i> and the other where the direct product irrep acts |j>. My recollectin was that your description ended up only with access to irrep label |j>. In particular it is important in the paper I just pu on the arxiv that the multiplicity register is available…that’s the one where all the information is for the hscp (as opposed to what happens in your dihedral algorithm)
But you’re right that I should have sighted the transform you use as well as the one of Moore (and also the one in Aram’s thesis). Doh. But is my understanding of what these transform do right or wrong?
Oh, and we physicist just remember what reference goes to what title and the full names of all authors. 🙂
In the current arXiv version of my paper, the reduction is given as Proposition 9.1. In principle you do get access to the multiplicity state as well, but I have not thought about whether the information is there in any simple form. I think that it has to be there somehow, actually. You get two registers which are both copies of the group algebra C[G]. The right register has the in-representation state |j>, which of course I use in my algorithm. Probably the left register has the multiplicity state in it.
Where you are correct is that no one has previously considered the multiplicity state in the quantum Clebsch-Gordan transform as far as I know. At the very least, the method of Proposition 9.1 has to be refined to explain how to get at it.
This did cross my mind, considering that Aram and Ike and I got the first paper of 06.
Hi Dave,
Congratulations for your new paper..you are working hard and the more you write the more my admiration towards you and the honour of having collaborated with you grows fast..
Hope to see you see soon
Andrea
I’m so gonna nail that 1st paper of ’07 title…