@yuichirominato 2019.01.06更新 316views

Bernstein-Vazirani(ベルンシュタイン・ヴァジラニ)アルゴリズム。

Bernstein-Vazirani Blueqat Deutsch 量子ゲート 量子コンピュータ

はじめに

Bernstein-Vaziraniのアルゴリズムを見てみます。名前がなんとなくカッコ良かったからですが、ベルンシュタイン・ヴァジラニ。勝手にオラクル調べるシリーズとしてDeutschなどのアルゴリズムシリーズに入れてます。実は調べてみたらあまり資料がなかったのですが、ドイチェアルゴリズムなどと似ているので、その流れを踏襲しました。

概要

$f:\{0,1\}^n \rightarrow s\cdot x , (mod 2)$のように、$x\in\{0,1\}^n$の入力に対して$s\in\{0,1\}^n$を効率的に求めるアルゴリズムです。

参考

とてもいいアルゴリズムですが、参考が少ないです。
https://www.scottaaronson.com/qclec/18.pdf

量子回路

量子回路はDeutschのアルゴリズムなどと同じように、オラクルを調べます。ただ、入力が複数ビットなります。この辺りはとても似てます。xはnビットの|0…000>で、求めたいsもnビットの二進数が入ります。

参考:https://blog.mdrft.com/post/1530

|x> --H--??--H-- |s>
|1> --H--??--H-- |1>

例題と実装

上記のxやsは複数ビットを想定しているので、複数ビットで実装してみます。

|0> -----H-----H--M
|0> -----H--*--H--M
|0> -----H--|--H--M
|0> -----H--|--H--M
            |        
|0> --X--H--X--H---

こちらのオラクルはCNOTでq[1]に対してcxをかけてます。Blueqatのコードは、

from blueqat import Circuit
Circuit().x[4].h[:].cx[1,4].h[:].m[:].run(shots=100)                                                                                                             
Counter({'01001': 100})

s=0100となりました。今回はCNOT(CX)1つでオラクルを構成しましたが、このオラクルを変えてみることで色々結果を試してみるのも面白いと思います。

Recommended


Wikiへ移動