Frédéric Wang    About    Mathematics    Computer Science    Miscellaneous    Archive

Thoughts on the Dihedral Hidden Subgroup Problem (part 2)

In a previous post, I've proposed a way to solve the Dihedral Hidden Subgroup Problem using a superposition of oracle evaluations. However, it seems to require a way to inverse the functions x f ( x , . ) which is a bit cheating since we do not have this feature for the classical problem. In this post, we will consider the case M = N N ' = 2 , d = 2 d ' + b and try to determine the parity b of d . If N is a power of two, this is enough to find d recursively. As in the previous post, the main idea is to consider the superpositions

ψ 0 = 1 N i = 0 N 1 f ( 2 i , 0 )

and

ϕ 0 = 1 N i = 0 N 1 f ( 2 i , 1 )

Using the equality f ( g ( d , 1 ) ) = f ( g ) we can rewrite the latter state

ϕ 0 = 1 N i = 0 N 1 f ( 2 i b , 0 )

If b = 0 , the latter state is the same superposition as the former state, over N ' values of N . Otherwise, b = 1 and the latter state is the superposition over the N ' other values of N . We let f i b = f ( 2 i b , 0 ) and measure the product state ψ 0 ϕ 0 in the basis x x x N , x y + x y x < y N , x y x y x < y N . It turns out that this allows to distinguish the two cases:

  • If b = 0 , the product contains vectors with the same coordinates f i 0 f i 0 for i N . For the other vectors, we have a symmetry between the two coordinates. Hence we can group them by pairs f i 1 0 f i 2 0 + f i 2 0 f i 1 0 for i 1 < i 2 N . Finally, the product state belongs to the space spanned by x x x N and x y + x y x < y N .
  • If b = 1 , the product contains vectors f i 1 0 f i 2 1 where the two coordinates are not equal. We never have two symmetric vectors i.e. which are the same after permutating the two coordinates. Moreover, each vector f i 1 0 f i 2 1 is the expression of a sum/difference (according to the respective order of f i 1 0 and f i 2 1 ) of two vectors x y + x y and x y x y . So the product state belongs half to x y + x y x < y N and half to x y x y x < y N .

Suppose that we have a procedure to create many states ψ 0 and ϕ 0 . We measure a state in the space x y x y x < y N with probability b 2 . So repeating the procedure a constant number of times allow to determine b with high probability.

The only gap in the previous algorithm is whether we can create the states ψ 0 and ϕ 0 . As in the previous post, this is possible if the gates V f , . are available. Otherwise, we can create a superposition of states over N ' and use the gate U f as well as a Quantum Fourier Transform to randomize the first coordinate. We get two random numbers j 1 , j 2 N ' and the states

ψ j 1 = 1 N i = 0 N 1 2 π j 1 i N f ( 2 i , 0 )

and ϕ j 2 = 2 π j 2 d N N i = 0 N 1 2 π j 2 i N f ( 2 ib , 0 )

Next, we can apply the same measurement as above. After a bit of calculation,we get the probabilities:

Space case b = 0 case b = 1
x x x N 1 N ' 0
x y + x y x < y N 2 N 2 i 2 = 0 N 1 i 1 = 0 i 2 1 cos 2 π N ( j 2 j 1 ) ( i 2 i 1 ) 1 2
x y x y x < y N 2 N 2 i 2 = 0 N 1 i 1 = 0 i 2 1 sin 2 π N ( j 2 j 1 ) ( i 2 i 1 ) 1 2

If we repeat the procedure several times, we need to take the means over the choice of j 1 , j 2 N ' . Using some trigonometric identities, it is possible to write the sums of the first column 1 2 + S + o ( 1 N ' ) where S is a sum of cosinus. Unfortunately, evaluating S with a computer suggests that S = Θ ( 1 N ' ) . Hence, we can not distinguish the two cases with only a polynomial (in log N ) number of samplings.

It is still open whether we can find a variation to make such an algorithm efficient...