Abstract
We present a randomized algorithm to solve a system of diagonal polynomial equations over finite fields when the number of variables is greater than some fixed polynomial of the number of equations whose degree depends only on the degree of the polynomial equations. Our algorithm works in time polynomial in the number of equations and the logarithm of the size of the field, whenever the degree of the polynomial equations is constant. As a consequence we design polynomial time quantum algorithms for two algebraic hidden structure problems: for the hidden subgroup problem in certain semidirect product \(p\)-groups of constant nilpotency class, and for the multi-dimensional univariate hidden polynomial graph problem when the degree of the polynomials is constant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ajtai, M.: Generating hard instances of lattice problems. In: 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 99–108 (1996)
Bacon, D., Childs, A.M., van Dam, W.: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In: 46th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 469–478 (2005)
Chevalley, C.: Démonstration d’une hypothèse de M. Artin. Abh. Math. Sem. Hamburg 11, 73–75 (1936)
Childs, A.M., Schulman, L., Vazirani, U.: Quantum algorithms for hidden nonlinear structures. In: 48th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 395–404 (2007)
Decker, T., Draisma, J., Wocjan, P.: Quantum algorithm for identifying hidden polynomial function graphs. Quantum Inf. Comput. 9, 0215–0230 (2009)
Decker, T., Høyer, P., Ivanyos, G., Santha, M.: Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Inf. Comput. 14, 790–806 (2014)
Decker, T., Ivanyos, G., Santha, M., Wocjan, P.: Hidden symmetry subgroup problems. SIAM J. Comput. 42, 1987–2007 (2013)
Denney, A., Moore, C., Russell, A.: Finding conjugate stabilizer subgroups in \(PSL(2; q)\) and related groups. Quantum Inf. Comput. 10, 282–291 (2010)
Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and translating coset in quantum computing. SIAM J. Comput. 43, 1–24 (2014)
Grigni, M., Schulman, L., Vazirani M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In: 33rd ACM Symposium on Theory of Computing (STOC), pp. 68–74 (2001)
Hallgren, S., Russell, A., Ta-Shma, A.: Normal subgroup reconstruction and quantum computation using group representations. SIAM J. Comput. 32, 916–934 (2003)
Huang, M-D.A: Riemann hypothesis and finding roots over finite fields. In: 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 121–130 (1985)
Ivanyos, G., Santha, M.: On solving systems of diagonal polynomial equations over finite fields. arXiv:1503.09016 [cs.CC]
Ivanyos, G., Sanselme, L., Santha, M.: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Algoritmica 62, 480–498 (2012)
Jozsa, R.: Quantum factoring, discrete logarithms, and the hidden subgroup problem. Comput. Sci. Engin. 3, 34–43 (2001)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, New York (1972)
Kitaev, A.Y.: Quantum measurements and the Abelian Stabilizer Problem (1995). arXiv:quant-ph/9511026v1
Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35, 170–188 (2005)
Moore, C., Rockmore, D., Russell, A., Schulman, L.: The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1113–1122 (2004)
Papadimitriou, C.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48, 498–532 (1994)
Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33, 738–760 (2004)
Shanks., D.: Five number-theoretic algorithms. In: 2nd Manitoba Conference on Numerical Mathematics, pp. 51–70 (1972)
Shor, P.: Algorithms for quantum computation: discrete logarithm and factoring. SIAM J. Comput. 26, 1484–1509 (1997)
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)
van de Woestijne, C.E.: Deterministic equation solving over finite fields. Ph.D. thesis, Universiteit Leiden (2006)
Warning, E.: Bemerkung zur vorstehenden Arbeit von Herrn Chevalley. Abh. Math. Sem. Hamburg 11, 76–83 (1936)
Acknowledgements
Research was supported in part by the Hungarian Scientific Research Fund (OTKA) Grant NK105645, the Singapore Ministry of Education and the National Research Foundation Tier 3 Grant MOE2012-T3-1-009, by the European Commission IST STREP project Quantum Algorithms (QALGO) 600700, and the French ANR Blanc Program Contract ANR-12-BS02-005.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Ivanyos, G., Santha, M. (2015). On Solving Systems of Diagonal Polynomial Equations Over Finite Fields. In: Wang, J., Yap, C. (eds) Frontiers in Algorithmics. FAW 2015. Lecture Notes in Computer Science(), vol 9130. Springer, Cham. https://doi.org/10.1007/978-3-319-19647-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-19647-3_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19646-6
Online ISBN: 978-3-319-19647-3
eBook Packages: Computer ScienceComputer Science (R0)