2019-06-16

Groverのアルゴリズム

勉強中の量子アルゴリズムについてまとめます。間違いがありましたら、コメントください。

Groverのアルゴリズムはnビットで表される $2^{n}$ 個のビット列から、1個のビット列を探し出す量子アルゴリズムです。

アルゴリズムはおおまかには以下です。 $N = 2^{n}$ とします。

量子ビットをn個用意して、 $N$ 個の状態の重ね合わせ状態を作る。各状態が各ビット列に対応する。ここで、各状態の確率振幅が等しく $\frac{1}{\sqrt{N}}$ になるようにする。
重ね合わせ状態のうち、探索対象の状態の確率振幅にだけ-1を掛ける
確率振幅の平均値 $\mu = \sum_{x=0}^{N-1}a_{x}$ を求め、各状態の確率振幅を $a_{x}\to 2\mu - a_{x}$ のように変化させる。

2と3を繰り返すことで、探索対象の状態の確率振幅を増幅させていきます。

アルゴリズムの詳細は以下の動画が分かりやすかったです。

www.youtube.com

今回の記事では、上記手順の2と3を何回繰り返せばよいかを求めます。

まず、n個の量子ビットの状態を次のようにセッティングします。

$|\psi>=\sum_{x\neq x^{\ast}}a_{0}|x>+b_{0}|x^{\ast}>$

ここで $|x^{\ast}>$ は探索対象の状態です。また、 $a_{0}=b_{0}=\frac{1}{\sqrt{N}}$ です。

2と3を1回行うと探索対象でない状態の確率振幅 $a_{1}$ と、探索対象の状態の確率振幅 $b_{1}$ はそれぞれ以下になります。

$a_{1}=2\mu_{0}-a_{0}$ $b_{1}=2\mu_{0}+b_{0}$

ここで平均値 $\mu_{0}=\frac{(N-1)a_{0}-b_{0}}{N}$ を使いました。

2と3をk回行った後の確率振幅を求めるためには、以下の連立漸化式を解く必要があります。

$a_{0}=b_{0}=\frac{1}{\sqrt{N}}$ $\mu_{k}=\frac{(N-1)a_{k}-b_{k}}{N}$ $a_{k+1}=2\mu_{k}-a_{k}=\frac{N-2}{N}a_{k}-\frac{2}{N}b_{k}$ $b_{k+1}=2\mu_{k}+b_{k}=\frac{2(N-1)}{N}a_{k}+\frac{N-2}{N}b_{k}$

行列で書くと次のようになります。

$\begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix} = \begin{pmatrix} \frac{N-2}{N} &-\frac{2}{N} \\ \frac{2(N-1)}{N} &\frac{N-2}{N} \end{pmatrix}\begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix}$

行列

$A= \begin{pmatrix} \frac{N-2}{N} &-\frac{2}{N} \\ \frac{2(N-1)}{N} &\frac{N-2}{N} \end{pmatrix}$

を $k$ 回掛けた $A^{k}$ を求めるために $A$ の固有ベクトルを使います。

固有ベクトル $\vec{x_{+}}(固有値: \lambda_{+})$ , $\vec{x_{-}}(固有値: \lambda_{-})$ を並べた行列

$P=\begin{pmatrix} \vec{x_{+}} &\vec{x_{-}} \end{pmatrix}$

を使って、

$(P^{-1}AP)^{k}=P^{-1}A^{k}P=\begin{pmatrix} \lambda_{+}^{k} & 0 \\ 0 & \lambda_{-}^{k}\end{pmatrix}$

となるので、

$A^{k}=P\begin{pmatrix} \lambda_{+}^{k} & 0 \\ 0 & \lambda_{-}^{k}\end{pmatrix} P^{-1}$

となります。

固有値、固有ベクトルは以下の特性方程式を解いて求めます。

$det(A-\lambda I) = 0$

解くと、固有値、固有ベクトルは次になります。

$\lambda_{\pm} = \frac{N-2\pm 2i\sqrt{N-1}}{N}$

