銀の光と碧い空

クラウドなインフラとC#なアプリ開発の狭間にいるエンジニアの日々

Q#のDeutsch–Josza Algorithmのサンプルコードをのぞいてみる

Q#

ひとりAdvent Calendar 15日目です。

adventar.org

今日はQ#のサンプルにのっているDeutsch–Josza Algorithmのサンプルコードをのぞいてみたいと思います。アルゴリズムそのものの説明ではなく、そのアルゴリズムとテストコードをどのようにQ#で実装しているかの説明になります。このSimpleAlgorithmの中で実装しているアルゴリズムの一つがDeutsch–Josza Algorithmです。

https://github.com/Microsoft/Quantum/tree/release/v0.3.1810/Samples/src/SimpleAlgorithms

Deutsch–Josza Algorithmそのものについてはこちらのブログがわかりやすかったです。

hydrakecat.hatenablog.jp

http://quantum.classcat.com/category/deutsch-jozsa-algorithm/

Deutsch–Josza Algorithmというのはある関数f(x)の性質を求めるアルゴリズムで、関数f(x)というのはnビットの入力xに対しすべて0あるいは1を返す定数(constant)な関数か、それぞれ半分の確率で0,1を返すバランスされた(balanced)な関数のどちらかです。与えられた関数f(x)がどちらの性質を持っているかを求めるアルゴリズムになります。

で、このサンプルコードでは、Q#への入力が関数の入力xのビット数と、1を返すビットのインデックスを配列で渡しています。

var balancedTestCase = new QArray<long> { 1, 2 }; 
if (DeutschJozsaTestCase.Run(sim, 2, balancedTestCase).Result)
{
    throw new Exception("Measured that test case {1, 2} was constant!");
}

Quantum/Driver.cs at release/v0.3.1810 · Microsoft/Quantum · GitHub

2ビットの入力に対しbalancedTestCaseが定義されていますが、これは2ビットの入力のインデックス0~3に対し、1と2のときだけ1を返す関数を渡しています。また、3ビットの入力に対しては、すべてのインデックス0~7で1を返すconstantTestCaseを渡しています。

var balancedTestCase = new QArray<long> { 1, 2 }; 

var constantTestCase = new QArray<long> { 0, 1, 2, 3, 4, 5, 6, 7 };

つまり4ビットの入力のときのconstantTestCase は 0から15までの配列になりますし、balancedTestCase はその中から任意に選んだ8個の配列となります。

さて、この入力を渡されたQ#コード側を見てみます。IsConstantBooleanFunctionというのは後で見ますが、名前のとおり関数f(x)がconstantな場合にtrueを返すoperationです。で、この関数f(x)を表現しているのが、BooleanFunctionFromMarkedElementsというfunctionになります。引数がQubitの数を表すnQubitsとその入力ビットに対して1を返すインデックスの一覧を表した配列のmarkedElementsです。そした返り値が(Qubit[] => Unit)となっていますが、これはQubit[]を引数にとり、返り値がUnitなOperationです。つまりOperationを返すfunctionとなります。またこのfunctionの実装にある_は、返り値でかえされたoperationが評価される際に引数のプレースホルダとなる値です。

operation DeutschJozsaTestCase (nQubits : Int, markedElements : Int[]) : Bool {        
    return IsConstantBooleanFunction(BooleanFunctionFromMarkedElements(nQubits, markedElements), nQubits);
}

function BooleanFunctionFromMarkedElements (nQubits : Int, markedElements : Int[]) : (Qubit[] => Unit) {        
    return BooleanFunctionFromMarkedElementsImpl(nQubits, markedElements, _);
}

Quantum/SimpleAlgorithms.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

次に、BooleanFunctionFromMarkedElementsImplを見て、どのように入力Qubitに対し指定されたインデックスのときに1を返すように実装するか見ていましょう。いわゆる関数f(x)に対するオラクル関数を実装する部分でもあります。

operation BooleanFunctionFromMarkedElementsImpl (n : Int, markedElements : Int[], qs : Qubit[]) : Unit {
    
    let target = qs[Length(qs) - 1];
    let inputs = qs[0 .. Length(qs) - 2];
    
    let nMarked = Length(markedElements);
    
    for (idxMarked in 0 .. nMarked - 1) {
        (ControlledOnInt(markedElements[idxMarked], ApplyToEachCA(X, _)))(inputs, [target]);
    }
}

