加算器シミュレーション
フルアダーとリップルキャリーアダー
フルアダーは3つの入力ビット（$a$、$b$、$i$（キャリーイン））と 2つの出力ビット（$o$（キャリーアウト）と$s$（和））で構成される。 3つの入力ビットの和は、これら2つの出力ビットを用いて表現される。
リップルキャリー加算器は、複数のフル加算器をカスケード接続することで2つの多ビット整数の和を計算します。下図の通りです：
このリップルキャリー加算器は、4ビット整数$x_3x_2x_1x_0$と$y_3y_2y_1y_0$の和を計算し、 4つのフルアダーを用いて4ビットの和$z_3z_2z_1z_0$を出力する。 対応する5ビットのキャリー信号$c_4c_3c_2c_1c_0$も示されている。
フルアダーのQUBO表現
フルアダーは次の式を用いて定式化できる：
\[\begin{aligned} fa(a,b,i,c,s) &=((a+b+i)-(2o+s))^2 \end{aligned}\]この式は、5つの変数が有効なフルアダー演算と整合する値を取る場合にのみ、最小値0を達成する。 以下のQUBO++プログラムは、網羅的ソルバーを用いてこの定式化を検証する：
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
int main() {
auto a = qbpp::var("a");
auto b = qbpp::var("b");
auto i = qbpp::var("i");
auto o = qbpp::var("o");
auto s = qbpp::var("s");
auto fa = (a + b + i) - (2 * o + s) == 0;
fa.simplify_as_binary();
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(fa);
auto sol = solver.search_optimal_solutions();
std::cout << sol << std::endl;
}
このQUBOプログラムでは、制約$fa(a,b,i,c,s)$を等式演算子 ==で実装されており、これは直感的に制約 $a+b+i=2o+s$ を表す。
プログラムは以下の出力を生成し、式がフルアダーを正しくモデル化していることを確認する:
(0) 0:{{a,0},{b,0},{i,0},{o,0},{s,0}}
(1) 0:{{a,0},{b,0},{i,1},{o,0},{s,1}}
(2) 0:{{a,0},{b,1},{i,0},{o,0},{s,1}}
(3) 0:{{a,0},{b,1},{i,1},{o,1},{s,0}}
(4) 0:{{a,1},{b,0},{i,0},{o,0},{s,1}}
(5) 0:{{a,1},{b,0},{i,1},{o,1},{s,0}}
(6) 0:{{a,1},{b,1},{i,0},{o,1},{s,0}}
(7) 0:{{a,1},{b,1},{i,1},{o,1},{s,1}}
一部のビットが固定されている場合、残りのビットの有効な値を導出できる。
例えば、3つの入力ビットは次の関数で固定できる replace() 関数で固定できます：
fa.replace({{a, 1}, {b, 1}, {i, 0}});
するとプログラムは以下の出力を生成します：
(0) 0:{{o,1},{s,0}}
逆に、2つの出力ビットが固定されている場合：
fa.replace({{o, 1}, {s, 0}});
プログラムは入力ビットの全有効な組み合わせを出力します：
(0) 0:{{a,0},{b,1},{i,1}}
(1) 0:{{a,1},{b,0},{i,1}}
(2) 0:{{a,1},{b,1},{i,0}}
複数の全加算器を用いたリップルキャリー加算器のシミュレーション
フルアダのQUBO式を用いて、リップルキャリー加算器をシミュレートするQUBO式を構築できる。 以下のQUBO++プログラムは、4つのフルアダを組み合わせることで4ビット加算器をシミュレートするQUBO式を生成する:
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
int main() {
auto a = qbpp::var("a");
auto b = qbpp::var("b");
auto i = qbpp::var("i");
auto o = qbpp::var("o");
auto s = qbpp::var("s");
auto fa = (a + b + i) - (2 * o + s) == 0;
auto x = qbpp::var("x", 4);
auto y = qbpp::var("y", 4);
auto c = qbpp::var("c", 5);
auto z = qbpp::var("s", 4);
auto fa0 = qbpp::replace(fa, {{a, x[0]}, {b, y[0]}, {i, c[0]}, {o, c[1]}, {s, z[0]}});
auto fa1 = qbpp::replace(fa, {{a, x[1]}, {b, y[1]}, {i, c[1]}, {o, c[2]}, {s, z[1]}});
auto fa2 = qbpp::replace(fa, {{a, x[2]}, {b, y[2]}, {i, c[2]}, {o, c[3]}, {s, z[2]}});
auto fa3 = qbpp::replace(fa, {{a, x[3]}, {b, y[3]}, {i, c[3]}, {o, c[4]}, {s, z[3]}});
auto adder = fa0 + fa1 + fa2 + fa3;
adder.simplify_as_binary();
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(adder);
auto sol = solver.search_optimal_solutions();
std::cout << sol << std::endl;
}
このQUBO++プログラムでは、 qbpp::Expr オブジェクトが replace() 関数で作成され、単一の式 adder。
その後、網羅的ソルバーを使用して全ての最適解を列挙する。
このプログラムは4ビット加算器の全入力組み合わせに対応する512個の有効解を生成する:
(0) 0:{{x[0],0},{x[1],0},{x[2],0},{x[3],0},{y[0],0},{y[1],0},{y[2],0},{y[3],0},{c[0],0},{c[1],0},{c[2],0},{c[3],0},{c[4],0},{s[0],0},{s[1],0},{s[2],0},{s[3],0}}
(1) 0:{{x[0],0},{x[1],0},{x[2],0},{x[3],0},{y[0],0},{y[1],0},{y[2],0},{y[3],0},{c[0],1},{c[1],0},{c[2],0},{c[3],0},{c[4],0},{s[0],1},{s[1],0},{s[2],0},{s[3],0}}
(2) 0:{{x[0],0},{x[1],0},{x[2],0},{x[3],0},{y[0],0},{y[1],0},{y[2],0},{y[3],1},{c[0],0},{c[1],0},{c[2],0},{c[3],0},{c[4],0},{s[0],0},{s[1],0},{s[2],0},{s[3],1}}
(3) 0:{{x[0],0},{x[1],0},{x[2],0},{x[3],0},{y[0],0},{y[1],0},{y[2],0},{y[3],1},{c[0],1},{c[1],0},{c[2],0},{c[3],0},{c[4],0},{s[0],1},{s[1],0},{s[2],0},{s[3],1}}
... omitted ...
(510) 0:{{x[0],1},{x[1],1},{x[2],1},{x[3],1},{y[0],1},{y[1],1},{y[2],1},{y[3],1},{c[0],0},{c[1],1},{c[2],1},{c[3],1},{c[4],1},{s[0],0},{s[1],1},{s[2],1},{s[3],1}}
(511) 0:{{x[0],1},{x[1],1},{x[2],1},{x[3],1},{y[0],1},{y[1],1},{y[2],1},{y[3],1},{c[0],1},{c[1],1},{c[2],1},{c[3],1},{c[4],1},{s[0],1},{s[1],1},{s[2],1},{s[3],1}}
あるいは、C++関数を定義することで fa より簡潔で読みやすい方法でフルアダー制約を構築するC++関数を定義することもできます：
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
qbpp::Expr fa(qbpp::Var a, qbpp::Var b, qbpp::Var i, qbpp::Var o, qbpp::Var s) {
return (a + b + i) - (2 * o + s) == 0;
}
int main() {
auto x = qbpp::var("x", 4);
auto y = qbpp::var("y", 4);
auto c = qbpp::var("c", 5);
auto z = qbpp::var("s", 4);
auto fa0 = fa(x[0], y[0], c[0], c[1], z[0]);
auto fa1 = fa(x[1], y[1], c[1], c[2], z[1]);
auto fa2 = fa(x[2], y[2], c[2], c[3], z[2]);
auto fa3 = fa(x[3], y[3], c[3], c[4], z[3]);
auto adder = fa0 + fa1 + fa2 + fa3;
adder.simplify_as_binary();
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(adder);
auto sol = solver.search_optimal_solutions();
std::cout << sol << std::endl;
}
このプログラムは、前の実装と同じ512個の最適解を生成します。
一部の二進変数が固定されている場合、残りの変数の有効な値は網羅的ソルバーを用いて導出できる。
例えば、以下の qbpp::MapList オブジェクト ml キャリーイン、キャリーアウト、および和ビットを固定します:
qbpp::MapList ml = {{c[4], 1}, {c[0], 0}, {z[3], 1},
{z[2], 1}, {z[1], 0}, {z[0], 1}};
adder.replace(ml);
結果として生成されるプログラムは以下の出力を生成します:
(0) 0:{{x[0],0},{x[1],1},{x[2],1},{x[3],1},{y[0],1},{y[1],1},{y[2],1},{y[3],1},{c[1],0},{c[2],1},{c[3],1}}
(1) 0:{{x[0],1},{x[1],1},{x[2],1},{x[3],1},{y[0],0},{y[1],1},{y[2],1},{y[3],1},{c[1],0},{c[2],1},{c[3],1}}