sparse-dense by FoYo: ドイチュのアルゴリズムで量子計算のこころに触れる（続）

2022年9月18日日曜日

ドイチュのアルゴリズムで量子計算のこころに触れる（続）

　前回の記事で、ドイチュの量子アルゴリズムを述べた。今回は、その拡張版であるドイチュ・ジョサのアルゴリズムを試した。

■ドイチュ・ジョサのアルゴリズム

　この場合も、値として0か１をとる２値関数f(x)が定数関数か平衡関数かを、ただ１回の関数の評価で判定できるという不思議なアルゴリズムである。今回は、変数xは、0,1,2, ... , 2ⁿ-1を取るように値域が拡大されている。この場合の定数関数とは、どのxに対してもf(x)の値は同一であり、平衡関数とは、半分のxに対してはf(x)=0であり、残り半分のxに対してはf(x)=1ということである。

　従来のコンピュータで平衡関数/定数関数を判定するには、f(x)を最大2^n-1+1回調べる必要があるが、ドイチュ・ジョサの量子アルゴリズムでは、ただ１回で済む、という素晴らしさがある。

■ドイチュ・ジョサのアルゴリズムの量子回路

　前回同様、渡邉靖志著[1]のドイチュ・ジョサのアルゴリズムとその量子回路の説明を参考にさせていただいた。この著書には、簡潔にその真髄が書かれている。図１に示す通り、特に難しい数式を含むわけではないが巧妙に組み立てられているので、じっくりと腰を据えて理解する必要がある。ここには詳細説明は書けないが、ともかく、この量子回路によって最終的に測定した結果、n個の0の列 "000...0" が観測される可能性が0%であれば、平衡関数であるということだ。

■IBM Quantum実機での実行

　理解を確認するため、n=3の場合の量子回路図を作り、それをIBM Quantum実機で動かしてみた。その際、Qiskitの解説[2]を参考にさせていただいた。図２に定数関数の場合の、図３に平衡関数の場合の判定結果をそれぞれ示した。いずれも納得できる結果だが、現状の実機ではノイズのために幾らかの誤差が生ずる。すなわち、理論的には観測されないはずのビット列も若干観測されたが、結果の判断に影響はない。