On the complexity of the hidden subgroup problem. (English) Zbl 1139.68343
Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 70-81 (2008).
Summary: We show that several problems that figure prominently in quantum computing, including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or reducible to Hidden Subgroup. We also show that, over permutation groups, the decision version and search version of Hidden Subgroup are polynomial-time equivalent. For Hidden Subgroup over dihedral groups, such an equivalence can be obtained if the order of the group is smooth. Finally, we give nonadaptive program checkers for Hidden Subgroup and its decision version.
For the entire collection see [Zbl 1136.68001].
For the entire collection see [Zbl 1136.68001].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 81P68 | Quantum computation |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
References:
| [1] | Arvind, V.; Kurur, P. P., Graph Isomorphism is in SPP, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (2002), New York: IEEE, New York · Zbl 1110.68090 |
| [2] | Arvind, V.; Torán, J., A nonadaptive NC checker for permutation group intersection, Theoretical Computer Science, 259, 597-611 (2001) · Zbl 0974.68022 · doi:10.1016/S0304-3975(00)00159-6 |
| [3] | Blum, M.; Kannan, S., Designing programs that check their work, Journal of the ACM, 42, 1, 269-291 (1995) · Zbl 0886.68046 · doi:10.1145/200836.200880 |
| [4] | Childs, A. M.; Schulman, L. J.; Vazirani, U. V., Quantum algorithms for hidden nonlinear structures, FOCS 2007: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 395-404 (2007), Washington: IEEE Computer Society, Washington |
| [5] | Childs, A.M., van Dam, W.: Quantum algorithm for a generalized hidden shift problem. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1225-1232 (2007) · Zbl 1302.68121 |
| [6] | Ettinger, M.; Høyer, P., On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics, 25, 239-251 (2000) · Zbl 0967.68076 · doi:10.1006/aama.2000.0699 |
| [7] | Ettinger, M.; Høyer, P.; Knill, E., The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters, 91, 1, 43-48 (2004) · Zbl 1178.68268 · doi:10.1016/j.ipl.2004.01.024 |
| [8] | Furst, M.L., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. In: Proceedings of the 21st IEEE Symposium on Foundations of Computer Science, pp. 36-41 (1980) |
| [9] | Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and orbit coset in quantum computing. In: Proceedings of the 35th ACM Symposium on the Theory of Computing, pp. 1-9 (2003) · Zbl 1192.81066 |
| [10] | Grigni, M.; Schulman, J.; Vazirani, M.; Vazirani, U., Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Combinatorica, 24, 1, 137-154 (2004) · Zbl 1057.81009 · doi:10.1007/s00493-004-0009-8 |
| [11] | Hallgren, S., Moore, C., Rötteler, M., Russell, A., Sen, P.: Limitations of quantum coset states for graph isomorphism. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 604-617 (2006) · Zbl 1301.68130 |
| [12] | Hallgren, S.; Russell, A.; Ta-Shma, A., The hidden subgroup problem and quantum computation using group representations, SIAM Journal on Computing, 32, 4, 916-934 (2003) · Zbl 1029.81015 · doi:10.1137/S009753970139450X |
| [13] | Jozsa, R.: Quantum factoring, discrete algorithm and the hidden subgroup problem (manuscript, 2000) |
| [14] | Kitaev, A.Y.: Quantum measurements and the Abelian Stabilizer problem, quant-ph/9511026 (1995) |
| [15] | Kempe, J., Shalev, A.: The hidden subgroup problem and permutation group theory. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouver, British Columbia, January 2005, pp. 1118-1125 (2005) · Zbl 1297.68077 |
| [16] | Mathon, R., A note on the graph isomorphism counting problem, Information Processing Letters, 8, 131-132 (1979) · Zbl 0395.68057 · doi:10.1016/0020-0190(79)90004-8 |
| [17] | Mosca, M.: Quantum Computer Algorithms. PhD thesis, University of Oxford (1999) |
| [18] | Moore, C., Russell, A., Schulman, L.J.: The symmetric group defies strong fourier sampling. In: FOCS 2005: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 479-490 (2005) · Zbl 1155.68029 |
| [19] | Moore, C., Russell, A., Sniady, P.: On the impossibility of a quantum sieve algorithm for graph isomorphism. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 536-545 (2007) · Zbl 1232.68054 |
| [20] | Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2000), Cambridge: Cambridge University Press, Cambridge · Zbl 1049.81015 |
| [21] | Quantum pontiff, http://dabacon.org/pontiff/?p=899 |
| [22] | Regev, O., Quantum computation and lattice problems, SIAM Journal on Computing, 33, 3, 738-760 (2004) · Zbl 1057.81012 · doi:10.1137/S0097539703440678 |
| [23] | Scott, W.R.: Group Theory. Dover Publications, Inc. (1987) · Zbl 0641.20001 |
| [24] | Sims, C.C.: Computational methods in the study of permutation groups. In: Computational problems in abstract algebra, pp. 169-183 (1970) · Zbl 0215.10002 |
| [25] | van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. In: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms, pp. 489-498 (2003) · Zbl 1092.68729 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
