이 논문은 이면군 잉여류 문제(Dihedral Coset Problem, DCP)를 다항 시간에 푸는 양자 알고리즘을 제시한다. 이 알고리즘은 이면군 부분군 문제(DSP)를 모듈러 부분집합합 문제로 다항 시간에 환원하는 Regev의 기법을 기반으로 하되, 부분집합합 오라클 없이 표본 비트를 지우는 다른 기법을 사용한다. 이를 Brakerski, Kirshanova, Stehlé, Wen이 개선한 Regev의 격자 문제-DCP 환원과 결합하면, n차원 격자에서 최단벡터문제(SVP)의 다항식 근사나 오류가 있는 학습(LWE) 문제 등 다양한 격자 문제에 대한 다항 시간 양자 알고리즘을 얻을 수 있다. 이 알고리즘은 최대 1/O(log n) 수준의 결함 표본율까지 견딜 수 있어, 예를 들어 √n·polylog(n) 근사 계수의 SVP나 α=√n·polylog(n)인 LWE 인스턴스를 효율적으로 풀 수 있게 해준다. 다만 저자는 최초 초안의 보조정리 3 증명에 오류가 있었음을 인정하고 수정했으며, 최근 이 알고리즘이 작동할 수 없음을 주장하는 별도의 프리프린트가 게시돼 저자 측이 이를 검토 중이라고 밝혔다.

• •이면군 잉여류 문제(DCP)를 다항 시간에 푸는 새로운 양자 알고리즘 제시
• •Regev의 DSP→모듈러 부분집합합 환원을 기반으로 하되 부분집합합 오라클 없이 표본 비트 삭제하는 새 기법 사용
• •개선된 격자-DCP 환원과 결합해 SVP·LWE 등 격자 문제의 다항 시간 양자 알고리즘 도출 가능
• •결함 표본율 최대 1/O(log n)까지 허용, √n·polylog(n) 근사 SVP 등에 적용 가능
• •초안의 보조정리 증명 오류를 수정했으며, 알고리즘이 작동 불가능하다고 주장하는 반박 프리프린트가 게시돼 저자가 검토 중