$\vec{x_{\pm}}=\begin{pmatrix} 1 \\ \mp i\sqrt{N-1} \end{pmatrix}$ $P=\begin{pmatrix} \vec{x_{+}} & \vec{x_{-}} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -i\sqrt{N-1} & i\sqrt{N-1} \end{pmatrix}$ $P^{-1}=\frac{1}{2i\sqrt{N-1}}\begin{pmatrix} i\sqrt{N-1} & -1 \\ i\sqrt{N-1} & 1 \end{pmatrix}$

よって

$A^{k} = \begin{pmatrix} \frac{\lambda_{+}^{k} + \lambda_{-}^{k}}{2} & -\frac{1}{\sqrt{N-1}}\frac{\lambda_{+}^{k} - \lambda_{-}^{k}}{2i} \\ -\sqrt{N-1}\frac{\lambda_{+}^{k} - \lambda_{-}^{k}}{2i} & \frac{\lambda_{+}^{k} + \lambda_{-}^{k}}{2} \end{pmatrix}$

ここで

$\cos\theta = \frac{N-2}{N}$ $\sin\theta = \frac{2\sqrt{N-1}}{N}$

とおくと

$A^{k}=\begin{pmatrix} \cos k\theta & -\frac{1}{\sqrt{N-1}}\sin k\theta \\ -\sqrt{N-1}\sin k\theta & \cos k\theta \end{pmatrix}$

したがって

$\begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix} = \begin{pmatrix} \cos k\theta & -\frac{1}{\sqrt{N-1}}\sin k\theta \\ -\sqrt{N-1}\sin k\theta & \cos k\theta \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{N}} \\ \frac{1}{\sqrt{N}} \end{pmatrix}$ $= \begin{pmatrix} \frac{1}{\sqrt{N-1}}(\sqrt{\frac{N-1}{N}}\cos k\theta - \frac{1}{\sqrt{N}}\sin k\theta) \\ -\sqrt{\frac{N-1}{N}}\sin k\theta + \frac{1}{\sqrt{N}}\cos k\theta \end{pmatrix}$ $= \begin{pmatrix} \frac{1}{\sqrt{N-1}} \cos(k\theta+\alpha) \\ \sin(k\theta + \alpha) \end{pmatrix}$

最後の式で、

$\cos \alpha = \sqrt{\frac{N-1}{N}}$ $\sin \alpha = \frac{1}{\sqrt{N}}$

と置きました。

求める $k$ は以下を満たします。

$\sin(k\theta + \alpha)=1$

すなわち、

$k\theta + \alpha = \frac{\pi}{2}$

$k$ について解くと

$k=\frac{\frac{\pi}{2} - \sin^{-1} (\frac{1}{\sqrt{N}})}{\sin^{-1}( \frac{2\sqrt{N-1}}{N})}$

となりました。

※2019/6/21追記

$\cos^{2}\alpha - \sin^{2}\alpha = \cos 2\alpha = \frac{N-2}{N} = \cos \theta$

なので、

$\theta = 2\alpha$

となります。

2019-05-19

量子コンピューティング向け言語Q#の問題集 QuantumKatas Teleportation Task 4.1〜4.2 Alice, Bob, Charlie

Task 4.1〜4.2はAlice, Bob, Charlieが登場する量子テレポーテーションの問題です。

Task 4.1は、Alice, Bob, Charlieの状態を|Ψ³⟩ = (|000⟩ + |011⟩ + |101⟩ + |110⟩) / 2 にするという問題です。
Task 4.2は、以下の設定です。

Aliceがメッセージの量子ビットを持っている
AliceがAlice自身の量子ビットとメッセージの量子ビットをエンタングルさせる
AliceがAliceの量子ビットとメッセージの量子ビットを測定し、測定結果を2bitの古典ビットとしてCharlieに送信する
BobもBob自身の量子ビットを測定し、測定結果を1bitの古典ビットとしてCharlieに送信する
Charlieは、受信した3bitを利用して、自身の状態をメッセージの状態にする

