TY - GEN

T1 - How hard is deciding trivial versus nontrivial in the dihedral coset problem

AU - Chia, Nai Hui

AU - Hallgren, Sean

N1 - Publisher Copyright:
© Nai-Hui Chia and Sean Hallgren; licensed under Creative Commons License CC-BY.

PY - 2016/9/1

Y1 - 2016/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84990232113&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990232113&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.TQC.2016.6

DO - 10.4230/LIPIcs.TQC.2016.6

M3 - Conference contribution

AN - SCOPUS:84990232113

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016

A2 - Broadbent, Anne

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016

Y2 - 27 September 2016 through 29 September 2016

ER -