가우스 합

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

${\mathbb{F}}_q$를 유한체라고 하자. $0$이 아닌 ${\mathbb{F}}_q$의 원소는 곱셈에 대한 군 ${\mathbb{F}}_q^{\times }$를 이루고, 또 ${\mathbb{F}}_q$의 원소는 (아벨 군이지만 순환군은 아닌) 덧셈에 대한 군 ${\mathbb{F}}_q^{+}$를 이룬다. ${\mathbb{F}}_q^{\times }$에서 지표 ${\chi }^{\times }$를, ${\mathbb{F}}_q^{+}$에서 ${\chi }^{+}$를 택하도록 하자. 이에 해당하는 가우스 합은 이 지표들의 내적이다: ${\sum }_{x\ne 0\in {\mathbb{F}}_q}{\chi }^{+}(x){\chi }^{\times }(x)$. 반 담(van Dam)과 세루시(Seroussi)가 보인 바와 같이 [90], 양자 컴퓨터를 사용하면 가우스 합을 다항 시간에 다항 정밀도로 추정할 수 있을 것으로 보인다. 유한환은 곱셈에 대하여 군을 이루지 않지만, 그 유한환의 가역원은 가능하다. 환의 덧셈군에서 표현을 택하고 또 가역원의 곱셈군에서 표현을 택한다면, 유한환의 가역원 상에서 가우스 합을 얻을 수 있다. 이것도 양자 컴퓨터로 다항 시간에 다항 정밀도로 추정할 수 있을 것으로 보인다. 고전 알고리즘 중에서 다항 시간에 가우스 합을 추정할 수 있는 것은 알려지지 않았다. 이산 로그 문제는 가우스 합 추정 문제로 환산될 수 있다 [90]. 일부 포츠 모형의 분배 함수는 가우스 합 추정에 관련된 알고리즘을 통해 다항 시간에 계산할 수 있다 [47].