\newcommand{\Bra}[1]{\mathinner{\left\langle{#1}\right|}}
\newcommand{\Ket}[1]{\left|{#1}\right\rangle}
\def\set#1{\left\{{#1}\right\}}
はじめに
本記事ではHamiltonian Complexityと呼ばれる、物性物理学・数学・計算機科学の交わる比較的新しい分野でよく研究されている、$k$-局所ハミルトニアン問題の定義とその性質について簡単に紹介します。本記事の内容を理解する上での前提知識として、量子計算と計算量理論に関する知識が必要となりますが、量子計算については多岐に渡るので参考文献に譲り、後者に関して必要な最小限の知識を記事内で説明します。参考文献は最後のセクションにまとめて置いてあります。
用語・定義
計算量理論では、与えられたインスタンス$x \in \set{0,1}^{✴︎}$がある言語$\set{0,1}^{✴︎}$に属するか否かを判定するのに、時間やメモリといった計算リソースをどれだけ必要とするか調べることを主な関心としています(ただし、$\set{0, 1}^{✴︎}$は$0, 1$から成る有限列全体の集合)。このような、ある言語への帰属を判定するような問題は決定問題と呼ばれ、本記事では決定問題を一般化した約束問題について考えます。
約束問題
約束問題$S$は、$S_{yes} \cap S_{no} = \varnothing$であるような集合$S_{yes}$と$S_{no}$の対$S=(S_{yes}, S_{no})$として定義される。$S_{yes}$を$S$のYESインスタンス、$S_{no}$を$S$のNOインスタンスと呼び、あるアルゴリズム$A$が存在して
- $x \in S_{yes} \Rightarrow A(x)=1$
- $x \in S_{no} \Rightarrow A(x)=0$
を満たす時、$A$は約束問題$S$を解くという。
※一般に$S_{yes} \cup S_{no} \subseteq \set{0,1}^{✴︎}$であり、決定問題の時は $S_{yes} = L, S_{no} = \bar{L}$ であるから$S_{yes} \cup S_{no} = \set{0,1}^{✴︎}$となる。
次に、約束問題の間の関係として帰着の概念を導入します。
Karp帰着
約束問題$S=(S_{yes},S_{no})$が約束問題$S^{′} = (S_{yes}^{′},S_{no}^{′})$にKarp帰着可能とは、多項式時間アルゴリズム$A:\set{0,1}^{✴︎} \rightarrow \set{0, 1}^{✴︎}$が存在して、
- $x \in S_{yes} \Rightarrow A(x) \in S_{yes}^{′}$
- $x \in S_{no} \Rightarrow A(x) \in S_{no}^{′}$
を満たすことを言う。
※本記事では約束問題$S$が約束問題$S^{′}$にKarp帰着可能であることを、$S \leq_{m}^{p} S^{′}$のように表す。
困難性、完全性
$C$を計算量クラス、$S$を約束問題とする。任意の$S^{′} \in C$について、$S{′}$から$S$への帰着が可能であれば、$S$は(その帰着の下で)$C$困難であると言う。$S$が$C$困難かつ$S \in C$ ならば、$S$は$C$完全であると言う。
k-局所ハミルトニアン
物理系には、その系の時間発展を支配するエルミート演算子が与えられ、その演算子はハミルトニアンと呼ばれます。系全体に対して局所的な作用をする項の和で表せるハミルトニアンは局所ハミルトニアンと呼ばれ、多くの興味深い系のハミルトニアンが局所ハミルトニアンで表現または近似的に表現出来ることが知られています。
より正確には、局所性を表すパラメータ$k$を使って以下のように定義されます。
k-局所ハミルトニアン
$n$量子ビット上の演算子$H$が$k$-局所ハミルトニ アンであるとは、高々$k$個の量子ビットにしか非自明な作用をしないようなエルミート演算子$H_{j}$を用いて、$H = \sum_{j} H_{j}$のように表せる事を言う。
k-局所ハミルトニアン問題
物理系の最もエネルギーの低い状態は基底状態とよばれ、そのエネルギーは基底エネルギーと呼ばれます。この値は、数学的にはハミルトニアンの最小の固有値(記事内では$\lambda_{1}(H)$と表記)に対応しており(基底状態は最小固有値を持つ固有ベクトルに対応している)、 自然な$k$-局所ハミルトニアンに関する計算問題の定義としてこの基底エネルギーの大小を判定するような問題を考えることが出来ます。
k-局所ハミルトニアン問題
約束問題$k$-LOCAL HAMILTONIAN($H$, $a$, $b$)は、与えられた$n$量子ビット上の$k$-局所ハミルトニアン$H = \sum_{j=1}^{r} H_{j}$と、$b-a \geq \frac{1}{poly(n)}$を満たす二つの実数$a,b$ に対し、
- (YES): $\lambda_{1}(Q) \leq a$
- (NO): $\lambda_{1}(Q) ≥ b$
のどちらであるかを判定する問題である。
(以下、$k$LHと略記することがある。)
k-局所ハミルトニアン問題の難しさ
$k$LHはKitaevによって導入され、$k\geq5$の場合に$QMA$完全だと示されました。QMAは$NP$を量子に拡張した計算量クラスです。(正確には$MA$の量子拡張バージョン)。この結果は後に拡張され、$k=2$の場合でも$k$LHはQMA完全であることが知られています($k=1$の場合は$P$に入ります)。QMA完全性の証明は非常に複雑なため、ここではそれより弱い結果であり、比較的簡単に示せる、局所ハミルトニアン問題の$NP$困難性の証明を紹介しようと思います。
3LHはNP困難
$NP$完全問題である3SATからのKarp帰着によって示します。
証明: $\phi = \land_{j} C_{j}$を$n$変数3CNF論理式とする。$\phi$の各節$C_{j}$ に対し、$C_{j}$を充足するような割当に対応する状態には固有値0を、$C_{j}$を充足しないような割当に対応する状態には固有値1を与える$n$量子ビット上の演算子$H_{j}$を定義する。すなわち、例えば
$$C_{j} = x_{a} \lor \bar{x_{b}} \lor x_{c}$$
であれば、
$$H_{j} = \Ket{0}\Bra{0}_{a} \otimes \Ket{1}\Bra{1}_{b} \otimes \Ket{0}\Bra{0}_{c} \otimes I$$
となる。(エルミート演算子$H_{j}$は、$C_{j}$を充足しないような状態に対して“ペナルティー”1を与える制約と見なすことが出来る。)
この$H_{j}$から3-局所ハミルトニアン$H = \sum_{j}H_{j}$ を定義する。もし$\phi$が充足可能であれば、$\lambda_{1}(H) = 0$である。もし$\phi$が充足可能でなければ、任意の$n$量子ビット上の状態$\Ket{\psi}(=\sum_{i \in \set{0,1}^{n}} c_{i}\Ket{i})$に対して、
\begin{align}
\Bra{\psi}H\Ket{\psi} &= \sum_{i}\alpha_{i}^{*}\Bra{i}H\sum_{j}\alpha_{j}\Ket{j} \\
&= \sum_{ij}\alpha_{i}^{*}\alpha_{j}\Bra{i}H\Ket{j} \\
&\geq \sum_{i}|\alpha_{i}|^{2}\Bra{i}H\Ket{i} \\
&\geq \sum_{i}|\alpha_{i}|^{2} \cdot 1 \\
&= 1 \quad (i.e. \lambda_{1}(H) \geq 1)
\end{align}
であるので、
$$3SAT(\phi) \leq_m^{p}3LH(H,0,1)$$
が成立する。3SATはNP完全であるので、題意は示された。
最後に
もし記事の説明に関して間違いや不明瞭な点、誤字脱字などがあればご連絡頂けると幸いです。今後余裕があれば$QMA$完全性の証明について書けたらなと思います。記事を読んで頂きありがとうございました。
宣伝
オプティマインドでは「多様性が進んだ世の中でも、全ての人に物が届く世界を持続可能にする」という物流業界の壮大な社会課題を解決すべく、一緒に働く仲間を大募集中です。とりあえずもう少し聞いてみたいという方はお気軽にカジュアル面談をお申し込みください！
https://recruit.optimind.tech/#join-us
参考文献
- 量子計算関連
- 計算量理論関連
- Hamiltonian Complexityのサーベイ
- 局所ハミルトニアン問題が定義され、$k$が5以上の場合についてQMA完全であることが示された(正確には、Kitaevは$QMA$を$BQNP$と定義していたので$BQNP$完全あることが示された)
- $k=2$の場合にも局所ハミルトニアン問題が$QMA$完全であることが示された