近年量子情報科学ではBell不等式の研究が活発である.Bell不等式のうち関連する多面体のファセットに対応するもの(Bell不等式の研究ではタイトなものと呼ばれる)はそうでないもの(冗長なものと呼ばれる)より重要である.この論文ではまず2観測者2値測定に対するBell不等式と,多面体的組合せ論でカット多面体と呼ばれる高次元の凸多面体の関係を確立する.この関係を用いてBell不等式を調べることができるが,一つ問題がある.Bell不等式を調べるには,完全2部グラフとそのsuspension graphのカット多面体に関する知識が必要だが,完全グラフ以外のグラフのカット多面体に関してはほとんどわかっていないことである.この間を埋めるため,この論文では三角消去という手法を提案する.三角消去はカット多面体に対して成立する不等式に対する持ち上げ操作である.持ち上げ操作はある不等式がカット多面体のファセットであることを証明するための中心的な道具である.三角消去を使うと,完全グラフのカット多面体のファセット不等式を上で述べたグラフを含む様々なグラフのカット多面体のファセット不等式に変換することができ,その結果タイトなBell不等式を構成することができる.三角消去で構成される完全2部グラフやそのsuspensionのファセット不等式の対称性についても考察する.K9のカット多面体CUT□9のファセットの膨大なリストがChristofとReineltによって計算されており,これに三角消去を適用することで,対称性に関して等価でない2億以上のBell不等式を構成することができる.

　完全グラフのカット多面体に対して成り立つ不等式の族がいくつか知られている.これに三角消去を適用すると,無限個のBell不等式の族を表現する一般的な式を得ることができる.三角消去を導入する前は,そのようなBell不等式の族はCollinsとGisinによるI(mm22)Bell不等式しか知られていなかった.

　カット多面体との関係や三角消去を用いる手法は,2観測者の相関不等式にも適用することができる.本論文では,m=n=4の場合とmin{m,n}≦3の場合について,(m,n)個の2値観測量を用いる場合のタイトな相関不等式の完全なリストを提示し,新しい相関不等式の一般的な族を与える.

　次に,新たに見つかったBell不等式の一部が,Clauser-Horne-Shimony-Holt(CHSH)不等式と呼ばれる最も基本的なBell不等式に比べて「強い」ことを示す.すなわち,3準位量子系の等方的状態と呼ばれる対称性の高い状態の中に,CHSH不等式を破らないが当該Bell不等式を破るものが存在することを示す.これにより,CollinsとGisinによる未解決問題に部分的な解決を与える.一方,2準位系に対する同じ問題では,CHSH不等式より強いBell不等式は見つからなかった.これは,多準位系での非局所性の構造がqubit系より複雑であることを示唆している.証明の中で,Bell不等式間の包含関係という組合せ的な関係を利用する.この概念はCollinsとGisinが論じたCHSH不等式とI(3322)不等式の関係の議論を一般化したものである.

　完全グラフのカット多面体に対して成り立つ不等式の族のうちもっとも基本的なものは,CUT□3に対する三角不等式やCUT□5に対する五角形不等式を一般化したhypermetric不等式である.一方,Grishukhin不等式と呼ばれるカット多面体CUT□7のファセットに対しては,自然な一般化が知られていなかった.驚くべきことにI_(3322)$Bell不等式とI_(4422)Bell不等式はそれぞれ五角形不等式とGrishukhin不等式の三角消去であることがわかった.この観察に基づき,I(mm22)Bell不等式に対して三角消去を適用する前の形を求めることで,完全グラフのカット多面体に対して成り立つ不等式の列を構成することができる.この不等式の列を一般化することにより,完全グラフのカット多面体に対するI(G,H)不等式族とI'(G,H;C)不等式族を得て,標準的手法である持ち上げ操作を用いる方法により,これらの不等式族がファセットになるための十分条件を示した.この十分条件からI(mm22)Bell不等式がタイトであることが自然に証明でき,CollinsとGisinによって出された問題を解決した.

　さらに進んで,量子相関実験に関連する凸体と組合せ最適化で研究されている凸体の間の関係を調べる.Tsirelsonによって導入された隠れ決定性behavior,量子的behavior,no-signalling behaviorを表現する凸体と同等の凸体が,カット多面体に関連して知られている凸体の中に見付けられることを示す.これにより,これらの凸体の別の表現が得られ,no-signalling多面体の頂点に対する必要条件がわかるとともに,量子的behaviorの集合を含む凸体を考えることで,半定値計画によって効率良くBell不等式の量子破れの上界を求める方法が得られる.

