1. Introduction
Let be a finite group and a hidden subgroup of . A function which is constant on left -cosets and takes distinct values on distinct left -cosets is called a separating function for the subgroup .
The hidden subgroup problem (HSP) is the problem of finding generators for the hidden subgroup , given access to evaluations of a separating function for . This problem can be solved in polynomial time using a quantum computer when is an abelian group and has been extensively studied for many finite groups [5] [3] [4]. The cyclic group case leads to an efficient quantum algorithm to factor integers [5] [9]. A survey of known results about the HSP for dihedral groups can be found in [6] [4], where we note a subexponential quantum algorithm is given in [7].
A polynomial time quantum algorithm for solving the hidden subgroup problem on dihedral groups would imply a polynomial time quantum algorithm to solve certain hard lattice problems which are considered intractable using classical computers [8]. Another example is the HSP on the symmetric group, which can be used to solve the graph isomorphism problem, a well-known NP-complete problem.
In this paper, we review the standard HSP algorithm as it applies to the dihedral groups and detail the obstructions for this algorithm to succeed in this case. On the other hand, we explain how the standard HSP algorithm yields the polynomial query complexity result of [1].
Finally, we prove a number of results which provide a new connection between the dihedral coset problem (DCP) and cloning of quantum states.
2. Acknowledgements
We would like to thank P. Høyer for helpful comments and bringing to our attention [7].
3. The QFT for finite groups
Let be a finite group and denote a complete set of representatives for the isomorphism classes of irreducible representations of over . For a representation , let be the dimension of
. Recall the Quantum Fourier Transform (QFT) on
is defined as the linear transformation
(3.1) | ||||
where is the
-vector space generated by
, and is the -vector space generated by , . Picking an isomorphism , it is a unitary operator which can be efficiently approximated using quantum circuits.Suppose is the dihedral group of order , which can be presented as
If is even, there are four -dimensional representations given by
(3.2) |
where . These are pull backs of the four -dimensional representations of under the quotient homomorphism , where denotes the cyclic group of order .
If
is odd, there are two
-dimensional representations given by where . These are pull backs of the two -dimensional representations of under the quotient homomorphism .There are irreducible representations of dimension given by
(3.3) | ||||
for , where . These are the induction of the representation given by from to .
The representations and form the complete list of irreducible representations of up to isomorphism.
4. The standard HSP algorithm
In the standard algorithm for finding hidden subgroups from a separating function, we perform the following steps:
We form the state
(4.1) |
where is the given separating function.
This can be achieved by starting with the state , where is the identity element of , then performing the following computations:
(4.2) | ||||
(4.3) |
Measuring the second register and discarding it, we obtain a state of the form
(4.4) |
We apply the QFT to the above state to obtain
(4.5) |
In the case of being an abelian group, measuring gives sufficient information to determine efficiently after running this process repeatedly and using post processing [5].
In the case of and
, the probability of obtaining
is when , which does not allow one to distinguish the groups .Explicitly, in the complex basis (3.3):
If , then
(4.6) | ||||
(4.7) |
If , then
(4.8) | ||||
(4.9) | ||||
If one changes to the real basis, we get a probability distribution dependent on
, but it is very flat, making it hard to distinguish the subgroups .More generally, in order for the QFT to be an unitary operator, we require that be unitary for every and for . In particular, for any set of -dimensional irreducible representations , we have that
where is the probability of observing the state . Although the choice of basis may result in probability distributions of states which depend on , if is very large, the above inequalities show that the probabilities will always be very flat.
Remark 4.10.
In [1], it is shown that the hidden subgroup problem for for a general subgroup is reduced to the case of a single reflection subgroup .
5. Dihedral coset sampling
In the standard HSP algorithm, after the first step we are left with random coset samples as in (4.4). In the case of , the dihedral group of order , and , this is explicitly of the form
(5.1) | ||||
where .
Remark 5.2.
The second case is reduced to the first by the transformation if this transformation leaves the distribution of invariant.
Given samples of the form
(5.3) |
the dihedral coset problem (DCP) is the problem of finding generators for the hidden subgroup . The states are called DCP samples for .
For HSP samples produced from the standard algorithm, where
is from the uniform distribution, we may view HSP samples as DCP samples by Remark
5.2.6. Polynomial quantum query complexity
In [1], it is shown that a polynomial number of HSP samples is sufficient to recover using exponential time post processing. A related result in [2] using different methods shows the HSP problem in a general finite group has polynomial quantum query complexity.
Transposing , and applying a Hadamard gate to the state in (4.6), gives the state
(6.1) |
The probability of observing the first row is
(6.2) |
For the second row, it is
(6.3) |
We are now in the situation of [1] and can apply the post processing algorithm described (which is exponential in time) to determine with high probability, for large .
7. Relation to quantum cloning
By copying a state , we mean forming the composite state for a blank initialization state and ancilla state , and applying a quantum algorithm to produce the state .
The no cloning theorem asserts that there is no unitary operation which can copy a general unknown quantum state. However, if the states are chosen from a known set of mutually orthogonal states, cloning is possible as the following proposition shows.
Proposition 7.1.
Let be a set of mutually orthogonal states which depend on a parameter . Suppose for some index (which is unknown).
If the value of is known, then there is a unitary operation which copies .
Proof.
First note that we can copy any state of the computational basis. Start with
(7.2) |
where we have encoded the last two registers into qubits, for large enough.
Applying a CNOT gate to the th and th qubits produces for every . Hence, we can produce the state
(7.3) |
Now, encode a unitary operator which has the effect
Starting with
(7.4) |
apply to the first register to obtain
(7.5) |
Copy the state to obtain
(7.6) |
Applying to both registers gives
(7.7) |
∎
Proposition 7.8.
Let be a set of mutually orthogonal states which depend on a parameter . Suppose for some index (which is unknown).
Suppose we can encode a unitary operator such that .
If we have the value of in a register, then there is a unitary operation which copies .
Proof.
Starting with
(7.9) |
apply to obtain
(7.10) |
Copy the states and to obtain
(7.11) |
Applying to both pairs of registers gives
(7.12) |
which we can permute to obtain
(7.13) |
∎
Proposition 7.14.
If we can copy any given DCP sample
(7.15) |
to produce a state of the form
(7.16) |
then we can determine the value of from DCP samples for .
If is known, then we can copy any given DCP sample for using a unitary operation.
Proof.
Given samples of the form (7.16), we measure both registers, and with probability we obtain
(7.17) |
The sum of the observed exponents of the two registers gives .
Remark 7.18.
In [7], it is shown that the HSP for reduces to determining the parity of . Copying a DCP sample up to parity would allow one to determine the parity of .
Theorem 7.19.
If is unknown, there is no unitary operation, which from a list of DCP samples for , copies an additional DCP sample for the same , while leaving the list of DCP samples alone.
Proof.
Suppose there is a unitary operator which transforms
(7.20) |
where is a DCP sample for fixed, and randomly chosen for each such state (the quantity is suppressed in the notation ). Here is a blank initialization state and is an ancilla state.
We are supposing performs the above operation for any (unknown) . Thus, we also have that
(7.21) |
for any other .
Taking the inner product of both sides of (7.20) and (7.21) we deduce
(7.22) |
However, there are choices of for , and which do not satisfy (7.22).
To see this, recall the states
have possible inner product , and there are choices of and such that , for instance, if and .
We may thus suppose without loss of generality that for all , and hence (7.22) becomes
We obtain a contradiction again by choosing and so that as then
(7.23) | |||
(7.24) |
∎
Theorem 7.25.
There is no unitary operation to compute the value of into a register from a list of DCP samples for .
Proof.
Suppose there is a unitary operator which has the effect
(7.26) |
That is, takes takes a list of DCP samples for fixed but unknown , a blank initialization state , and an ancilla state , and then computes into the blank register.
Using an additional blank register and copying , there is a unitary operator with the effect
(7.27) |
Use and permute and to obtain
(7.28) |
Thus, without loss of generality, we may assume the unitary operator has the effect
That is, takes takes a list of DCP samples for fixed but unknown , a blank initialization state , and an ancilla state , and then computes into the blank register, while leaving the list of DCP samples alone.
Now, note that DCP samples can be encoded using two registers as
The unitary operator which sends
will have the effect
Using a Hadamard gate, we can encode a unitary operator such that
Then the unitary operator has the effect
The proof of Theorems 7.19 and 7.25 are based on the no cloning theorem [10], which preclude unitary operations, but not more general quantum algorithms, which may allow for approximate outputs, probabilistic processes, or post-processing. Indeed, computing the exact value of into a register is rather strong: even in the finite cyclic group case, the standard algorithm only determines a generator for the hidden subgroup using a probabilistic process.
On the other hand, Proposition 7.14 has the consequence that advances in quantum cloning algorithms would have implications for the DCP problem.
References
- [1] M. Ettinger and P. Høyer, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics 25 (2000), 239–251.
- [2] M. Ettinger and P. Høyer, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters 91 (2004), no. 1, 43–48.
- [3] M. Grigni, L. Schulman, M. Vazirani, and U. Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Combinatorica, 24 (1) (2004), 137–154.
- [4] S. Hallgren, A. Russell, and A. Ta-Shma, The hidden subgroup problem and quantum computation using group representations, SIAM J. Comput., 32 (4) (2003), 916–834.
- [5] A. Kitaev, Quantum computations: Algorithms and error correction, Russian Math. Surveys, 52 (1997), 1191–1249.
- [6] H. Kobayashi and F. Le Gall, Dihedral hidden subgroup problem: a survey, IPSJ Journal, 46 (10) (2005), 2409–2416.
- [7] G. Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Computing, 35 (1) (2005), 170–188.
- [8] O. Regev. Quantum computation and lattice problems. SIAM Journal on Computing, 33 (3) (2004), 738–760.
- [9] P. Shor. Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Fundamentals of Comp. Science (FOCS), 1994, 124–134.
- [10] W.K. Wootters and W.H. Zurek. A single quantum cannot be cloned. Nature 299 (1982), 802–803.
Comments
There are no comments yet.