量子コンピューティングと Z₂ 上の多項式方程式

量子コンピュータの計算能力はどの程度ですか？私たちは、量子計算の出力を決定することが、有限体 Z₂ 上で定義された簡単に計算される多項式の解の数を数えることと同等であることを示します。この関係により、BQP/P/\#P と BQP/PP の間の2つの既知の関係のために簡単な証明が提供されます。