　量子情報処理においては,量子状態を用いて情報を表現・操作・伝送することによって情報処理を実現する.ここで重要なことは,これまでの情報処理が古典力学系に依存して展開されていたのに対して,量子状態を用いた場合の情報処理ではどのような新しいことができるかを解明することである.本研究は,古典力学系の状態では表現できない量子的相関について解析を行うものである.すなわち,量子力学において真の量子性を示すBell不等式の理論を,現代の組合せ的凸多面体論の枠組みから見直すことにより,凸多面体論とBell不等式の両分野の架け橋となり,それぞれの分野に新たな知見をもたらすことに成功した.

　論文は8章より構成されている.まず1章で組み合わせ最適化における凸多面体論と量子情報処理におけるBell不等式論について概観し,2章ではそれぞれの分野における基礎的な知識を取りまとめた後,3章から7章までにおいて本論が展開される.

　3章では,Bell不等式論と凸多面体論とをつなぐ架け橋として基本的な役割を果たす道具である「三角消去」を提案している.離散最適化の分野においては完全グラフのカット多面体に対する不等式が詳しく研究されているのに対して,2観測者2値測定に対するBell不等式を調べるには3部グラフのカット多面体を考えなければならない.これに対し「三角消去」を用いると完全グラフのカット多面体に対する不等式を3部グラフのカット多面体に対する不等式に変換することができる.さらに不等式がファセットを生成するという性質も一定の条件下で保存することができる.

　4章では,提案した三角消去を用いることにより,凸多面体論の成果をBell不等式の分野に適用している.4章で述べられている結果は次の3点にまとめられる.

　(1)Bell不等式は,従来は限られた数しか知られていなかったが,凸多面体論における既知の不等式に三角消去を適用することにより,新たなBell不等式を得ることができるようになった.K7までのすべての不等式と,K8,K9の部分的な不等式の情報から,あわせて2億以上の等価でないBell不等式が得られた.得られたBell不等式の応用については6章でも一部論じられている.

　(2)I(mm22)というBell不等式族は,無限個のBell不等式を表す一般的な式として,従来知られていた唯一の例であった.これに対し本研究では,hypermetric不等式やpure clique-web不等式といった凸多面体論で知られていた不等式族から,無限個の不等式からなるBell不等式族を生成することができた.

　(3)Bell不等式よりも一般的な状況を示す相関不等式と呼ばれるものに対しても,三角消去を用いた凸多面体論との関連付けができることを示した.具体的には2観測者で(2,2),(3,n)および(4,4)個の2値観測量の場合のタイトな相関不等式の完全なリストを示すことに成功し,また不等式の族を得ることもできた.

　これら4章の成果は,離散最適化における凸多面体論における知見が,三角消去という道具により,Bell不等式・相関不等式の分野に貢献できることを具体的に示している.

　5章では三角消去の逆変換を用いることにより,Bell不等式における知見を凸多面体論に応用することができることを示している.具体的には前述のI(mm22)不等式から三角消去の逆変換をほどこすことにより,凸多面体論では「散発的」と考えられていたGrishukhinの不等式を含む不等式族が得られることを示した.さらにこれを発展させることにより凸多面体論では従来知られていなかった2種類の不等式族を得ることができた.また,これによりI(mm22)不等式がタイトであることを自然に証明することができた.

　6章では,4章で得られたBell不等式を用いて,Bell不等式間の関係についての研究が展開されている.得られたBell不等式のうち比較的観測数が少ない89個を対象として,まずBell不等式間の「包含」という関係について調査して結果を出した.さらに,3準位系ではCHSH不等式よりも「強い」不等式が存在することを数値計算により示した.しかし2準位系ではそのような不等式は発見されなかった.

　7章では,Bell不等式論と凸多面体論との相互関係について議論が展開されている.古典的なBell不等式に対応する凸体は完全2部グラフのsuspensionグラフのカット多面体と対応することが知られていた.これに対して本研究では,相対論的な不等式に対応する凸体がカット多面体の線形緩和の一つとして知られている根付き擬距離多面体と同型であること,量子の場合を表す凸体は根付き擬距離多面体と半定値緩和であるelliptopeの共通部分に含まれることを示した.

　最後に8章では以上の研究成果をまとめ,将来展望を述べている.

　このように本研究は量子情報処理と離散最適化の両分野でそれぞれ展開されていた不等式の概念を結びつける手段を提供し,その結合によりそれぞれの分野において新たな知見を与えたり概念を拡張・整理したりすることにより貢献し,新たな知見も得ることにも成功している.本研究によりその端緒が開かれた両分野の融合と交流は,今後さらに発展することが期待されるものである.従って,本研究は量子情報処理と組み合わせ最適化の両分野においてきわめて価値の高いものである.

　よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。