Adiabatic Quantum Computing Conference 2016 (AQC2016)

量子アニーリングの国際会議"Adiabatic Quantum Computing Conference 2016 (AQC2016)" [link] は、2016年6月27日から6月30日にかけてGoogle Los Angelesにて開催されました。 毎年開催され、今年5回目となる当国際会議は、これまでは行われなかったパラレルセッションが一部で行われるなど、これまで以上の盛り上がりを見せていました。 次回は来年、日本で開催される運びです。

1日目から3日目は招待講演、口頭講演、ポスター講演からなる通常の国際会議が開催され、 4日目は片道2時間程度かけてバスで移動し、Google Santa BarbaraにあるQuantum hardware labの見学会が行われました。

このサイトではAQC2016にて得た情報をまとめました。 本サイトは網羅的な情報を尽くすというよりは、私自身の興味に基づき作成しています。 そのため詳細は講演者らの論文及び、公開される予定の動画を参考にしていただけますよう、よろしくお願いいたします。 Programはこちら を参照してください。

以下では特に印象に残った講演について述べます。

Opening remarksとして、量子アニーリングの重要なトピックスや考え方について、6点に渡って紹介。

  1. Vasil Denchev (Google) の「1億倍速い計算」の論文[1]の簡単な紹介。
  2. Helmut Katzgraber (Texas A&M) のReplica Overlap distribution, P(q) から問題の困難性の話[2]。
  3. Quantum Parallel Tempering Algorithmの紹介。温度方向だけでなく量子項方向にも交換法を実行。
  4. Helmut Katzgraber (Texas A&M) のPopulation Annealing (PA) と量子アニーリングとの比較の話[3]。
  5. Asynchronous Server Architecture として、様々な階層のマシンの連携の話。
  6. たった数%の計算効率改善としても、大きなインパクトがある市場はあり、それは重要であるということ。

補足
「1億倍速い計算」とは、ある組合せ最適化問題をSimulated Annealing, 量子モンテカルロ法を使った場合の量子アニーリング、そしてD-Waveを使った量子アニーリングについて ある精度を得るために必要な計算時間を見積もり、Simulated Annealingに比べD-Waveを使った量子アニーリングが1億倍速いことを示唆する結果のことを示す。 1000量子ビットで表現できる問題サイズについて取り扱っているが、あらゆるタイプの組合せ最適化問題に対して1億倍高速であるというわけではないことに注意。 またQuantum Parallel Tempering Algorithmについては、我々も2009年に温度と量子項の同時制御を提案[4]し、その後いくつかの場合についてその方法を適用している[5,6]。

参考文献
[1] Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven, "What is the Computational Value of Finite Range Tunneling?", arXiv:1512.02206. [link]
[2] Helmut G. Katzgraber, Firas Hamze, Zheng Zhu, Andrew J. Ochoa, and H. Munoz-Bauza, "Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly", Physical Review X 5, 031026 (2015). [link]
[3] Wenlong Wang, Jonathan Machta, and Helmut G. Katzgraber, "Population annealing: Theory and application in spin glasses", Physical Review E 92, 063307 (2015). [link]
[4] Kenichi Kurihara, Shu Tanaka, and Seiji Miyashita, "Quantum Annealing for Clustering", Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009). [link]
[5] Issei Sato, Kenichi Kurihara, Shu Tanaka, Hiroshi Nakagawa, and Seiji Miyashita, "Quantum Annealing for Variational Bayes Inference", Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009). [link]
[6] Issei Sato, Shu Tanaka, Kenichi Kurihara, Seiji Miyashita, and Hiroshi Nakagawa, "Quantum annealing for Dirichlet process mixture models with applications to network clustering", Neurocomputing 121, 523 (2013). [link]

2015年12月にarXivにアップロードされていた「1億倍速い計算」の論文[1]の第一著者による講演。 理想的な孤立系では十分ゆっくり(最小エネルギーギャップの逆2乗程度で)量子アニーリングを行えば確実に基底状態が得られる、いわゆる断熱定理の話から。 その後、実際のデバイスでは有限温度下にあるため、熱励起が存在すること。高く狭い障壁の場合には量子アニーリングがSimulated Annealingよりも良いことを紹介。 D-Waveのような実機があるのだから、まずはそれを使ってみれば、というスタンス。 ただし、相互作用値、磁場値の精度の制限、1152量子ビット搭載のD-Wave 2Xで実際に動作する量子ビットは1097量子ビットであることなど、実機の現在の状況についてもコメント。

有限温度下にあることから、熱の及ぼす効果について説明。 Weak-strong cluster pairと呼ばれる、強磁性的相互作用で繋いだ2つのクラスタにそれぞれ逆方向の磁場を印加したモデル[2]について導入。 量子揺らぎである横磁場が強い場合には局所解=最小解であるが、横磁場が弱くなると準安定状態と安定状態に分かれるモデルである。

