Physics and computation: An insight from non-Hermitian quantum computing

非ユニタリ量子ゲート $G$ を導入した非エルミート量子コンピュータ（NQC）は、NP 問題だけでなく $\text{P}^{\sharp\text{P}}$ 級の問題も多項式時間で解く驚異的な計算能力を持つが、その能力は指数関数的に増大する物理的資源に依存していることを明らかにした。

要約

この論文は、**「物理学と計算（コンピューター）の深い関係」**について、非常に興味深く、かつ少し悲観的な（しかし重要な）発見を報告しています。

一言で言うと、**「もし物理法則を少しだけ『非対称』にすれば、コンピューターはどんな難問も一瞬で解けるようになるが、その代償として『膨大なエネルギー（資源）』が必要になり、現実的には不可能だ」**という話です。

以下に、専門用語を排して、日常の比喩を使ってわかりやすく解説します。

---

1. 普通のコンピューター vs. この新しい「魔法の」コンピューター

まず、現在のコンピューター（量子コンピューター含む）は、**「ルールを守ったゲーム」**のようなものです。

• ルール： 情報の量（確率の合計）は常に一定でなければなりません（これを「ユニタリ性」と言います）。
• 結果： 難しい問題（例：パズルの解き方、暗号の解読）を解くのに、時間がかかりすぎることがあります。

この論文では、**「非エルミート量子コンピューター（NQC）」**という新しいモデルを提案しています。

• 新しいルール： 「情報の量」が増えたり減ったりしてもいいことにします（非ユニタリ）。
• 魔法のゲート「G」： 普通のコンピューターにはない特別な操作（ゲート G）を使います。
  • このゲートは、**「正解の答えの確率を、爆発的に増幅（増やす）」**ことができます。
  • 逆に、**「間違いの答えの確率を、爆発的に減衰（消す）」**こともできます。

【比喩：迷子の子供を探す】

• 普通のコンピューター： 迷路の入り口から、すべての道を一つずつ探して、出口を見つけるまで何時間もかかります。
• この新しいコンピューター： 迷路の出口に「魔法のメガホン」を置きます。正解の道にいる子供の声だけが、**「ブーン！！！」**と何万倍にも大きく響き、他の道にいる子供の声は「シャッ」と消えます。
  • これなら、一瞬で「あ、あの子が出口にいる！」とわかります。
  • この論文は、この「魔法のメガホン（ゲート G）」を使えば、**「NP 完全問題」**と呼ばれる超難問も、一瞬で解けることを数学的に証明しました。

2. なぜ「魔法」は現実では使えないのか？（ここが重要！）

「じゃあ、そんなすごいコンピューターを作ればいいじゃん！」と思うかもしれませんが、ここで**「物理学の壁」**が現れます。

この「魔法のメガホン」を実現するには、**「粒子（原子など）の数を増やしたり減らしたりする操作」**が必要です。

• 正解の確率を 100 倍にするには、100 倍の「粒子」を用意する必要があります。
• 問題が難しくなる（入力データが増える）と、必要な粒子の数は**「指数関数的」**に増えます。
  • 例：問題が少し大きくなるだけで、必要な原子の数が「100 個」→「10,000 個」→「100 億個」→「全宇宙の原子の数」のように跳ね上がります。

【比喩：巨大な増幅器】
この「ゲート G」は、「小さな声（答え）」を「巨大な声」にする増幅器のようなものです。

• しかし、この増幅器は**「声にするためのエネルギー（粒子）」を、声の大きさに比例して消費します。**
• 小さな問題ならまだしも、現実的な複雑な問題を解こうとすると、**「全宇宙のエネルギーと物質をすべて集めても足りない」**レベルの資源が必要になります。

3. 2 つの実験的な試みと、その壁

著者たちは、この「ゲート G」を現実に作るための 2 つの方法を提案し、検証しました。

1. 冷たい原子の「増えたり減ったり」を利用する方法

   • 2 つの箱（井戸）に原子を入れ、一方の箱には原子を注入し、もう一方から原子を逃がすことで、増幅・減衰を作ろうとしました。
   • 問題点： 必要な原子の数が膨大すぎて、実験室に収まりきらないだけでなく、原子同士がぶつかることで情報が壊れてしまう（「デコヒーレンス」という現象）リスクが極めて高いです。

