| 講演抄録／キーワード |
| 講演名 |
2022-12-08 16:45
ガイド付きローカルハミルトニアン問題の計算複雑性の進展
○早川 龍（京大）・フランソワ ルガル（名大）・Sevag Gharibian（Paderborn University）・森前智行（京大） |
| 抄録 |
（和） |
ローカルハミルトニアンの基底状態のエネルギーを推定する問題は、量子化学において中心的な問題である。量子化学の問題を量子計算機を用いて解くことの有用性や計算複雑性について明らかにするために、Gharibian と Le Gall によって「ガイド付きローカルハミルトニアン問題」（GLH）が導入された(STOC 2022)。GLHとは、問題の入力として、ハミルトニアンの記述だけでなく、基底状態を近似することが保証された状態が「ガイド」として与えられるようなローカルハミルトニアン問題である。
本発表では、Gharibian と Le GallによるGLHの計算複雑性の結果を最適な形で改善した結果を示す。具体的には、量子化学における量子優位性（GLH問題のBQP完全性）が、２-localなハミルトニアンでも成り立ち、さらに、ガイドがほとんど正確に(1-1/polyの精度で)基底状態を近似するような場合でもBQP困難性がいえることを示す。更に、物理学で重要な模型として登場するような2-ローカルなハミルトニアン、例えばハイゼンベルク模型やXY模型、反強磁性的なハイゼンベルク模型やXY模型、についてのBQP困難性の結果を示す。これらの結果は、量子化学での実際的な状況における量子優位性を示すという目標に向けた進展であるといえる。 |
| （英） |
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has overlap (inverse-polynomially) close to $1/sqrt{2}$ with a ground state.
In this paper, we optimally improve both the locality and the overlap parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has overlap (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. This makes a further step towards establishing practical quantum advantage in quantum chemistry. |
| キーワード |
（和） |
量子計算 / 量子優位性 / ハミルトニアン計算複雑性 / 量子化学 / / / / |
| （英） |
Quantum Computing / Quantum advantage / Hamiltonian complexity / Quantum chemistry / / / / |
| 文献情報 |
信学技報 |
| 資料番号 |
|
| 発行日 |
|
| ISSN |
|
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
QIT |
| 開催期間 |
2022-12-08 - 2022-12-09 |
| 開催地（和） |
慶應義塾大学 |
| 開催地（英） |
Keio Univ. |
| テーマ（和） |
量子情報，一般 |
| テーマ（英） |
Quantum Information |
| 講演論文情報の詳細 |
| 申込み研究会 |
QIT |
| 会議コード |
2022-12-QIT |
| 本文の言語 |
日本語 |
| タイトル（和） |
ガイド付きローカルハミルトニアン問題の計算複雑性の進展 |
| サブタイトル（和） |
|
| タイトル（英） |
Improved Hardness Results for the Guided Local Hamiltonian Problem |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
量子計算 / Quantum Computing |
| キーワード(2)（和/英） |
量子優位性 / Quantum advantage |
| キーワード(3)（和/英） |
ハミルトニアン計算複雑性 / Hamiltonian complexity |
| キーワード(4)（和/英） |
量子化学 / Quantum chemistry |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
早川 龍 / Ryu Hayakawa / ハヤカワ リュウ |
| 第1著者 所属（和/英） |
京都大学 (略称： 京大)
Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
フランソワ ルガル / Francois Le Gall / フランソワ ルガル |
| 第2著者 所属（和/英） |
名古屋大学 (略称： 名大)
Nagoya University (略称： Nagoya Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
Sevag Gharibian / Sevag Gharibian / Sevag Gharibian |
| 第3著者 所属（和/英） |
Paderborn University (略称： Paderborn University)
Paderborn University (略称： Paderborn University) |
| 第4著者 氏名（和/英/ヨミ） |
森前 智行 / Tomoyuki Morimae / モリマエ トモユキ |
| 第4著者 所属（和/英） |
京都大学 (略称： 京大)
Kyoto University (略称： Kyoto Univ.) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 第21著者 氏名（和/英/ヨミ） |
/ / |
| 第21著者 所属（和/英） |
(略称： )
(略称： ) |
| 第22著者 氏名（和/英/ヨミ） |
/ / |
| 第22著者 所属（和/英） |
(略称： )
(略称： ) |
| 第23著者 氏名（和/英/ヨミ） |
/ / |
| 第23著者 所属（和/英） |
(略称： )
(略称： ) |
| 第24著者 氏名（和/英/ヨミ） |
/ / |
| 第24著者 所属（和/英） |
(略称： )
(略称： ) |
| 第25著者 氏名（和/英/ヨミ） |
/ / |
| 第25著者 所属（和/英） |
(略称： )
(略称： ) |
| 第26著者 氏名（和/英/ヨミ） |
/ / |
| 第26著者 所属（和/英） |
(略称： )
(略称： ) |
| 第27著者 氏名（和/英/ヨミ） |
/ / |
| 第27著者 所属（和/英） |
(略称： )
(略称： ) |
| 第28著者 氏名（和/英/ヨミ） |
/ / |
| 第28著者 所属（和/英） |
(略称： )
(略称： ) |
| 第29著者 氏名（和/英/ヨミ） |
/ / |
| 第29著者 所属（和/英） |
(略称： )
(略称： ) |
| 第30著者 氏名（和/英/ヨミ） |
/ / |
| 第30著者 所属（和/英） |
(略称： )
(略称： ) |
| 第31著者 氏名（和/英/ヨミ） |
/ / |
| 第31著者 所属（和/英） |
(略称： )
(略称： ) |
| 第32著者 氏名（和/英/ヨミ） |
/ / |
| 第32著者 所属（和/英） |
(略称： )
(略称： ) |
| 第33著者 氏名（和/英/ヨミ） |
/ / |
| 第33著者 所属（和/英） |
(略称： )
(略称： ) |
| 第34著者 氏名（和/英/ヨミ） |
/ / |
| 第34著者 所属（和/英） |
(略称： )
(略称： ) |
| 第35著者 氏名（和/英/ヨミ） |
/ / |
| 第35著者 所属（和/英） |
(略称： )
(略称： ) |
| 第36著者 氏名（和/英/ヨミ） |
/ / |
| 第36著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2022-12-08 16:45:00 |
| 発表時間 |
15分 |
| 申込先研究会 |
QIT |
| 資料番号 |
|
| 巻番号（vol） |
vol. |
| 号番号（no） |
|
| ページ範囲 |
|
| ページ数 |
|
| 発行日 |
|