トップ 差分 一覧 ソース 検索 ヘルプ PDF RSS ログイン

量子アルゴリズム輪講

趣旨

"論文を手分けして読み、発表することで、個々人が論文読みに費やす時間を短縮すること"、および、"既存の量子アルゴリズムのアイディアについて理解を深めること"が目的です。

Quantum Algorithm Zoo に紹介されている論文から興味のあるものを各自読み、1,2時間程度で論文の結果、アイデア、テクニックなどについて紹介を行います。(*もちろんそのほかに興味のある論文でもよい。)

進め方

毎回、1人が担当。発表の方法は自由。

論文の中には、ページ数制限などの影響も有り、完全に読みこなすのは現実的に難しいものもあります。このようなものには無理に時間をかけずに、解る範囲で発表をしてください。また、解析等で疑問点がある場合は発表時に議論することにより解消していきましょう。

論文リスト(興味あるものを適宜追加)

アルゴリズム タイトル 著者
Searching Nested quantum search and NP-hard problems N.J.Cerf, L.K.Grover, and C.P.Williams
Span program Span Programs for Functions with Constant-Sized 1-certificates A.Belovs

発表担当の決まったもの

発表者 タイトル 著者

これまでに読んだ論文

アルゴリズム タイトル 著者
Searching A quantum algorithm for finding the minimum C.Durr and P.Hoyer
Walk algorithm Quantum walk algorithm for element distinctness A.Ambainis
Searching The quantum query complexity of approximating the median and related statistics A.Nayak and F.Wu.
Searching Quantum search with advice A.Montanaro
下界証明 A polynomial quantum query lower bound for the set equality problem G.Midrijanis