Tomoyuki Morimae
森前智行
京都大学基礎物理学研究所 量子情報グループ 准教授
Yukawa
Institute for Theoretical Physics, Quantum Information Group, Associate
Professor
Email address: first.family (at) yukawa.kyoto-u.ac.
私の研究室を志望する学生の方は
京都大学大学院理学研究科 物理学・宇宙物理学専攻 物理学第一分野
に応募してください。研究室や研究内容について興味のある方は、ローレンツ祭などの機会を利用して見学に来てください。
研究場所は京都大学基礎物理学研究所になります。
----------------------------------------------------------------------------
研究テーマ
私の専門は量子情報理論です。量子情報というと広い意味では量子と情報に関する研究全てを含みますが、狭い意味では量子を情報処理に応用することによりこれまでにない高性能な情報処理技術を実現する研究を指します。私はその狭い意味での量子情報の分野で、特に量子計算と量子暗号の理論的研究を行ってきています。
（１）量子計算理論
量子計算の研究は大きく分けて量子アルゴリズムの研究と量子計算量理論の研究に分けることができます。私自身は量子アルゴリズムはあまり詳しくありませんが、研究室では学生が研究を行っています。詳しくはこちらをご覧ください。
量子計算量理論についてはいろいろ研究を行ってきました。特に、量子スプレマシー理論、counting complexityと量子計算量理論、量子対話型証明などです。
1．量子優位性（量子スプレマシー）の理論的証明
量子計算が古典計算より速いというのは、計算量理論の「標準的」な意味ではBQP≠BPPを意味しますが、実はこれはまだ証明されていません。（もしこれが証明できてしまうとP≠PSPACEという古典計算量理論における大未解決問題を証明したことになるので、そう簡単には証明できないだろうと考えられています。）そうはいうものの、皆量子計算は古典計算より速いだろうと信じているわけですが、その証拠として以下の３つのタイプの結果がこれまでに得られてきています。
（１）素因数分解等のように、古典のベストのアルゴリズムより速い量子アルゴリズムが見つかっている。
（２）検索問題等のように、「サブルーチン」を呼ぶ回数が量子のほうが古典より少なくて済むという結果が知られている。（query complexityのことをいっています。）
（３）多項式階層の無限性といったような古典の計算量理論において信じられている仮定のもとでは、サンプリング問題は量子計算のほうが古典計算よりも高速に解けることが示されている。
私はこの（３）について研究をしてきました。きれいに初期化された量子ビットが一つしか使えないような「弱い」量子計算モデルであっても（多項式階層が崩壊しない限り）古典計算機では多項式時間でシミュレートできないことを示したり、古典のfine-grained complexity theoryにおける仮定に基づいて、古典のある指数時間であっても量子計算がシミュレートできないことなどを示してきました。詳しくは昔の解説、拙著「観測に基づく量子計算」の7.3節、拙著「量子計算理論」の10章、量子計算で出来ること・出来ないこと」 日本物理学会誌２０１９年２月号 話題、また以下の論文等を参照してください。
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．Counting 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)
（２）量子暗号理論
私は量子暗号理論の研究も行ってきています。量子暗号は広い意味では量子と暗号に関する研究を全て指しますが、主に以下の３つにわけることができます。
（１）量子鍵配送（QKD）：量子状態を送ることにより秘密鍵を共有する量子暗号プロトコル
（２）量子暗号プロトコル：様々な暗号的タスクを量子を使って実現する方法の研究。（（１）のQKDは（２）の特殊な場合ですので（２）に含まれますが、歴史のあるテーマであり実用化もかなり進んでおり、独立した研究コミュニティで研究が行われているように見えるので区別しました。実際、うちの研究室ではQKDの研究は今のところ行っていません。）
（３）耐量子暗号：古典の暗号の量子的攻撃に対する安全性を調べる研究。量子計算機でも解けなさそうな問題をベースにして暗号プリミティブを作ったり、その量子的な安全性証明（例えば量子的重ね合わせでオラクルにクエリーする場合の安全性等）を研究したりします。
私は（２）の量子暗号プロトコル、特にブラインド量子計算、量子計算の検証、量子ゼロ知識証明等について研究を行ってきました。
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 deletionやcertified 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の世界ではすべての耐量子暗号は存在しないわけですが（NP⊆BQPなので）、そのような状況でも量子コミットメントや量子署名は可能であることを示しています。特に、BQP=QMAの世界では耐量子一方向性関数も存在しないわけですので、量子コミットメントや量子署名は古典と違い一方向性関数無しでも存在することを示しています。
Morimae and Yamakawa,
Quantum commitments and signatures without one-way functions, arXiv:2112.06369
----------------------------------------------------------------------------
----------------------------------------------------------------------------
----------------------------------------------------------------------------
Book
(1) 「観測に基づく量子計算」 小柴健史、藤井啓祐、森前智行、コロナ社 （略称MBQC本）
(2) 「量子計算理論」 森前智行、森北出版 （略称QC本）
----------------------------------------------------------------------------
一般向けの解説
第16回京都大学附置研究所・センター シンポジウム「量子計算と量子暗号」
「量子計算量理論と量子アルゴリズム」 森前智行 早川龍 電子情報通信学会誌
2021年11月号
「量子計算で出来ること・出来ないこと」 日本物理学会誌２０１９年２月号 話題
「セキュアな量子計算の基盤技術」 JST ACT-I 2018年成果発表会の動画
「測定型量子計算の物性、暗号への応用」 パリティ 2016年1月号
T. Morimae, Quantum computation: Honesty test, Nature Physics 9, 693 (2013) (News and Views Article)
「弱い量子コンピューターはどのくらい強いのか？−量子スプレマシー研究の最前線」 academist Journal 研究コラム 2017年10月
----------------------------------------------------------------------------
雑文
「量子スピードアップ」にはエンタングルメントもマクロ量子コヒーレンスも必要ない
なぜ９０量子ビットなのか 〜３０年の基礎研究から量子スプレマシーへ〜
Interactive proof of quantumness: 暗号を使った対話型量子性証明
----------------------------------------------------------------------------
Slides
AQIS2018 (2018/9)
大阪市立大コロキウム (2018/9)
東北大セミナー (2018/10)
Recent progress in theoretical physics based on quantum information theory (2021/3/2)
第１６回京都大学附置研究所・センターシンポジウム（2021/3/6）
IEICE総合大会 量子計算と暗号の進展（2021/3/9）
---------------------------------------------------------------
大学院講義
２０２１年度前期月曜２限（１０：３０〜１２：００）
スケジュール
１回目：Clifford、Gottesman-Knill、Magic
参考文献：
Nielsen-Chuangの教科書（英語！）
森前、量子計算理論、森北出版
２回目：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
３回目: 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)
４回目: 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
５回目：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
６回目：量子計算の検証、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
７回目：QMAM、Deutchのアルゴリズム、Fourier hierarchy、多項式法
Marriott-Watrous, https://arxiv.org/pdf/cs/0506068.pdf
http://tomoyukimorimae.web.fc2.com/query_complexity_j.pdf
８回目：量子スプレマシー（multiplicative-error
sampling）、postBQP、NQP
森前、量子計算理論（森北出版）、１０章
９回目：量子スプレマシー(additive-error
sampling)、Fine-grained量子スプレマシー
森前、量子計算理論（森北出版）、１０章
Morimae and Tamaki, Quantum 4,
329 (2020); arXiv:1912.06336
Morimae and Tamaki, Quant. Inf.
Comput. 19, 1089 (2019); arXiv:1901.01637
１０回目：LWE、Noisy trapdoor claw-free function、Proof of quantumness、Remote state preparation、QFactory、量子マネー、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
１１回目：Simpler proof of quantumness、Yamakawa-Zhandry、quantum tokenized MAC、One-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
１２回目：Quantum garbled circuits
https://arxiv.org/pdf/2006.01085.pdf
https://arxiv.org/pdf/2011.11212.pdf
１３回目：Quantum two-party
computation
https://arxiv.org/abs/2011.11212
----------------------------------------------------------------------------