Microsoft Q# Coding Contest - Summer 2020 に参加してQ#言語を書いて量子コンピュータを学んだ。量子ゲートを通すのはできたが機械学習は結局最後までBiasがどこに影響してくるのか理解できなかった。解いた問題だけ記録しておく。
量子について
X, Y, ZゲートはそれぞれX, Y, Z軸を中心に180°回転させる。Hゲートはアダマール変換でZ軸方向とX軸方向を入れ替えるように回転させる。ただし、2qubit以上だと回転を考えても意味不明なので行列で計算したほうがよさそう。
1.0 |0> と (0.707 + 0.707i) |0> はブロッホスフィアでz軸|0>の方向で等しく、同じ状態で区別しない。|0>と|1>を同時に複素数倍してもQubitは状態が同じものだと考えられるので紙の上で考えるときは計算しやすい係数にすればよい、例えば|0>の係数を非負実数することができる (global phase)。
Z軸上向きは|0>、下向きは|1>
X軸上向きは 1/√2 (|0> + |1>)、下向きは 1/√2 (|0> - |1>)。
Y軸上向きは 1/√2 (|0> + i|1>)、下向きは 1/√2 (|0> - i|1>)。
Q#について
前回のQDK2.1からバージョンが上がってQDK3.1になり、かなり書きやすくなっている。
Visual Studio 2019を先にインストールしてからQDKをインストールし、紐づける必要がある。
最初にQubit宣言したときは|00...00> の係数のノルムが1で初期化されていて Z軸がZeroの状態。使い終わったら同じ状態にして破棄する必要がある。
ゲートを通すたびにDumpMachine(“”); でqubitの係数をターミナルに出力できる（引数がファイル名。空文字ならターミナル）。
Microsoft Q# Coding Contest - Summer 2020 - Warmup
https://codeforces.com/contest/1356
A1 Distinguish I from X
Iゲートは恒等写像。Xゲートは|0>を180°先の|1>に移動させるので１回ゲートを通した後でZ軸で測定する。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (q = Qubit()) {
unitary(q);
let m = M(q);
Reset(q);
if (m == Zero) {
return 0;
} else {
return 1;
}
}
}
}
A2 Distinguish I from Z
ZゲートはX軸方向を180°回転させる。Hゲートを通してからZゲートを通した場合X軸方向が反転する。Hゲートの逆写像はHゲート自身なのでもう一度通してZ軸に向ける。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (q = Qubit()) {
H(q);
unitary(q);
H(q);
let m = M(q);
Reset(q);
if (m == Zero) {
return 0;
} else {
return 1;
}
}
}
}
A3 Distinguish Z from S
Sゲートは |1> を i倍する。Zを2回通せば恒等写像、Sを2回通せば |1>を -1倍 つまりZゲートになる。あとはA2と同じ。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (q = Qubit()) {
H(q);
unitary(q);
unitary(q);
H(q);
let m = M(q);
Reset(q);
if (m == Zero) {
return 0; // Z
} else {
return 1; // S
}
}
}
}
A4 Distinguish I ⊗ X from CNOT
I ⊗ X は qs[0]を恒等写像、qs[1]を反転させる。
CNOTはqs[0]が1の時にqs[1]を反転させる。
|00>を通したときに|01>に移動するならば I ⊗ X。qs[1]を測定すればよい。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[2]) {
unitary(qs);
let m = M(qs[1]);
ResetAll(qs);
if (m == One) {
return 0; // I \times X
} else {
return 1; // CNOT
}
}
}
}
A5 Distinguish Z from -Z
2qubit用意して、qs[0]でControllする。
qs[0]をHゲートに通してからテストするゲートを通す。
(H |0>) ⊗ |0> = (1/√2 |0> + 1/√2 |1>) ⊗ |0> = 1/√2 |00> + 1/√2 |10>
(Controlled Z)(1/√2 |00> + 1/√2 |10>) = 1/√2 |00> + 1/√2 |10> = (1/√2 |0> + 1/√2 |1>) ⊗ |0>
(Controlled -Z)(1/√2 |00> + 1/√2 |10>) = 1/√2 |00> - 1/√2 |10> = (1/√2 |0> - 1/√2 |1>) ⊗ |0>
H(1/√2 |0> + 1/√2 |1>) = |0>
H(1/√2 |0> - 1/√2 |1>) = |1>
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[2]) {
H(qs[0]);
Controlled unitary(qs[0..0], qs[1]);
H(qs[0]);
let m = M(qs[0]);
ResetAll(qs);
if (m == Zero) {
return 0;
} else {
return 1;
}
}
}
}
B1 Increment
|0000> の係数は |1000>へ移動、|1000>の係数は|0100>へ移動…するような回路を書く問題。Xゲートで適切な交換を繰り返す。
X(qs[0])が1ビットのインクリメントになっていて |0xxx> と |1xxx> が交換される。これで |1xxx>の係数は完成している。
次のビットは |00xx> と |01xx>を交換したいのでqs[0]が0の時にControl する必要がある。そのゲートの記法は ControlledOnInt(0, X)。同様にqs[0..1]が00のとき、qs[0..2]が000のとき、と繰り返す。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Arithmetic;
operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
let qs = register!;
let n = Length(qs);
X(qs[0]);
for (i in 1..n-1) {
(ControlledOnInt(0, X))(qs[0..i-1], qs[i]);
}
}
}
B2 Decrement
Incrementの逆操作。1の時にControlする。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Arithmetic;
operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
let qs = register!;
let n = Length(qs);
X(qs[0]);
for (i in 1..n-1) {
(Controlled X)(qs[0..i-1], qs[i]);
}
}
}
C Prepare state |01⟩ + |10⟩ + |11⟩
過去問とほぼ同じなので同様に解く。まずHゲートで均等に配って 1/2 (|00>+|01>+|10>+|11>) を作る。補助用のAncilla bitを付け加えて 1/2 (|000>+|010>+|100>+|110>)。|110>だけancillaをフリップさせると 1/2 (|000>+|010>+|100>+|111>)。Ancillaが0になる状態は000,010,100で二乗和が3/4である。ancillaを測定すると3/4=75%の確率で0 になり、測定して失われた |111> の係数は均等に分配され1/√3 (|000>+|010>+|100>)になる。最後にフリップして1/√3 (|01>+|10>+|11>) にする。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Measurement;
operation Solve (qs : Qubit[]) : Unit {
using (a = Qubit()) {
repeat {
H(qs[0]);
H(qs[1]);
Controlled X(qs, a);
let m = MResetZ(a);
} until(m == Zero) fixup {
ResetAll(qs);
}
X(qs[0]);
X(qs[1]);
}
}
}
Microsoft Q# Coding Contest - Summer 2020
https://codeforces.com/contest/1357
A1 Figure out direction of CNOT
unitary(qs[0..1]) は CNOT(qs[0], qs[1]) か CNOT(qs[1], qs[0]) に等しいので判定せよ、という問題。ただし、unitaryは1回しか呼ぶことができない。
|11>を通すと|10>か|01>になるのでどちらかのビットを測定すればよい。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[2]) {
X(qs[0]);
X(qs[1]);
unitary(qs);
let m = M(qs[0]);
ResetAll(qs);
if (m == Zero) {
return 1;
} else {
return 0;
}
}
}
}
A2 Distinguish I, CNOTs and SWAP
|01>を通すとそれぞれ、|01>, |01>, |11>, |10> で、qs[0]を測定すると {I, CNOT12}と{CNOT21, SWAP}に分類できる。
|10>を通すとそれぞれ、|10>, |11>, |10>, |01> で、qs[1]を測定すると{I, CNOT21}と{CNOT12, SWAP}に分類できる。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[4]) {
X(qs[1]);
X(qs[2]);
unitary(qs[0..1]);
unitary(qs[2..3]);
let m0 = M(qs[0]);
let m1 = M(qs[1]);
let m2 = M(qs[2]);
let m3 = M(qs[3]);
ResetAll(qs);
if (m0 == Zero and m1 == One and m2 == One and m3 == Zero) {
return 0;
} elif (m0 == Zero and m1 == One and m2 == One and m3 == One) {
return 1;
} elif (m0 == One and m1 == One and m2 == One and m3 == Zero) {
return 2;
} else {
return 3;
}
}
}
}
A3 Distinguish H from X
HゲートかXゲートか判定せよ。ただし2回しか呼び出してはならない。
|0>を通してみる。
H|0> = 1/√2(|0> + |1>) = |+>
X|0> = |1>
前者はX軸上方向、後者はZ軸下方向を指している。Z軸で180°回転させると前者だけ変化させることができる。
Z H|0> = 1/√2(|0> - |1>) = |->
Z X|0> = |1>
もう一度判定するゲートを通してZ軸に向ける。
H Z H|0> = |1>
X Z X|0> = |0>
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (q = Qubit()) {
unitary(q);
Z(q);
unitary(q);
let m = M(q);
Reset(q);
if (m == Zero) {
return 1;
} else {
return 0;
}
}
}}
A4 Distinguish Rz from R1
Rz(θ)、R1(θ) は Z軸中心にθ rad 回転させる。ただしR1は絶対的にθ/2 rad 掛かっている。 これはControlしなければ同じ意味を持つ操作。
θ = 2π のとき
Rz(2π) = -I
R1(2π) = I
|+>でControllしてHゲートで戻す。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : ((Double, Qubit) => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[2]) {
H(qs[0]);
H(qs[1]);
(Controlled unitary)([qs[1]], (PI()*2.0, qs[0]));
H(qs[1]);
H(qs[0]);
let m = M(qs[1]);
ResetAll(qs);
if (m == Zero) {
return 1;
} else {
return 0;
}
}
}
}
A5 Distinguish Rz(θ) from Ry(θ)
θは定数でゲートunitaryが Rz(θ) か Ry(θ) か判定せよ。
ゲートを複数回通すことで π rad 回転に近づけることができる。
|0>を通すと、unitaryが Rzならば|0>から変わらず、Ryならば|1>に近くなる。つまり測定して|1>ならば必ずRyで、|0>ならば高い確率でRz になる。複数回繰り返せば十分な確率で判定できる。
さらに賢い方法として、1/√2(|0> + i|1>)を通すと、Rzならば1/√2(|0> - i|1>) に近くなり、Ryならば変わらず1/√2(|0> + i|1>)になる。y方向で測定してOneならば必ずRzでZeroならば高確率でRyである。1つの判定だけでは高い確率で判定できるだけであったが、2つの手法を交互に繰り返すことで（非常に低い確率で終了しないが）間違い無く判定できるアルゴリズムになる。前者がモンテカルロ法、後者がラスベガス法。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Extensions.Math;
open Microsoft.Quantum.Measurement;
operation Solve (theta : Double, unitary : (Qubit => Unit is Adj+Ctl)) : Int {
mutable sum = 0.0;
mutable cnt = 0;
repeat {
set cnt = cnt + 1;
set sum = sum + theta;
if (sum > 1.4 * PI()) {
set sum = sum - PI();
}
} until (0.6 * PI() <= sum and sum <= 1.4 * PI());
mutable a0 = 0;
mutable a1 = 0;
using (q = Qubit()) {
repeat {
for (i in 1..cnt) {
unitary(q);
}
let m = MResetZ(q);
if (m == Zero) {
set a0 = a0 + 1;
} else {
set a1 = a1 + 1;
}
} until (a1 > 0 or a0 == 40);
}
// Message($"{sum} {cnt} {a0} {a1}");
if (a1 > 0) {
return 1;
} else {
return 0;
}
}
}
A6 Distinguish four Pauli gates
I, X, Y, Z ゲートのどれかが与えられるので1回だけ呼び出してどれであるか判定せよ、という問題。
ベル状態の量子を通すと4つのゲートはそれぞれ別のベル状態に写す。Superdense Codingと名前がついている。ベル状態は過去に出題されていたが使い方を学んでいなかったので解けなかった。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[2]) {
H(qs[0]);
CNOT(qs[0], qs[1]);
unitary(qs[1]);
CNOT(qs[0], qs[1]);
H(qs[0]);
let m0 = M(qs[0]);
let m1 = M(qs[1]);
ResetAll(qs);
if (m0 == Zero and m1 == Zero) {
return 0; // I
} elif (m0 == Zero and m1 == One) {
return 1; // X
} elif (m0 == One and m1 == One) {
return 2; // Y
} else {
return 3; // Z
}
}
}
}
A7 Distinguish Y, XZ, -Y and -XZ
4種のゲートのどれかが与えられるので3回まで呼び出してどれであるか判定せよ。
2回連続で呼び出すとY^2と(-Y)^2は I ゲートに等しく、(XZ)^2と(-XZ)^2は -I ゲートに等しい。
Yと-Yの判定はYを通すことで I と -I の判定にできる。XZと-XZの判定は ZX を通すことで I と -I の判定にできる。結局 Iと-Iの判定だけできれば良くてこれはWarmup A5 とほぼ同様にできる。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Measurement;
operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int {
using (qs = Qubit[2]) {
H(qs[0]);
(Controlled unitary)(qs[0..0], qs[1]);
(Controlled unitary)(qs[0..0], qs[1]);
if (MResetX(qs[0]) == Zero) {
H(qs[0]);
(Controlled Y)(qs[0..0], qs[1]);
(Controlled unitary)(qs[0..0], qs[1]);
return MResetX(qs[0]) == Zero ? 0 | 2;
} else {
H(qs[0]);
(Controlled X)(qs[0..0], qs[1]);
(Controlled Z)(qs[0..0], qs[1]);
(Controlled unitary)(qs[0..0], qs[1]);
return MResetX(qs[0]) == Zero ? 3 | 1;
}
}
}
}
B1 "Is the bit string balanced?" oracle
長さ10以下の偶数のinput qubitsが0の個数と1の個数が等しいならば、output qubitをXゲートに通せ、という問題。
10以上が数えられるancilla bitsを用意する（4ビット）。inputの各ビットでコントロールして、|1>ならばancillaをincrementする。ancilla が n/2 と等しくなっていればoutputをXゲートに通す。解説ではancilla を |0>に戻すために、within-apply 文を使っていて読みやすい。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Increment(qs : Qubit[]) : Unit is Adj+Ctl {
let n = Length(qs);
X(qs[0]);
for (i in 1..n-1) {
(ControlledOnInt(0, X))(qs[0..i-1], qs[i]);
}
}
operation Solve (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl {
let n = Length(inputs);
using (qs = Qubit[4]) {
within {
for (i in 0..n-1) {
(Controlled Increment)(inputs[i..i], qs);
}
} apply {
(ControlledOnInt(n/2, X))(qs, output);
}
}
}
}
B2 "Is the number divisible by 3?" oracle
長さ8以下のInputの状態を2進数と見たときに3の倍数ならば、outputをXゲートに通せ。
桁和のMODを考えると1の位は1、2の位は2、4の位は1、8の位は2、…。12以上数えられるようなancillaを用意してincrementして、合計が0, 3, 6, 9, 12 ならばXゲートに通す。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Increment(qs : Qubit[]) : Unit is Adj+Ctl {
let n = Length(qs);
X(qs[0]);
for (i in 1..n-1) {
(ControlledOnInt(0, X))(qs[0..i-1], qs[i]);
}
}
operation Solve (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl {
let n = Length(inputs);
using (qs = Qubit[4]) {
within {
for (i in 0..n-1) {
if (i % 2 == 0) {
(Controlled Increment)(inputs[i..i], qs);
} else {
(Controlled Increment)(inputs[i..i], qs);
(Controlled Increment)(inputs[i..i], qs);
}
}
} apply {
(ControlledOnInt(0, X))(qs, output);
(ControlledOnInt(3, X))(qs, output);
(ControlledOnInt(6, X))(qs, output);
(ControlledOnInt(9, X))(qs, output);
(ControlledOnInt(12, X))(qs, output);
}
}
}
}
C1 Prepare superposition of basis states with 0s
|11...1> の係数は0、それ以外は均等にした状態を作る問題。2qubitのものをwarmupでやった。同様に最初に全ての状態にHゲートで均等に分けた後、ancillaを付けて、|11...1>でControlする。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Measurement;
operation Solve (qs : Qubit[]) : Unit {
using (a = Qubit()) {
repeat {
ApplyToEachA(H, qs);
Controlled X(qs, a);
let m = MResetZ(a);
} until(m == Zero) fixup {
ResetAll(qs);
}
}
}
}
C2 Prepare superposition of basis states with the same parity
N qubitのinputをバイナリの parity が入力に等しいところに均等に分配する問題。
qs[i]が1の時にqs[0]をフリップをすればparity=0が得られる（i=1..n-1）。最後に1ビットだけフリップすればparity=1にもなる。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation Solve (qs : Qubit[], parity : Int) : Unit {
for (i in 1..Length(qs)-1) {
H(qs[i]);
CNOT(qs[i], qs[0]);
}
if (parity == 1) {
X(qs[0]);
}
}
}
E1 Power of quantum Fourier transform
QFT 量子フーリエ変換をp回通した結果を高速に求める問題。
フーリエ変換の逆変換が、複素共役を取ってからフーリエ変換をし1/N倍する、というものである、実装によってはbit reverseも必要になる。量子の1/N倍は意味がないので無視し、4回フーリエ変換すれば元の状態に戻る。pを4で割った余りを求めてその回数だけQFTを行えばよい。
namespace Solution {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
operation SolveE1 (p : Int, inputRegister : LittleEndian) : Unit is Adj+Ctl {
for (i in 1..p%4) {
QFTLE(inputRegister);
}
}
}
