가역원군

• 영어 명칭: Unit Group
• 속도 향상: 초다항적
• 구현 코드: ∅

$\theta$를 근으로 갖는 다항식 중 가장 낮은 차수가 $d$일 때, 수체 $\mathbb{Q}(\theta )$의 차수를 $d$라고 한다. $\mathbb{Z}[x]$ 상에서 최고차항의 계수가 1인 다항식의 근인 $\mathbb{Q}(\theta )$의 원소로 이루어진 집합 $\mathcal{O}$은 환을 이루는데, 이 환을 $\mathbb{Q}(\theta )$의 정수환이라고 한다. 환 $\mathcal{O}$의 가역원으로 이루어진 집합은 군 ${\mathcal{O}}^{\ast }$를 이룬다. 홀그렌(Hallgren)이 보인 바와 같이 [50] (슈미트(Schmidt)와 볼머(Vollmer)도 독자적으로 보임 [116]), 고정된 차수를 가지는 임의의 $\mathbb{Q}(\theta )$에 대하여, 양자 컴퓨터는 주어진 $\theta$를 토대로 ${\mathcal{O}}^{\ast }$의 생성자를 다항 시간에 찾을 수 있다. 이를 다항 시간에 해결하는 고전 알고리즘은 알려지지 않았다. 홀그렌과 공동 연구자들은 곧바로 차수가 커짐에도 다항 시간에 해결하는 방법을 발견했다 [213]. [329]도 참고. 이 알고리즘은 실수 덧셈군 상에서의 아벨 숨은 부분군 문제를 해결하는데 기반한다.