MSのQ#を使った量子コンピューティングのプログラミングコンテスト（の練習ラウンド）。
Microsoft Q# Coding Contest - Summer 2018 - Warmup
→本選
Mac*1に環境入れるのとか面倒で、Warmupラウンドをやってたのは知ってたけどスルーしてた。
本戦開始まで2時間切ったあたりで急にやる気になったので、Visual Studio CodeとQ#環境をセットアップして、過去問のWarmupに本戦前にいくつか投げてみた（とりあえず6AC+1WA）。
Warmupというだけに、チュートリアルっぽい問題が並ぶ。
Q#触るのは今回が初めてだけど
- H（アダマール）ゲートは
H() - CNOTゲートは
CNOT() - Xゲートは
X() - 計測は
M()
とか、そのまんまなので書きやすい。
【追記】本戦の途中ですがwarmup全完（7/8 13:14）
A - Generate plus state or minus state
と
を作る。H()するだけ。
namespace Solution
{
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Primitive;
operation Solve (q : Qubit, sign : Int) : ()
{
body
{
if (sign == 1) {
H(q);
} else {
X(q);
H(q);
}
}
}
}
B - Generate Bell state
が与えられて、4種類のBell stateの中の指定されたやつに変える。
1つ目のqubitにH()をかけてにしたのをCNOTで
にする、みたいな感じ。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[], index : Int) : ()
{
body
{
if (index == 0) {
// B0 : 00 + 11 = cnot(00 + 10) = cnot(H(0)0)
H(qs[0]);
CNOT(qs[0], qs[1]);
} elif (index == 1) {
// B1 : 00 - 11 = cnot(00 - 10) = cnot(H(1)0)
X(qs[0]);
H(qs[0]);
CNOT(qs[0], qs[1]);
} elif (index == 2) {
// B2 : 01 + 10
H(qs[0]);
X(qs[1]);
CNOT(qs[0], qs[1]);
} elif (index == 3) {
// B3 : 01 - 10
X(qs[0]);
H(qs[0]);
X(qs[1]);
CNOT(qs[0], qs[1]);
}
}
}
}
C - Generate GHZ state
みたいなのを作るやつ。1つ目のqubitにH()してあとはCNOTで2番目以降をひっくり返していく。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : ()
{
body
{
H(qs[0]);
let n = Length(qs);
for (i in 0 .. n-2) {
CNOT(qs[i], qs[i+1]);
}
}
}
}
D - Distinguish plus state and minus state
と
の識別。Hして計測するだけ。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (q : Qubit) : Int
{
body
{
H(q);
let res = M(q);
if (res == Zero) {
return 1;
} else {
return -1;
}
}
}
}
E - Distinguish Bell states
4つのBell stateの識別。
作る時の逆の手順、というかCNOTしてHしてから計測。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Int
{
body
{
CNOT(qs[0], qs[1]);
H(qs[0]);
let s0 = M(qs[0]);
let s1 = M(qs[1]);
if (s1 == Zero) {
if (s0 == Zero) {
return 0;
} else {
return 1;
}
} else {
if (s0 == Zero) {
return 2;
} else {
return 3;
}
}
}
}
}
F - Distinguish multi-qubit basis states
与えられたqubit列が、2つ与えられたビット列のどちらと同じ状態かを見分ける。
計測して比べていくだけ。必ずどちらかと同じらしいので最後まで見なくても分かることもある。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[], bits0 : Bool[], bits1 : Bool[]) : Int
{
body
{
let n = Length(qs);
for (i in 0 .. n-1) {
let v = M(qs[i]);
if (v == One) {
if (!bits0[i]) {
return 1;
}
if (!bits1[i]) {
return 0;
}
} else {
if (bits0[i]) {
return 1;
}
if (bits1[i]) {
return 0;
}
}
}
return -1;
}
}
}
G - Oracle for f(x) = k-th element of x
Oracleの意味がわかってなくて x[k] を計測して同じ値（か
）yをセットして返してた
// WA解
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
{
body
{
let desired = M(x[k]);
let current = M(y);
if (desired != current) {
X(y);
}
}
}
}→WA(3)
https://codeforces.com/contest/1001/submission/40034414
https://codeforces.com/contest/1001/submission/40058174
https://codeforces.com/contest/1001/submission/40058189
本戦にもOracle問題が出てきたのでちゃんとやらないと駄目だなと思って、これを読めと言われていたチュートリアル記事を読んだ。
返すべき値は x[k] じゃなくて xor(y, x[k]) なんだよね。あと多分、x[k] を破壊しちゃいけない。
CNOTですよCNOT
// AC解
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
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
x[i] すべてについてCNOTするだけでは
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (x : Qubit[], y : Qubit) : ()
{
body
{
let n = Length(x);
for (i in 0 .. n-1) {
CNOT(x[i], y);
}
}
}
}
I - Deutsch-Jozsa algorithm
与えられたOracleが定数（または
）を返すものか、それらを均等に返すものかを「Oracleを1回だけ呼び出して」調べる。
引数に重ね合わせたqubitを渡して1回でこれを言い当てることのできる魔法としかいいようのないDeutsch-Jozsaのアルゴリズムというやつを実装するだけ
…なのだけれど
H()する前にyをにセットしていなかったりxじゃなくてyを計測してたり（いやOracleの結果はyに来るわけだからyを計測すると普通思うじゃん？）
→WA
https://codeforces.com/contest/1001/submission/40075052
x[]を計測するようにしたのはいいんだけど結果がtrue/false逆だったり
→WA
https://codeforces.com/contest/1001/submission/40075147
// AC解
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool
{
body
{
mutable ans = true; // const if 0000
using (x = Qubit[N]) {
using (y = Qubit[1]) {
ResetAll(x);
Reset(y[0]);
X(y[0]); // y = |1>
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 ans = false;
}
}
Reset(y[0]);
ResetAll(x);
}
}
return ans;
}
}
}
*1:只今修理入院中につきレンタル代替機を使用中