上記Weak-Strong cluster pairをネットワーク上につなげた問題[3]についても説明。 さらに、量子アニーリングにおける量子トンネル現象を理解するための量子モンテカルロ法による最近の研究[4]についても紹介がなされた。 この研究[4]では量子モンテカルロ法による虚時間方向の境界条件を周期境界条件から自由境界条件にすることにより、 量子アニーリングにおいてエネルギーギャップに対するトンネル確率のスケーリング則が変わることを指摘している。

参考文献
[1] Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven, "What is the Computational Value of Finite Range Tunneling?", arXiv:1512.02206. [link]
[2] Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani, Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, Mohammad H. Amin, Anatoly Yu Smirnov, Masoud Mohseni, and Hartmut Neven, "Computational multiqubit tunnelling in programmable quantum annealers", Nature Communications 7, 10327 (2016). [link] [3] Salvatore Mandrà, Zheng Zhu, Wenlong Wang, Alejandro Perdomo-Ortiz, and Helmut G. Katzgraber, "Strengths and Weaknesses of Weak-Strong Cluster Problems: A Detailed Overview of State-of-the-art Classical Heuristics vs Quantum Approaches", arXiv:1604.01746. [link]
[4] Sergei V. Isakov, Guglielmo Mazzola, Vadim N. Smelyanskiy, Zhang Jiang, Sergio Boixo, Hartmut Neven, and Matthias Troyer, "Understanding Quantum Tunneling through Quantum Monte Carlo Simulations", arXiv:1510.08057 [link]

量子アニーリングにおける量子トンネリング現象を解析的議論を用いて検討するという話。 対象とする古典ハミルトニアンが全(縦)磁化の関数で表現できる場合について検討。量子項についても、全横磁化で書ける形で導入し、これをWKB近似で解析。 量子ビットのノイズについて幾つか論文を紹介していた[1,2,3,4,5,6]。 さらにDephasingやインコヒーレントトンネル現象について紹介したのち、平均場モデルを用いた開放系量子アニーリングの解析を行った最新の研究を紹介[7]。 この研究では、指数関数的に縮退が増加する古典模型に対する量子アニーリングの解析に相当。

補足
基底状態に縮退がある場合の熱アニーリングと量子アニーリングの差異については松田らによる研究が過去にある[8]。 またフラストレーションが引き起こす巨視的縮退に着目した安定状態到達遅延効果については我々も過去に研究を行った[9,10]。

参考文献
[1] M. H. S. Amin and Dmitri V. Averin, "Macroscopic Resonant Tunneling in the Presence of Low Frequency Noise", Physical Review Letters 100, 197001 (2008). [link]
[2] Vadim N. Smelyanskiy, Davide Venturelli, Alejandro Perdomo-Ortiz, Sergey Knysh, and Mark I. Dykman, "Quantum annealing via environment-mediated quantum diffusion", arXiv:1511.02581 [link]
[3] Jonas Bylander, Simon Gustavsson, Fei Yan, Fumiki Yoshihara, Khalil Harrabi, George Fitch, David G. Cory, Yasunobu Nakamura, Jaw-Shen Tsai, and William D. Oliver, "Noise spectroscopy through dynamical decoupling with a superconducting flux qubit", Nature Physics 7 565 (2011). [link]
[4] E. Paladino, Y. M. Galperin, G. Falci, and B. L. Altshuler, "1/f noise: Implications for solid-state quantum information", Review of Modern Physics 86, 361 (2014). [link]
[5] T. Lanting, M. H. Amin, A. J. Berkley, C. Rich, S.-F. Chen, S. LaForest, and Rogério de Sousa, "Evidence for temperature-dependent spin diffusion as a mechanism of intrinsic flux noise in SQUIDs", Physical Review B 89, 014503 (2014). [link]
[6] Daniel Sank, R. Barends, Radoslaw C. Bialczak, Yu Chen, J. Kelly, M. Lenander, E. Lucero, Matteo Mariantoni, A. Megrant, M. Neeley, P. J. J. O’Malley, A. Vainsencher, H. Wang, J. Wenner, T. C. White, T. Yamamoto, Yi Yin, A. N. Cleland, and John M. Martinis, "Flux Noise Probed with Real Time Qubit Tomography in a Josephson Phase Qubit", Physical Review Letters 109, 067001 (2012). [link]
[7] Kostyantyn Kechedzhi and Vadim N. Smelyanskiy, "Open-System Quantum Annealing in Mean-Field Models with Exponential Degeneracy", Physical Review X 6, 021028 (2016). [link]
[8] Yoshiki Matsuda, Hidetoshi Nishimori, and Helmut G Katzgraber, "Ground-state statistics from annealing algorithms: quantum versus classical approaches", New Journal of Physics 11, 073021 (2009). [link]
[9] Shu Tanaka and Seiji Miyashita, "Mechanism of Slow Relaxation due to Screening Effect in a Frustrated System", Journal of the Physical Society of Japan 78, 084002 (2009). [link]
[10] Shu Tanaka and Seiji Miyashita, "Non-monotonic Dynamics in Frustrated Ising Model with Time-Dependent Transverse Field", Physical Review E 81, 051138 (2010). [link]

