butch’s blog

メモ置き場。

【Qiskit Textbook】2. Multiple Qubits and Entanglement

Qiskit 量子コンピュータ

個人的メモ。

2.1 Multiple Qubits Entangled States

複数量子ビット状態の行列表示

状態をベクトルで表現する時はAer.get_backend('statevector_simulator')を使う。
ゲートはAer.get_backend('unitary_simulator')を使うことで行列表示することが出来る。

複数量子ビットのブラケット表記

ゲートの図で表記する時は0から順番に上のビットに割り当てられている。
ブラケット表記する時は一番右のビットが0になり右から左に読んでいく。
$\left|{011}\right\rangle$の場合は0番目の量子ビットが1、1番目の量子ビットが1、2番目の量子ビットが0である。
2進数表記との対応がしやすいためだと思う。

2.2 Phase Kickback

制御NOTゲート

ハードウェアの実装時にはコントロールビットとターゲットビットが一方向にしか定義されていない。
制御NOTゲートの両端にアダマールゲートを作用させることでターゲットとコントールビットを入れ替えることが出来る。

制御Tゲート

単一量子ビットに作用するTゲートで現れる位相はグローバルな量であった。
そのため観測して確率振幅を計算すると相殺される。
制御Tゲートを作用させることで相対的な位相に変わる。
観測時の確率振幅の大きさに影響を与える。

2.4 More Circuit Identities

Arbitrary rotations from H and T

$R_z(\pi/4)$だけでは$\pi$の有利数倍の回転になっている。
8回同じ計算を繰り返すと元に戻る。
よって$\pi$の無理数倍の回転を施すゲートを作成する必要がある。
それが$R_z(\pi/4)~R_x(\pi/4)$である。
$R_z(\pi/4)~R_x(\pi/4)$を1回作用させるたびに$\theta=\cos{\biggl(\frac{2\sqrt{2}-1}{4}\biggr)}^{-1}$の回転を行う。
これは$\pi$の無理数倍になっている。

$2\pi$をn等分にスライスする。
$R_z(\pi/4)~R_x(\pi/4)$を作用させる度に角度はこのスライスのどこか1区間に収まる。
(次に作用させると今のスライスから別のスライスに移動する。)
n+1回の回転を行うと少なくともどこか1つのスライスに2つの角度が存在する。
その時の回数を$n_1, n_2$と記録しておく。
すると

\theta_{n_2-n_1} \neq 0 \\ \frac{2\pi}{n} \leq \theta_{n_2-n_1} \leq \frac{2\pi}{n}

であることが分かる。
よって$n$を大きくしていくことでより小さい角度を表現することが出来る。
参考動画: Qiskit Textbook 日本語解説 2.3章 2.4章 2.5章 - YouTube
参考文献: https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/229039/1/bussei_el_064217.pdf

【Qiskit Textbook】1. Quantum State and Qubits

量子コンピュータ Qiskit

個人的メモ。

1.2 Atoms Computation

1量子ビットの加算はNOT, CNOT, Toffoliゲートで行える。
(CNOTゲートはなくても良いみたいです。)
Toffoliゲートは3量子ビットに間に働く制御ゲートでQiskitではccxとして提供されている。
実装はめんどくさそう。

qiita.com

1量子ビットの加算が行えればプログラミングではほとんど何でも出来る。

1.3 Representing Qubit States

初期状態の設定

initial_state = [0,1]
qc.initialize(initial_state, 0)

initial_stateに設定するのは1量子ビットを2次元の複素ベクトルで展開した時の値を入力する。
qc.initializeの第2引数には初期化するビットの番号を入力する。
上の例では0番目のビットを$(0, 1) = \left|{1}\right\rangle$に初期化している。
initial_stateで設定する係数の値が規格化した時に1になっていないとエラーになる。

statevector

svsim = Aer.get_backend('statevector_simulator') # Tell Qiskit how to simulate our circuit

statevector_simulatorは.get_statevector()を使うと途中の量子状態を複素ベクトルとして取り出せる。(実際の量子コンピュータでは不可能)
qasm_simulatorには.get_statevector()が備わっていない。(実際の量子コンピュータで行える操作に寄せている。)

Measurement

回路の途中に測定を行うとその時点で状態が確定してしまう。

qc = QuantumCircuit(1) # We are redefining qc
initial_state = [0.+1.j/sqrt(2),1/sqrt(2)+0.j]
qc.initialize(initial_state, 0)
qc.measure_all()
qobj = assemble(qc)
state = svsim.run(qobj).result().get_statevector()
print("State of Measured Qubit = " + str(state))

