Microsoft Q# Coding Contest - Summer 2018
MSのQ#を使った量子コンピューティングのプログラミングコンテスト（本選）。
Microsoft Q# Coding Contest - Summer 2018
週末の3日間で15問を解く。
→練習ラウンド
12完で151位。
量子コンピューティングの授業の演習問題、みたいな教育的な感じだなと思った。
ところどころトリッキーではあるけれど難しすぎるというほどでもない。（Q#歴0日から始めた割に善戦したが全完したかった）
公式Editorialはこちら。
A1 - Generate superposition of all basis states (x359)
0000.. から ..1111 までの全ての状態の重ね合わせを作る問題。
全qubitにH (hadamard gate) をかけるだけ。イディオム的な操作。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : ()
{
body
{
let n = Length(qs);
for (i in 0 .. n-1) {
H(qs[i]);
}
}
}
}（Q#だともっと簡潔に書けるはず）
→AC
http://codeforces.com/contest/1002/submission/40034693
A2 - Generate superposition of zero state and a basis state (x332)
00000..と、引数のビット列で指定された通りに立てた状態で重ね合わせたものを作る問題。
最初のqubitをHして 00000..+10000.. を作り、あとはbits[i]が1のところを順にCNOTして回る。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[], bits : Bool[]) : ()
{
body
{
H(qs[0]);
let n = Length(qs);
mutable last = 0;
for (i in 1 .. n-1) {
if (bits[i]) {
CNOT(qs[last], qs[i]);
set last = i;
}
}
}
}
}（別にqs[last]とかじゃなくてもqs[0]で良かったんだけど）
→AC
http://codeforces.com/contest/1002/submission/40035048
A3 - Generate superposition of two basis states (x273)
引数の2つのビット列で指定された通りに立てた2つの状態の重ね合わせを作る問題。
ψ0,ψ1どちらも1のところはXで反転して1にして、片方だけ1になってる最初のところをHで0+1にして、あとはCNOTで返していく。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[], bits0 : Bool[], bits1 : Bool[]) : ()
{
body
{
let n = Length(qs);
mutable s = new Int[n];
mutable one = -1;
for (i in 0 .. n-1) {
set s[i] = 0;
if (bits0[i]) {
set s[i] = s[i] + 2;
}
if (bits1[i]) {
set s[i] = s[i] + 1;
}
if (s[i] == 1) {
set one = i;
}
}
if (one == -1) {
for (i in 0 .. n-1) {
if (s[i] == 1) {
set s[i] = 2;
} elif (s[i] == 2) {
set s[i] = 1;
if (one == -1) {
set one = i;
}
}
}
}
//
for (i in 0 .. n-1) {
if (s[i] >= 2) {
X(qs[i]);
}
}
H(qs[one]);
for (i in 0 .. n-1) {
if (s[i] == 1) {
if (i != one) {
CNOT(qs[one], qs[i]);
}
} elif (s[i] == 2) {
CNOT(qs[one], qs[i]);
}
}
}
}
}
A4 - Generate W state (x133)
2^kビットの generalized W state (10000..+01000..+...+..00010+..00001) を作る問題。（普通 W state といったら3-qubitのものを指すらしい）
（作れなかった）
解説読んだ（けどまだ理解できていない）
- 再帰的に前半分を作る
- 後ろ半分：例えば 10+01 から（というか(10+01)00から）1000+0100+0010+0001 を作るには？
- 演算補助（フラグ）用に1つqubitを用意しa=0+1にする（これはフラグとしては"0"なのかな）
- i=0..H-1 について (Controlled SWAP)([a], (qs[i], qs[i+H]))
- Controlled SWAP (C-SWAP, Fredikin gate) というものを知らなかった。
- これって何が起こる？aの値によって qs[i]とqs[i+H]のSWAPが発生したりしなかったり？aが0+1のときはどうなる？
- フラグが"0"のとき何もせず、"1"のとき前半を後半へ、後半を前半へ
- どゆこと？
- i=H..N-1について CNOT(qs[i], a)。これは+-だとaが-のときqs[i]のほうが反転する。
- "Hamming weight"が1になるようにqs[] の後半のqubitをフラグaにXORしていく
- なぜCNOT(a, qs[i]) ではないのか
B1 - Distinguish zero state and W state (x295)
00000... と W state (10000..+01000..+...+..00010+..00001) を識別する問題。
2ビット目から最後までのビットを制御ビットとして先頭ビットに対してCNOTをかけていくことで、W stateなら必ず先頭ビットが1になって終わるはず。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Int
{
body
{
let n = Length(qs);
for (i in 1 .. n-1) {
CNOT(qs[i], qs[0]);
}
let v = M(qs[0]);
if (v == One) {
return 1;
} else {
return 0;
}
}
}
}
B2 - Distinguish GHZ state and W state (x275)
GHZ state (0…0 + 1…1) と W state (10000.. + 01000.. + .. + ..00010 + ..00001) を識別する問題。
00000..とW stateの識別の時みたいに、2ビット目から最後までを制御ビットとしてCNOTで先頭を改変していく。W stateはこれで先頭を1に出来る。
ビット数が偶数の場合：flipが奇数回起こるから、GHZ stateでは最初が0になって識別可能。
ビット数が奇数の場合：どちらも先頭が1になっている。(W:100000100のようにどこかが1つだけ立っているか、100000000; GHZ:11111111) 先頭ビット(1)を制御ビットとして他のビットをCNOTでフリップしていくと、Wでは2ビット目以降が「ほぼ」全て1に、GHZでは2ビット目以降が全て0になる。ここまで出来ればあとは計測するだけ。（「ほぼ」なので失敗する可能性もある確率的な方法。）
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Int
{
body
{
let n = Length(qs);
for (i in 1 .. n-1) {
CNOT(qs[i], qs[0]);
}
if (n % 2 == 0) {
// 1 if W -> 1
// 0 if GHZ -> 0
let v = M(qs[0]);
if (v == One) {
return 1;
} else {
return 0;
}
} else {
// 1 if W (100 + 010 + 001) -> 1
// 0+1 if GHZ (000 + 111) -> 0
for (i in 1 .. n-1) {
CNOT(qs[0], qs[i]);
let v = M(qs[i]);
if (v == One) {
return 1; // probabilistic
}
}
// GHZ
return 0;
}
}
}
}
B3 - Distinguish four 2-qubit states (x263)
2 qubitから成る状態4種類のどれかが与えられるのでどれかを答える問題。
各ビットをHしてMした結果で場合分け。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Int
{
body
{
H(qs[0]);
H(qs[1]);
let s0 = M(qs[0]);
let s1 = M(qs[1]);
if (s0 == Zero) {
if (s1 == Zero) {
return 0;
} else {
return 1;
}
} else {
if (s1 == Zero) {
return 2;
} else {
return 3;
}
}
}
}
}
B4 - Distinguish four 2-qubit states - 2 (x190)
2 qubitから成る状態4種類のどれかが与えられるのでどれかを答える問題（その２）。
今回はH2回＋M2回に加え、CNOTを1回使う必要がある。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Int
{
body
{
H(qs[1]);
CNOT(qs[0], qs[1]);
H(qs[0]);
let s0 = M(qs[0]);
let s1 = M(qs[1]);
if (s0 == One) {
if (s1 == One) {
return 0;
} else {
return 2;
}
} else {
if (s1 == One) {
return 1;
} else {
return 3;
}
}
}
}
}
C1 - Distinguish zero state and plus state with minimum error (x166)
と
と識別する問題。
厳密に識別するのは物理的に（量子力学的に）不可能なので1000回のうち80％以上合ってれば良い。
数回回せば確率的に解けるんじゃないかなと思ってたけど0.75前後から全く変わらない...
// WA解
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (q : Qubit) : Int
{
body
{
mutable result = 0;
using (y = Qubit[1]) {
for (i in 0 .. 3) {
Reset(y[0]);
CNOT(q, y[0]);
let st = M(y[0]);
if (st == One) {
set result = 1;
}
}
ResetAll(y);
}
return result;
}
}
}→WA(2)
http://codeforces.com/contest/1002/submission/40080987
http://codeforces.com/contest/1002/submission/40081006
あ、回転させればいい感じに差がつくんじゃないかな
（22.5度回転してみた。45度回転でも良かった）
// AC解
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (q : Qubit) : Int
{
body
{
mutable result = 0;
Ry(22.5/180.0*3.14159265358979323846, q);
let st = M(q);
if (st == One) {
return 1;
} else {
return 0;
}
return result;
}
}
}
C2 - Distinguish zero state and plus state without errors (x145)
C1と同様だが今回は間違いが許されず、分からない時には-1と答えろという問題。
（全体の8割まで-1と答えて良い）
POVMによる計測で同じことをする話はネットで読んだ。
2qubit用意して、何らかの操作を行って、その2qubitが00か11になった時は答えがはっきり分かって、01か10の時は分からないので-1、みたいな感じ
でもその回路が書けずに終了...
解説読んだ
そんな回路を書く必要はなく、で計測するか
で計測するかを2回に1回（ランダムに）選べばいいだけ…目から鱗、というか個人的トンチ問題大賞はこの問題に差し上げたい
D1 - Oracle for f(x) = b * x mod 2 (x260)
f(x)=b・x mod 2のOracleを実装する問題。
Oracle分かってなくて古典的に解こうとしてた…
→WA
http://codeforces.com/contest/1002/submission/40038721
WarmupのOracle問題のところに解説へのリンクがあったのでそちらを通してから再訪。
要するにbが立ってる箇所だけCNOT
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (x : Qubit[], y : Qubit, b : Int[]) : ()
{
body
{
let n = Length(x);
for (i in 0 .. n-1) {
if (b[i] == 1) {
CNOT(x[i], y);
}
}
}
}
}
D2 - Oracle for f(x) = b * x + (1 - b) * (1 - x) mod 2 (x243)
f(x)=b・x + (1-b)・(1-x) mod 2のOracleを実装する問題。
bが0の所はxをひっくり返してCNOT（してxはまた戻しておく）
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (x : Qubit[], y : Qubit, b : Int[]) : ()
{
body
{
let n = Length(x);
for (i in 0 .. n-1) {
if (b[i] == 1) {
CNOT(x[i], y);
} else {
X(x[i]);
CNOT(x[i], y);
X(x[i]);
}
}
}
}
}
D3 - Oracle for majority function (x209)
与えられた3 qubitの多数決をするOracleを実装する問題。
3ビットの加算回路を作らないといけないんだけどAND演算をするのに必要なCCNOTを知らなくて困った。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (x : Qubit[], y : Qubit) : ()
{
body
{
CNOT(x[0], x[1]); // b ^= a
CNOT(x[0], x[2]); // c ^= a
CCNOT(x[1], x[2], x[0]); // if (b & c) a = ~a
CNOT(x[0], y);
CCNOT(x[1], x[2], x[0]);
CNOT(x[0], x[2]);
CNOT(x[0], x[1]);
}
}
}
E1 - Bernstein-Vazirani algorithm (x213)
f(x)=b・x mod 2のOracleが与えられるので、b[]を一発で知りたい。
Bernstein-Vaziraniアルゴリズムを実装するだけの問題。
それ聞いたことある…（Courseraで受けた量子コンピューティングの講師がVazirani先生だった）
古典的には2^n回とか（確率的にはもっと少ない回数で）呼び出せば分かるのだけれど量子計算ではこれを1発で調べられるという有難い話。
x全ビットに0+1を、yに0-1をセットしてOracleを1回呼び出す。
CNOTがターゲットにが来ると制御側の
が反転する仕様を利用して、bが立っている箇所のxが
になっているのをHしてMして検出する。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Int[]
{
body
{
mutable b = new Int[N];
for (i in 0 .. N-1) {
set b[i] = 0;
}
using (x = Qubit[N]) {
using (y = Qubit[1]) {
ResetAll(x);
ResetAll(y);
X(y[0]);
for (i in 0 .. N-1) {
H(x[i]);
}
H(y[0]);
Uf(x, y[0]);
for (i in 0 .. N-1) {
H(x[i]);
}
for (i in 0 .. N-1) {
let st = M(x[i]);
if (st == One) {
set b[i] = 1;
} else {
set b[i] = 0;
}
}
ResetAll(x);
ResetAll(y);
}
}
return b;
}
}
}
E2 - Another array reconstruction algorithm (x110)
E1の類題だけど、今回はf(x)=b・x + (1-b)・(1-x) mod 2のb[]を一発で調べたい、という問題。
E1の要領でやるとbは11111...になる。
と
になるのかな。計測では見分けられない。
（計測に他のパウリ基底を使えば行けるのかとか思ったけど行けなかった）
これどうすればいい？って辺りで終了。
解説読んだ
なるほど、bを厳密に合わせに行かなくてもよくて、Ufの中のbと、「立っているビットの数」の偶奇さえ一致していれば良い、と。
問題文の
Note that in this problem we're comparing the oracle generated by your return to the oracle Uf, instead of comparing your return to the (hidden) value of used to generate Uf.
ってそういう意味だったのね。
https://t.co/GR0PczHUee Q# Coding Contest終わってた。結局最後の問題が一番正解者数少なかったのか。これなんかもう量子コンピューティング関係なくて完全にトンチだった気がするんだが…。時間かけて解けなかった人が答え見ると怒り出しそう（一つ前に置いてある問題が盛大な罠だった）
— 2018年こそ夏バテにならない (@tomerun) July 9, 2018
トンチといえばトンチかな。E1のBernstein-Vazirani algorithmの後に置かれてるのは罠。
総評
Macに急遽Q#開発環境（Visual Studio CodeとMicrosoft Quantum Development Kit for Visual Studio Code）をインストールして臨んだ本選。
量子計算の知識は以前CourseraでVazirani教授の講義を受講したのと、池袋でやっていた量子情報勉強会に何度か参加したのが全てで、（Q#を含め）プログラムを書くのは今回が初めてでした。
全完はできなかったものの、問題を解く過程で色々思い出したり調べたりでいい勉強になりました。
Visual Studio Code（ってほとんどatomだった）でQ#（とC#）を触ってみて割と楽しかったことで、Microsoftチョットキライだった*1のが少し上書きされました。
*1:MSが嫌いになるような出来事が先週あったばかりだった
