$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$
ちょっと前の話ですが、Codeforces というプロコンサイトで Microsoft Q# Coding Contest というのをやっていたので、面白そうなので参加してみました。量子コンピューターのプログラムは、日ごろから書いてみたい書いてみたいと思いつつ、なかなか腰が重かったのですが、こうタスクが与えられて、競い合えといわれるとなんとなくモチベが出てきて、ようやく入門することができました。
この年になっても新しい概念のプログラムを書くという経験をするというのはなかなか楽しいもので、せっかくなのでその記録を残しておこうと思い、参加記を書いてみることにします。
量子計算やMicrosoftの量子コンピューター向けプログラミング言語Q#の説明を行うことはここではしませんが、https://docs.microsoft.com/en-us/quantum/?view=qsharp-preview に大変わかりやすい入門記事が用意されていますので、興味のある方はこちらを参照されることをお勧めします。
Warmup Contest
Q#を初めて書く人が多いという配慮からか（？）Warmupコンテストが行われました。
http://codeforces.com/contest/1001
Warmupというだけあって、非常に初歩的なタスクが用意されていて、初めてでもなんとか量子プログラミングを楽しむことができました。
A. Generate plus state or minus state
問題
$\ket{0}$ と、整数signが与えられるので、sign = 1 ならば、$\ket{+} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$ に、sign = -1 ならば、$\ket{-} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$ に変換せよ。
解答
Wikipediaの Quantum logic gate に、よく使いそうな量子ゲートの一覧が載っているので、ここから使えそうなゲートを探してきます。
一番最初に、Hadamardゲート(H) というのがあって、これが $\ket{0}$ を $\frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$ に、$\ket{1}$ を $\frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$ にそれぞれ変換するものなので、これを使えばよさそうです。
与えられる入力は $\ket{0}$ なので、sign = -1 の時は、あらかじめ $\ket{1}$ に変換しておく必要があります。これはまたまた先ほどのゲートカタログによりますと、2番目に載っているPauli-Xゲート(X)というのを使えばできそうです。
というわけで、これらを合わせると、
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve (q : Qubit, sign : Int) : ()
{
body
{
if (sign == -1) {
X(q);
}
H(q);
}
}
}
という答えが得られます。
B. Generate Bell state
問題
$\ket{00}$ と整数(0～3)が与えられるので、入力に対してそれぞれ次のような Bell state を作成せよ。
- $\ket{B_0} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$
- $\ket{B_1} = \frac{1}{\sqrt{2}}(\ket{00} - \ket{11})$
- $\ket{B_2} = \frac{1}{\sqrt{2}}(\ket{01} + \ket{10})$
- $\ket{B_3} = \frac{1}{\sqrt{2}}(\ket{01} - \ket{10})$
解答
Bell stateというのは、最大にもつれ合った2Qubitの量子もつれ4通りの状態らしく、量子もつれは言わずもがな量子計算のパワーの根源みたいなものですから、ようやく本質に少し近づける問題です。
まず適当に1Qubit目にHadamardゲートをかけてみると、$\ket{00}$ が $\frac{1}{\sqrt{2}}(\ket{00} + \ket{01})$ になります。これを$\frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$にするには、Controlled NOTゲートを使えば良さそうです。これで$\ket{B_0}$はできました。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(qs : Qubit[], index : Int) : ()
{
body
{
if (index == 0) {
H(qs[0]);
CNOT(qs[0], qs[1]);
}
// ......
}
}
}
$\ket{B_1}$は、符号が入れ替わったものなので、最初のHadamardゲートの前に、Pauli-Xゲートをかけておけばよさそうです。これで $\ket{00} \Rightarrow \ket{01} \Rightarrow \frac{1}{\sqrt{2}}(\ket{00} - \ket{01}) \Rightarrow \frac{1}{\sqrt{2}}(\ket{00} - \ket{11})$ といった具合に $\ket{B_1}$ が作れます。
if (index == 1) {
X(qs[0]);
H(qs[0]);
CNOT(qs[0], qs[1]);
}
$\ket{B_2}$は、よく見れば$\ket{B_0}$の左のQubitを反転したものだということがわかります。
$\frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) \Rightarrow \frac{1}{\sqrt{2}}(\ket{10} + \ket{01}) = \frac{1}{\sqrt{2}}(\ket{01} + \ket{10})$
また、CNOTゲートの第二引数は、先に変換しても後に変換しても同じだということがわかるので、結局このケースは、先にqs[1]にXゲートをかけて、同様にすればいいことがわかります。
if (index == 2) {
X(qs[1]);
H(qs[0]);
CNOT(qs[0], qs[1]);
}
残る $\ket{B_3}$ ですが、同様に考えると、qs[0]とqs[1]の両方にXゲートをかけてから同様にすればよいことがわかります（計算は省きます）。
if (index == 3) {
X(qs[0]);
X(qs[1]);
H(qs[0]);
CNOT(qs[0], qs[1]);
}
めでたく4通りすべてが作れたので、これらを組み合わせて答えの完成です。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(qs : Qubit[], index : Int) : ()
{
body
{
if (index == 0) {
H(qs[0]);
CNOT(qs[0], qs[1]);
}
if (index == 1) {
X(qs[0]);
H(qs[0]);
CNOT(qs[0], qs[1]);
}
if (index == 2) {
X(qs[1]);
H(qs[0]);
CNOT(qs[0], qs[1]);
}
if (index == 3) {
X(qs[0]);
X(qs[1]);
H(qs[0]);
CNOT(qs[0], qs[1]);
}
}
}
}
このコードをよく眺めると、綺麗にまとめられそうなことに気が付きます。これは、indexのビット0が立っている時に、X(qs[0])を、indexのビット1が立っている時にX(qs[1])を行った後、H(qs[0])とCNOT(qs[0], qs[1])を行うコードにほかなりません。よって、
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(qs : Qubit[], index : Int) : ()
{
body
{
if ((index &&& 1) != 0) {
X(qs[0]);
}
if ((index &&& 2) != 0) {
X(qs[1]);
}
H(qs[0]);
CNOT(qs[0], qs[1]);
}
}
}
このように書くことができます(&&& は bitwise and)。ディラックの記法では、
- $\ket{00} = \ket{0}$
- $\ket{01} = \ket{1}$
- $\ket{10} = \ket{2}$
- $\ket{11} = \ket{3}$
のように、Qubitのテンソル積を2進表記として略記できるのですが、これは結局のところ$\ket{B_{index}}とは、 \ket{index}$を作って、それに対してHとCNOTをかけたものであるということになります。なかなかすっきりした解答になりました。
C. Generate GHZ state
問題
0状態の N Qubit $\ket{0...0}$ (1<=N<=8) が与えられるので、ここから次の Greenberger–Horne–Zeilinger (GHZ) state を作成せよ。
$$\ket{GHZ} = \frac{1}{\sqrt{2}}(\ket{0...0} + \ket{1...1})$$
解答
0 Qubit目にHを掛けると $\frac{1}{\sqrt{2}}(\ket{0...00} + \ket{0...01})$ ができます。この末尾の1を上位まで伝搬させていけばいいんですが、ここでCNOTを使うと $\ket{01} \Rightarrow \ket{11}$ にすることができるので、CNOT(qs[0], qs[1]) を掛けると $\frac{1}{\sqrt{2}}(\ket{0...000} + \ket{0...011})$ になります。同様にCNOT(qs[0], qs[2])をさらに掛けると、$\frac{1}{\sqrt{2}}(\ket{0...0000} + \ket{0...0111})$ と、1をさらに伝搬させられます。これを繰り返していけば、目的のGHZ stateが得られます。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(qs : Qubit[]) : ()
{
body
{
H(qs[0]);
for (i in 1..Length(qs)-1) {
CNOT(qs[0], qs[i]);
}
}
}
}
D. Distinguish plus state and minus state
問題
$\ket{+} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})$ か $\ket{-} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$ のどちらかの状態のQubitが与えられるので、どちらの状態であるか判定せよ。
解答
問題Aの逆を行わせる問題です。
Qubitの状態を確かめるには測定（Q#ではMという関数）を行う必要がありますが、与えられたQubitをそのまま測定すると、これはどちらも0と1が等確率で得られます。Qubitが単なる確率変数ではないということが、このあたりからも窺われます。
では、どうすればいいのかというと、$\ket{+}$ と $\ket{-}$ はそれぞれ $\ket{0}$ と $\ket{1}$ をHadamardゲートに適用したものです。Hadamardゲートは対称行列で、かつユニタリ行列（量子論理ゲートはすべてユニタリ行列）なので、二回掛けると単位行列になり、元に戻ります。つまり、Hを掛けてから観測してやれば、どちらの状態であったか100%の確率で確かめることができます。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(q : Qubit) : Int
{
body
{
H(q);
if (M(q) == Zero) {
return 1;
} else {
return -1;
}
}
}
}
$H\ket{+}$ が本当に $\ket{0}$になるのかは、計算してもわかります。
$$
\begin{align}
H\ket{+} &= H(\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})) \\
&= \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})+\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})) \\
&= \frac{1}{\sqrt{2}}(\frac{2}{\sqrt{2}}\ket{0}) \\
&= \ket{0}
\end{align}
$$
$H\ket{-}$ も同様。
なお測定の際に実は何らかの変換を掛けられるようで、Pauli-Zゲートを用いるのがデフォルトのM関数で、この問題の場合、Pauli-Xゲートを用いると前処理なしでいけるみたいです。Pauli Measurementに詳しいことが書いてあります。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(q : Qubit) : Int
{
body
{
if (Measure([PauliX], [q]) == Zero) {
return 1;
} else {
return -1;
}
}
}
}
E. Distinguish Bell states
問題
Bell stateのいずれかが与えられるので、どれが与えられたかを判別せよ。
- $\ket{B_0} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$
- $\ket{B_1} = \frac{1}{\sqrt{2}}(\ket{00} - \ket{11})$
- $\ket{B_2} = \frac{1}{\sqrt{2}}(\ket{01} + \ket{10})$
- $\ket{B_3} = \frac{1}{\sqrt{2}}(\ket{01} - \ket{10})$
解答
先ほどと同じように、今度はB問題の逆の変換を施してゆけばよさそうです。
Hを掛けてからCNOTを掛けたので、今度は逆にCNOTを掛けてからHを掛けると、
$$
\frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) \Rightarrow \frac{1}{\sqrt{2}}(\ket{00} + \ket{01}) \Rightarrow \ket{00}
$$
$$
\frac{1}{\sqrt{2}}(\ket{00} - \ket{11}) \Rightarrow \frac{1}{\sqrt{2}}(\ket{00} - \ket{01}) \Rightarrow \ket{01}
$$
$$
\frac{1}{\sqrt{2}}(\ket{01} + \ket{10}) \Rightarrow \frac{1}{\sqrt{2}}(\ket{11} + \ket{10}) \Rightarrow \ket{10}
$$
$$
\frac{1}{\sqrt{2}}(\ket{01} - \ket{10}) \Rightarrow \frac{1}{\sqrt{2}}(\ket{11} - \ket{10}) \Rightarrow \ket{11}
$$
この状態になってしまえば、測定すればどの状態だったかが分かります。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(qs : Qubit[]) : Int
{
body
{
CNOT(qs[0], qs[1]);
H(qs[0]);
let m0 = M(qs[0]);
let m1 = M(qs[1]);
if (m0 == Zero && m1 == Zero) {
return 0;
}
if (m0 == One && m1 == Zero) {
return 1;
}
if (m0 == Zero && m1 == One) {
return 2;
}
if (m0 == One && m1 == One) {
return 3;
}
return -1; // Unreachable
}
}
}
ところで、B問題の知見がない状態だとこれはどう考えれば解けるんでしょうか。まず、2qubitで2状態の重ね合わせしかないので、まずはもつれをほどけないか試してみるのでしょうか。CNOT(qs[0], qs[1])をすれば、全ケースで両Qubitのもつれがなくなることに気づけば、あとは簡単かと思いますが、このぐらい単純なケースならともかく、もっと複雑な場合に都合よくいいやり方を見つけるのは難しそうです。逆に考えて、どうせユニタリ変換で可逆なものしか存在しないのだから、識別タスクでも生成する方法を考えたりするとうまくいくのだろうか。この辺はまだ経験が浅く、よくわからないところです。
F. Distinguish multi-qubit basis states
問題
2つの基底状態のうちのどちらかの1つの状態にあるN Qubit、および2つの基底状態を表す2つのboolの配列が与えられる。与えられたQubitがどちらの状態なのかを判別せよ。
2つの基底状態は少なくとも一箇所のビットが異なっていることが保障される。
解答
入力は重ね合わせ状態にはないので、計測すればどちらの状態かが分かります。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve(qs : Qubit[], bits0 : Bool[], bits1 : Bool[]) : Int
{
body
{
for (i in 0..Length(qs)-1) {
let m = M(qs[i]);
if (ToBool(m) != bits0[i]) {
return 1;
}
}
return 0;
}
}
}
6問目なのに簡単すぎて逆に不安になりますね。
G. Oracle for f(x) = k-th element of x
問題
$f(x)=x_k$ となる N Qubit に対する Quantum Oracle $f(x): \{0, 1\}^n \rightarrow \{0, 1\} $を実装せよ。
解答
最初 Quantum Oracleについて、ただの関数だと思っていたので、かなり誤答を重ねてしまった。Quantum Oracleに付いては ここ に解説があるので、仕様が分かれば非常に簡単な問題。
Quantum oracle $O$ とは、入力 $\ket{x}$ と出力 $\ket{y}$ に対して $O(\ket{x} \otimes \ket{y}) = \ket{x} \otimes \ket{y \oplus f(x)}$ となるものです（$\otimes$ はテンソル積、$\oplus$ は排他的論理和）。単に $O\ket{x} = \ket{f(x)}$ としたのでは、随伴操作が作れなくてユニタリー変換にならないので、量子論理ゲートで表現できません。出力のベクトルを入力に追加して、Q
ubitとのxorを取ることにして、逆関数を作れるようにするようです。
なので、この問題は、x[k]をyとCNOTするだけです。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
{
body
{
CNOT(x[k], y);
}
}
}
H. Oracle for f(x) = parity of the number of 1s in x
問題
N Qubitに対して、$f(x) = \sum_i x_i mod 2$ を計算する Quantum Oracleを実装せよ。
解答
CNOTでxorができるので、全Qubitに対して、出力にCNOTすれば良いです。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve (x : Qubit[], y : Qubit) : ()
{
body
{
for (i in 0..Length(x)-1) {
CNOT(x[i], y);
}
}
}
}
I. Deutsch-Jozsa algorithm
問題
$N+1$ Qubitに対する Quantum Oracle $f$ が与えられる。$f$ は、constant(全ての入力に対して、0または1を返す)か、balanced(入力ドメインのちょうど半分に対して0を返し、残りの半分に対して1を返す)のどちらかである。どちらであるかを判別せよ。ただし、$f$ を呼び出せるのは1回だけである。
解答
ここまで来てようやくそれっぽい問題が出てきました。解き方は、問題のタイトルにあるとおり、Deutsch-Jozsa algorithm を実装すれば良いです。
Deutsch-Jozsa algorithm というのは、量子コンピューターが、どのような決定的古典アルゴリズムよりも、指数的に高速であると言うことを示した最初のアルゴリズムの一つだそうで、たしかにこの問題は、最低でも入力ドメインの過半数（つまり$2^{n-1}+1$）回の呼び出しをしなければ、古典的で決定的なアルゴリズムにはならなさそうです。とても恣意的で巧妙な問題設定ですが、計算量理論的にはとても大きな意味のあるアルゴリズムだと思います。
というわけで、この問題を解いてウォームアップは終了です。アルゴリズムについての説明は、ここで行うのは大変なので、詳しくはこちらの Wikipediaのエントリをご参照ください。
アルゴリズム自体はとても簡単で、$\ket{0}$をn個、$\ket{1}$を1個用意して、全てにHadamardゲートを掛けて、それから$f$を呼び、元々$\ket{0}$だったN qubitに再度Hadamardゲートを掛けると、constantの場合は100%の確率で$\ket{0..0}$になり、balancedの場合は100%の確率でそれ以外の値になると言うものです。図で見た方が分かりやすいかもしれません。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool
{
body
{
mutable zeros = 0;
using (qs = Qubit[N]) {
using (output = Qubit[1]) {
for (i in 0..N-1) {
H(qs[i]);
}
X(output[0]);
H(output[0]);
Uf(qs, output[0]);
for (i in 0..N-1) {
H(qs[i]);
if (M(qs[i]) == Zero) {
set zeros = zeros + 1;
}
}
// Qubit解放時には |0> にしておかないと怒られる
Reset(output[0]);
for (i in 0..N-1) {
Reset(qs[i]);
}
}}
return zeros == N;
}
}
}
なぜこれで正しい答えになるのかはの解説はちょっと面倒なのでまたの機会に。
だいぶ長くなってしまったので本編は次回。