How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?

Authors Nai-Hui Chia, Sean Hallgren



PDF
Thumbnail PDF

File

LIPIcs.TQC.2016.6.pdf
  • Filesize: 499 kB
  • 16 pages

Document Identifiers

Author Details

Nai-Hui Chia
Sean Hallgren

Cite AsGet BibTex

Nai-Hui Chia and Sean Hallgren. How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.TQC.2016.6

Abstract

We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density > 1 and also to quantum sampling subset sum solutions. We examine a decision version of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density >1. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density >1 but approaching 1 as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions.
Keywords
  • Quantum algorithms
  • hidden subgroup problem
  • random subset sum problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. D. Bacon, A. M. Childs, and Wim van Dam. Optimal measurements for the dihedral hidden subgroup problem. Chicago J. Theor. Comput. Sci., 2006. Google Scholar
  2. Matthijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern. Improved low-density subset sum algorithms. Computational Complexity, 2(2):111-128, 1992. Google Scholar
  3. Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, and Miklos Santha. An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pages 226-238, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_20.
  4. Mark Ettinger and Peter Høyer. On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics, 25(3):239-251, 2000. Google Scholar
  5. Stephen Fenner and Yong Zhang. Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings, chapter On the Complexity of the Hidden Subgroup Problem, pages 70-81. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-79228-4_6.
  6. Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, and Pranab Sen. Hidden translation and translating coset in quantum computing. SIAM J. Comput., 43(1):1-24, 2014. URL: http://dx.doi.org/10.1137/130907203.
  7. Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, and Pranab Sen. Limitations of quantum coset states for graph isomorphism. J. ACM, 57:34:1-34:33, November 2010. URL: http://dx.doi.org/10.1145/1857914.1857918.
  8. Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology, 9:236-241, 1996. Google Scholar
  9. Gábor Ivanyos, Luc Sanselme, and Miklos Santha. An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. In Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, and Luerbio Faria, editors, LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings, pages 759-771, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-540-78773-0_65.
  10. Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput., 35(1):170-188, 2005. Google Scholar
  11. Greg Kuperberg. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, May 21-23, 2013, Guelph, Canada, pages 20-34, 2013. Google Scholar
  12. J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. Journal of the Association for Computing Machinery, 32(1):229-246, 1985. Google Scholar
  13. Oded Regev. Quantum computation and lattice problems. SIAM J. Comput., 33(3):738-760, 2004. Google Scholar
  14. Phillip Rogaway and Thomas Shrimpton. Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance, pages 371-388. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. URL: http://dx.doi.org/10.1007/978-3-540-25937-4_24.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail