任意の量子一方向性関数に対するハードコア述語の一般的構成法

概要

論文の詳細を見る
本論文で我々は任意の量子一方向性関数に対するハードコア述語の一般的構成法を示す. 我々のその構成方法は与えられた量子アルゴリズムの設計方法の基礎となる枠組に基づいており, その枠組は与えられた誤りなしオラクルを同定する量子アルゴリズムの典型的設計手法となっている. また一方でハードコア述語のための安全性帰着は誤りありオラクルが与えられた場合にその同定問題を解くことに相当しており, 我々はそのアルゴリズムの枠組がそのような誤りありオラクルに対しても頑健に動作することを証明することで, その枠組がハードコア述語の安全性帰着に利用できることを示す. 従って, その枠組の上で効率良く解けるオラクル同定問題から, 任意の量子一方向性関数に対するハードコア述語を構成でき, Goldreich-Levinの定理を包含するようなハードコア述語の広いクラスを与えることができる. この我々の構成方法の具体的応用として, 任意の量子一方向性関数に対する以下の二つの新しいハードコア述語を得た. 一つ目の述語QNR_x(r)は, ある適当な素数pに対してx+r mod pが平方剰余でなければQNR_x(r)=1, 平方剰余であれば0と定義される. 二つ目の述語EQ^<2+>_x(r)は, もしx_ix_<i+1>=r_ir_<i+1>ならばEQ(x_ix<i+1>, r_ir<i+1>)=1, そうでなければ0としたときにEQ^<2+>_x(r)=[○!+]^<n/2>_<i=1>EQ(x_ix_<i+1>, r_ir_<i+1>)で定義される. これらは古典計算において任意の一方向性関数に対するハードコア述語であるかどうか知られていない.
2005-03-11

任意の量子一方向性関数に対するハードコア述語の一般的構成法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク