Nothing like a little shameless self-promotion: quant-ph 0501044
Optimal measurements for the dihedral hidden subgroup problem
Dave Bacon, Andrew Childs, and Wim van Dam
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
Why is this algorithm important? Who would use it and for what? Is it something only of interest to mathematicians? I’m afraid that if I try to explain your algorithm to my wife, she will tell me that a “Hello World” program is more useful to her than yours. She’ll also ask me, “But honey, can’t you use QCs to program general things?” What should I tell her? Another thing: I looked in vain in your paper for a picture of a qubit circuit that performs your algorithm. Have you reduced it to a qubit circuit, yes or no, and if not, when and how.
Well if you ask someone in quantum computing what the algorithm would be useful for (note that we don’t actually construct an algorithm in this paper, this is why you see no quantum circuit in the paper) then I would say for breaking a lattice based cryptosystem. But certainly “hello world” is more important. More importantly, the problem is related to the graph isomorphism problem, but again you wife might say “why do I care about that.” (sorry I mean no offense in using your wife in the example.)
I think in general its very hard to explain why one should wokr in theoretical computer science. Mostly because a majority of people use computers as magic tools without understanding the inner workings. So I guess I might motivate the theory of algorithms by simply saying “more magic.”