Quantum/SimpleAlgorithms.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

ほぼほぼメインはControlledOnIntのところです。ControlledOnIntはMicrosoft.Quantum.Canonに組み込みのoperationで第一引数で指定した状態のときのみ、第二引数で指定したunitary operatorをtargetに適用するようなoperatorを返すoperatorです。

ControlledOnInt function (Microsoft.Quantum.Canon) | Microsoft Docs

なんのこっちゃという感じですが、第一引数で指定した状態というのは、markedElementsで指定しているような状態のインデックスであらわされます。2量子ビットなら0から3、３量子ビットなら0から7という0から2n-1のインデックスを状態として指定します。つまり、markedElementsが状態のインデックスの配列で表現されていたのはこのoperationに値を渡したいためだったと思われます。適用したいunitary operatorは0から1に反転させたいので、PauliXゲートになるのですが、ControlledOnIntが返すoperatorはQubitの配列を入力として受け取るようになっています。実際にはtargetである一つのQubitのみを入力に渡せばよいのですが、配列として渡せるように、ApplyToEachCAというoperatorを引数で渡したQubit配列の要素全部に適用するoperatorをかませています。

ApplyToEachCA operation (Microsoft.Quantum.Canon) | Microsoft Docs

ちなみにApplyToEachCAのCAはControlledかつAdjointなoperatorのときに使えることを意味しており、ApplyToEach、ApplyToEachC、`ApplyToEachAがほかに用意されています。

ようやく肝心のアルゴリズムの実装であるIsConstantBooleanFunctionに入ります。アルゴリズムがわかっていればこの実装は比較的簡単かと思います。

アルゴリズムの流れは

  1. 測定結果を確保する長さnの配列を用意
  2. 入力用nビットと出力用1ビット、合わせてn+1ビットのQubitを用意する
  3. 入力用nビットは0(初期化時に0なのでそのまま)、出力用1ビットは1(初期化時に0なので反転させる)にセットする。
  4. 全部のビットにHadamard変換を施す
  5. 関数f(x)のオラクル関数に入力として渡す
  6. 入力用nビットにHadamard変換を施す
  7. 入力用nビットを測定しつつ、0にリセットする
  8. Qubitのusingを抜けるので、残りの出力用1ビットもリセットする
  9. constantな関数であれば、全部の測定結果が0なので、この場合のみtrueを返す

となっています。ApplyToEachはfor文でも書けます。MResetZは以前のバージョンでは測定とリセットが別のoperationだったはずですが、一つのoperationにまとまっています。qubits[0 .. n - 1]は0からn-1まで(n-1を含む）部分配列です。C# 8で導入予定のRange型に似ていますが末尾を含むのが違っていますので注意しましょう。Q#が末尾を含むのはfor (idx in 0 .. n - 1)みたいにfor文のインデックス範囲を指定する際にも利用するためだと思われます。

operation IsConstantBooleanFunction (Uf : (Qubit[] => Unit), n : Int) : Bool {
    
    mutable resultArray = new Result[n];
    using (qubits = Qubit[n + 1]) {
        
        X(qubits[n]);
        
        ApplyToEach(H, qubits);
        
        Uf(qubits);
        
        ApplyToEach(H, qubits[0 .. n - 1]);
        
        for (idx in 0 .. n - 1) {
            set resultArray[idx] = MResetZ(qubits[idx]);
        }
        
        Reset(qubits[n]);
    }
    
    return ForAll(IsResultZero, resultArray);
}

Quantum/SimpleAlgorithms.qs at release/v0.3.1810 · Microsoft/Quantum · GitHub

という感じでDeutsch–Josza Algorithmのサンプルは作られています。アルゴリズムそのもの部分はそこまで複雑ではないですが、シンプルな量子ゲートのみでは実装が面倒そうなところを1つのoperationで実行できます。また、古典的コンピューターであるC#の入力からどのように準備するかという部分も参考になるかと思います。