Pythonで浮動小数点数をビットパターンに変換する方法

64bit浮動小数点数(1.0の例)

>>> import struct
>>> hex(struct.unpack('<Q', struct.pack('<d', 1.0))[0])
'0x3ff0000000000000'

32bit浮動小数点数(1.0の例)

>>> import struct
>>> hex(struct.unpack('<I', struct.pack('<f', 1.0))[0])
'0x3f800000'

16bit浮動小数点数(1.0の例) Python3.6以上で動く

>>> import struct
>>> hex(struct.unpack('<H', struct.pack('<e', 1.0))[0])
'0x3c00'

Vim練習1

正規表現で検索した文字列を置換する方法

ファイル全体に対して、一括で置換を行うコマンド

:%s/\v<正規表現>/<置換後文字列/g

ドットコマンドを使って置換を行う方法

まず、以下で検索する

/\v<正規表現>

次に1つ目の検索対象を置換する

cgn<置換後文字列>

後は、「n.」を繰り返す

n.の繰り返し

指定の行を現在行の下にコピー/ムーブする方法

例) 6行目を現在行の下にコピーする

:6t.

例) 6行目を現在行の下にムーブする

:6m.

アクティブなディレクトリにあるファイルを開く方法

今、<ディレクトリ>/aaa.txt を編集しているとする。
<C-w>vで画面分割して、隣に<ディレクトリ>/bbb.txt を表示させたい。
<C-w>l で隣の画面に移動して、以下のコマンドでbbb.txtが開ける。

:e <ディレクトリ>/bbb.txt

<ディレクトリ>のパスが長いときは、この方法は面倒だ。

そこで、以下のようにすると<ディレクトリ>/が自動で入力される。

:e %:h<TAB>

自分用メモ ARM64クロスコンパイルとx86_64での実行

参考サイト

qiita.com

環境はx86_64, Ubuntu 18.04.2 LTS。

まず、qemuとg++-aarch64-linux-gnuを以下のようにインストール。

$ sudo apt-get install qemu
$ sudo apt-get install g++-aarch64-linux-gnu

helloworld.c

#include <stdio.h>

int main() {
  printf("hello world\n");
  return 0;
}

ロスコンパイル

$ aarch64-linux-gnu-gcc -o helloworld_arm64 helloworld.c

fileコマンドを実行してみる

$ file helloworld_arm64 
helloworld_arm64: ELF 64-bit LSB shared object, ARM aarch64, version 1 (SYSV), dynamically linked, interpreter /lib/ld-, for GNU/Linux 3.7.0, BuildID[sha1]=0b7252ec780aca58b8d0d95f117438281433d569, not stripped

実行

$ qemu-aarch64 -L /usr/aarch64-linux-gnu/ ./helloworld_arm64 
hello world

以下のようにスタティックリンクすると、qemu-aarch64を使わなくても実行できるのはなぜ? 勝手に裏でqemu-aarch64が実行される?

$ aarch64-linux-gnu-gcc -o helloworld_arm64_static -static helloworld.c
$ ./helloworld_arm64_static 
hello world

GroverアルゴリズムでSAT問題を解くための繰り返し回数がわからない

$$N: SAT問題の変数の数をnとしたとき N=2^{n}$$ $$t: SAT問題の解の個数$$ $$k: Gover探索の繰り返し回数$$

以下の xの絶対値を最大化させる kを求めたいが、なかなか簡単にならない。

$$x=\frac{1}{4\beta}\sqrt{\frac{1-t}{N}}(\alpha^{2}-\beta^{2})(\lambda_{+}^{k}-\lambda_{-}^{k})+\frac{1}{2\beta}\sqrt{\frac{t}{N}}[(\alpha+\beta)\lambda_{+}^{k}-(\alpha-\beta)\lambda_{-}^{k}]$$

$$\lambda_{\pm}=\frac{N-t-1\pm i \sqrt{4N - (t+1)^{2}}}{N}$$

$$\alpha=(N-2)(N-1)$$

$$\beta=N i \sqrt{4N-(t+1)^{2}}$$

Groverのアルゴリズム

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

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

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

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

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

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

www.youtube.com

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$$

となります。

量子コンピューティング向け言語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は、以下の設定です。

  1. Aliceがメッセージの量子ビットを持っている
  2. AliceがAlice自身の量子ビットとメッセージの量子ビットエンタングルさせる
  3. AliceがAliceの量子ビットとメッセージの量子ビットを測定し、測定結果を2bitの古典ビットとしてCharlieに送信する
  4. BobもBob自身の量子ビットを測定し、測定結果を1bitの古典ビットとしてCharlieに送信する
  5. 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);
      }
    }

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

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

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

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

  1. AliceとBobの量子ビットエンタングルさせる
  2. メッセージの量子ビットを準備する
  3. メッセージとAliceの量子ビットエンタングルさせる
  4. Alice側でメッセージの量子ビットとAliceの量子ビットを測定し、測定結果を古典ビットとしてBobに送信する
  5. 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]);
          }
        }
    }