2. 「ポストセレクション（事後選択）」を利用する方法

   • 実験を何回も繰り返し、「たまたま成功した結果だけ」を選んで使うという方法です。
   • 問題点： 成功する確率が、問題のサイズが大きくなるにつれて**「指数関数的にゼロ」に近づいてしまいます。つまり、成功するまで何回も繰り返そうとすると、「全宇宙の寿命が尽きるまで試しても、1 回も成功しない」**可能性があります。

4. 結論：物理学と計算の「トレードオフ」

この論文が伝えたい最大のメッセージは以下の通りです。

• 理論的には： 物理法則を少し変えれば（非エルミート系を使えば）、コンピューターは神のような計算能力（P♯P クラスの問題も一瞬で解く）を持てる。
• 現実的には： その能力を引き出すためには、**「指数関数的な物理資源（エネルギーや粒子）」**が必要になる。
• 結論： **「計算能力を劇的に上げるためには、物理的なコストが天文学的に跳ね上がる」という、避けられない「トレードオフ（交換関係）」**がある。

【まとめの比喩】
この研究は、**「もし魔法の杖があれば、どんな願いも叶えられるが、その代償として全宇宙の寿命を捧げなければならない」**と言っているようなものです。

私たちは、新しい物理法則を発見しない限り、この「魔法のコンピューター」を現実のものにすることはできません。つまり、**「計算の限界は、物理の限界と密接につながっている」**という、とても深遠で美しい（そして少し寂しい）真理を突き止めたのです。

著者のメッセージ

「新しい物理法則を見つけられない限り、従来の量子コンピューターを超えるような『魔法のコンピューター』を作るのは、物理的な壁（資源の不足）によって不可能だ」というのが、この論文の核心です。それは、古典的なコンピューターで量子シミュレーションをするのが大変なのと同じくらい、ハードルが高いということです。

技術概要

非エルミート量子コンピューティングからの物理学と計算への洞察：技術的サマリー

本論文は、張起（Qi Zhang）と呉飙（Biao Wu）によって執筆され、物理学と計算理論の深い関係性を解明する新しい理論的計算モデル「非エルミート量子コンピュータ（NQC: Non-Hermitian Quantum Computer）」を提案・検討した研究です。

以下に、問題設定、手法、主要な貢献、結果、そして意義について詳細にまとめます。

1. 問題設定

従来の量子コンピュータ（BQP 複雑性クラス）は、Shor のアルゴリズムや Grover のアルゴリズムなどで古典コンピュータを上回る能力を示しますが、NP 完全問題や P♯P（P 階層の #P 完全問題）を多項式時間で効率的に解くことはできません。
これまでに、閉じた時間的曲線（CTC）の利用、非線形ゲートの導入、ポストセレクション（後選択）の活用、ローレンツ量子コンピュータ（LQC）の提案など、標準的な量子力学の枠組みを超えた物理原理に基づく計算モデルがいくつか提案され、これらは NP 完全問題や P♯P を多項式時間で解く能力を持つとされています。しかし、これらの多くは「仮想的な能力」や「非物理的な原理」に依存しており、現実の物理系で実装可能かという点に疑問が残っていました。

本研究の目的は、現実の物理系（非エルミート系）で実装可能な非ユニタリゲートを導入することで、NP 完全問題や P♯P を多項式時間で解く計算モデルを構築し、その計算能力の源泉が物理的なリソースにどう依存するかを明らかにすることです。

2. 手法と理論モデル

非エルミート量子コンピュータ（NQC）の定義

従来の量子コンピュータのユニタリ性（確率保存）の制約を緩和し、非ユニタリな線形ゲート $G$ を導入したモデルを提案しました。

• ユニバーサルゲートセット: ハダマードゲート（H）、位相ゲート（T）、CNOT ゲート、および非ユニタリゲート $G$。
• ゲート $G$ の定義:
  $$G = \begin{pmatrix} g^{-1} & 0 \\ 0 & g \end{pmatrix}$$
  ここで、$g > 0$ かつ $g \neq 1$ は実数です。このゲートを $r$ 回適用すると、状態のノルムが指数関数的に変化します（$g^r$ と $g^{-r}$）。
• 複雑性クラス BNQP: 非エルミート量子コンピュータで多項式時間で解ける有界誤差問題のクラスを BNQP と定義し、これが P♯P に等価であることを証明しました。

アルゴリズムの提案：最大独立集合（MIS）問題

NP ハード問題である「最大独立集合（Maximum Independent Sets: MIS）」問題を例に、NQC の計算能力を示すアルゴリズムを設計しました。