Task 4.2は上記1〜4は既に完了しているとして、5を行うという問題です。

この記事ではTask 4.2を説明します。

メッセージの量子ビットの状態を|m⟩ = a|0⟩ + b|1⟩ とすると、メッセージ, Alice, Bob, Charlieの状態は、 |m⟩|Ψ³⟩ = (a|0000⟩ + a|0011⟩ + a|0101⟩ + a|0110⟩ + b|1000⟩ + b|1011⟩ + b|1101⟩ + b|1110⟩) / 2 になります。

Aliceとメッセージをエンタングルさせる、すなわち、CNOT(メッセージ, Alice)を行った後、H(メッセージ)を行うとメッセージ, Alice, Bob, Charlieの状態は、 |m⟩|Ψ³⟩ = (a|0000⟩ + a|1000⟩ + a|0011⟩ + a|1011⟩ + a|0101⟩ + a|1101⟩ + a|0110⟩ + a|1110⟩ + b|0100⟩ - b|1100⟩ + b|0111⟩ - b|1111⟩ + b|0001⟩ - b|1001⟩ + b|0010⟩ - b|1010⟩) / (2*sqrt(2)) になります。ふぅ。

次にこの状態に対してメッセージとAliceの測定を行います。測定結果と測定後の状態は次のようになります。

メッセージ量子ビットの測定結果	Alice量子ビットの測定結果	測定後の状態
0	0	(a\|0000⟩ + a\|0011⟩ + b\|0001⟩ + b\|0010⟩) / sqrt(2)
0	1	(a\|0101⟩ + a\|0110⟩ + b\|0100⟩ + b\|0111⟩) / sqrt(2)
1	0	(a\|1000⟩ + a\|1011⟩ - b\|1001⟩ - b\|1010⟩) / sqrt(2)
1	1	(a\|1101⟩ + a\|1110⟩ - b\|1100⟩ - b\|1111⟩) / sqrt(2)

この状態に対してBobの測定を行います。ここで疑問があります。問題文には以下のように書いてあります。

Bob has also measured his own qubit from |Ψ³⟩

これは不可能ではないでしょうか? なぜかというと、メッセージとAliceの測定を行った後にBobの測定を行うので、Aliceの状態が確定しているからです。
間違っていたらすみません。コメントで指摘してください。

測定結果の3bitと測定後状態は以下の表のようになります。

メッセージ量子ビットの測定結果	Alice量子ビットの測定結果	Bob量子ビットの測定結果	測定後の状態	Charlie量子ビットに行う操作
0	0	0	a\|0000⟩ + b\|0001⟩	なし
0	0	1	a\|0011⟩ + b\|0010⟩	X
0	1	0	a\|0101⟩ + b\|0100⟩	X
0	1	1	a\|0110⟩ + b\|0111⟩	なし
1	0	0	a\|1000⟩ - b\|1001⟩	Z
1	0	1	a\|1011⟩ - b\|1010⟩	X → Z
1	1	0	a\|1101⟩ - b\|1100⟩	X → Z
1	1	1	a\|1110⟩ - b\|1111⟩	Z