1.4 Single Qubit Gates

Outer Product

Xゲートをブラケット表記すると$ \left|{0}\right\rangle \left\langle{1}\right| + \left|{1}\right\rangle \left\langle{0}\right|$である。
このブラケットの状態から外積(Outer Product)を行うことで行列表示に出来る。
$\left|{0}\right\rangle = (1, 0)^{T}, \left|{1}\right\rangle = (0, 1)^{T}$なので$ \left|{0}\right\rangle \left\langle{1}\right|$は、

\left|{0}\right\rangle \left\langle{1}\right| = \left( \begin{array}{cc} 1 *(0, 1) \\ 0 * (0, 1) \end{array} \right) = \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right)

になる。
$ \left|{1}\right\rangle \left\langle{0}\right|$も同様にすると、

\left|{1}\right\rangle \left\langle{0}\right| = \left( \begin{array}{cc} 0 & 0 \\ 1 & 0 \end{array} \right)

となる。

1.5 The Case for Quantum Computers

  • デジタルコンピュータ：0と1の離散値を使う。エラーが多いけど訂正する仕組みが整っている。
  • アナログコンピュータ：連続値を使用する。エラーが小さいため検出できず訂正しにくい。
  • 量子コンピュータ：0と1の離散値だが連続的なパラメータで制御できる。粒子と波動の2重性に由来する。

【Qiskit Textbook】What is Quantum?のQuantum Coin Tossについて

量子コンピュータ Qiskit

現在QiskitのTextbookを読んで量子コンピュータについて勉強しています。
0章に入る前の導入部分「What is Quantum?」で紹介されている「Quantum Coin Toss」について考察したいと思います。

qiskit.org

いきなり「Quantum Coin Toss」が導入されて何のことか分からなかった人も多いはずです。
これは1量子ビットにアダマールゲートを作用させて状態を観測することに対応していると思います。
まだアダマールゲートなどが紹介されていないので分からなくて当然ですね。

最初のQuantum Coin Tossを1回行う操作は、1量子ビットの初期状態$\left|{\psi_i}\right\rangle$にアダマールゲートを作用させて状態を観測することに対応しています。

初期状態が$\left|{0}\right\rangle$の場合、

\def\ket#1{\mathinner{\left|{#1}\right\rangle}} \ket{0} \rightarrow \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})

初期状態が$\left|{1}\right\rangle$の場合、

\def\ket#1{\mathinner{\left|{#1}\right\rangle}} \ket{0} \rightarrow \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})

となります。
いずれの初期状態からスタートしても観測後に得られる状態は50%の確率で$\left|{0}\right\rangle$, $\left|{1}\right\rangle$がそれぞれ得られることが分かります。

続いてQuantum Coin Tossを2回行う場合について考えます。
これはアダマールゲートを2回連続で量子ビットに作用させることに対応しています。
以下で実際に計算していますが、2回連続でアダマールゲートを作用させると元の状態に戻ります。

初期状態が$\left|{0}\right\rangle$の場合、

\def\ket#1{\mathinner{\left|{#1}\right\rangle}} \ket{0} \rightarrow \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \rightarrow \frac{1}{2}(\ket{0} + \ket{1}) + \frac{1}{2}(\ket{0} - \ket{1}) = \ket{0}

初期状態が$\left|{1}\right\rangle$の場合、

\def\ket#1{\mathinner{\left|{#1}\right\rangle}} \ket{1} \rightarrow \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) \rightarrow \frac{1}{2}(\ket{0} + \ket{1}) - \frac{1}{2}(\ket{0} - \ket{1}) = \ket{1}

となります。

古典のコイントスでは2回連続で行っても50%の確率で表と裏になっていたのに対して、量子計算では表(0)から始めると必ず表(0)に、裏(1)から始めると必ず裏(1)になってしまうことが分かります。
負の確率振幅が計算の途中に現れることである状態に遷移する確率が打ち消しあって0になっています。
(1の状態にアダマールゲートを作用させると係数に-1が出てくる。)
この負の確率振幅を使ったアルゴリズムを考えることで計算の高速化が行える可能性があるそうです。

【ABC】 182 D - Wandering

atcoder.jp

解説読むとめっちゃ簡単ですよね...。 なぜ解けなかったのか...。 こちらの動画のコードを丸パクリさせて頂きました。 他の人のコードを読むのも勉強になります。

youtu.be

N = int(input())
N += 1
A = [0] + list(map(int, input().split()))