1. 初期化: $n$ 個の作業量子ビットと、非ユニタリ変換を受ける追加の量子ビット（$|n\rangle$）を用意し、全状態の重ね合わせを作成。
2. オラクル: 独立集合（IS）かどうかを判定するオラクルを適用し、IS である状態とそうでない状態を区別。
3. 非ユニタリ増幅: 各作業量子ビットを制御ビット、追加量子ビットをターゲットとして、制御付き $G^r$ ゲート（C-$G^r$）を適用。これにより、IS である状態の振幅が $g^{mr}$（$m$ は頂点数）倍に、そうでない状態の振幅が $g^{-mr}$ 倍に指数関数的に増幅・減衰します。
4. 測定: 追加量子ビットを測定することで、MIS に相当する状態を高い確率で選択します。
   このアルゴリズムの時間計算量は $O(n^2)$ であり、MIS 問題を多項式時間で解くことができます。

物理的実装スキームの検討

ゲート $G$ を物理的に実現するための 2 つのスキームを検討しました。

1. 粒子数の変化を利用した双井戸冷原子系:
   • 2 種類のボソン（例：Rb と Na）を用いた双井戸ポテンシャル系。
   • 一方の井戸で粒子の増殖（ゲイン）、他方で粒子の消失（ロス）を制御し、非エルミートハミルトニアンを構築。
   • 非ユニタリゲートは、パラメータをアディバティックに循環させることで生じる「純虚数の幾何学的位相（ベリー位相）」によって実現されます。
2. ポストセレクション（後選択）:
   • 補助量子ビットを導入し、ユニタリ変換後に特定の測定結果（例：$|0\rangle$）を得た場合のみ計算を継続する手法。
   • これは非エルミートダイナミクスを模擬する効果を持ちます。

3. 主要な結果

計算能力の証明

• BNQP = P♯P: NQC によって多項式時間で決定可能な言語のクラスは、P♯P に等価であることが証明されました。これは、ローレンツ量子コンピュータ（LQC）と同様の結果であり、非ユニタリゲートによる「指数関数的な振幅増幅」が計算能力の源泉であることを示しています。
• NP 完全問題の解決: 上記の MIS アルゴリズムにより、NP 完全問題（および NP ハード問題）が NQC において多項式時間で解けることが示されました。

物理的実現の障壁（重要な発見）

理論的には強力な計算能力を持つ NQC ですが、物理的実装には指数関数的な物理リソースが必要であることが明らかになりました。

• 粒子数の要求: ゲート $G$ を実装する双井戸系において、振幅の増幅を確実に行うためには、入力サイズ $n$ に対して指数関数的に多い粒子数（$N \sim 2^n$ 以上）が必要です。
• デコヒーレンスの問題: 多粒子系では、デコヒーレンス時間が粒子数 $N$ に反比例して短縮されます（$T'_2 \approx T_2 / N$）。指数関数的に多い粒子数が必要であるため、デコヒーレンス時間が極端に短くなり、計算が完了する前に量子状態が崩壊してしまいます。
• ポストセレクションの成功率: ポストセレクション方式の場合、成功確率が $n$ に対して指数関数的に減少します。これを克服するには、指数関数的に多くの並列量子コンピュータを用意する必要があります。

4. 結論と意義

本研究は、以下の重要な洞察を提供しています。

1. 物理学と計算の深い関係性: 非エルミート量子力学（ゲイン・ロス系）を計算リソースとして利用することで、P♯P 相当の計算能力を理論的に獲得できることを示しました。
2. 物理的コストのトレードオフ: 従来の量子コンピュータを超える計算能力を得るためには、物理的に「指数関数的なリソース（粒子数や並列マシン数）」を投入する必要があることを明らかにしました。これは、古典コンピュータで量子多体系をシミュレーションする際のメモリ不足の問題と本質的に類似しています。
3. 実用性の限界: 現在の物理技術では、指数関数的なリソースと極端に短いデコヒーレンス時間を克服することが不可能であるため、NQC を実用的な計算装置として構築することは現実的ではないという結論に至りました。

総括:
この論文は、「物理法則を拡張することで計算能力を飛躍的に向上させる理論的モデルは存在するが、その実装には物理的に克服不可能なほどの巨大なリソースが必要である」という、物理学と計算理論の間の根本的な制約関係を浮き彫りにしました。これは、量子超越性（Quantum Supremacy）の議論において、単にアルゴリズムの効率性だけでなく、物理的な実装コストが計算複雑性クラスを決定づける重要な要因であることを示唆しています。