ライツアウトパズル（2020年 Week2a）

ライツアウトパズル（2020年 Week2a）#

ライツアウトは有名なパズルゲームです。プレーヤーに格子状に並べられたライトが与えられます。このうちいくつかは点灯しており、いくつかは消灯しています。この問題の目的は、ライトを全て消灯させることです。各ライトにはスイッチがついており、それを押すことで点灯/消灯させることができます。しかしながらこのライトは少し特殊で、あるライトのスイッチを押すと、連動して上下左右の隣接したライトの状態も切り替わってしまいます。

例題#

以下の図は、3x3のライツアウトパズルの例です。各ライトには0から8までのラベルが付いています。バイナリのリストを使用して与えられた盤面を表すことができます。1はオンになっているライトを表し、0はオフになっているライトを表します。以下のリスト(lights)は、この例の初期盤面を表しています（ライト 3、5、6、7がオンで、残りはオフです）。

lights = [0, 0, 0, 1, 0, 1, 1, 1, 0]

例題は、図で示されているように、0、3、4のスイッチを操作することで解決できます。少し遊んでみると、すぐにこのパズルゲームの2つの重要な特性に気付くでしょう。

  1. 同じスイッチを複数回押す必要はありません。

  2. スイッチを押す順序は特に意味を持ちません。

従って、初期の盤面同様にバイナリのリストでパズルの解を表現できます。 ただし、ここでは0と1の意味が盤面のそれと異なります。1はスイッチを切り替えることを表し、0はスイッチを切り替えないことを表します。

solution = [1, 0, 0, 1, 1, 0, 0, 0, 0]

ラーニング演習 II-A#

第1週で学んだことをいかして、ライツアウトをGroverのアルゴリズムを使って解いてみましょう！

Groverのアルゴリズムを使ったライツアウトパズル

以下の盤面を解くための量子回路を作成してください。提出する量子回路では、パズルの答えとなる**solution(9bit)のみを観測してください。** 提出形式は、lightsを引数とし、QuantumCircuitを返す関数です（関数名は任意のものを付けて問題ありません）。異なる入力(lights)でも問題が解ける関数にしてください。異なる入力で検証を行います。

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

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

qc = qc.reverse_bits()

Hint

この問題を解くにはWeek1-Bのものよりも複雑なオラクルが必要になるでしょう。補助量子ビットを追加することでオラクル部分の設計が容易になりますが、その取り扱いには注意が必要です。オラクル部分の終了時点では全ての補助量子ビットが初期状態に戻っているいる必要があります（この操作はUncomputationと呼ばれることもあります）。
2019年のIBM Quantum Challenge のWeek3はこの概念の理解に役立つかもしれません。

# 初期状態は以下のリストで与えられます。 
# 回路の入力としてお使いください。
lights = [0, 1, 1, 1, 0, 0, 1, 1, 1]

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

# 提出用コード
from qc_grader import prepare_ex2a, grade_ex2a, submit_ex2a

# 以下のprepare_ex2a()関数で回路を実行してください。
# prepare_ex2a()関数はQuantumCircuitのみを引数として、execute()関数のように働きます。
job = prepare_ex2a(week2a_ans_func)

result = job.result()
count = result.get_counts()
original_problem_set_counts = count[0]

original_problem_set_counts
# 最も観測回数が多いビット列が解として扱われます。
Contents