これまで紹介してきた定式化は、以下の通りです。 分割問題 整数計画問題 被覆・パッキング問題 不等式問題 彩色問題 ハミルトニアンサイクル セールスマン巡回問題 参考資料には、その他、以下のような定式化が紹介されています […]

ハミルトニアン・サイクルとパス問題 グラフ $G = (V, E)$ $N=|V|$とします。有向グラフであっても、無向グラフであっても、この解法の結果に変わりはありません。 ハミルトンパス問題とは、グラフ内のあるノード […]

グラフ彩色問題 (Graph Coloring) 無向グラフ $G = (V,E)$ を $n$ 種類の色で、同じ色の 2 つの頂点を結ぶ辺がないように、グラフの各頂点に特定の色を付けることは可能かという問題です。国境を […]

制約が等式ではなく不等式を含む問題です。スピン数の拡張により、等式のみを含む制約として書き直すことができます。 分割問題と同様に、これらのハミルトニアンでは、多数のスピンが必要であることがわかります。 これにより、現在の […]

厳密被覆問題 (Exact Cover) 以下のような関係にある集合 $U={1, \ldots, n}$ と、部分集合 $V_{i} \subseteq U(i=1, \ldots, N)$ に対して $$U=\big […]

整数計画問題（Integer Linear Programming）は、整数計画問題は、与えられた線形制約式に整数条件がついた変数に対して，線形目的関数の値を最小化／最大化する問題です。 ベクトル $\mathbf{x} […]

QAOAの応用（問題の定式化）では、何例かの定式化を紹介しました。ここでは、Andrew Lucas “Ising formulations ofmanyNPproblems” arXiv:130 […]

quboの計算で、以下のように多項式を展開する必要があります。かつ、$q_n$ は、０または１なので、$q_n^2=q_n$と置き換えないといけません。もちろん、筆算でもいいのですが、このご時世ですから、プログラムで処理 […]

このブログの QAOAの応用（問題の定式化）で見たように、コスト関数は、コストすなわち目的関数とハイパーパラメータ $\lambda$ を掛けた成約条件を加えたものになります。この $\lambda$ をどう決めるのかが […]

QAOAでは、目的関数と制約条件を加えたものをコスト関数として、その最小値を量子断熱計算で求めるものです。「IBM Quantumで学ぶ量子コンピュータ」で紹介せれている交通最適化問題を例に、課題をみてみたいと思います。 […]