https://codeforces.com/contest/1002/problem/E2
$N+1$桁のqubit（$N$桁の入力qubitと1桁のオラクルqubit）に作用するオラクルが与えられる。オラクルは 、あるbit列$\vec{b}\in\{0,1\}^N$を用いて $$f(x)=\left(\vec{b}\cdot\vec{x}+\left( \vec{1}-\vec{b}\right)\cdot\left( \vec{1}-\vec{x} \right) \right)\; {\rm mod}\;2=\sum^{N-1}_{k=0}\left(b_kx_k+\left( 1-b_k \right)\cdot\left( 1-x_k \right)\right)\; {\rm mod}\;2$$ で定義されている（D2と同様）。このオラクルを1度だけ呼び出して、bit列$\vec{b}$を再構築せよ。
ただし、この問題においては、正誤の判定は出力された$\vec{b}$と真の$\vec{b}$を比較することによってではなく、それぞれを使って作られたオラクル$U_f$どうしを比較することによって行われる。
上述のように定義されたオラクルが与えられるので、全く同じ作用をもったオラクルを構成できる$\vec{b}$を1つ構築せよという問題です。同じオラクルが作れればよいので、与えられたオラクルを作成するのに使われた$\vec{b}$を特定する必要はありません。
はじめに、このオラクルがどのような作用をするかを考えます。$f(x)=\left(\vec{b}\cdot\vec{x}+\left( \vec{1}-\vec{b}\right)\cdot\left( \vec{1}-\vec{x} \right) \right)$とは、各桁について$b_k$と$x_k$が一致していればオラクルqubitを反転させるという操作を表しています。
ここで、いくつかの異なる$\vec{b}$が同じオラクルを生成する場合は存在するでしょうか？これは存在して、今回の定義においては、1であるbitの偶奇が同じであるような$\vec{b}$はすべて同じオラクルを生成します。以下に示します。
このオラクルが各桁における$b_k$と$x_k$が一致している場合にオラクルqubitを反転させていることは先に述べましたが、qubitを2回反転させるともとに戻ることから、$b_k$と$x_k$の一致数の偶奇が同じであれば同じ結果を返すことがわかります。さらに、$\ket{x}$がどのような状態であっても、$\vec{b}$から任意の2つのbitを変更（swapを含む）した状態の一致数の偶奇は元の状態と同じになる（変更された桁が一致していた場合は一致しなくなり、一致していなかった場合は一致するようになる）ので、このオラクルの出力は$\vec{b}$のなかで1であるようなbitの数の偶奇のみによっていることがわかります。
オラクルから$\vec{b}$の1であるようなbitの数の偶奇を知ることは簡単で、状態$\ket{1}^{\otimes N}\otimes\ket{0}$を入れてやるだけでよいです。
偶奇がわかったら、$N$桁すべて0のbit列か最初だけ1のbit列を出力して終了です。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Int[]
{
body
{
mutable b=new Int[N];
using(qs=Qubit[N+1]){
let x=qs[0..N-1];
let y=qs[N];
ApplyToEach(X,x);
Uf(x,y);
if(M(y)==One){
set b[0]=1;
}
ResetAll(qs);
}
return b;
}
}
}