これをコードにするとTask 4.1を含めて次のようになります。

    // Quantum teleportation using entangled states other than Bell pairs is also feasible.
    // Here we look at just one of many possible schemes - in it a state is transferred from
    // Alice to a third participant Charlie, but this may only be accomplished if Charlie
    // has the trust of the second participant Bob.
    
    // Task 4.1*. Entangled trio
    // Input: three qubits qAlice, qBob, and qCharlie, each in |0⟩ state.
    // Goal: create an entangled state |Ψ³⟩ = (|000⟩ + |011⟩ + |101⟩ + |110⟩) / 2 on these qubits.
    //
    // In the context of the quantum teleportation protocol, this is the preparation step:
    // qubits qAlice, qBob, and qCharlie will be sent to Alice, Bob, and Charlie respectively.
    operation EntangleThreeQubits (qAlice : Qubit, qBob : Qubit, qCharlie : Qubit) : Unit {
      H(qAlice);
      H(qBob);
      (ControlledOnInt(1, X))([qAlice, qBob], qCharlie);
      (ControlledOnInt(2, X))([qAlice, qBob], qCharlie);
    }
    
    
    // Task 4.2*. Reconstruct the message (Charlie's task)
    // Alice has a message qubit in the state |ψ⟩ to be teleported, she has entangled it with
    // her own qubit from |Ψ³⟩ in the same manner as task 1.2 and extracted two classical bits
    // in order to send them to Charlie. Bob has also measured his own qubit from |Ψ³⟩ and sent
    // Charlie the result.
    //
    // Transform Charlie's qubit into the required state using the two classical bits
    // received from Alice, and the one classical bit received from Bob.
    // Inputs:
    //      1) Charlie's part of the entangled trio of qubits qCharlie.
    //      2) The tuple of classical bits received from Alice,
    //         in the format used in task 1.2.
    //      3) A classical bit resulting from the measurement of Bob's qubit.
    // Goal: transform Charlie's qubit qCharlie into the state in which the message qubit had been originally.
    operation ReconstructMessageWhenThreeEntangledQubits (qCharlie : Qubit, (b1 : Bool, b2 : Bool), b3 : Bool) : Unit {
      if ((not b2 && b3) || (b2 && not b3)) {
        X(qCharlie);
      }

      if (b1) {
        Z(qCharlie);
      }
    }

2019-05-12

量子コンピューティング向け言語Q#の問題集 QuantumKatas Teleportation Task 1.5~1.7 メッセージがパウリ行列の固有状態のときのテレポーテーション

Task 1.5~1.7 はパウリ行列の固有状態をメッセージとするテレポーテーションです。

登場人物は以下の3つです。

AliceからBobに伝えるメッセージの量子ビット
Aliceの量子ビット
Bobの量子ビット

テレポーテーションのおおまかな手順は以下です。

AliceとBobの量子ビットをエンタングルさせる
メッセージの量子ビットを準備する
メッセージとAliceの量子ビットをエンタングルさせる
Alice側でメッセージの量子ビットとAliceの量子ビットを測定し、測定結果を古典ビットとしてBobに送信する
Bob側で受信した古典ビットを利用して、Bobの量子ビットをメッセージの量子ビットと同じ状態にする

あまり、深く理解していないのですが、上記の4と5を行ってしまったら、古典的な通信と何が違うのかなぁと、疑問に思っています。

それはさておき、問題を解きます。

パウリ行列とその固有状態は以下です。

パウリ行列	固有値+1の固有状態	固有値-1の固有状態
$\sigma_{x}$	(\|0⟩ + \|1⟩) / sqrt(2)	(\|0⟩ - \|1⟩) / sqrt(2)
$\sigma_{y}$	(\|0⟩ - i\|1⟩) / sqrt(2)	(\|0⟩ + i\|1⟩) / sqrt(2)
$\sigma_{z}$	\|0⟩	\|1⟩

Task 1.5は手順の2〜4までを行う問題です。

Task 1.6は手順の5を行う問題です。

