IBM Quantum Challenge 2020 体験記
こんにちは、sakumatchoです。 2020/11/9 ~ 2020/11/30の22日間実施されたIBM Quamtum Challenge 2020に参加した体験記を書きます。
対象とする読者
- これから量子プログラミングを始めたいという方
- すでに学んでいるけど実践する場・挑戦する場が欲しいという方
- 惜しくも参加できず内容が気になる方
など
目次
- 自己紹介
- IBM Quantum Challengeとは
- IBM Quantum Challenge 2020 の出題内容
- 感想
自己紹介
昔
- 学生時代の専門：
超伝導量子干渉計(SQUID)を使って、半導体量子ドット中の光励起電子スピンの磁化やというカイラルP波超伝導体といわれている新奇超伝導体の磁化について研究する超伝導など磁気物性の実験屋でした
- 量子情報処理・量子計算との関わり：
- FIRST 量子情報処理プロジェクトに関わっていました
- 量子情報関東StudentChapterの運営委員やっていました
- 論文(arXivには上げてないので見られない人多いと思います、すみません。)
今
- 職業：データサイエンティスト
- 趣味：
- 量子計算(趣味で量子計算だなんて良い時代になったもんだ)
- プログラミング
- 水泳(観る・やる、両方)
- マインド：
- 機械学習や量子計算を現実の問題に適用させようとしています
- 一人でも量子計算に興味を持つ人が増えてほしいと願っています
IBM Quantum Challengeとは
こちらで記載されていますが、IBMが年に一度主催している量子コンピューターの競技型オンライン・プログラミング・コンテストです。 コンテストではありますが、初心者向けの導入から課題が与えられるので、Pythonさえ書ければ量子プログラミング・量子計算が初めての方でも参加可能です。
IBM Quantum Challenge 2020 の出題内容
詳細は僕のGitHubでノートブックを公開していますのでご確認ください。 ここでは概要だけ示します。
なお、公式でも公開されています。
期間は3週間で、問題は1A, 1B, 2A, 2B, Finalの全5題でした。
1連の問題を解くとGroverの探索アルゴリズムを使いこなせるようになっており、また量子並列性や重ね合わせ状態の威力を実感できる内容となっています。
それぞれの課題では、前半で基礎知識を導入し、後半で問題が1題出題され、量子回路を構成する関数を作成して関数を提出します。
提出用に運営が作成した関数に関数を引数として渡し、チェック処理が走って構成した量子回路が必要な入出力や条件など満たしていれば正答となり次の課題に進むことができます。
なお、導入部ではIBMQ ExperienceのナビゲータであるDr. Ryoko(量子(りょうこ)ちゃん)とのアドベンチャーストーリーが展開され、課題を解くごとに先に進む話がまた面白いです(笑)
僕は今回期間内に2Bまで解くことができ、Finalはいまだ解けていません（笑） 解けた人ホントすごいです！
なお、IBMからbadgeをもらいました！
1A：量子全加算器
導入
- 量子ゲートの使い方
- 古典論理ゲート(AND, OR, NOT, XOR, NANDなど)を量子ゲートで再現
- 古典半加算器を量子ゲートで再現
- 量子回路のコスト計算の方法
古典半加算器
図1が通常の論理回路(量子と対比して古典回路とここで呼ぶことにします。)で作成される半加算器です。 回路の上側で左側が弧を描いている部品がXORゲート(排他的論理和)で、下側で半楕円の部品がANDゲート(論理積)です。
量子半加算器
図2が量子回路で作成した半加算器です。 回路を縦破線で区切って一番左でXORゲート、中央でANDゲートを作成し、最後に2と3の量子ビットを測定して計算結果の出力としています。
という感じに、集合演算は古典回路を量子で再構成することで同じように実行することができます。 「なんだ、じゃあ量子コンピュータも従来のコンピュータとできること変わらないのか、、」なんてことはありません！ 後でGorverのアルゴリズムを使うと分かりますが、論理演算を並列に実行できるところが量子コンピュータのすごいところです！
課題
下記の真理値表を満たす全加算器を量子ゲートだけで実装します。 僕が提出した回路はオーソドックスなものですが、別解もあり1問目からやりこみが発生したようです。
全加算器の真理値表
| A(input) | B(input) | X(carry input) | S(sum) | C(carry out) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
提出した全加算器
図3が提出した回路で、課題の入力に合わせて最初にXゲートを加えている以外は基本的には先の半加算器を2つ組み合わせた構造です。 図4の古典全加算器と同じ構造になっていることを確かめてみてください。
古典全加算器
公式解答
学べる事・身につくこと
- 量子ゲートを使った論理演算の方法
1B：Groverのアルゴリズムの反復回数
導入
- Groverのアルゴリズム概要
- オラクルと確率振幅の反転増幅について
- Groverのアルゴリズムの実装例
- 外部入力(auxiliary bits)を用いた場合のGroverのアルゴリズムの実装例
- Groverのアルゴリズムの繰り返し回数と確率振幅
Groverのアルゴリズムの実装(外部入力を用いた場合)
図4の回路を構成して実行すると、最初に0と1はアダマールゲートが実行されることによって|00>, |01>, |10>, |11>の4状態が等確率で生成されるはずですが、結果は図5のように|11>だけが残ります！
繰り返し回数と確率振幅の大きさの関係
4量子ビットを使って|0000>から|1111>の中から|0111>だけ増幅するという例題で回路は図6で、Groverを3回繰り返している例です。
ここでのGroverの繰り返し回数はオラクル(一番縦に長いMCT)の数を数えてください。
3本あるはずです。
その|0111>の確率振幅の大きさは図7のように繰り返し回数に対してで変化します。
課題
例題と同様に使う量子ビットの数を7にして、[tex: N=27 = 128]個の状態の中から、|0000111>だけを増幅しその確率振幅の大きさが最大になる繰り返し回数を求め、回数を答えます。
例題と同様の回路(図6)を7量子ビット用に直して実行すると図8のような結果が得られます。 図からは8回で最大となるので、これが答えです。
公式解答
学べる事・身につくこと
- Groverのアルゴリズムの基本
2A：Groverのアルゴリズムでライツアウトパズルを解く
導入
- ライツアウトパズルとは
ライツアウトパズル
図9に示すのがライツアウトパズルと解答例です。
初期の点灯状態がinputの配列で与えられ、1が点灯で0が消灯を示します。
対してすべてのマスを消灯状態にする正解状態をoutput配列として求め、1がpushで0がunpushを示します。
課題
例題と同じく3 x 3のライツアウトパズルをGroverのアルゴリズムだけを使って解きます。
入力は3 x 3 = 9マスの点灯状態を示す0/1の配列数9の任意の配列とし、パズルの解としてpushするボタンの0/1を示すやはり配列数9の配列を測定結果として取り出す量子回路を構成する関数を作成し、関数を提出します。
ただし制約が大きく2つあります。
- 外部のソルバなどを使ってパズルを解くことは不可でGroverアルゴリズムだけを使うこと
- 出題された問題だけでなく、任意のライツアウトパズルを解ける回路であること
提出した回路
図11が僕が提出した量子回路(長くてデバッグがしんどい、、)で、図12がその回路の計測結果です。
1つの状態だけ確率が飛びぬけていて、それが実際正解の状態で[1, 1, 0, 0, 1, 0, 1, 0, 1]です。
僕のGitHubではこの量子回路を構成するまでの検証も含めてご紹介しています。
公式解答
学べる事・身につくこと
- Groverのアルゴリズムの応用
2B：Groverのアルゴリズムで複数のライツアウトパズルを同時に解く
導入
- 4つのライツアウトパズルの重ね合わせ状態
- QRAM
4つのライツアウトパズルの重ね合わせ状態
重ね合わせ状態のライツアウトってどういうことだよ、って突っ込みたいところですが、
このストーリによるとこのライツアウト自体が量子ビットでできていてこの4状態でfluctuateしているそうです。
量子の世界の話なら仕方ないですね、解きましょう。
今回はpushするマスの配列を求めて終わりではなく、それも求めた上で各面のpushするマスの数を数えます。 例題では1回で解ける面を求めよというものでした。
古典の世界なら順に解いていけば解けるのですが、量子の世界だそうで1度で4面解いて目的の面を答えないといけません。
でも大丈夫、Groverならできるそうです。
qRAM
課題
図13と同様な3 x 3のライツアウトパズルが4面同時に出題され、その中に一つだけ3箇所だけpushして解ける問題があり、それが何番目の面かをGroverのアルゴリズムで当てるというものです。 提出するのは問題を解いて2ビットで表された0~3の面番号を測定して出力するような量子回路を構成する関数です。
図で示すと長いのでノートブックを参照してください。
コンセプトとしては公式のヒントにある図15の回路です。
オラクルの中でオラクルを記述するせいで量子回路が長くなります。
公式解答
学べる事・身につくこと
- qRAM
- オラクルの応用
Final：Groverのアルゴリズムで複数のアステロイドパズルを解く
公式からのノートブック公開が12/14現在ありませんので、解説を書けていませんが僕のノートブックをご参照ください。
導入
- アステロイドパズル
アステロイドパズルとは図16に示したように面に配置された星を縦横1列まとめて消せます。 面に配置された星をすべて消去できればクリアです。
課題
4 x 4のアステロイドパズルが16面同時に出題され、15面は縦横計3列消せばクリアできます。 その中に一つ含まれている3列消しでは解けない面が何番か当てることが課題です。 人間が目で見て解くことも可能ですが、やはり重ね合わせで出題されるのでGroverのアルゴリズムで解かないといけないという制約があります。 この問題を解いて面番号を出力する量子回路を構成し提出します。
まだ解けていません。 3列消去で解ける15面の解を抽出することはできましたが、それぞれの面番号と3列消去で解ける・解けないというフラグを結び付けられていません、、 3列消去で解ける問題は4列以上を消去しても解けるので、そのあたりの枝刈りもしないといけません。 これを解けた人が全体の17%くらいで200人くらいいるみたいですが、すごいです。
学べる事・身につくこと
- これでGroverのアルゴリズムマスター
- 枝刈りなど数理的な素養も試されている感じがあります
感想
- Groverのアルゴリズムはデータベース探索としか知りませんでしたが、データベースだけでなくより広い問題を解くことだできる便利なアルゴリズムであることが分かった。
- ライツアウトもアステロイドもトイプロブレムだけれども、量子計算を使って問題を解くことが出来て嬉しかった。 量子情報処理を知って10年経って「量子計算スゲー」って思えました。 (それまでは論文のイントロとかで、この結果は量子計算にも応用ができるらしいとか、量子計算で並列計算ができるらしいとか字面でしか知らなかった)
- こういう問題を解いていった結果のノウハウが溜まって、いずれ実際の問題を解けるようにしていきたい！
- 今回はQASMシミュレータ上での計算だったので、実機で動くのか知りたい。
- 来年も開催されたら、最後まで解きたい！