動機として

  1. 量子アニーリングは高速か?
  2. 量子アニーリングの応用は?
  3. 横磁場を用いた量子アニーリングの限界は?
の3つを掲げ、講演が始まった。

Mooreの法則のよくある話[1]から始まり、Troels F. Rønnowらによる量子による加速の論文[2]の紹介。再びVasil Denchevの講演でも紹介がされていた論文[3,4]の紹介。 量子アニーリングの比較として熱アニーリング(Simulated annealing)ではなくPopulation annealingを用いて評価をしたという論文[5]の紹介。 「1億倍高速」の論文[3]の上に重ね書きされた膨大なアルゴリズムリスト(論文[4]に掲載されている):

  • Hamze-de Freitas-Selby algorithm[6]
  • Super-spin approximation[4]
  • Hybrid Cluster methods[7]
  • Population annealing[5]
  • Parallel tempering and isoenergetic cluster optimizer[8]
  • Replica Monte Carlo and isoenergetic cluster optimizer[4]
  • Simulated annealing[9]
  • Quantum Monte Carlo[3]

続いてReplica Overlap Distribution(ROD), P(q)を用いて解析した論文[10,11]についての紹介。

さらに横磁場による量子アニーリングでは、基底状態に縮退がある場合に、得られやすい基底状態と得られにくい基底状態が存在するという彼らの過去の研究[12]を登場させ、 横方向相互作用の場合には偏りがなかったことを紹介。これに関係する最新の論文[13]を紹介。

参考文献
[1] M. Mitchell Waldrop, "The chips are down for Moore’s law", Nature 530, 144 (2016). [link]
[2] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer, "Defining and detecting quantum speedup", Science 345, 420 (2014). [link]
[3] Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven, "What is the Computational Value of Finite Range Tunneling?", arXiv:1512.02206. [link]
[4] Salvatore Mandrà, Zheng Zhu, Wenlong Wang, Alejandro Perdomo-Ortiz, and Helmut G. Katzgraber, "Strengths and Weaknesses of Weak-Strong Cluster Problems: A Detailed Overview of State-of-the-art Classical Heuristics vs Quantum Approaches", arXiv:1604.01746. [link]
[5] Wenlong Wang, Jonathan Machta, and Helmut G. Katzgraber, "Population annealing: Theory and application in spin glasses", Physical Review E 92, 063307 (2015). [link]
[6] Firas Hamze and Nando de Freitas, "Intracluster Moves for Constrained Discrete-Space MCMC", Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (UAI2010). [link]
[7] Davide Venturelli, Salvatore Mandrà, Sergey Knysh, Bryan O’Gorman, Rupak Biswas, and Vadim Smelyanskiy, "Quantum Optimization of Fully Connected Spin Glasses", Physical Review X 5, 031040 (2015). [link]
[8] Zheng Zhu, Andrew J. Ochoa, and Helmut G. Katzgraber, "Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension", Physical Review Letters, 115, 077201 (2015). [link]
[9] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, "Optimization by Simulated Annealing", Science 220, 671 (1983). [link]
[10] B. Yucesoy, Helmut G. Katzgraber, and J. Machta, "Evidence of Non-Mean-Field-Like Low-Temperature Behavior in the Edwards-Anderson Spin-Glass Model", Physical Review Letters 109, 177204 (2012). [11] Helmut G. Katzgraber, Firas Hamze, and Ruben S. Andrist, "Glassy Chimeras Could Be Blind to Quantum Speedup: Designing Better Benchmarks for Quantum Annealing Machines", Physical Review X , 021008 (2014). [link] [12] Yoshiki Matsuda, Hidetoshi Nishimori, and Helmut G Katzgraber, "Ground-state statistics from annealing algorithms: quantum versus classical approaches", New Journal of Physics 11, 073021 (2009). [link]
[13] Salvatore Mandrà, Zheng Zhu, and Helmut G. Katzgraber, "Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians", arXiv:1606.07146. [link]

こちらでは、1998年に量子アニーリングを提案した西森秀稔教授(東京工業大学)ご自身による量子アニーリングに関する概要や最新情報を読むことができます。
また、こちらから大関真之博士(京都大学)による、躍動感あふれるコラム「知的情報処理の最前線:Googleがやはり作っていた『量子コンピュータ』」が読めます。 このコラムでは当該国際会議の様子がレポートされています。

RCO Study Night 「D-Waveが切り開く、量子コンピュータを活用する未来」 [link]
早稲田大学高等研究所、株式会社リクルートコミュニケーションズ、D-Wave Systems社と共同で、2016年5月11日に開催しました。
株式会社リクルートコミュニケーションズによる開催報告(使用スライドへのリンクあり)はこちら

次世代量子情報技術 量子アニーリングが拓く新時代 情報処理と物理学のハーモニー
2016年1月18日公開

次世代情報処理技術「量子アニーリング」を用いたデータ駆動型社会イノベーション
2015年8月25日公開