Task 1.7は全ての手順を行ってテストするという問題です。

    // Task 1.5. Prepare a state and send it as a message (Alice's task)
    // Given a Pauli basis along with a state 'True' as 'One' or 'False'
    // as 'Zero' prepare a message qubit, entangle it with Alice's qubit,
    // and extract two classical bits to be sent to Bob.
    // Inputs:
    //      1) Alice's part of the entangled pair of qubits qAlice.
    //      2) A PauliX, PauliY, or PauliZ basis in which the message
    //         qubit should be prepared
    //      3) A Bool indicating the eigenstate in which the message
    //         qubit should be prepared
    // Output:
    //      Two classical bits Alice will send to Bob via classical channel as a tuple of Bool values.
    //      The first bit in the tuple should hold the result of measurement of the message qubit,
    //      the second bit - the result of measurement of Alice's qubit.
    //      Represent measurement result 'One' as 'True' and 'Zero' as 'False'.
    // The state of the qubit qAlice in the end of the operation doesn't matter.
    operation PrepareAndSendMessage (qAlice : Qubit, basis : Pauli, state : Bool) : (Bool, Bool) {
      mutable bMessage = false;
      mutable bAlice = false;

      using (qMessage = Qubit()) {
        if (state) {
          X(qMessage);
        }

        PrepareQubit(basis, qMessage);
        CNOT(qMessage, qAlice);
        H(qMessage);

        set bMessage = M(qMessage) == One;
        set bAlice = M(qAlice) == One;

        Reset(qMessage);
      }

      return (bMessage, bAlice);
    }
    
    
    // Task 1.6. Reconstruct and measure the message state (Bob's task)
    // Transform Bob's qubit into the required state using the two classical bits
    // received from Alice and measure it in the same basis in which she prepared the message.
    // Inputs:
    //      1) Bob's part of the entangled pair of qubits qBob.
    //      2) The tuple of classical bits received from Alice,
    //         in the format used in task 1.5.
    //      3) The PauliX, PauliY, or PauliZ basis in which the
    //         message qubit was originally prepared
    // Output:
    //      A Bool indicating the eigenstate in which the message qubit was prepared, 'One' as
    //      'True' and 'Zero' as 'False'.
    // Goal: transform Bob's qubit qBob into the state in which the message qubit was originally
    // prepared, then measure it. The state of the qubit qBob in the end of the operation doesn't matter.
    operation ReconstructAndMeasureMessage (qBob : Qubit, (b1 : Bool, b2 : Bool), basis : Pauli) : Bool {
      if (b2) {
        X(qBob);
      }

      if (b1) {
        Z(qBob);
      }

      return Measure([basis], [qBob]) == One;
    }
    
    
    // Task 1.7. Testing standard quantum teleportation
    // Goal: Test that the StandardTeleport operation from task 1.4 is able
    // to successfully teleport the states |0⟩ and |1⟩, as well as superpositions such as
    // (|0⟩ + |1⟩) / sqrt(2),
    // (|0⟩ - |1⟩) / sqrt(2),
    // (|0⟩ + i|1⟩) / sqrt(2), and
    // (|0⟩ - i|1⟩) / sqrt(2)
    operation StandardTeleport_Test () : Unit {
        // Hint: You may find your answers for 1.5 and 1.6 useful
        let messages = [(PauliZ, false),  // |0>
                        (PauliZ, true ),  // |1>
                        (PauliX, false),  // (|0> + |1>) / sqrt(2)
                        (PauliX, true ),  // (|0> - |1>) / sqrt(2)
                        (PauliY, true ),  // (|0> + i|1>) / sqrt(2)
                        (PauliY, false)   // (|0> - i|1>) / sqrt(2)
                        ];

        using ((qAlice, qBob) = (Qubit(), Qubit())) {
          for (i in 0 .. Length(messages) - 1) {
            H(qAlice);
            CNOT(qAlice, qBob);

            let (basis, state) = messages[i];

            let classicalBits = PrepareAndSendMessage(qAlice, basis, state);
            let receivedState = ReconstructAndMeasureMessage(qBob, classicalBits, basis);
            AssertBoolEqual(receivedState, state, $"send state: {state}, received state: {receivedState}");
            ResetAll([qAlice, qBob]);
          }
        }
    }

2019-05-04

C言語でPythonのモジュールを自作する

C言語でPythonのモジュールを自作する方法を書く。

環境

Ubuntu 18.04.2 LTS
Python 2.7.15rc1

参考にしたサイト

1. 準備(virtualenvで実験用環境を作る)

virtualenvコマンドを使って、実験用の環境を作る。virtualenvコマンドを使うとシステムのPython環境と分離した環境が作れる。

まず、virtualenvをインストール。

$ sudo apt install virtualenv

次に、実験用環境mypylibを作って、activateする。 (activateするとプロンプトに(ディレクトリ名)が付く。元の環境に戻るためには$ deactivateを実行。)