Aの要素iまでの増加分を足し合わせた累積和をaccum_sumとしています。 ステップiを行った時に増減する幅が格納されています。

accum_sum = A[:]
for i in range(1, N):
    accum_sum[i] += accum_sum[i-1]

入力例1の場合は

print(accumulation_sum) 
[0, 2, 1, -1]

ステップiを行った後の実際の座標は初期位置をnow=0としてaccumulation_sumの要素をそれぞれ足せば求まります。

now = 0
for i in range(1, N):
    now += accum_sum[i]
    print(i, now)

出力

1 2
2 3
3 2

次にステップiで移動できる最大幅を計算します。 これはステップiまでのaccum_sumの最大値を計算すれば良いです。 全体に対してmax(accumulation_sum)ではない点に注意して下さい。

accum_max = accum_sum[:]
for i in range(1, N):
    accum_max[i] =max(accum_max[i], accum_max[i-1])
print(accum_max) # [0, 2, 2, 2]

後はこれらを元に全ステップで到達できる座標の最大値を計算して行きます。

ans = 0
now = 0
for i in range(1, N):
    ans = max(ans, now+accum_max[i])
    now += accum_sum[i]
print(ans) # 5

コード全体は以下のUpしました。

github.com

【ABC】 181 E - Transformable Teacher

ABC python

atcoder.jp

コンテスト中はコストの計算量の抑え方が分からずにsubmitできませんでした。
公式解説にもあるように生徒hを昇順にソートし、前と後ろからの累積和を予め計算しておけば$O(1)$でコストが計算できます。
累積和系のテクニックの大事さを痛感しました。

全体のコードは以下にUpしました。

github.com

提出結果

atcoder.jp

【ABC】 181 D - Hachi

文字列に含まれる数字の順番を入れ替えて8の倍数が作れるかどうかを判定する問題です。

atcoder.jp

1000が8の倍数で割り切れるのがポイントです。
1000が8の倍数で割り切れるので当然それより桁の大きい10000も8で割り切れます。
つまり並べ替えた数列の下３桁が8の倍数かどうかを調べれば良いです。
0が含まれる場合を除いた8の倍数を全て列挙して各桁で必要な数字の個数を格納したdictを用意しました。
例えば

dict[168] = {1:1, 6:1, 8:1}
dict[888] = {8:3}

みたいな感じです。
問題で与えられたSに含まれる数字ごとの個数をカウントして上のdictのどれかよりも多ければYesに、少なければNoにします。
桁数が1桁と2桁の場合だけ例外処理を施しています。

全体のコードは以下にUpしています。

github.com

提出結果

atcoder.jp

ABC181でようやく緑色になりました。
かなりギリギリですがw

atcoder.jp

E問題も方針はある程度立ったのですが、1箇所だけ計算量的に不味そうな点があってsubmitできませんでした。

【ABC】 180 E - Traveling Salesman among Aerial Citie

ABC python DP

巡回セールスマン問題(TSP)です。

atcoder.jp

$N$が17なのでビットDPを使えば計算量的に間に合うようです。
$S$をビット列の集合として以下のDPを作成します。

  • DP[S][v]: 訪問済みの集合Sの頂点vからスタートする時の距離の総和

例えば$N=5$の場合、右から順番に都市1, 都市2と対応づけると、$00110$のビット列は都市2と都市3を訪問した状態を表します。
これがDPのSに対応します。
このデータからは都市2→都市3なのか、都市3→都市2の順番で訪問したのかが分かりません。 今までに訪問した都市の順番を保持する必要はなく最後に訪れた都市の番号さえ分かれば良いのでそれをDPのvで保持しています。

都市jからkへ移動する場合、DPの更新は以下の式で行われます。

DP[i|1<<k][k] = min(DP[i|1<<k][k], DP[i][j]+dist[j][k])

ややこしいのがi|1<<kだと思います。
まず1<<kは1を左に$k$だけシフトさせたビット列を作り出します。
例えばS=00110、v=3、k=5の場合を考えます。
1<<k=10000を表します。
これに対して今i=Sなのでi|1<<k=00110 | 10000=10110となります。
これでDP[i|1<<k][k]は都市2,3,5を訪問して都市5にいる状態を表します。

この更新を行い最終的にはDP[n2-1][0]が求める答えになります。 ここでn2 = 1 << nになります。

全体のコードは以下のリポジトリにupしました。 github.com

atcoder.jp

ちなみにABC180でレーティングが一気に100ぐらい上がりました。
まだ茶色のクソザコですが。

atcoder.jp