https://codeforces.com/contest/1002/problem/A4
$2^k$桁の量子状態$\ket{0...0}$が与えられる。W状態 $$\ket{W_N}=\frac{1}{\sqrt{N}}\left(\ket{100...0}+\ket{010...0}+...+\ket{00...01} \right)$$ を作れ。
$2^n$桁のW状態から$2^{n+1}$桁のW状態を作る手順があれば、$2^0$桁のW状態$\ket{100...0}$を始状態として再帰的に$2^k$桁のW状態を構成することができるので、以下ではそのような手順を考えます。
問題によって$2^k$桁のqubitが与えられているので、以下、「$2^n$桁のW状態」とは、$2^k$桁のqubitのうち、最初の$2^n$桁がW状態を構成しているような状態を指します。例えば、$k=3,\;n=2$であれば $$\ket{W_{2^2}}=\frac{1}{\sqrt{2^2}}\left( \ket{1000}+\ket{0100}+\ket{0010}+\ket{0001} \right)\otimes\ket{0000}$$ です。
$2^n$桁のW状態が与えられたとき、$2^{n+1}$桁のW状態を構成することは、Fredkinゲート（Controlled Swapゲート）を使えば実現できます。Frendkinゲートは1つの制御bitと2つのターゲットbitをもつゲートで、制御bitが1であるとき2つのターゲットbitを入れ替えます。
以下、例として$k=3$において$2^1$桁のW状態から$2^{2}$桁のW状態を構成することを考えます。$2^1$桁のW状態 $$\ket{W_{2^1}}=\frac{1}{\sqrt{2^1}}\left( \ket{10}+\ket{01} \right)\otimes\ket{000000}$$ に対して、新しいqubit$\ket{+}$を用意し、末尾にくっつけます。 \begin{align*} \ket{W_{2^1}}\otimes\ket{+}&=\frac{1}{\sqrt{2^1}}\left( \ket{10}+\ket{01} \right)\otimes\ket{000000}\otimes\ket{+}\\ &=\frac{1}{\sqrt{2^2}}\left( \ket{10000000}\otimes\ket{0}+\ket{01000000}\otimes\ket{0}+\ket{10000000}\otimes\ket{1}+\ket{01000000}\otimes\ket{1} \right) \end{align*} 次に、くっつけた桁（$2^k$桁め）を制御bitとして、$0$桁めから$2^n-1$桁めまでのqubitを$2^n$桁めから$2^{n+1}-1$桁めまでとそれぞれペアにしてFredkinゲートを作用させます。すると、$2^k$めが$\ket{1}$である状態のみ、W状態が$2^n$桁だけ後ろにずれたような状態になります。 $$F^{\otimes 2^n}\ket{W_{2^1}}\otimes\ket{+}=\frac{1}{\sqrt{2^2}}\left( \ket{10000000}\otimes\ket{0}+\ket{01000000}\otimes\ket{0}+\ket{00100000}\otimes\ket{1}+\ket{00010000}\otimes\ket{1} \right)$$ ここで、自分でくっつけた桁以外の部分はすでに$2^{n+1}$桁のW状態になっていますが、末尾がその他のqubitとエンタングルしているため、そのまま取り出して捨ててしまうことはできません。エンタングル状態を解除するために、C-NOTゲートを利用します。末尾が$\ket{1}$である状態は$2^n$桁め以降に$\ket{1}$を1つだけもつので、$2^n$桁め以降を制御bitとしてC-NOTゲートを作用させてあげればよいです。 \begin{align*} G^{\otimes 2^n}F^{\otimes 2^n}\ket{W_{2^1}}\otimes\ket{+} &=\frac{1}{\sqrt{2^2}}\left( \ket{10000000}\otimes\ket{0}+\ket{01000000}\otimes\ket{0}+\ket{00100000}\otimes\ket{0}+\ket{00010000}\otimes\ket{0} \right)\\ &=\frac{1}{\sqrt{2^2}}\left( \ket{1000}+\ket{0100}+\ket{0010}+\ket{0001}\right)\otimes\ket{0000}\otimes\ket{0}\\ &=\ket{W_{2^2}}\otimes\ket{0} \end{align*}
以上の手順で、$2^n$桁のW状態から$2^{n+1}$桁のW状態を作ることができて、$2^0$桁のW状態は簡単に作ることができる$(\ket{W_{2^0}}=\ket{100...0})$ので、これを繰り返せば求める状態を作り出すことができます。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : ()
{
body
{
let N=Length(qs);
//qsが2^0桁のとき、|10...0>をつくる
if(N==1){
X(qs[0]);
}
else{
let K=N/2;
//N/2桁のW状態を得る
Solve(qs[0..K-1]);
using(q=Qubit[1]){
H(q[0]);
//Fredkinゲートを作用させる
for(i in 0..K-1){
(Controlled SWAP)([q[0]],(qs[i],qs[i+K]));
}
//C-NOTゲートでエンタングルを解く
for(i in K..N-1){
CNOT(qs[i],q[0]);
}
ResetAll(q);
}
}
}
}
}