Cryptology ePrint Archive: Report 2021/419

On The Dihedral Coset Problem

Javad Doliskani

Abstract: We propose an efficient quantum algorithm for a specific quantum state discrimination problem. An immediate corollary of our result is a polynomial time quantum algorithm for the Dihedral Coset Problem with a smooth modulus. This, in particular, implies that $\text{poly}(n)$-unique-SVP is in BQP.

Category / Keywords: foundations / Dihedral Coset Problem, Quantum Walk, SVP

Date: received 29 Mar 2021, withdrawn 30 Mar 2021

Contact author: javad doliskani at ryerson ca

Available format(s): (-- withdrawn --)

Version: 20210330:170714 (All versions of this report)

Short URL: ia.cr/2021/419


[ Cryptology ePrint archive ]