Tomoyuki Morimae 森前智行

 

京都大学基礎物理学研究所 准教授

 

Associate Professor

Quantum Information group

Yukawa Institute for Theoretical Physics, Kyoto University, Japan

Email address: first.family (at) yukawa.kyoto-u.

Post address: Kitashirakawa Oiwakecho, Sakyo-ku, Kyoto, 606-8502 Japan

 

私の研究室を志望する学生の方は

京都大学大学院理学研究科 物理学・宇宙物理学専攻 物理学第一分野

T2 物性基礎論:量子情報(基礎研)

に応募してください。また、一度アポイントメントを取って見学に来てください。

研究場所は都大学基礎物理学研究所になります。

 

----------------------------------------------------------------------------

大学院講義

2021年度前期月曜2限(10:30〜12:00)

オンラインになりました。こちらから登録してリンクを得てください。

https://zoom.us/meeting/register/tJMpd-yvqTwjH9aEKpKudqMVZZowItW8iSj1

 

 

スケジュール

 

1回目:CliffordGottesman-KnillMagic

参考文献:

Nielsen-Chuangの教科書(英語!)

森前、量子計算理論、森北出版

 

 

2回目:Stabilizer rank, Obfuscation for Clifford circuits, 測定型量子計算

参考文献:

Bravyi and Gosset, Phys. Rev.Lett. 116, 250501 (2016).

Bravyi, Smith, and Smolin, Phys. Rev. X 6, 021043 (2016).

Broadbent and Kazmi, arXiv:2005.14699

小柴、藤井、森前、観測に基づく量子計算、コロナ社

Raussendorf本人のVideo lecture: https://phas.ubc.ca/~raussen/Supplements/VideoLectures.html

 

 

3回目: MPS, Tensor-network, AKLTと測定型量子計算、ブラインド量子計算、量子計算の検証

参考文献:

小柴、藤井、森前、観測に基づく量子計算、コロナ社

Raussendorf本人のVideo lecture: https://phas.ubc.ca/~raussen/Supplements/VideoLectures.html

Broadbent-Fitzsimons-Kashefi, FOCS2009

Morimae-Fujii, PRA 87, 050301 (2013)

Fitzsimons-Kashefi, PRA 96, 012303 (2017)

Hayashi-Morimae, PRL 115, 220502 (2015)

Morimae-Nagaj-Schuch, PRA 93, 022326 (2016)

 

 

4回目: P, BPP, BQP, PSPACE, NP, MA, QMA

参考文献:

Sipser, Introduction to The Theory of Computation

Arora and Barak, Computational Complexity: A Modern Approach

Vidick and Watrous, Quantum proofs: https://arxiv.org/abs/1610.01664

 

 

5回目:IP, QIP, Local Hamiltonian problem

参考文献:

Vidick and Watrous, Quantum proofs: https://arxiv.org/abs/1610.01664

Aharonov and Naveh, Quantum NP -A survey: https://arxiv.org/abs/quant-ph/0210077

 

 

6回目:量子計算の検証、Posthoc protocol、ゼロ知識証明

Gheorghiu, Kapourniotis, Kashefi, https://arxiv.org/pdf/1709.06984.pdf

Morimae and Yamakawa, https://arxiv.org/pdf/2102.09149.pdf

Broadbent and Grilo, https://arxiv.org/pdf/1911.07782.pdf

Aharonov and Green, https://arxiv.org/pdf/1710.09078.pdf

 

 

7回目:QMAMDeutchのアルゴリズム、Fourier hierarchy、多項式法

Marriott-Watrous, https://arxiv.org/pdf/cs/0506068.pdf

http://tomoyukimorimae.web.fc2.com/query_complexity_j.pdf

 

 

8回目:量子スプレマシー(multiplicative-error sampling)、postBQPNQP

森前、量子計算理論(森北出版)、10章

 

 

9回目:量子スプレマシー(additive-error sampling)Fine-grained量子スプレマシー

森前、量子計算理論(森北出版)、10章

Morimae and Tamaki, Quantum 4, 329 (2020); arXiv:1912.06336

Morimae and Tamaki, Quant. Inf. Comput. 19, 1089 (2019); arXiv:1901.01637

 

 

10回目:LWENoisy trapdoor claw-free functionProof of quantumness、マハデフ

 

 

11回目:

 

 

12回目:

 

 

13回目:

 

 

14回目:

 

 

(今後の予定)

IT secure QFHEの不可能性

WiesnerConjugate codingPrivate量子マネー、量子ビットコミットメント、量子Oblivious transferRemote state preparationQfactory

Quantum tokenized MACCertified deletionUnclonable encryption

Quantum lightningOne-shot signatureWitness encryption for QMA

 

----------------------------------------------------------------------------

研究テーマ

1.量子優位性(量子スプレマシー)の理論的証明

