名大 情報学研究科 数理情報学 2024年度 院試 解答例・解説

クロネッカー積を見る目

この問題の狙いは、成分計算だけでなく「大きな行列を小さな行列のクロネッカー積として 見る」ことである。$4$ 次行列をそのまま固有方程式で解くと計算量が増えるが、$2$ 次 行列二つの積に分解すれば、固有値は積、固有ベクトルはクロネッカー積で得られる。

答案で落としやすい点

$(A\otimes B)(v\otimes w)=Av\otimes Bw$ を使うときは、最後に $v\otimes w\ne 0$ も確認しておくと固有ベクトルであることが明確になる。また、全ての 固有ベクトルを求める場面では、4本が一次独立であることを添えれば「これで全て」と 言える。

方針

被積分関数 $\arctan(y/x)$ は、原点から見た偏角だけに依存する。三角形状の領域では $y=tx$、円を含む領域では極座標を使うと、積分がほぼ一変数に分離される。

検算

$S_3$ の値は $$\frac{\pi^2}{4}-\pi+2\log2\fallingdotseq 0.71>0$$ であり、面積積分として符号が正になる。最後に正値性を確認しておくと、積分範囲や $\sec^2\theta$ の係数の符号ミスに気づきやすい。

核となる見方

この問題は、$\theta$ を $0$ に潰したときに何が残るかを問うている。多項式表示で考えると、 $T=0$ と $f(T)=0$ を同時に課すので、残る条件は $f(0)=n$ だけである。したがって $\mathbb{Z}[\theta]/(\theta)$ は $\mathbb{Z}/n\mathbb{Z}$ になる。

答案上の注意

「表示を変えても $a$ の剰余が変わらない」ことを直接成分計算で示そうとすると煩雑に なりやすい。商環を一度書けば、well-defined 性と後半の $(p,\theta)$ による商が同じ 計算で処理できる。

順序付き集合として見る

射の条件は「出発側の値が到着側の値以下」という不等式である。そのため、積では二つの 射影へ同時に射になるように $\min$ を取り、余積では各成分の値をそのまま貼り合わせる。 この $\min/\max$ の使い分けが、後半の束構造にもそのまま現れる。

部分対象の注意点

この圏のモノ射は台集合上の単射であり、値 $E_A(a)$ が $E_Z(m(a))$ と等しい必要はない。 等号を仮定してしまうと部分対象を狭く見積もってしまい、$\operatorname{Sub}(Z)$ の順序を 正しく記述できない。

重ね合わせと混合の違い

二体系の $|\Phi\rangle$ は、二つの基底状態の重ね合わせであり、$X\otimes X$ によって 二つの項が入れ替わっても全体として同じ状態に戻る。そのため期待値は $1$ になる。 一方、確率混合では各基底状態ごとの期待値を平均するだけで、項どうしの干渉は現れない。 この違いが (5) と (6) の値の差である。

計算の短縮

$X^2=I$ を先に確認すれば、指数行列は三角関数の形に直ちに整理できる。パウリ行列型の 問題では、この性質を使うと級数を直接展開し続けずに済む。

貪欲法の限界

密度順貪欲法は分数ナップサックでは最適だが、0-1 ナップサックでは一度選んだ小さな 高密度要素が、大きな高利得要素を締め出すことがある。主張 B の反例はこの現象を極端に したもので、近似比が任意に悪くなり得ることを示している。

上界の意味

主張 C の式は、密度順に詰めて最後の要素だけを分割してよいとした場合の値である。 0-1 問題の実行可能解は分割を許した緩和問題の実行可能解でもあるため、緩和問題の最適値 は元の問題の上界になる。