Codeforcesで行われたコンテスト
codeforces.com
Microsoftによって作られた量子プログラミング言語Q#を使ったコンテスト
面白そうなので解いた。
Warmupなので練習コンテスト。本番は今週の土曜日1:00から3日間らしい(気が向いたら出よう)。
環境準備
今回の環境はUbuntu 16.04。Visual Studio Code上で書いた。
これを参考に環境準備
まず、CLI上に.NET環境(dotnet)を用意する
.NET and C# - Get started in 10 minutes
$ wget -q https://packages.microsoft.com/config/ubuntu/16.04/packages-microsoft-prod.deb $ sudo dpkg -i packages-microsoft-prod.deb $ sudo apt-get install apt-transport-https $ sudo apt-get update $ sudo apt-get install dotnet-sdk-2.1
次にMicrosoft Quantum Development Kitをインストール
Setting up the Q# development environment | Microsoft Docs
$ dotnet new -i "Microsoft.Quantum.ProjectTemplates::0.2.1806.2802-preview"
Visual Studio CodeにQ#拡張機能があるらしいので入れた。
Microsoft Quantum Development Kit - Visual Studio Marketplace
Q#のQuick Start
Write a quantum program | Microsoft Docs
コンテスト問題
基本の問題のみ。
ただし、量子プログラミング言語では量子ビット(qubit)を扱うため、量子ビットを少し理解しておく必要がある。
当然だけど、Q#の言語仕様がわからないのでリファレンスを参照しながら書いた。
あと、ローカルでテストしながら解いたけど、コードに特定の入力を与えるためにある程度コードを書かないといけないのが少しつらかった。
以下、かなり雑な解法説明。
公式解説はこれ
A問題: Generate plus state or minus state
状態のqubitとsignが与えられ、
- sign = 1 であれば
- sign = -1 であれば
にqubitの状態を変化させる問題。
X operationとH operationを使えばできる。
提出コード: http://codeforces.com/contest/1001/submission/39794453
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (q : Qubit, sign : Int) : () { body { if (sign == -1) { X(q); } H(q); } } }
B問題: Generate Bell state
状態の2個のqubitとindexが与えられ、
- index = 0 であれば
- index = 1 であれば
- index = 2 であれば
- index = 3 であれば
にqubitの状態を変化させる問題。
CNOT operationを使えば各状態に変化させられる。
を計算する場合、の状態によって以下のように状態が変化する。
-
- なら、は状態に変化
- なら、は状態に変化
-
- なら、は状態に変化
- なら、は状態に変化
提出コード: http://codeforces.com/contest/1001/submission/39796595
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (qs : Qubit[], index : Int) : () { body { let q0 = qs[0]; let q1 = qs[1]; if(index >= 2) { X(q1); } if(index % 2 == 1) { X(q0); } H(q0); CNOT(q0, q1); } } }
C問題: Generate GHZ state
個のqubitが与えられ、これらの状態をにする問題。A問題、B問題の一般化。
1つのqubitをにして、残りのをCNOTで状態を変化させるのみ。
提出コード: http://codeforces.com/contest/1001/submission/39797122
namespace Solution { open Microsoft.Quantum.Canon; open Microsoft.Quantum.Primitive; operation Solve (qs : Qubit[]) : () { body { let num = Length(qs); let q0 = qs[0]; H(q0); for (i in 1..num-1) { CNOT(q0, qs[i]); } } } }
D問題: Distinguish plus state and minus state
与えられたqubitの状態がかかを判定する。
であるため、、で判別する。
提出コード: http://codeforces.com/contest/1001/submission/39797759
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (q : Qubit) : Int { body { H(q); if (M(q) == Zero) { return 1; } return -1; } } }
E問題: Distinguish Bell States
与えられた2個のqubitの状態が、、、かを判定する。
CNOT operationとH operationでうまく判別する。
を計算する場合、の状態によって以下のようにの状態が変化する。(B問題の逆)
-
- なら、は状態に変化
- なら、は状態に変化
-
- なら、は状態に変化
- なら、は状態に変化
と状態が変化したからindexを計算する。
提出コード: http://codeforces.com/contest/1001/submission/39798093
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (qs : Qubit[]) : Int { body { mutable res = 0; let q0 = qs[0]; let q1 = qs[1]; CNOT(q0, q1); if (M(q1) == One) { set res = res + 2; } H(q0); if (M(q0) == One) { set res = res + 1; } return res; } } }
F問題: Distinguish multi-qubit basis states
0もしくは1の基底状態を持つ個のqubitと、個のbool値を持つbits0, bits1が与えられる。各番目のqubitはbits0[i], bits1[i]のどちらか一方のみの各bool値と一致する。どちらに一致するかを計算する。
これは各bool値とqubitを比較して一方が一致しなくなったら、正しい方を出力するだけ。
提出コード: http://codeforces.com/contest/1001/submission/39798458
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) { if (bits0[i] != bits1[i]) { if(M(qs[i]) == One) { if(bits1[i]) { return 1; } return 0; } else { if(bits1[i]) { return 0; } return 1; } } } return -1; } } }
G問題: Oracle for f(x) = k-th element of x
個のqubitを引数に取るquantum oracleとして (つまりk番目のqubitを返す)を計算する。
k番目の要素を返せばいいのかなと思ってReset -> CNOTで書いたらWA出まくって悩んで結局Editorialを見る。
Resetなしでただ単純にCNOTだけでよかったっぽい。
提出コード: http://codeforces.com/contest/1001/submission/39853159
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
個のqubitを引数に取るquantum oracleとしてを計算する。
G問題の応用問題みたいなものなので瞬殺。
提出コード: http://codeforces.com/contest/1001/submission/39853214
namespace Solution { open Microsoft.Quantum.Canon; open Microsoft.Quantum.Primitive; 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
関数を計算するquantum oracleが与えられる。この関数を1回だけ呼び出して定数関数かbalancedに0,1になる関数かを判定する問題。
この問題は問題名のDeutsch-Jozsa algorithmにより判定できるらしい。
- 状態の個のqubitを含む、状態の1個のqubit を用意
- 全てのqubitにH operationを適用
- を入力、を出力としてquantum oracle に与える
- に含まれるqubitにH operationを適用した上で、全て0か判定 (0であれば定数関数、そうでなければbalanced function)
提出コード: http://codeforces.com/contest/1001/submission/39871458
namespace Solution { open Microsoft.Quantum.Canon; open Microsoft.Quantum.Primitive; operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool { body { mutable v = true; using (register0 = Qubit[N]) { let qs = register0; for (i in 0..N-1) { H(qs[i]); } using (register1 = Qubit[1]) { let qn = register1[0]; X(qn); H(qn); Uf(qs, qn); for (i in 0..N-1) { H(qs[i]); if (M(qs[i]) == One) { set v = false; } } Reset(qn); } ResetAll(register0); } return v; } } }