量子一方向性置換の計算量理論的特徴付け

摘要

この論文では量子一方向性置換の計算の複雑さのクラスによる特徴付けという観点から量子一方向性関数の存在について議論する．GrollmannとSelman [GS88]の技法をもとにHomanとThakurはP≠UP∩coUPと一方向性置換の存在の等価性を示し[HT03]，Kashefi，Nishimura，Vedralは逆方向の計算に量子計算を許した場合の一方向性関数（c-q量子一方向性関数）の特徴付けとしてEQP{not contains}UPとc-q量子一方向性関数の存在の等価性を示した[KNV02]．本論文では，まず初めにこの結果を拡張して，EQP{not contains}UP∩coUPとc-q量子一方向性置換の存在の等価性を証明する．二つ目の結果としてUPの量子版UQPを定義することによって，逆方向の計算に加え順方向の計算にも量子計算を許すような量子一方向性置換（q-q量子一方向性置換）においてもEQP≠UQP∩coUQPとq-q量子一方向性置換の存在が等価であることを証明する．