https://codeforces.com/contest/1001/problem/G
$N$桁の量子状態$\ket{x}$とqubit$y$、整数$k$が与えられる。$\ket{x}$の$k$桁めのqubitの値を$x_k$とするとき、$\ket{y}$をオラクルqubitとして$f(x)=x_k$で定義されるオラクルを作成せよ。
オラクルについては、問題文に解説記事へのリンクがついています。
オラクルの動作は$n$bitの入力と$m$bitの出力をもつ関数$f:\{0,1\}^n\rightarrow\{0,1\}^m$を用いて、$n$桁の入力qubit$\ket{x}$と$m$桁のオラクルqubit$\ket{y}$に対して $$O\left( \ket{x}\otimes\ket{y} \right)=\ket{x}\otimes\ket{y\oplus f(x)}$$ と定義されます（$\oplus$は排他的論理和）。
この問題においては、$n=N, m=1$であり、$f(x)=x_k$であるので、この問題は「$\ket{y}$に$\ket{x}_k$をxor代入せよ」という問題に読み替えることができて、これはC-NOTゲートを使って実現できます。
なお、オラクルに入力される$\ket{x}$の各bitが必ず$\ket{0}, \ket{1}$のどちらかであるという保証はないので、$\ket{x}_k$に対してPauli Zを対角とする測定をして、測定値-1が出たらNOTゲートで$\ket{y}$を反転するといった実装方法では正解できません。つまり、たとえば入力として \begin{align*} \ket{x}\otimes\ket{y}&=\ket{++}\otimes\ket{0}\\ &=\ket{00}\otimes\ket{0}+\ket{01}\otimes\ket{0}+\ket{10}\otimes\ket{0}+\ket{11}\otimes\ket{0} \end{align*} が与えられ、$k=0$が指定された場合、オラクルを作用させたあとには \begin{align*} O\left(\ket{x}\otimes\ket{y}\right)&=\ket{00}\otimes\ket{0\oplus0}+\ket{01}\otimes\ket{0\oplus0}+\ket{10}\otimes\ket{0\oplus1}+\ket{11}\otimes\ket{0\oplus1}\\ &=\ket{00}\otimes\ket{0}+\ket{01}\otimes\ket{0}+\ket{10}\otimes\ket{1}+\ket{11}\otimes\ket{1} \end{align*} が残っていてほしいということです。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
{
body
{
CNOT(x[k],y); //|y>→|y xor x_k>
}
}
}