Home // FUTURE COMPUTING 2022, The Fourteenth International Conference on Future Computational Technologies and Applications // View article

A Heuristic Approach to the Dihedral Hidden Subgroup Problem

Authors:
Hachiro Fujita

Keywords: dihedral group, hidden subgroup problem, quantum algorithm, statistical test

Abstract:
The Dihedral Hidden Subgroup Problem (DHSP) is a long-standing open problem in quantum computation. The best known quantum algorithm for the DHSP is Kuperberg’s sieve algorithm which runs in subexponential time. Regev showed that the DHSP is related to a lattice problem on which the security of some public-key cryptosystems is based, and that an efficient solution to the DHSP would lead to breaking such cryptosystems. In this paper, we present a simple quantum algorithm for the hidden subgroup problem over the dihedral group of order a power of two, which runs in polynomial time under some heuristic assumptions. We have implemented our algorithm in MATLAB and tested it with a small example. The simulation result shows evidence of the correctness of our algorithm.

Pages: 1 to 2

Copyright: Copyright (c) IARIA, 2022

Publication date: April 24, 2022

Published in: conference

ISSN: 2308-3735

ISBN: 978-1-61208-949-2

Location: Barcelona, Spain

Dates: from April 24, 2022 to April 28, 2022