4-ライツアウトパズル（2020年 Week2b）

4-ライツアウトパズル（2020年 Week2b）#

Attention

このNotebookはQiskit v0.44の仕様に合わせてコードを改変しています。

1度のスイッチでボードをクリア#

Dr. リョウコのいる部屋の床は３ｘ３のタイルでできている。ひとつのタイルはひとつの量子ビットに対応している。
エネルギーの低い基底状態のタイルは平らだが、エネルギーレベルの高い励起状態の量子ビットは柱のようにそびえ立ち行く手を阻む。
しかも2つの状態間を行き来する量子ビットがいくつか存在している。更に観察をつづけると、各量子ビットが取り得る状態の組み合わせが、
全部で４パターンしかないことに気づく。だが、スイッチは1度しか押せない。これは4枚のライツアウト問題を1度のスイッチ操作で解くのと同じだ。
１度のスイッチ操作でクリアできるボードをみつけて、Dr.リョウコが無事に部屋を通過できるのを助けよう。

Week2-B: 4-ライツアウト#

この問題では、複数のバイナリデータを同時に取り扱います。与えられた4枚のライツアウトボードのそれぞれが制約条件下で解けるかどうか、一つの量子回路で同時に判断できるよう工夫してみましょう。

例として、以下の4ボードの中から”１度のスイッチ操作でクリアできるボード”を発見する方法を考えてみましょう。 4ボードの初期状態は以下の２次元配列で与えられ、０と1がそれぞれ消灯と点灯を示しています。 lightsout4_ex=[[Board 0],[Board 1],[Board 2],[Board 3]]

from IPython.display import Image, display
Image('resources/2020-w2-b-4lightsout_ex.png')

_images/b18d385076061db7c0fd0c11f9c112d45abe03b7efbcbf2f009d32613b171b22.png

解答戦略#

ボードが一つなら、この例題は決定問題となります。

2-a問題のアルゴリズムを使って、出力に含まれる”１”を数え上げることで解決できるでしょう。

ボードが複数の場合、いくつかのアプローチが考えられます。

各ボードに対して、１ボード用のアルゴリズムを繰り返し適用する。
複数のボード情報を同時に保持し、一度のアルゴリズム実行で解決する。

以下のコンテンツでは、後者のアプローチに挑戦します。

ここで、全てのボード情報をQubit上に保持するにはどうすれば良いでしょうか？

ナイーブなデータ構造:　　9 Qubits/board * 4 boards > 32 qubits (ibm_qasm_simulatorの上限)。
重ね合わせ状態を準備する: $\vert Board 0\rangle + \vert Board 1\rangle + \vert Board 2\rangle + \vert Board 3\rangle$.
- 状態生成に用いる回路構成は非自明。
一つの解法としてqRAMが知られている。
- 長所: 直感的な実装が可能。
- 短所: 計算量が大きい。

もちろん他のより優れた方法を採用しても構いません。

ここではqRAMに焦点を当て、その構成と実装について説明します。

from qiskit import *
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from qiskit import Aer, execute
from qiskit_ibm_provider import IBMProvider
provider = IBMProvider()

qRAM: Quantum Random Access Memory#

古典的なコンピュータでは、RAM(Random Access Memory)は揮発性メモリの一種で、メモリアドレス $j$ を持ち、各アドレス $D_j$ に対応するバイナリデータを格納しています。

量子コンピュータのqRAMの場合、アドレスQubits $a$ は、$N$ 個のアドレスを重ね合わせ状態で持ち、対応するバイナリデータを状態ベクトルとしてデータQubit $d$ に格納しています。

$ \sum_{j}\frac{1}{\sqrt{N}}\vert j \rangle_{a}\vert 0 \rangle_{d}\xrightarrow{qRAM}\sum_{j}\frac{1}{\sqrt{N}}\vert j \rangle_{a}\vert D_{j} \rangle_{d} $

右辺の状態を”qRAM”、対応するゲート操作を”qRAM演算”と呼ぶことにします。

qRAM演算には $\mathcal{O}(N\log N)$ 個のゲートが必要ですが、直感的にバイナリデータの重ね合わせ状態を作ることができます。 qRAMは、HHLアルゴリズムをはじめとする量子機械学習の様々なアルゴリズムに応用されています。今回は、GroverのアルゴリズムにqRAMを適用してみましょう。

