不完全な知識グラフ上の複雑な論理クエリへの応答は困難な課題であり、広く研究されてきました。埋め込みベースの手法は複雑なクエリの学習を必要とし、分布外のクエリ構造には十分に一般化できません。最近の研究では、この課題をエンドツーエンドの最適化問題として捉え、事前学習されたリンク予測器のみを必要とする方法が提案されています。しかし、指数関数的に大きな組み合わせ探索空間のため、最適解は近似されるしかなく、最終的な精度が制限されます。本研究では、QTO（Query Computation Tree Optimization）を提案します。QTOは木構造の計算グラフであるクエリ計算木上で前進・後退伝播を行うことで効率的に正確な最適解を見つけることができます。特に、QTOはクエリ計算木に符号化された独立性を利用することで探索空間を縮小し、最適化プロセス中には局所的な計算のみが行われます。3つのデータセットでの実験結果から、QTOは複雑なクエリ応答において最先端の性能を達成しており、従来の最高結果よりも平均で22%改善しています。さらに、QTOはクエリ内の各1ホップ原子に対する中間解を90%以上の精度で解釈することができます。当該論文のコードは https://github.com/bys0318/QTO で公開されています。