Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

技術要約：行列操作アルゴリズムにおける量子制御測定、エルミート共役、および正規化

問題提起
本論文は、既存の量子行列操作アルゴリズム（具体的には、文献[33–35]で提案されている、純粋な重ね合わせ状態の確率振幅に行列要素を符号化する手法に基づくもの）における3つの決定的な制限事項に対処している：

1. ポストセレクションの非効率性： 現行のアルゴリズムは、不要な「ゴミ」の状態をフィルタリングして望ましい結果を選択するために、単一の量子ビットのアニラ（補助量子ビット）の測定に依存している。このプロセスは、行列の次元に対して多項式または指数関数的に減少する低い成功確率に苦しんでいる。その結果、アルゴリズムは望ましい結果を得るために複数回の実行を必要とし、効率を著しく低下させている。
2. エルミート共役への対応不能： これらのアルゴリズムは一般に複素行列を扱えるが、特定の操作であるエルミート共役は標準的な符号化フレームワーク内では実現できず、代数的操作の多様性を制限している。
3. 厳格な正規化制約： 行列要素を純粋な量子状態に符号化することは、厳格な正規化条件（$\sum |a_{jk}|^2 = 1$）を課す。これは行列要素の絶対値を制限することになり、必ずしも最適とは言えない特定のスケーリングを必要とする。

手法
著者らは、行列操作フレームワークに対する3つの異なる拡張を提案している：

1. 量子制御測定 (Quantumly Controlled Measurement: QCM):

   • 単一のアニラ量子ビット（$B_1$）に対する標準的な射影測定の代わりに、2量子ビットのアニラ系（$B_1$ および $B_2$）を導入する。
   • 第1の量子ビット（$B_1$）の状態が、第2の量子ビット（$B_2$）に適用される測定演算子の制御として機能する。
   • 具体的には、システムが「有用な」項が $|1\rangle_{B_1}$ と絡み合い、「ゴミ」が $|0\rangle_{B_1}$ と絡み合った重ね合わせ状態にある場合、C-NOTゲートが $B_1$ と $B_2$ を絡み合わせる。その後、制御測定演算子 $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$ が適用される。
   • このメカニズムにより、有用な成分が存在する場合（$\alpha \neq 0$）、$B_2$ への測定が決定論的にトリガーされ、標準的なポストセレクションに伴う確率的な失敗なしに、システムを目的の状態で崩壊させる。

2. 実部と虚部の分離符号化：

   • エルミート共役を可能にするため、著者らは追加の1量子ビット部分系（$M$）を用いて、複素行列要素の実部と虚部を2つの直交する部分空間に符号化することを提案している。
   • 状態 $|0\rangle_M$ は実部を、$|1\rangle_M$ は虚部をラベル付けする。
   • エルミート共役は、行/列レジスタに対するSWAP操作と $M$ レジスタに対する $\sigma_z$ 操作を組み合わせることで実現され、実質的に転置と複素共役を行う。

3. 緩和された正規化制約：

   • 符号化スキームに別の補助量子ビット（$K$）を導入する。
   • 初期状態は、状態 $|0\rangle_K$ に関連付けられた振幅 $b$ を持つ追加の項を含めることで修正され、行列要素は $|1\rangle_K$ に関連付けられる。
   • これにより、正規化条件は等式（$\sum |a_{jk}|^2 = 1$）から不等式（$\sum |a_{jk}|^2 \leq 1$）へと変化し、行列要素の大き度の柔軟性が高まる。

主要な貢献と結果

• 行列乗算への実装： 著者らは、QCMとこれら2つの符号化拡張を、行列乗算アルゴリズムに統合している。彼らは、このアルゴリズムが標準的な乗算だけでなく、エルミート共役を含む操作（例：$A^\dagger B$, $A B^\dagger$）を実行できることを示している。
• 回路構成： 以下のための詳細な量子回路が提示されている：
  • QCMサブルーチン。
  • エルミート共役演算子。
  • 3つの拡張すべてを組み込んだ修正行列乗算アルゴリズム。
• 複雑性解析：
  • 空間量： これらの修正には、定数個の追加量子ビット（符号化拡張のための4つの追加量子ビットと、乗算の文脈におけるQCM用のアニラ1つ）のみが必要である。空間複雑度は、$N=2^n$ を行列次元としたとき、$O(n)$ のままである。
  • 深さ： 回路の深さは $O(n)$ のままである。著者らは、低確率の成功を克服するための繰り返しの実行が必要であったため、従来のアルゴリズムの実効的な総実行時間が $O(2^n n)$ であったのに対し、QCMベースのアルゴリズムは、回路自体の $O(n)$ 深さの特性を維持しながら、単一の実行で結果を得られることを指摘している。
  • 正規化の回収： 著者らは、QCMが（以前は測定の成功確率から導出されていた）正規化定数 $G$ に関する確率的情報を除去することを認めている。彼らは、補助状態 $|0\rangle_K$ の確率を測定するためにアルゴリズムを複数回実行することで、確率的に $G$ を測定する方法を提案しているが、これは単発の結果生成とは別の実行を必要とする。

意義と主張
本論文は、量子制御測定（QCM）の導入が、測定ベースの量子行列アルゴリズムに固有の「ポストセレクション問題」を根本的に解決することを主張している。ゴミの状態に対する確率的なフィルタリングを、決定論的な量子制御プロセスに置き換えることで、繰り返し実行に伴う指数関数的なオーバーヘッドを排除している。

著者らは、QCMが単なる振幅増幅技術（Groverのアルゴリズムのようなもの）ではなく、量子制御と古典的測定を組み合わせた明確な演算子であり、潜在的に新しいタイプの「量子・古典制御」を提供することを強調している。

さらに、エルミート共役および緩和された正規化制約に関する拡張は、より広範な複素行列およびデータ符号化シナリオへの行列操作アルゴリズムの適用性を広げるものである。著者らは、QCMの実際的な物理的実現が標準的な量子/古典演算の観点からはまだ詳細に記述されていないものの、その理論的定式化は量子重ね合わせ状態の実在性を正当化し、より効率的な量子線形代数への道筋を提供するものであると述べている。

結論として、これらの修正は、行列乗算だけでなく、文献[34, 35]で議論されている行列加算、行列式計算、逆行列計算、線形方程式ソルバー、およびその他の測定ベースの量子アルゴリズムにも適用可能であるとしている。