Tomoyuki Morimae 森前智行

 

京都大学基礎物理学研究所 量子情報グループ 准教授

Yukawa Institute for Theoretical Physics, Quantum Information Group, Associate Professor

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

 

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

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

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

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

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

 

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

研究テーマ

私の専門は量子情報理論です。量子情報というと広い意味では量子と情報に関する研究全てを含みますが、狭い意味では量子を情報処理に応用することによりこれまでにない高性能な情報処理技術を実現する研究を指します。私はその狭い意味での量子情報の分野で、特に量子計算と量子暗号の理論的研究を行ってきています。

 

(1)量子計算理論

量子計算の研究は大きく分けて量子アルゴリズムの研究と量子計算量理論の研究に分けることができます。私自身は量子アルゴリズムはあまり詳しくありませんが、研究室では学生が研究を行っています。詳しくはこちらをご覧ください。

量子計算量理論についてはいろいろ研究を行ってきました。特に、量子スプレマシー理論、counting complexityと量子計算量理論、量子対話型証明などです。

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

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

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

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

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

私はこの(3)について研究をしてきました。きれいに初期化された量子ビットが一つしか使えないような「弱い」量子計算モデルであっても(多項式階層が崩壊しない限り)古典計算機では多項式時間でシミュレートできないことを示したり、古典のfine-grained complexity theoryにおける仮定に基づいて、古典のある指数時間であっても量子計算がシミュレートできないことなどを示してきました。詳しくは昔の解説、拙著「観測に基づく量子計算」の7.3節、拙著「量子計算理論」の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)

2Counting complexityと量子計算量理論

GapP関数と量子計算、AWPPと量子計算、postBQPなどについても研究してきました。詳しくは拙著「観測に基づく量子計算」の7.2.1節、拙著「量子計算理論」の9章を参照してください。また以下の論文も参照してください。

TM and Nishimura, Quantum interpretations of AWPP and APP, Quant. Inf. Comput. 16, pp.0498-0514 (2016)

TM, Nishimura, and Le Gall, Modified group non-membership is in AWPP, Quant. Inf. Comput. 17, 0242 (2017)

3.量子対話型証明

詳しくは拙著「観測に基づく量子計算」の7.2.2節、拙著「量子計算理論」の8章、また以下の論文を参照してください。

TM, Hayashi, Nishimura, and Fujii, Quantum Merlin-Arthur with Clifford Arthur, Quant. Inf. Comput. 15, pp1420-1430 (2015)

TM and Nishimura, Merlinization of complexity classes above BQP, Quant. Inf. Comput. 17, pp 0959-0972 (2017)

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

 

(2)量子暗号理論

私は量子暗号理論の研究も行ってきています。量子暗号は広い意味では量子と暗号に関する研究を全て指しますが、主に以下の3つにわけることができます。

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

(2)量子暗号プロトコル:様々な暗号的タスクを量子を使って実現する方法の研究。((1)のQKDは(2)の特殊な場合ですので(2)に含まれますが、歴史のあるテーマであり実用化もかなり進んでおり、独立した研究コミュニティで研究が行われているように見えるので区別しました。実際、うちの研究室ではQKDの研究は今のところ行っていません。)

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

私は(2)の量子暗号プロトコル、特にブラインド量子計算、量子計算の検証、量子ゼロ知識証明等について研究を行ってきました。

1. ブラインド量子計算

ブラインド量子計算というのはほぼ古典の計算能力しかない利用者が、遠隔にある量子サーバー上で、自分のプライバシー情報(計算の入力、プログラム、出力)を秘密にしたまま量子計算を行う、というものです。詳しくは昔の解説、拙著「観測に基づく量子計算」の6章、拙著「量子計算理論」の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)

2. 量子計算の検証

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

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)

3. 他の量子暗号プロトコル

