$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

◇◇Microsoft Q# Coding Contest – Summer 2020 A7 - Distinguish Y, XZ, -Y and -XZ◇◇

☆問題URL

https://codeforces.com/contest/1357/problem/A7

☆問題の概要

1 qubitに対する演算$unitary$が与えられ、ここで$unitary$は$Y, XZ, -Y, -XZ$のうちどれかである。$unitary$を1度だけ呼び出して、それが$Y$なら0、$-XZ$なら1、$-Y$なら2、$-XZ$なら3を返せ。

☆解法

はじめに $$Y = i\ket{1}\bra{0} - i\ket{0}\bra{1}$$ であり \begin{align*} XZ &= \left( \ket{1}\bra{0} + \ket{0}\bra{1} \right)\left( \ket{0}\bra{0} - \ket{1}\bra{1} \right) \\ &= \ket{1}\bra{0} - \ket{0}\bra{1} \end{align*} であることから $$XZ = -iY$$ と書き換えることができて、結果的にこの問題は$Y, iY, -Y, -iY$という4つの演算子を識別する問題であると言い換えることができます。

この4つの演算子の違いはグローバル位相だけなので、通常は状態の測定確率の違いとして現れることはありません。そこで、量子位相推定というアルゴリズムを使って識別することを考えます。

○量子フーリエ変換

量子フーリエ変換とは離散フーリエ変換の量子実装であり、ある状態$\ket{x}$を $$\ket{x} \rightarrow \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi i\frac{xy}{N}}\ket{y}$$ と変換する演算です。直感的には、全状態の重ね合わせ $$\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}\ket{y}$$ について、それぞれの基底を回転させたものであって、それぞれの回転角は一周($2\pi$)を$N$等分したものを1単位として$x, y$にそれぞれ比例します。ここで、$N$は一般に基底の桁数$n$を用いて$N = 2^n$となります。

量子位相推定では、この量子フーリエ変換の逆変換を用いて位相を近似します。

○量子位相推定

量子位相推定とは、あるユニタリ演算子$U$がその固有状態$\ket{\psi}$に対して $$U\ket{\psi} = e^{2\pi i\theta}\ket{\psi}$$ のように与えられるとき、その$\theta$を近似するアルゴリズムです。直感的には、状態の位相を変化させる演算を用いてフーリエ基底での表現を直接作ってしまってから量子フーリエ逆変換で計算基底に戻して測定するというイメージになると思います。

量子位相推定の手順は以下のようになっています。前提条件として、ユニタリ演算子のControlled派生が作れることと、測定したいユニタリ演算子の固有状態$\ket{\psi}$がわかっている必要があります。

$n$個の$\ket{0}$状態（カウントレジスタ）と固有状態$\ket{\psi}$の直積状態を準備する $$\ket{\psi_0} = \ket{0}^{\otimes n}\ket{\psi}$$ このカウントレジスタの桁数が近似の精度に影響します。
すべてのカウントレジスタにアダマール・ゲートを作用させ、全状態の等しい重ね合わせ状態を作る \begin{align*} \ket{\psi_1} &= H^{\otimes n}\ket{\psi_0} \\ &= \frac{1}{\sqrt{2^n}}\sum_{y=0}^{N-1}\ket{y}\ket{\psi} \end{align*}
カウントレジスタの$i$桁目を制御qubitに、$\ket{\psi}$をターゲットqubitとして$Controlled\;U$演算を$2^i$回作用させる \begin{align*} \ket{\psi_2} &= U_{0,n}U_{1,n}U_{1,n}U_{2,n}U_{2,n}U_{2,n}U_{2,n}...\ket{\psi_1} \\ &= \frac{1}{\sqrt{2^n}}\sum_{y=0}^{N-1}e^{2\pi i(\theta y)}\ket{y}\ket{\psi} \end{align*} この操作は、カウントレジスタが$\ket{y}$であるような状態に$U$を$y$回作用させることに相当します。
量子フーリエ逆変換によって、計算基底 $$\ket{2^n\theta}$$ を得る。ここで、量子フーリエ変換によって計算基底$\ket{x}$を変換した結果が $$\frac{1}{\sqrt{2^n}}\sum_{y=0}^{N-1}e^{2\pi i\frac{xy}{2^n}}\ket{y}$$ であることから、比較して$\frac{x}{2^n} = \theta$であり、$\ket{\psi_2}$は計算基底$\ket{2^n\theta}$を量子フーリエ変換したものであるということができます。

定義より$\theta$は回転角そのものではなく回転数を表していることから$0\leq\theta\lt1$であり、$2^n\theta$は「回転角0から$2\pi$までの間に$2^n$個の目盛を振った際に何番目に相当するか」を表していると解釈できます（なお、回転角が$n$桁の2進小数で正確に表せない場合でも近い基底の測定確率が大きくなるそうです）

今回の問題では$\theta = \frac04, \frac14, \frac24, \frac34$の4つを区別したいので、カウントレジスタは2桁で必要充分です。また、演算子$Y$の固有状態は$\ket{\psi} = \frac{1}{\sqrt{2}}\left( \ket{0} + i\ket{1} \right)$です。

これで、この問題が解けました。

☆ソースコード

Q#にはQuantumPhaseEstimationという関数があるため、量子位相推定を自前で実装する必要はありません。

                
namespace Solution {
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Characterization;
    open Microsoft.Quantum.Oracles;

    operation unitary_power(unitary : (Qubit => Unit is Adj + Ctl), power : Int, target : Qubit[]) : Unit is Adj + Ctl
    {
        for(_ in 1..power)
        {
            unitary(target[0]);
        }
    }

    operation Solve (unitary : (Qubit => Unit is Adj+Ctl)) : Int
    {
        using((countRegister, eigenState) = (Qubit[2], Qubit())){
            // eigenState -> 1/sqrt(2) (|0> + i|1>)
            H(eigenState);
            S(eigenState);

            QuantumPhaseEstimation(DiscreteOracle(unitary_power(unitary, _, _)) ,[eigenState] ,BigEndian(countRegister));

            let ans = MeasureInteger(BigEndianAsLittleEndian(BigEndian(countRegister)));

            ResetAll(countRegister);
            Reset(eigenState);

            return ans;
        }
    }
}

☆参考

量子フーリエ変換 - Qiskitを使った量子計算の学習（2021/09/22アクセス）
量子位相推定アルゴリズム (Quantum Phase Estimation) とは - 物理とか（2021/09/22アクセス）

戻る