Seminar 

セミナー

有限次元スピングラスの量子アニーリングにおける横磁場の量子1次相転移の回避の証明

山口瑞樹（東京大学総合文化研究科相関基礎科学系）

2023/10/17 15:30- 情報科学研究科教育研究棟206大講義室

量子アニーリング（QA）は、組合せ最適化問題を解くための手法の1つとして注目されている。QAは、ハミルトニアンをゆっくり動かしながら基底状態を持ち続けることで、自明な構造を持つ量子系から始め、最後に解きたい組合せ最適化問題の解を得る手法である。経験的にはいくつかの組合せ最適化問題で古典的な手法に比べて高速な計算ができる一方、計算量理論の考察から、QAは最も難しいクラスの最適化問題を効率的に解くことはできないことが知られている。量子計算の限界とその物理学的な原因の解明は重要な研究対象であるため、QAの失敗の原因は活発に研究されてきた。いくつかの先行研究[1]は、QAが失敗する多くの事例において、横磁場の量子1次相転移を伴うことを明らかにし、QAの失敗の起源はこの転移であると主張している。一方で、QAの失敗としてこの転移とは異なる要因を挙げる先行研究[2]もある。このように、QAが失敗する理由については、主に数値計算や近似的な解析計算に基づいた議論が交わされていたものの、決定的な答えは得られていなかった。
これに対し私の研究では、QAの一種[3]では、有限次元スピングラスの基底状態探索問題において、横磁場の量子1次相転移が起こらないことを厳密に証明した[4]ので、本発表ではその結果を紹介する。有限次元スピングラスの基底状態探索は難しい（NP困難な）問題であるため、QAを含むいかなる量子計算を用いても効率的に解くことはできないと広く信じられている。そのためこの研究結果は、横磁場の量子1次相転移は、難しい組合せ最適化問題におけるQAの失敗の主要因ではないということを強く示唆している。なおこの結果は、相互作用が短距離的で、結合定数が並進対称な分布から生成されるような、任意の有限次元スピングラス系に対して成り立つ、極めて一般性の高い結果である。

[1] T. Jörg, F. Krzakala, J. Kurchan, A. C. Maggs, and J. Pujos, EPL 89, 40004 (2009).
[2] S. Knysh, Nat Commun 7, 12370 (2016).
[3] Y. Seki and H. Nishimori, Phys. Rev. 85, 051112 (2012).
[4] M. Yamaguchi, N. Shiraishi, and K. Hukushima, arXiv:2307.00791

SDPアルゴリズムによるHeisenberg模型の基底状態近似とMaxCut問題

高橋惇 (Center for Quantum Information and Control, University of New Mexico)

2023/07/18 15:30-

MaxCut問題はNP困難であることが知られている最適化問題であり、物理的には反強磁性Ising模型に対応する。その性質の良さからMaxCut問題は量子アニーリングやQAOA等のベンチマークとしても頻繁に用いられるが、その背景には近似アルゴリズムによる整備された理解がある。具体的にはMaxCut問題はGoemans-WIlliamsonアルゴリズムというSDP(半正定値計画問題)緩和を用いた手法で87.8%という非自明な値の多項式時間近似率が保証される一方、87.8+ε%の近似率はNP困難であると計算論的に予想されている(Unique Games Conjecture)。これは単純に「基底状態を求めることはNP困難である」ということ以上に「基底状態に87.8+ε%“近い“状態を求めることもNP困難であるが、87.8%であればSDPで可能」という物理と計算の関係についてのより詳しい主張になっている。
本研究では、古典MaxCut問題のSDP緩和/近似に対応する概念を量子的な状況設定で探究した。反強磁性Heisenberg模型が “量子MaxCut問題” にあたること、そのための最も自然なSDPアルゴリズムの構成、古典の場合との対応関係などを示したのちに、Heisenberg相互作用で記述される種々の統計力学模型（Majumdar-Ghosh模型、Shastry-Sutherland模型、Heisenberg鎖など）の性質をよく近似することを数値的にみる。量子スピン系の文脈における “frustration-free模型” とSDPの関係性についても論じる。
JT, C. Rayudu, C. Zhou, R. King, K. Thompson, O. Parekh, arxiv:2307.XXXX (edited) 

最尤推定を誤り訂正したらベイズ推定になった話

一木輝久氏（福岡大学）

2023/05/16 10:00-

データの背景にある確率密度を推定する際に最もよく用いられるのは最尤法であろう．最尤推定の目的は真の確率密度に最も近い確率モデルを選択することにある．しかし真の確率密度は未知であるため、経験分布を手掛かりに確率モデルを選択することになる．このため最尤推定はデータに過剰にフィットしてしまうという問題点を持っている．よく考えてみるとこの状況は通信分野と似ていることに気がつく．すなわち、通信路のノイズのために劣化したメッセージから正しいメッセージを復元することと似ている．通信分野では正しいメッセージを復元するために誤り訂正の技術が用いられる．本講演では、最尤推定の問題点を誤り訂正の観点から再考察する．誤り訂正符号ではゲージ対称性が重要な役割を果たしていることが指摘されているが、最尤推定においてもKullback-Leiblerダイバージェンスのゲージ対称性に注目することにより、誤り訂正と同様の確率モデル選択ができることを示す．これにより得られる確率モデルは、従来の最尤法で得られる確率モデルよりも真の分布に近いことを示す．

History

過去のセミナー

2023/02/07 杉山友規（東京大学生産技術研究所）

熱力学と代数幾何学の構造、強化学習と最適制御との関連