量子ゼロ知識やQuantum randomized encodingも研究しています。QMAに対する古典検証者のNIZKを作ったり、古典Quantum randomized encodingの不可能性をNo-cloningから証明したりしました。

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, Quant. Inf. Comput. 21, 1111-1134 (2021)

4. 計算量的量子暗号プロトコル

量子を使っていろいろな暗号プロトコルを作る場合、量子の性質のみを使って情報理論的安全なものを作る場合と、計算量的仮定も組み合わせてさらにいろいろな機能を持ったものを作る場合があります。比較的、量子暗号プロトコルの分野ではこれまでは前者の研究が多かったように見えますが、Mahadevのブレークスルー等により、計算量的仮定も積極的に使う量子暗号プロトコルの構築が近年盛んに研究されてきています。私はこれまで学生とNTTの暗号理論の方と共同で古典通信に基づくcertified deletioncertified everlasting zero-knowledgeを構成しました。詳細は以下の論文を参照してください。

 

Hiroka, Morimae, Nishimaki, and Yamakawa, Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication, Asiacrypt2021 (QIP2022, Qcrypt 2021)

 

Hiroka, Morimae, Nishimaki, and Yamakawa, Certified Everlasting Zero-Knowledge Proof for QMA, arXiv:2109.14163

5. 量子暗号の基礎理論

古典の世界では、コミットメントや署名など多くの暗号プリミティブは一方向性関数から構成できることが知られています。私はNTTの暗号理論の方と共同で、量子の世界(つまり量子計算ができ、量子状態を送ることができるような世界)においては、コミットメントも署名もpseudorandom statesというものから構成できることを示しました。Pseudorandom statesというのは、直観的にいうと、効率的に生成できるが、Haarランダムな状態と計算量的に区別できないような状態であり、BQP=QMAになったとしても存在するだろうという証拠が得られています。BQP=QMAの世界ではすべての耐量子暗号は存在しないわけですが(NPBQPなので)、そのような状況でも量子コミットメントや量子署名は可能であることを示しています。特に、BQP=QMAの世界では耐量子一方向性関数も存在しないわけですので、量子コミットメントや量子署名は古典と違い一方向性関数無しでも存在することを示しています。

Morimae and Yamakawa, Quantum commitments and signatures without one-way functions, arXiv:2112.06369

 

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

Publication list

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

Press

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

Book

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

  日本物理学会誌の書評

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

  27回大川出版賞受賞!

  日本物理学会誌の書評

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

一般向けの解説

16回京都大学附置研究所・センター シンポジウム「量子計算と量子暗号」

 「量子計算量理論と量子アルゴリズム」 森前智行 早川龍 電子情報通信学会誌 2021年11月号

「量子計算」 数理科学2021年8月号

「量子計算と物理」京都大学市民講座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

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

大学院講義

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

 

スケジュール

 

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 quantumnessRemote state preparationQFactory、量子マネー、Certified deletion

Proof of quantumness, https://arxiv.org/pdf/1804.00640.pdf

Qfactory, https://arxiv.org/pdf/1904.06303.pdf

Adaptive attack on Wiesner’s Q money, https://arxiv.org/pdf/1404.1507.pdf

OT with quantum channel, https://arxiv.org/pdf/2011.13486.pdf

Verification with random BB84 states, https://arxiv.org/pdf/2102.09149.pdf

Certified deletion, https://arxiv.org/pdf/1910.03551.pdf

 

 

11回目:Simpler proof of quantumnessYamakawa-Zhandryquantum tokenized MACOne-shot signature

https://arxiv.org/pdf/2005.04826.pdf

https://eprint.iacr.org/2020/1270.pdf

https://arxiv.org/abs/1609.09047

https://arxiv.org/abs/2105.05016

https://eprint.iacr.org/2020/107.pdf

 

 

12回目:Quantum garbled circuits

https://arxiv.org/pdf/2006.01085.pdf

https://arxiv.org/pdf/2011.11212.pdf

 

 

13回目:Quantum two-party computation

https://arxiv.org/abs/2011.11212

 

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