量子計算が古典計算より速いというのは、計算量理論の「標準的」な意味ではBQPBPPを意味しますが、実はこれはまだ証明されていません。(もしこれが証明できてしまうとPPSPACEという古典計算量理論における大未解決問題を証明したことになるので、そう簡単には証明できないだろうと考えられています。)そうはいうものの、皆量子計算は古典計算より速いだろうと信じているわけですが、その証拠として以下の3つのタイプの結果がこれまでに得られてきています。

(1)素因数分解等のように、古典のベストのアルゴリズムより速い量子アルゴリズムが見つかっている。

(2)検索問題等のように、「サブルーチン」を呼ぶ回数が量子のほうが古典より少なくて済むという結果が知られている。(query complexityのことをいっています。)

(3)多項式階層の無限性といったような古典の計算量理論において信じられている仮定のもとでは量子計算のほうが古典計算よりも速いことが示されている。

私はこの(3)について研究をしてきました。きれいに初期化された量子ビットが一つしか使えないような「弱い」量子計算モデルであっても(多項式階層が崩壊しない限り)古典計算機では多項式時間でシミレートできないことを示したり、古典のfine-grained complexity theoryにおける仮定に基づいて、古典の指数時間であっても量子計算がシミレートできないことなどを示してきました。詳しくは昔の解説MBQC本の7.3節、QC本の10章、量子計算で出来ること・出来ないこと」 日本物理学会誌2019年2月号 話題、また以下の論文を参照してください。

TM, Fujii, and Fitzsimons, Hardness of classically simulating the one clean qubit model, Phys. Rev. Lett. 112, 130502 (2014)

Fujii, Kobayashi, TM, Nishimura, Tamate, and Tani, Impossibility of classically simulating one-clean-qubit computation, Phys. Rev. Lett. 120, 200502 (2018) 著者はアルファベット順

TM, Hardness of classically sampling one clean qubit model with constant toral variation distance error, Phys. Rev. A 96, 040302(R) (2017)

TM, Takeuchi, and Nishimura, Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy, Quantum 2, 106 (2018)

TM and Tamaki, Fine-grained quantum computational supremacy, Quant. Inf. Comput. 19, 1089 (2019)

TM and Tamaki, Additive-error fine-grained quantum supremacy, Quantum 4, 329 (2020)

 

2.量子暗号プロトコルの研究

量子に関連する暗号の研究は量子暗号と呼ばれます。量子暗号の研究は主に3つにわけることができます。

(1)量子鍵配送(QKD):量子状態を送ることにより秘密鍵を共有する量子暗号プロトコル

(2)量子暗号プロトコル:様々な暗号的タスクを量子を使って実現する方法の研究。((1)のQKDは(2)の特殊な場合ですので(2)に含まれますが、歴史のあるテーマであり実用化もかなり進んでいるので、独立に扱う場合が多いです。)

(3)耐量子暗号:古典の暗号の量子的攻撃に対する安全性を調べる研究。量子計算機でも解けなさそうな問題をベースにして暗号プロトコルを作ったり、その安全性を調べたり、量子的な安全性証明(例えば量子的重ね合わせでオラクルにクエリーする場合の安全性等)を研究したりします。

私は(2)の量子暗号プロトコル、特にブラインド量子計算、量子計算の検証、量子ゼロ知識証明等について研究を行ってきました。ブラインド量子計算というのはほぼ古典の計算能力しかない利用者が、遠隔にある量子サーバー上で、自分のプライバシー情報(計算の入力、プログラム、出力)を秘密にしたまま量子計算を行う、というものです。詳しくは昔の解説MBQC本の6章、QC本の7章、以下の論文を参照してください。

TM and Fujii, Blind topological measurement-based quantum computation, Nature Communications 3, 1036 (2012)

TM and Fujii, Blind quantum computation protocol in which Alice only makes measurements, Phys. Rev. A 87, 050301(R) (2013)

TM, Continuous-variable blind quantum computation, Phys. Rev. Lett. 109, 230502 (2012)

TM and Fujii, Secure entanglement distillation for double-server blind quantum computation, Phys. Rev. Lett. 111, 020502 (2013)

量子計算の検証というのは、ほぼ古典の能力しかない検証者が量子サーバーが正しい量子計算を行ったかどうかをチェックするというものです。量子計算機は古典計算機で効率的にシミレートできないから有用なわけですが、それがあだとなってしまい、量子計算機が正しく動いているのかを古典計算機ではシミレートしてチェックすることができない、という皮肉なジレンマに陥ってしまうため、量子計算の検証というのは非常に非自明な問題です。スタビライザーテストに基づく量子計算の検証プロトコルや、局所ハミルトニアンに基づくプロトコル(ポストフォックプロトコル)を提案しました。詳しくは昔の解説MBQC本の6章、QC本の7章、以下の論文を参照してください。