例題: データをqRAMから見つけよう#

$k_0, k_1, ... , k_{n-1}$ がこの順に格納された $n$ アドレスの qRAM を用意します。 Groverのアルゴリズムを使って，$m$という数字が格納されているアドレスを求めます。

$n = 4$
$k = [1,2,5,7]$
$m = 7$

qRAM演算#

以下にqRAM演算の実装例を示します。

address = QuantumRegister(2)
data = QuantumRegister(3)
c = ClassicalRegister(5)
qc = QuantumCircuit(address,data,c)

# address preparation
qc.h([address[0],address[1]])
qc.barrier()
# address 0 -> data = 1
qc.x([address[0],address[1]])
qc.ccx(address[0],address[1],data[2])
qc.x([address[0],address[1]])
qc.barrier()
# address 1 -> data = 2
qc.x(address[0])
qc.ccx(address[0],address[1],data[1])
qc.x(address[0])
qc.barrier()
# address 2 -> data = 5
qc.x(address[1])
qc.ccx(address[0],address[1],data[2])
qc.ccx(address[0],address[1],data[0])
qc.x(address[1])
qc.barrier()
# address 3 -> data = 7
qc.ccx(address[0],address[1],data[2])
qc.ccx(address[0],address[1],data[1])
qc.ccx(address[0],address[1],data[0])
qc.barrier()


#Check the qRAM　status
qc.measure(address[0:2], c[0:2])
qc.measure(data[0:3], c[2:5])
 
# Reverse the output string.
qc = qc.reverse_bits()

backend = Aer.get_backend('qasm_simulator')
job = execute(qc, backend=backend, shots=8000, seed_simulator=12345)
result = job.result()
count =result.get_counts()
print(count)

qc.draw(output='mpl')

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[2], line 1
----> 1 address = QuantumRegister(2)
      2 data = QuantumRegister(3)
      3 c = ClassicalRegister(5)

NameError: name 'QuantumRegister' is not defined

qRAM 内のデータ探索#

Groverのアルゴリズムを実行するには、$m$を含むアドレスQubitの符号を反転させます。また、拡散変換の前に別のqRAM演算でデータ Qubitを初期化する必要があります。

$

