In this paper we discuss about the existence of quantum one-way permutation, from the viewpoint of complexity theory. Homan and Thakur proved that there exists a one-way permutation if and only if P ≠UP ∩coUP [HT03], based on the technique by Grollmann and Selman [GS88]. As a characterization of the existence of c-q quantum one-way function (one-way function where we allow quantum adversaries to inverse the function), Kashefi, Nishimura, Vedral proved that there exists a quantum one-way function if and only if EQP (c) UP [KNV02]. First, we extend these results and prove that a c-q quantum one-way function exists if and only if EQP (c) UP∩coUP. For the second result, we consider about a q-q quantum one-way function (one-way function where we allow quantum algorithms not only to inverse the function but also to evaluate the function), and we show that a q-q quantum one-way permutation exists if and only if EQP ≠ UQP ∩ coUQP, where QUP is appropriately defined.%この論文では量子一方向性置換の計算の複雑さのクラスによる特徴付けという観点から量子一方向性関数の存在について議論する.GrollmannとSelman［GS88]の技法をもとにHomanとThakurはP≠UP∩coUPと一方向性置換の存在の等価性を示し［HT03］，Kashefi，Nishimura，Vedralは逆方向の計算に量子計算を許した場合の一方向性関数（c-q量子一方向性関数）の特徴付けとしてEQP(⊇)UPとc-q量子一方向性関数の存在の等価性を示した［KNV02］.本論文では,まず初めにこの結果を拡張して，EQP(⊇)UP∩co UPとc-q量子一方向性置換の存在の等価性を証明する.二つ目の結果としてUPの量子版UQPを定義することによって，逆方向の計算に加え順方向の計算にも量子計算を許すような量子一方向性置換（q-q量子一方向性置換）においてもEQP≠UQP ∩co UQPとq-q量子一方向性置換の存在が等価であることを証明する.
展开▼
