読み込み中...
投稿日
量子ゲート方式による最適化アルゴリズム
はじめに
戦略技術センター（STC）で量子コンピュータ関係の研究開発をしている吉岡です。この記事では、量子ゲート方式による最適化アルゴリズムの概要を紹介します。
量子コンピュータでは、組み合わせ最適化問題から機械学習まで、古典的なコンピュータでは解決困難な問題を量子力学の原理を用いて解決することが期待されています。 量子コンピュータは、量子ビットによる|0>と|1>の重ね合わせ状態として情報を扱います。 ここで、|0>と|1>は古典ビットの状態を表します。 量子コンピュータのなかでも、量子ビット、量子ゲート、計測などの要素を並べた量子回路を用いて計算する方式は、古典的なビットに論理ゲートを適用する古典計算を想起させるため、量子ゲート方式と呼ばれます。 この記事では、組み合せ最適化問題を解くために設計されたゲート方式の量子近似最適化アルゴリズム（QAOA）[^1]の概要を説明します。
NISQ時代における変分量子アルゴリズム（VQA）
現在のノイズのある中規模量子(NISQ: Noisy Intermediate-Scale Quantum)デバイスにおいては、 量子ゲートのノイズによって、正確に実行できる量子回路の大きさが制限されるため、量子アルゴリズム開発に大きな影響を及ぼします。 有用なNISQアルゴリズムを開発するには、次の2つの厳しい制約を克服する必要があります。
i) 少数量子ビットしか利用できない。
ii) エラーのため、回路の深さをできるだけ短くする必要がある。
これらの制約条件を満足する有力な手段として、パラメータ表記された量子回路に対して、そのパラメータをチューニングすることで、アプリケーションに適した量子状態を生成する変分量子アルゴリズム（VQA: Variational Quantum Algorithm）が登場しました。VQAは、図1に示すように量子コンピュータの研究者が想定しているすべてのアプリケーションに対して提案されており、NISQ時代において量子的な優位性を得るための最良の方法と考えられています[^2]。
図1. 変分量子アルゴリズム(VQA)応用例（引用元M. Cerezo et al., 2021)
組み合わせ最適化問題と量子近似最適化アルゴリズム（QAOA）
量子アルゴリズムの有望な応用例として、組み合せ最適化問題があります。 この問題は、金融、製造、物流などの分野で数多くのユースケースが想定されます。 一般に、組み合せ最適化問題を解くタスクは、ある要素のリストの中から、ある指標に関して最適な要素を見つけることです。 このような問題は組み合わせ構造であるため、リストの大きさは問題の大きさに対して少なくとも指数関数的に増大します。 従って、素朴な要素ごとの探索では指数関数的に多くの要素をチェックする必要があり、問題サイズが大きくなるとすぐに実行不可能になります。
構造化されていないリストから要素を見つけるグローバーのアルゴリズムは、古典的アルゴリズムに比べて二次の高速化（O(n) → O(√n)）を達成しており、 多数の解を探索する必要のある組み合わせ最適化問題の設定と類似しています。 このことから、量子コンピュータが、組み合わせ最適化においても同様の高速化を実現できるのではないかと期待されるようになりました。 さらに、量子ゲート方式とは異なる量子アニーリング方式[^3]に基づく量子アニーリングマシンなど、最適化問題に特化した初の量子デバイスが登場し、 量子コンピュータコミュニティでは最適化問題がさらに注目されるようになりました。
量子近似最適化アルゴリズム（QAOA: Quantum Approximate Optimization Algorithm）は、ゲート方式の量子コンピュータ上で組み合せ最適化問題の解を求める変分量子アルゴリズムです。 QAOAを組み合わせ最適化問題に適用するための最初のステップは、最適化問題を局所磁場下で相互作用するイジングモデルへ適切にマッピングすることです。 このスピンモデルの表現では、最適化問題のコスト関数はスピンモデルのエネルギーに対応するため、 最低エネルギー状態、 または低エネルギー状態を見つけることが計算の目的になります。 これを達成するために、QAOAでは以下の変分試行状態（ansatzと呼ばれる） |ψ({βl, γl})> を利用します。この状態は形式的に以下の形をとります。
|ψ({βl, γl})>= ΠlUM(βl)UP(γl)(H|0>)⊗N
ここで、Nは量子ビット数、Hはアダマールゲート、UP(γl)とUM(βl)は、それぞれ各ビット列の位相をコスト関数に応じて変化させる演算子（位相分離演算子）と|0>と|1>の重ね合わせを生成する演算子（ミキシング演算子）を表します。 この変分試行状態に対応する量子回路の模式図を図2に示します。 この量子回路に埋め込まれた2p個のパラメータ{βl, γl} を変化させることにより、エネルギー期待値E({βl, γl})が最小になるように最適化を行います。 なお、E({βl, γl})は通常の関数であるため、 最適化には古典的なスキームを利用できます。 最適なパラメータセット{βl*, γl*}が見つかれば、|0>、|1>の基底で量子ビットを測定することにより、最適化問題の解をサンプリングできます。 QAOAの一般的な構造により、様々な組み合わせ最適化問題に適用できます。さらに、実機を用いて様々な問題にQAOAを適用した例が存在します[^4][^5]。 しかしながら、QAOAが古典的アルゴリズムを凌駕することを示す正式な証明や実証は今のところ存在しません。
図2. QAOAにおける変分試行状態
QAOAの拡張
QAOAでは、最適化問題を2値変数で定式化する必要があります。 しかし、産業界の多くの最適化問題には、多変量または連続変数が含まれており、QAOAを適用する前に、これらを2値変数に符号化する必要があります。 例えば、3値変数x = {0、1、2}の3つの状態は、ハミング重み1の3つのスピンの構成にエンコードされます。 これは、1つのスピンが1の状態にある構成、すなわち{100、010、001}になります。 ハミング重み1の構成のみを用いた符号化は、one-hot encodingとして知られています。 このエンコーディングでは、スピンの他の可能な配置を無効な状態としてフラグを立てる制約を実装することが必要です。 量子アニーリングでは、すべての不要な状態にエネルギーペナルティを課すことでこれを実現できます。 しかし、エネルギーペナルティの適切な大きさを設定することは、対象とする問題のエネルギースケールを圧倒しないようにしながらも、制約を満たすように十分大きく選択しなければならない。 そのため、ペナルティ関数の設定が困難になる場合があります。
上記のコスト関数にペナルティ関数を足し合わせるスキームはQAOAでも使用可能ですが、Hadfieldらは別のスキームを導入しました[^6]。これが、量子交替作用素仮設（QAOA: Quantum Alternating Operator Ansatz）です。 ここでは、コスト関数にペナルティ関数を加える代わりに新たなミキサーを導入し、量子アルゴリズムによる状態変化を有効な解の部分空間に保つように設計されています。 文献[^7]では、このような方式がエネルギーペナルティを用いた方式よりも優れていることを示されました。 このようなミキサーは量子アニーリングマシン上で実装することが困難であるため、制御性の高いゲート方式によるQAOAが将来大きなアドバンテージをとる可能性があります。このようにQAOAの量子アルゴリズムの拡張は順調に進んでいます。
まとめ
今回は、組み合わせ最適化問題に対するNISQアルゴリズムQAOAの概要を説明しました。 今後数百、数千の量子ビットを持つNISQ計算機が登場した場合、産業界に関連する最適化問題を解くためには量子アルゴリズムのさらなる改良が必要です。 さらに、QAOAで量子的な優位性を得るためには、産業界から適切なユースケースを見つけ出す必要があります。 今後は、アルゴリズムの詳細やその具体的な適用例について紹介する予定です。