$ mkdir mypylib
$ virtualenv --no-site-packages mypylib
$ source mypylib/bin/activate

2. 自作モジュールのC言語ソースを書く

自作モジュールのC言語ソースmypylib/spammodule.cは以下。

#include <Python.h>

static PyObject *
spam_system(PyObject *self, PyObject *args)
{
  const char *command;
  int sts;

  if (!PyArg_ParseTuple(args, "s", &command))
    return NULL;

  sts = system(command);
  return Py_BuildValue("i", sts);
}

static PyMethodDef SpamMethods[] = {
  {"system", spam_system, METH_VARARGS, "Execute a shell command."},
  {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
initspam(void)
{
  (void) Py_InitModule("spam", SpamMethods);
}

3. .whlファイル作成用のsetup.pyを用意

.whlファイルを作成するためのmypylib/setup.pyは以下。

from setuptools import setup, Extension

setup(
    name='spam',
    ext_modules=[Extension('spam', sources=['spammodule.c'])]
    )

4. .whlファイル作成

以下のコマンドで.whlファイルを作成する。

(mypylib)$ python setup.py bdist_wheel

mypylib/dist/spam-0.0.0-cp27-cp27mu-linux_x86_64.whlが出来上がる。

5. .whlのインストールと動作確認

作った.whlファイルを実験用環境にインストールする。

(mypylib)$ pip install dist/spam-0.0.0-cp27-cp27mu-linux_x86_64.whl

動作確認。

$ python
Python 2.7.15rc1 (default, Nov 12 2018, 14:31:15) 
[GCC 7.3.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import spam
>>> status = spam.system("ls -l")

2019-04-27

量子コンピューティング向け言語Q#の問題集 QuantumKatas Measurements Task 1.10 ベル状態の識別

Task 1.10は、4つのベル状態を識別する問題です。

解答1

    // Task 1.10. Distinguish four Bell states
    // Input: two qubits (stored in an array) which are guaranteed to be in one of the four Bell states:
    //         |Φ⁺⟩ = (|00⟩ + |11⟩) / sqrt(2)
    //         |Φ⁻⟩ = (|00⟩ - |11⟩) / sqrt(2)
    //         |Ψ⁺⟩ = (|01⟩ + |10⟩) / sqrt(2)
    //         |Ψ⁻⟩ = (|01⟩ - |10⟩) / sqrt(2)
    // Output: 0 if qubits were in |Φ⁺⟩ state,
    //         1 if they were in |Φ⁻⟩ state,
    //         2 if they were in |Ψ⁺⟩ state,
    //         3 if they were in |Ψ⁻⟩ state.
    // The state of the qubits at the end of the operation does not matter.
    operation BellState (qs : Qubit[]) : Int {
      CNOT(qs[0], qs[1]);
      H(qs[0]);

      let q0 = M(qs[0]);
      let q1 = M(qs[1]);

      if (q0 == Zero && q1 == Zero) {
        return 0;
      } elif (q0 == One && q1 == Zero) {
        return 1;
      } elif (q0 == Zero && q1 == One) {
        return 2;
      } else {
        return 3;
      }
    }

解答2

    // Task 1.10. Distinguish four Bell states
    // Input: two qubits (stored in an array) which are guaranteed to be in one of the four Bell states:
    //         |Φ⁺⟩ = (|00⟩ + |11⟩) / sqrt(2)
    //         |Φ⁻⟩ = (|00⟩ - |11⟩) / sqrt(2)
    //         |Ψ⁺⟩ = (|01⟩ + |10⟩) / sqrt(2)
    //         |Ψ⁻⟩ = (|01⟩ - |10⟩) / sqrt(2)
    // Output: 0 if qubits were in |Φ⁺⟩ state,
    //         1 if they were in |Φ⁻⟩ state,
    //         2 if they were in |Ψ⁺⟩ state,
    //         3 if they were in |Ψ⁻⟩ state.
    // The state of the qubits at the end of the operation does not matter.
    operation BellState (qs : Qubit[]) : Int {
      CNOT(qs[0], qs[1]);
      Ry(PI() / 2.0, qs[0]);

      let q0 = M(qs[0]);
      let q1 = M(qs[1]);

      if (q0 == Zero && q1 == Zero) {
        return 1;
      } elif (q0 == One && q1 == Zero) {
        return 0;
      } elif (q0 == Zero && q1 == One) {
        return 3;
      } else {
        return 2;
      }
    }

CNOT(qs[0], qs[1]);は(Controlled X)([qs[0]], qs[1]);と同じ。

2019-04-03

量子コンピューティング向け言語Q#の問題集 QuantumKatas Superposition Task 15

Superposition Task 15は2日くらい悩んでやっとテストが通った。

Task 15は、次の入力状態からゴール状態を作る問題。

入力状態: N個の量子ビットの状態|0...0> (Nは2の冪乗とは限らない)
ゴール状態: W stateという状態、すなわち、 (|10...0> + |010...0> + ... + |0...1>)/sqrt(N)

以下の写真の方針で考えました。

f:id:yabaniyatun:20190403234435j:plain

解答

    // Task 15**. W state on arbitrary number of qubits
    // Input: N qubits in |0...0⟩ state (N is not necessarily a power of 2).
    // Goal: create a W state (https://en.wikipedia.org/wiki/W_state) on these qubits.
    // W state is an equal superposition of all basis states on N qubits of Hamming weight 1.
    // Example: for N = 3, W state is (|100⟩ + |010⟩ + |001⟩) / sqrt(3).
    operation WState_Arbitrary (qs : Qubit[]) : Unit {
      let N = Length(qs);
      Ry(2.0 * ArcCos(Sqrt(ToDouble(N - 1) / ToDouble(N))), qs[0]);
      for (i in 0..N-2) {
        (ControlledOnInt(0, Ry))(qs[0..i], (2.0 * ArcCos(Sqrt(ToDouble(N-i-2)/ToDouble(N-i-1))), qs[i+1]));
      }
    }

2019-04-01

QuantumKatas Superposition Task 14

    // And関数を使うためにimport
    open Microsoft.Quantum.Extensions.Bitwise;

    // Task 14**. W state on 2ᵏ qubits
    // Input: N = 2ᵏ qubits in |0...0⟩ state.
    // Goal: create a W state (https://en.wikipedia.org/wiki/W_state) on these qubits.
    // W state is an equal superposition of all basis states on N qubits of Hamming weight 1.
    // Example: for N = 4, W state is (|1000⟩ + |0100⟩ + |0010⟩ + |0001⟩) / 2.
    operation WState_PowerOfTwo (qs : Qubit[]) : Unit {
        // Hint: you can use Controlled modifier to perform arbitrary controlled gates.
        let N = Length(qs);
        let k = Floor(Lg(ToDouble(N)));

        using (qk = Qubit[k]) {
          ApplyToEach(H, qk);

          for (i in 0..N-1) {
            (ControlledOnInt(i, X))(qk, qs[i]);
          }

          for (i in 0..N-1) {
            for (j in 0..k-1) {
              if (And(i, Floor(PowD(2.0, ToDouble(j)))) > 0) {
                (ControlledOnInt(1, X))([qs[i]], qk[j]);
              }
            }
          }
        }
    }

メッセージ量子ビットの測定結果	Alice量子ビットの測定結果	測定後の状態
0	0	(a\|0000⟩ + a\|0011⟩ + b\|0001⟩ + b\|0010⟩) / sqrt(2)
0	1	(a\|0101⟩ + a\|0110⟩ + b\|0100⟩ + b\|0111⟩) / sqrt(2)
1	0	(a\|1000⟩ + a\|1011⟩ - b\|1001⟩ - b\|1010⟩) / sqrt(2)
1	1	(a\|1101⟩ + a\|1110⟩ - b\|1100⟩ - b\|1111⟩) / sqrt(2)