量子コンピュータでベクトルの内積

ベクトルの内積。古典コンピュータだとO(N)ですが、それをO(1)で行う方法。量子コンピュータで自由に初期状態を作る方法 - yukobaのブログの続きです。

$(\sqrt{\frac{4}{7}}, \sqrt{\frac{2}{7}}, 0, \sqrt{\frac{1}{7}}) \cdot (\sqrt{\frac{1}{2}}, 0, 0, \sqrt{\frac{1}{2}})$ の内積をとると、 $\sqrt{\frac{2}{7}} + \sqrt{\frac{1}{14}}$ になります。今回は、これが目標です。

アルゴリズムの概要は、ベクトルの値は状態の振幅に入れて、テンソル積でかけ算を行い、アダマール行列(H)で足し算を行います。

振幅の絶対値の2乗の和は1にならないといけないという制約があるので、ベクトルに一定の係数をかけて、1になるようにします。それぞれのベクトルの係数どうしもかけ算して、内積の結果に考慮に入れます。この部分もO(1)でできます。

答えは、|0> に入ってきます。ビット数をn、つまり、 $n = logN$ とした時、|0> の振幅 × $2^n$ が内積の値です。今回は、n = 2なので、 $(\sqrt{\frac{2}{7}} + \sqrt{\frac{1}{14}}) / 2^2$ = 0.200446 です。

以下のソースコードを実行すると、

: STATE: 5 / 32 qubits allocated, 27 / 32 qubits free
0.20045 |0> + 0.066815 |1> + 0.066815 |2> + ...

となるので、|0> のところが、0.20045 になっているので正しく実行できています。

ただし、量子コンピュータの離散フーリエ変換同様、振幅なので、直接値を取り出すことはできません。ショアの素因数分解のアルゴリズムに離散フーリエ変換が使われているのと同様、この、ベクトルの内積は計算の途中に使えるはずです。

量子コンピュータでベクトルの足し算・引き算 - yukobaのブログへと続く。

ソースコード

ファイル名は、dotProduct.qcl。

include "xor.qcl";
include "initAmpGeneral.qcl";

procedure testDotProduct() {
  const patternBitSize = 2;
  int vector xPatterns = vector(0, 1, 3);
  real vector xValues = vector(4.0/7.0, 2.0/7.0, 1.0/7.0);
  int vector yPatterns = vector(0, 3);
  real vector yValues = vector(0.5, 0.5);
  qureg x[patternBitSize];
  qureg y[patternBitSize];
  qureg m[1];

  initAmp(x, xPatterns, xValues);
  initAmp(y, yPatterns, yValues);

  // x = y のところは、m = 0 に集め、それ以外は、m = 1に集める。
  Xor(x, y);
  Not(x);
  CNot(m, x);
  Not(x);
  Xor(x, y);
  Not(m);
  
  // 和をとる
  H(x & y);
  
  // |0> の値 × 2^#x が内積の値
  dump;
}

ファイル名は、xor.qcl。ループを回していますが、正しく量子回路を組めば、O(1)のはずです。

qufunct Xor(qureg x, qureg y) {
  int i;
  for i = 0 to #x - 1 {
    CNot(x[i], y[i]);
  }
}