処理が一本道なら、手前から順に調べれば済みそうです。けれども、途中で道が分かれ、再び合流したり、前の処理へ戻ったりするとどうでしょう。後から届いた情報によって、一度調べた場所の答えが変わることがあります。
このとき、何をもう一度調べるかを管理するのが、データフロー解析のワークリスト法です。Open Quantum Design（OQD）の公開コンパイラー基盤には、その仕組みを汎用のグラフへ適用する実装があります。保存されたコードの具体例から、情報が合流する方法、ループで調べ直す理由、計算を終えてよい条件を見ていきます。
簡単にまとめると？
- ワークリストは「これから調べる場所」の一覧です。OQDの対象実装は最初に全ての点を入れ、その後は出力が変わった点の影響先を再登録します。
- 合流では、何を知りたいかに合わせて情報をまとめます。「どれかの経路から届く」なら和集合、「全ての経路に共通する」なら共通部分、という違いがあります。
- 同じ計算をしても値が変わらない状態が固定点です。単調性や有限の高さなどの条件が収束を支えますが、反復上限へ達してエラーになったことは、答えが確定した意味ではありません。
データフロー解析で流すのは、処理についての情報
データフロー解析は、処理のつながりに沿って情報を伝え、各地点で何が分かるかを調べる方法です。例えば、「この場所まで、どの処理からたどり着けるか」「この変数の値は、この先で使われるか」といった問いがあります。ここで流すのは解析用の集合や状態であり、量子ビットを物理的に運ぶ話ではありません。
OQDの対象実装では、グラフの各点について、入ってきた情報を表す in_states と、その点で計算した後の情報を表す out_states を持ちます。複数の相手から届く情報をまとめる merge と、その点で情報を変換する transfer は、解析を作る側が定義します。グラフの点と前後の隣接関係があれば使えるため、特定の量子回路専用の解析には固定されていません。［1］
この記事で扱うのは、OQD Compiler Infrastructureのコミット 1e861edacd25773df3b678c6002c5439b0691c37 です。保存版の宣言バージョンは0.1.0、開発状態はAlphaです。公開実装の読み取りと小さなソフトウェア例の検証であり、量子実機の性能向上を示すものではありません。［1、3］
合流とループがあると、一度の順番では足りない
例として、AからBとCへ分かれ、Dで合流してEへ進むグラフを考えます。さらに、DからBへ戻る道も一本あります。各点に持たせるのは、その点までたどり着ける点の集合です。自分自身も含めます。
最初は全て空集合にし、前の点から届いた集合を和集合で合わせ、そこへ自分の名前を加えます。これは、OQDの上流テストにある到達関係の解析を、合流とループを含む独自の例へ適用したものです。集合に入った名前は「そこから到達できる」という可能性を表し、実際のプログラムが全ての道を一度に通った、という意味ではありません。［2］
A、B、C、D、Eの順に最初の計算をすると、Aの出力は{A}、Bは{A, B}、Cは{A, C}です。DではBとCから来た情報を合わせ、自分のDも加えるので、{A, B, C, D}になります。
ここでDの出力が増えたため、その影響先であるBとEを調べる必要が生まれます。Eはまだワークリストにいるので追加せず、既に一度調べ終えたBだけを末尾へ戻します。残る順番はE、Bです。
Eを調べた後にBへ戻ると、今度はAだけでなくDからも情報が来ます。Bの出力は{A, B}から{A, B, C, D}へ増えます。そこで、Bの影響先であるDをもう一度登録します。
Dを調べ直しても、出力は既に{A, B, C, D}です。入力は更新されますが、出力には新しい情報が加わりません。このため、BやEをさらに登録せず、ワークリストが空になります。今回の初期順序と隣接関係の順序では、点を取り出す回数は7回でした。グラフ全体を7周した数でも、他の方法との速度比較でもありません。
出力が変わらなければ、先へ通知しない
対象のOQD実装は、待ち行列の先頭から点を取り出し、入力をまとめ、変換後の出力を前回と比べます。出力が同じなら、その点の処理はそこで終わります。変わったときだけ影響先を末尾へ追加し、既に待ち行列にある点を重ねて追加しません。［1］
大事なのは、途中で入力が変わったかだけでなく、その点から先へ渡す出力が変わったかで判断することです。今回のDのように、入力が増えても、出力に新しい情報がなければ先の計算は増やさずに済みます。ただし、この仕組みだけから、任意のグラフで何倍速くなるとまでは言えません。
なお、この到達集合の例では初期値を空集合へ明示的に変更しています。基底クラスの既定値はラティスの最上位値 top() です。「OQDの全ての解析が空集合から始まる」と読むと、別の解析を組むときに意味が変わってしまいます。
前向きと後向きは、知りたいことから選ぶ
過去の処理から現在へ届く情報を調べるなら、前向き解析が自然です。OQDの ForwardDataflowAnalysis は前の点から情報を受け取り、出力が変わると次の点を登録します。
一方、「この値がこの先で使われるか」のように、将来の必要性を現在へ伝えたい場合は後向き解析を考えます。BackwardDataflowAnalysis は次の点から情報を受け取り、前の点を登録します。ただし、方向を替えるだけで変数の生存解析が完成するわけではありません。何を使用・定義として扱うか、どの情報を残すかも別に定めます。［1、4］
この実装の in_states と out_states は、解析の情報が入る側・変換後の側の名前です。後向き解析ではプログラムの実行方向と逆になるので、コード上の名前をそのまま実行前・実行後と読み替えないことも大切です。
合流の方法も、問いと一緒に選びます。今回のように「どれかの経路で到達できる」を集めるなら和集合です。「どの経路を通っても必ず成り立つ」を調べるなら、各経路の情報の共通部分を残す設計が考えられます。和集合か共通部分かを替えれば済むとは限らず、状態の順序、初期値、入口や出口の条件も、その意味に合わせる必要があります。
固定点に着くことと、上限で止めることは違う
同じ関係式をもう一度計算しても値が変わらない状態を、固定点と呼びます。有限のグラフで、状態の変化が定めた順序を保つこと、異なる値がその順序に沿って際限なく続かないこと、適切な初期値と境界条件から始めることが、収束を考えるうえで重要です。順序を保つ性質が「単調性」、順序に沿う変化の段数が有限であることが「有限の高さ」です。［4］
今回の例は、A〜Eの有限個の名前を、空集合から和集合で増やしていきます。一度得た名前を消さず、追加できる名前も有限なので、ずっと新しい情報が増え続けることはありません。
けれども、解析を作る側が任意の変換を与えられる以上、フレームワークだけで全ての解析の収束が保証されるわけではありません。例えば、自分へ戻る点で「空なら名前を入れ、入っていれば空にする」と変換すれば、二つの状態を往復します。この非単調な独自例では、反復上限を4にして実行すると、結果を返す代わりに上限超過のエラーになりました。
OQDの対象版の max_iterations は、既定で1,000,000です。この数はワークリストから点を処理する回数の上限であり、実行時間の保証でも、正しい答えへ近づいた度合いでもありません。上限を超えたときは、単に値を大きくする前に、変換が収束する設計か、初期値や合流の意味が合っているかを確認する必要があります。［1］
この実装を読むときは、「何を知りたいか」「どちら向きに情報を伝えるか」「合流で何を残すか」「なぜ変化が止まるか」を一組で見ると、ワークリストの役割がはっきりします。待ち行列は調べ直す順番を管理しますが、何を答えとするかは、解析の設計に残されています。
参考資料
- Open Quantum Design — dataflow.py（対象コミットの実装）。グラフの契約は同版のinterface.py、順序・合流・等値比較はlattice.pyを参照。
- Open Quantum Design — test_dataflow.py。前向き・後向きの到達集合の上流テスト。本文の合流・ループ・上限例は、この保存版に対する独自のソフトウェア検証です。
- Open Quantum Design — pyproject.toml。宣言バージョン0.1.0、Alpha分類、Python要件など。コミット日時は2026年10月8日。最新の全機能や実機性能を確認したという意味ではありません。
- Cornell University, CS 4120（2023年春）— Iterative solving。固定点、単調性、有限高さと反復解析。講義の上から下へ進む順序と、本文の空集合から増やす例は順序の取り方が異なります。