TM, Honesty test, Nature Physics 9, 693 (2013) (Review article)

Hayashi and TM, Verifiable measurement-only blind quantum computing with stabilizer testing, Phys. Rev. Lett. 115, 220502 (2015)

TM, Nagaj, Schuch, Quantum proofs can be verified using only single qubit measurements, Phys. Rev. A 93, 022326 (2016)

Fitzsimons, Hadjusek, and TM, Posthoc verification of quantum computation, Phys. Rev. Lett. 120, 040501 (2018)

Takeuchi and TM, Verification of many-qubit states, Phys. Rev. X 8, 021060 (2018)

TM, Takeuchi, and Hayashi, Verified measurement-based quantum computing with hypergraph states, Phys. Rev. A 96, 062321 (2017)

量子ゼロ知識やQuantum randomized encodingも研究しています。

TM and Yamakawa, Classically verifiable (dual-mode) NIZK for QMA with preprocessing, arXiv:2102.09149

TM, Quantum randomized encoding, verification of quantum computing, no-cloning, and blind quantum computing, arXiv:2011.03141

計算量的仮定に基づく量子暗号プロトコル(Mahadevとか)も非常に興味があり研究しています。

 

3.量子計算量理論

量子計算量理論一般、特にCounting complexityと量子計算の関係についても研究していきました。GapP関数と量子計算、AWPPpostBQPMBQC本の7.2.1節、QC本の9章)

TM and Nishimura, Quantum interpretations of AWPP and APP, Quantum Information and Computation 16, pp.0498-0514 (2016)

TM, Nishimura, and Le Gall, Modified group non-membership is in AWPP, Quantum Information and Computation 17, 0242 (2017)

量子対話型証明系も研究してきました。(MBQC本の7.2.2節、QC本の8章)

TM, Hayashi, Nishimura, and Fujii, Quantum Merlin-Arthur with Clifford Arthur, Quantum Information and Computation 15, pp1420-1430 (2015)

TM and Nishimura, Merlinization of complexity classes above BQP, Quantum Information and Computation 17, pp 0959-0972 (2017)

TM, Quantum Arthur-Merlin with single-qubit measurements, Phys. Rev. A 93, 062333 (2016)

 

----------------------------------------------------------------------------

Publication list

----------------------------------------------------------------------------

Press

----------------------------------------------------------------------------

Book

(1) 「観測に基づく量子計算」 小柴健史、藤井啓祐、森前智行、コロナ社 (略称MBQC本)

  日本物理学会誌の書評

(2) 量子計算理論」 森前智行、森北出版 (略称QC本) 

  27回大川出版賞受賞!

  日本物理学会誌の書評

----------------------------------------------------------------------------

一般向けの解説

「量子計算と物理」京都大学市民講座2019年

「量子コンピューターの限界を追求する」京大先生シアター

「量子計算で出来ること・出来ないこと」 日本物理学会誌2019年2月号 話題

「セキュアな量子計算の基盤技術」 JST ACT-I 2018年成果発表会の動画

「研究への情熱」JST広報動画2017

「測定型量子計算の物性、暗号への応用」 パリティ 20161月号

T. Morimae, Quantum computation: Honesty test, Nature Physics 9, 693 (2013) (News and Views Article)

「弱い量子コンピューターはどのくらい強いのか?−量子スプレマシー研究の最前線」 academist Journal 研究コラム 201710

----------------------------------------------------------------------------

雑文

小学生でも分かる量子計算

「量子スピードアップ」にはエンタングルメントもマクロ量子コヒーレンスも必要ない

量子スプレマシーとは何か

量子計算のポストホック検証

量子コンピューターの重要なキーワード

量子コンピューターは組み合わせ最適化を苦手とする

なぜ90量子ビットなのか 〜30年の基礎研究から量子スプレマシーへ〜

なぜ量子計算はNPが苦手なのか〜多項式法〜

小学生でもわかる量子計算の分類

量子コンピューター検定

量子計算の指数時間古典シミレーション

古典通信による量子インターネット

Interactive proof of quantumness: 暗号を使った対話型量子性証明

Google論文について

ジョンマルチネスはどうしたらリークを未然に防げたのか

量子コンピューターを使って新元号を知らずに済ます方法

----------------------------------------------------------------------------

Slides

AQIS2018 (2018/9)

大阪市立大コロキウム (2018/9)

東北大セミナー (2018/10)

Tokyo Crypto Day (2019/3)

QIT40@九州大学(2019/5/21)

QIST2019@京都大学(2019/6/18)

京都大学市民講座 物理と宇宙(2019/10/20)

Recent progress in theoretical physics based on quantum information theory (2021/3/2)

第16回京都大学附置研究所・センターシンポジウム(2021/3/6

IEICE総合大会 量子計算と暗号の進展(2021/3/9