\[\begin{align*} \vert j \rangle_{a}\vert D_{j} \rangle_{d} \vert - \rangle_{f} \xrightarrow{oracle} \left \{ \begin{array}{l} -\vert j \rangle_{a}\vert D_{j} \rangle_{d} \vert - \rangle_{f}, D_{j} = m\\ \vert j \rangle_{a}\vert D_{j} \rangle_{d} \vert - \rangle_{f}, D_{j} \neq m \end{array} \right. \xrightarrow{qRAM} \left \{ \begin{array}{l} -\vert j \rangle_{a}\vert 0 \rangle_{d}\vert - \rangle_{f}, D_{j} = m \\ \vert j \rangle_{a}\vert 0 \rangle_{d}\vert - \rangle_{f},　D_{j}\neq m \end{array} \right. \end{align*}\]

$

ここで、$f$ はフラグQubitを表します。この例題の場合，C3X gateでオラクル操作を実行することができます。

以下にqRAMの例題の回路全体を示しています。

Image('resources/2020-w2-b-circuit_ex.png')

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[1], line 1
----> 1 Image('resources/2020-w2-b-circuit_ex.png')

NameError: name 'Image' is not defined

qRAMの実装についての考察#

上記の説明では、ナイーブなqRAM演算回路を紹介しました。
データ構造にもよりますが、ゲートの合成(等価変換)の技術を用いることで回路を簡略化することができます。また、RCCXなどの簡略化されたゲートは、あなたの実装におけるCNOTの節約に役立つかもしれません。以下にゲート合成の例を示します。

Image('resources/2020-w2-b-gatesynthesis_ex.png')

_images/0a8f6ff0d49a277ef02917fba13ce274f8c8eb6e9a6b86ffe82b72630a918fa6.png

ラーニング演習 II-B#

4-ライツアウトをqRAMを用いて解決してみましょう。

ボード状態が以下の lightsout4 = [[Board 0], [Board 1], [Board 2], [Board 3]] で与えられるとき、3回のスイッチ操作で解決できるボード番号を２進数形式で答える量子回路を作成してください。 (ex. Board 0 -> 00, 1->01, 2 -> 10, 3 -> 11)

量子回路では、パズルの答えとなるsolution(2bit)のみを観測してください。

提出形式は、lightsout4 を引数とし、QuantumCircuitを返す関数です（関数名は任意のものを付けて問題ありません）。lightsout4に別のデータセットをインプットしても機能するようにしてください。

尚、量子回路は 28 qubits 以内で実装してください。

説明で用いられているものと同じエンディアンで解答が得られるようになっているか注意してください。以下の関数を使っても構いません。

qc = qc.reverse_bits()

Image('resources/2020-w2-b-4lightsout_pr.png')

_images/758e4d14065499f11666a8bb91d3dd82cf5c836de00bc3ea169ab6c16433a544.png

lightsout4=[[1, 1, 1, 0, 0, 0, 1, 0, 0],[1, 0, 1, 0, 0, 0, 1, 1, 0],[1, 0, 1, 1, 1, 1, 0, 0, 1],[1, 0, 0, 0, 0, 0, 1, 0, 0]]

ヒント#

qRAM Data search のオラクルを適切なものに変更しましょう。
qRAM演算におけるデータ書き込みは任意の順序で行うことができます。アドレスの ハミング距離 や入力されるデータを考慮することでゲート数を削減できるかもしれません。

def week2b_ans_func(lightout4):
    ##### ここに量子回路を作成してください。
    ####  尚、異なる入力(lightout4)でも問題が解ける関数にしてください。異なる入力で検証を行います。
    
    return qc

解答例#

"""
 Week2-Aのライツアウトの関数
"""
# 初期化処理
def initialize_lights_out(qc,flip,oracle):
    qc.h(flip[:3])
    qc.x(oracle[0])
    qc.h(oracle[0])

# flipの1行目の操作する
def flip_1(qc,flip,tile):
    # push 0
    qc.cx(flip[0], tile[0])
    qc.cx(flip[0], tile[1])
    qc.cx(flip[0], tile[3])
    # push 1
    qc.cx(flip[1], tile[0])
    qc.cx(flip[1], tile[1])
    qc.cx(flip[1], tile[2])
    qc.cx(flip[1], tile[4])
    # push 2
    qc.cx(flip[2], tile[1])
    qc.cx(flip[2], tile[2])
    qc.cx(flip[2], tile[5]) 
    
# tileの1行目でflipの2行目を反転する
def inv_1(qc,flip,tile):
    # copy 0,1,2
    qc.cx(tile[0], flip[3])
    qc.cx(tile[1], flip[4])
    qc.cx(tile[2], flip[5])
    
# flipの2行目を操作する
def flip_2(qc,flip,tile):
    # apply flip[3,4,5]
    qc.cx(flip[3], tile[0])
    qc.cx(flip[3], tile[3])
    qc.cx(flip[3], tile[4])
    qc.cx(flip[3], tile[6])
    qc.cx(flip[4], tile[1])
    qc.cx(flip[4], tile[3])
    qc.cx(flip[4], tile[4])
    qc.cx(flip[4], tile[5])
    qc.cx(flip[4], tile[7])
    qc.cx(flip[5], tile[2])
    qc.cx(flip[5], tile[4])
    qc.cx(flip[5], tile[5])
    qc.cx(flip[5], tile[8])
    
# tileの2行目でflipの３行目を反転する
def inv_2(qc,flip,tile):
    # copy 3,4,5
    qc.cx(tile[3], flip[6])
    qc.cx(tile[4], flip[7])
    qc.cx(tile[5], flip[8])
    
# flipの3行目を操作する
def flip_3(qc,flip,tile):
    qc.cx(flip[6], tile[3])
    qc.cx(flip[6], tile[6])
    qc.cx(flip[6], tile[7])
    qc.cx(flip[7], tile[4])
    qc.cx(flip[7], tile[6])
    qc.cx(flip[7], tile[7])
    qc.cx(flip[7], tile[8])
    qc.cx(flip[8], tile[5])
    qc.cx(flip[8], tile[7])
    qc.cx(flip[8], tile[8])

# lightoutのオラクルを定義する
def lights_out_oracle(qc,tile,oracle,auxiliary):
    qc.x(tile[6:9])
    qc.mct(tile[6:9], oracle[0], auxiliary)
    qc.x(tile[6:9])
    
# flip操作のdiffusionゲートを操作する
def flipdiffusion(qc,flip):
    qc.h(flip[:3])
    qc.x(flip[:3])
    qc.h(flip[2])
    qc.ccx(flip[0],flip[1],flip[2])
    qc.h(flip[2])
    qc.x(flip[:3])
    qc.h(flip[:3])

解説（Week2-Aのライツアウトの関数）

Week2-Aのライツアウトの関数はWeek2-Aの解であるweek2a_ans_func(light)で使用される部品を関数として定義したものです。ライツアウトを解くための各関数の解説はWeek2-Aの範囲なので省略します。ここに記載した解とは別の解き方でも問題ありません。

"""
 関数定義
"""
# qRAMにlightoutを記録する
def qram_exercise(prob_array, qc, qr, qa):
    for k, board in enumerate(prob_array):
        if k//2==0:
            qc.x(qa[0])
        if k%2==0:
            qc.x(qa[1])            
        for j, i in enumerate(board):
            if i==1:
                qc.ccx(qa[0],qa[1],qr[j])
            j+=1
        if k//2==0:
            qc.x(qa[0])
        if k%2==0:
            qc.x(qa[1])

# flipの数をカウントする
def counter(qc,flip,auxiliary):
    for i in range(len(flip)):
        qc.mct([flip[i],auxiliary[0],auxiliary[1],auxiliary[2]],auxiliary[3],auxiliary[4:6])
        qc.mct([flip[i],auxiliary[0],auxiliary[1]],auxiliary[2],auxiliary[4])
        qc.ccx(flip[i],auxiliary[0],auxiliary[1])
        qc.cx(flip[i],auxiliary[0])
        
# flipの数をカウントする操作の逆操作を実行する
def revcounter(qc,flip,auxiliary):
    for i in range(len(flip)):
        qc.cx(flip[i],auxiliary[0])
        qc.ccx(flip[i],auxiliary[0],auxiliary[1])
        qc.mct([flip[i],auxiliary[0],auxiliary[1]],auxiliary[2],auxiliary[4])
        qc.mct([flip[i],auxiliary[0],auxiliary[1],auxiliary[2]],auxiliary[3],auxiliary[4:6])

# qRAM操作のdiffusionゲートを操作する
def addressdiffusion(qc,address):
    qc.h(address[:2])
    qc.x(address[:2])
    qc.cz(address[0],address[1])
    qc.x(address[:2])
    qc.h(address[:2])

解説

ここでは以下の解答で使用する関数を定義します。

qram_exercise(prob_array, qc, qr, qa)

量子回路qcの量子ビットqaで与えれるqRAMのアドレスに対して、対応するprob_arrayとして与えられたlightsout4配列を量子ビットqrに記録します。
$k=0$は$\ket{00}$に
$k=1$は$\ket{10}$に
$k=2$は$\ket{01}$に
$k=3$は$\ket{11}$に対応します。

counter(qc,flip,auxiliary)

量子回路qcのflipの1の数をカウントします。
カウントした結果はauxiliaryに2進数の形で記録されます。

revcounter(qc,flip,auxiliary)

counterの逆操作を実行します。
counterで実施したauxiliaryへの操作を初期化するために実施します。

addressdiffusion(qc,address)

量子回路qcのaddressに対するdiffusion操作です。この操作により求める解に対応する振幅を増幅します。

def week2b_ans_func(lightout4):
# 量子ビット & 回路定義
address=QuantumRegister(2)
tile = QuantumRegister(9)
flip = QuantumRegister(9)
oracle = QuantumRegister(1)
auxiliary = QuantumRegister(6)
c = ClassicalRegister(2)
qc = QuantumCircuit(address, tile, flip, oracle, auxiliary, c)

# addressを初期化
qc.h(address[0:2])

# ライツアウト処理の初期化
initialize_lights_out(qc,flip,oracle)

# 各アドレスに対してlightsoutに対応するtileを作成
qram_exercise(lightsout4, qc, tile, address)

# ライツアウトの解の振幅を増幅処理を2回繰り返す
for i in range(2):
    flip_1(qc,flip,tile)
    inv_1(qc,flip,tile)
    flip_2(qc,flip,tile)
    inv_2(qc,flip,tile)
    flip_3(qc,flip,tile)

    lights_out_oracle(qc,tile,oracle,auxiliary)

    flip_3(qc,flip,tile)
    inv_2(qc,flip,tile)
    flip_2(qc,flip,tile)
    inv_1(qc,flip,tile)
    flip_1(qc,flip,tile)

    flipdiffusion(qc,flip)

# 3量子ビットのflip情報を9量子ビットに変換
flip_1(qc,flip,tile)
inv_1(qc,flip,tile)
flip_2(qc,flip,tile)
inv_2(qc,flip,tile)

# flipの１をカウント
counter(qc,flip,auxiliary)

# ３Push以内に解ける解の位相を反転
qc.x(auxiliary[2])
qc.x(auxiliary[3])
qc.ccx(auxiliary[2],auxiliary[3],oracle[0])
qc.x(auxiliary[2])
qc.x(auxiliary[3])

# flipのカウント処理をリセット
revcounter(qc,flip,auxiliary)

# flip情報の9量子ビット化をリセット
inv_2(qc,flip,tile)
flip_2(qc,flip,tile)
inv_1(qc,flip,tile)
flip_1(qc,flip,tile)

# ライツアウトの振幅を増幅処理をリセット
for i in range(2):
    flipdiffusion(qc,flip)
    flip_1(qc,flip,tile)
    inv_1(qc,flip,tile)
    flip_2(qc,flip,tile)
    inv_2(qc,flip,tile)
    flip_3(qc,flip,tile)

    lights_out_oracle(qc,tile,oracle,auxiliary)

    flip_3(qc,flip,tile)
    inv_2(qc,flip,tile)
    flip_2(qc,flip,tile)
    inv_1(qc,flip,tile)
    flip_1(qc,flip,tile)

# 各アドレスに対してlightsoutに対応するtileを作成する処理をリセット
qram_exercise(lightsout4, qc, tile, address)

# 求める解を持つアドレスの振幅を増幅
addressdiffusion(qc,address)

# アドレスを測定
qc.measure(address,c[0:2])

# アドレスの順序を反転
qc = qc.reverse_bits()

return qc

  Cell In[3], line 3
    address=QuantumRegister(2)
    ^
IndentationError: expected an indented block after function definition on line 1

解説

Groverのアルゴリズムを用いて求める解を持つqRAMのアドレスを求めます。

使用量子ビット

address（2量子ビット）:qRAMのアドレス
tile（9量子ビット）:ライツアウトのタイルの状態
flip（9量子ビット）:タイルの操作の実施可否
oracle（1量子ビット）:Groverのアルゴリズムを解くための補助量子ビット
auxiliary（6量子ビット）:multi cxゲートやflipに含まれる1のカウントなどに使用する補助量子ビット
c（2古典ビット）アドレスを観測するための古典ビット

求める解を持つqRAMのアドレスを求める手順は以下のとおりです。ここで2〜11までの処理の繰り返し回数は1としています。（$\frac{\pi}{4}\sqrt{2^{2}}-\frac{1}{2} \fallingdotseq 1$）

address, flip, oracleを初期化（address, flipは均一な重ね合わせ状態に、oracleは補助量子としてx, hゲートを作用させる）
qRAMの各アドレスに対してlightsout4リストの解をtileにマップ
Week2-Aでの解に基づきGroverのアルゴリズムでライツアウトの解を求める（ここでは繰り返し回数は2回）
3で求めたライツアウトの解（3量子ビット）を9量子ビットに変換
flipに含まれる1をカウント
3Push以内に解ける解を探索
flipのカウント処理を逆操作でリセット
ライツアウトの解の9量子ビットへの変換を逆操作でリセット
ライツアウトの解を求める操作を逆操作でリセット
qRAMの各アドレスに対してlightsout4リストの解をtileにマップする操作を逆操作でリセット
求める解を持つアドレスを振幅増幅
求める解を持つアドレスを測定
測定したアドレスの順序を反転

qc = week2b_ans_func(lightsout4)

from qiskit import IBMQ, Aer, execute
backend = provider.get_backend('ibmq_qasm_simulator')
job = execute(qc, backend=backend, shots=8000, seed_simulator=123456)
result = job.result()
count = result.get_counts()

score_sorted = sorted(count.items(), key=lambda x:x[1], reverse=True)
final_score = score_sorted[0:40]
final_score

[('01', 7758), ('10', 99), ('11', 73), ('00', 70)]