本日はC1 |01⟩ + |10⟩ + |11⟩状態の生成です。
https://codeforces.com/contest/1356/problem/C
続きを読む前回のA1~A5 ユニタリーの識別に引き続き、今回はB1,B2の可逆計算(Reversible computing)のおさらいです。
可逆計算をWikipediaで見てみると次のように書いています。
可逆計算(かぎゃくけいさん、英: Reversible computing)とは、可逆な、すなわち計算過程において常に直前と直後の状態が一意に定まる計算。可逆計算は、計算過程において情報が消失しないため非破壊的計算(Non-destructive computing)としても知られている。
量子コンピューターにおいては古典的な計算を可逆的に表現することで、算術などの古典的な計算を量子コンピューター上で実行できるようになる、と解説に書いています。今回はIncrementとDecrementを表現することが課題になっています。
N個のQubitをレジスターとして表現できる 2N を法とする数値をIncrementするユニタリー操作を実装します。さて、スケルトンコードを見ると LittleEndianというタイプが引数として与えられています。
namespace Solution { open Microsoft.Quantum.Arithmetic; open Microsoft.Quantum.Intrinsic; operation Solve (register : LittleEndian) : Unit is Adj+Ctl { // your code here } }
定義を見るとわかるように、これはQubitの配列です。
newtype LittleEndian = Qubit[];
符号なし整数をリトルエンディアンでフォーマットしたもの、つまり最下位ビットが配列一番目の要素として表現されています。このようにある符号なし整数を表現したregister をIncrementする操作を実装します。問題文には例として、 をIncrementすると となるとあります。つまり、|3>と|1>を表す状態の重ね合わせなので、それぞれIncrementした|0>と|2>を同じ確率で重ね合わせた状態にする必要があります。
また、Q#ではそのものずばりのIncrementByInteger という操作もありますが、測定をふくむこのような操作をおこなわず、Xゲートとそのcontrolled操作のみで実装せよと条件があります。
どのように実装するか、ですが、まず古典的な数を2進法でIncrementするときの手順を考えます。
この操作を逆順に考えると次のようになります。
これを量子プログラミングで実装するとこうなります。さきほど逆順で考えたのは、制御量子ビットとして使う最下位の量子ビットが1になるときに条件付き操作をおこないたいからです。
だんだん実装イメージができてきました。Q#で実装する場合、registerを表現するQubitの配列をqarrayとすると、
となります。これでコードが書けます。Q#では newtype LittleEndian = Qubit[];
のように定義したタイプからQubit[]をアンラップして取り出す処理を!
で記述します。
namespace Solution { open Microsoft.Quantum.Arithmetic; open Microsoft.Quantum.Intrinsic; operation Solve (register : LittleEndian) : Unit is Adj+Ctl { let qarray = register!; if (Length(qarray) > 1) { (Controlled Solve)([qarray[0]], LittleEndian(qarray[1 ...])); } X(qarray[0]); } }
同じように考えると、古典的な数を2進法でデクリメントする操作がこう書けます。
で、これをQ#で書くと
となります。したがって実装するとこのようになります。
operation Solve (register : LittleEndian) : Unit is Adj+Ctl { let qarray = register!; X(qarray[0]); if (Length(qarray) > 1) { (Controlled Solve)([qarray[0]], LittleEndian(qarray[1 ...])); } }
これでよいのですが、この実装よくみると先ほどのインクリメントの操作の逆順です。またビットの操作の手順を考えてもインクリメントの逆順の操作となります。Q#ではある操作を逆順に行う操作もユニタリーである場合、操作がAdjointであるといい、Adjoint functorでその逆順操作を実行できます。したがって、B2のSolveはB1のSolveの実装を例えばIncrementという名前で定義し、そのAdjoint functorを呼び出すことで実装できます。
namespace Solution { open Microsoft.Quantum.Arithmetic; open Microsoft.Quantum.Intrinsic; operation Solve (register : LittleEndian) : Unit is Adj+Ctl { Adjoint Increment(register); } operation Increment (register : LittleEndian) : Unit is Adj+Ctl { let qarray = register!; if (Length(qarray) > 1) { (Controlled Increment)([qarray[0]], LittleEndian(qarray[1 ...])); } X(qarray[0]); } }
1か月以上前ですが、Microsoft Q# Coding Contest がSummer 2020として今年も行われました。復習をまとめておきたいと思います。まずは、warmupのA問題、ユニタリーの識別です。公式の解説記事はこちらです。
A1からA5の問題は与えられたユニタリーゲートが与えられたあるゲートと同じであるかどうかを判定する問題です。これらの問題はユニタリーの識別としてはQuantum Katasにも追加されたので、今から解く場合はこちらを使うのが手っ取り早いでしょう。
QuantumKatas/DistinguishUnitaries at master · microsoft/QuantumKatas · GitHub
最初の問題A1はIゲートもしくはXゲートのどちらかが unitary
として与えられるので、次の操作を実装してIゲートなら0をXゲートなら1を返すようにするものです。
operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int { return -1; }
今回の問題の共通の考え方として解説に説明されていますが、量子プログラムでは「測定」が情報を得る唯一の方法です。その測定とは量子ビット(Qubit)の状態を計測した結果です。ゲートは量子ビットの状態を変える操作ですので、既知の状態の量子ビットを与えられたゲートで変化させてその測定結果で判定する必要があります。すなわち、どのような状態の量子ビットを与えて、ゲートで操作した後、測定した結果でどちらか判定する必要があります。 一般に量子ビットの測定は確率的であるため、任意の2つの状態を測定で区別することはできません。しかし、直交する2つの状態であれば区別することができます。したがって、IゲートとXゲートを適用すると直交する状態になるような量子ビットの状態を見つける必要があります。
Iゲートは|0>と|1>の状態をそのままにし、Xゲートはそれぞれ反転させることを考えれば、|0>の量子ビットを用意しゲートを操作した後測定して、|0>ならIゲート、|1>ならXゲートと考えることができます。したがって答えは次のようになります。
operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int { using (q = Qubit()) { unitary(q); let res = M(q); Reset(q); return res == Zero ? 0 | 1; } }
usingを抜けるときにQubitは初期化しておかないといけないので、Reset
操作をしてから測定結果を比較して値を返しています。この計測してResetする操作をまとめておこなうMResetZという操作がMicrosoft.Quantum.Measurement
名前空間にあるので次のように書くことができます。
open Microsoft.Quantum.Measurement; operation DistinguishIfromX (unitary : (Qubit => Unit is Adj+Ctl)) : Int { using (q = Qubit()) { unitary(q); return MResetZ(q) == Zero ? 0 | 1; } }
今度は与えられたunitaryゲートがIゲートなら0をPauliZゲートなら1を返す問題です。PauliZゲートは|0>はそのままに、|1>は位相をひっくり返して-|1>にするためこの2つの状態では区別できません。しかし、|+>と|->の2つの直交する状態を考えると、PauliZは|+>を|->に変化させるので区別することができます。H|0>=|+>、H|+>=|0> とH|->=|1> を利用すると次のように書けます。
operation DistinguishIfromZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int { using(q = Qubit()) { H(q); unitary(q); H(q); let res = M(q); Reset(q); return res == Zero ? 0 | 1; } }
また、|+>と|->はPauliXに沿った測定で計測できることと、MResetX という操作があるので次のように短く書けます。
operation DistinguishIfromZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int { using(q = Qubit()) { H(q); unitary(q); return MResetX(q) == Zero ? 0 | 1; } }
今度はZゲートなら0をSゲートなら1を返す関数です。ヒントは問題文の条件がexactly once
からat most twice
に変わっていることです。いままでは1回しかunitary操作ができなかったところを、今回は2回できます。Zゲートを2回適用するとIゲートになり、Sゲートを2回適用するとZゲートになります。つまりA2と同じ問題になります。
ration DistinguishZfromS (unitary : (Qubit => Unit is Adj+Ctl)) : Int { using (q = Qubit()) { H(q); unitary(q); unitary(q); return MResetX(q) == Zero ? 0 | 1; } }
なぜか本来の問題の順番と、解説およびQuantumKatasではA4とA5の順番が逆になっています。おそらく単一Qubutに対するunitary操作の識別を最初に並べて、最後に2つのQubitの操作にしたのでしょう。本来の問題通り、I⊗XとCNOTの識別をA4として解きます。
I⊗Xは2番目のQubitのみにXゲートを適用させる操作で、CNOTは1番目のゲートを制御Qubitとして2番目のQubitにNOT操作(つまりXゲート)を適用する操作です。|0>と|1>の直交状態のQubit2つからなる4つの状態において、それぞれの操作でどのように変化するか考えてみましょう。
State | I⊗X | CNOT |
---|---|---|
|00> | |01> | |00> |
|01> | |00> | |01> |
|10> | |11> | |11> |
|11> | |10> | |10> |
2つのQubitはentangle状態にはなっていないので、|00>という状態のQubitに対してunitary操作をしたあとの2番目のQubitの状態が|0>か|1>か計測すれば識別できることになります。したがって答えは次のようになります。
operation DistinguishIXfromCNOT (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int { using (qs = Qubit[2]) { unitary(qs); return MResetZ(qs[1]) == One ? 0 | 1; } }
今度はZゲートなら0を-Zゲートなら1を返す関数です。Zゲートと-Zゲートはグローバル位相しか違わないので直交する2つの状態で識別できなさそうな気がしてきます。そこでここまで問題文に与えられているのに使っていない条件に着目します。unitary操作がControlled
という条件です。ひとつ前の問題でCNOTという操作を出しているのもこの条件に気付いてほしかったのではと、解説を読んで気付きました。制御Qubitが必要なので、2つQubitを用意し、1番目のQubitを制御Qubitとし、2番目のQubitにControlled ZもしくはControlled -Z を適用した場合の状態変化を考えます。
State | Controlled Z | Controlled -Z |
---|---|---|
|00> | |00> | |00> |
|01> | |01> | |01> |
|10> | |10> | -|10> |
|11> | -|11> | |11> |
1番目のQubitが|0>であればどちらの操作でも状態は変化しません。1番目のQubitが|1>のときだけ-1の位相のずれが発生します。そこで|00>と|10>が均等に混じった状態、つまり (|0> + |1>) ⊗ |0>に着目します。この状態にControlled Zを適用しても状態は変化しません。Controlled -Zを適用すると、|1> ⊗ |0> が位相-1だけずれ、 (|0> - |1>) ⊗ |0>の状態になります。1番目のQubitが (|0> + |1>) と (|0> - |1>) の状態を識別すればよいので、A2と同じ問題であることがわかります。というわけで答えは次のようになります。Q#のControlled functorはQubitの配列に対して適用できるので、単一Qubitを要素数1の配列として渡します。
peration DistinguishZfromMinusZ (unitary : (Qubit => Unit is Adj+Ctl)) : Int { using (qs = Qubit[2]) { H(qs[0]); Controlled unitary(qs[0..0], qs[1]); return MResetX(qs[0]) == Zero ? 0 | 1; } }
以上でwarmupラウンドのA問題のまとめになります。