ゆるふわ量子コンピュータ
バーンスタイン・ヴァジラニをQiskitで実装｜隠された数字を1回で当てる
2026-08-25 ・ 実践
「隠された秘密のビット列 s を当てよ」という問題を、古典なら n 回、量子なら たった1回で解くのが バーンスタイン・ヴァジラニ（BV） です。ドイチュ・ジョザの兄弟で、位相キックバックの威力がさらにはっきりわかります。
問題設定
オラクルは「入力 x と秘密 s の内積（mod 2）」を返します。古典では x を1ビットずつ立てて n 回問い合わせないと s がわかりません。量子は1回で s 全体を取り出します。
準備
pip install qiskit qiskit-aer
① 秘密を埋め込んだオラクル
秘密 s="1011" を、s のビットが1の位置だけ CX を置くことで表現します。
from qiskit import QuantumCircuit
def bv_oracle(s):
n = len(s)
qc = QuantumCircuit(n + 1, name="oracle")
for i, bit in enumerate(reversed(s)): # 右端がqubit0
if bit == "1":
qc.cx(i, n)
return qc
② BV本体
出力ビットを |−⟩ にして、入力を重ね合わせ、オラクルを通し、アダマールで戻すだけ。
from qiskit_aer import AerSimulator
def bernstein_vazirani(s):
n = len(s)
qc = QuantumCircuit(n + 1, n)
qc.x(n); qc.h(n) # 出力を |−⟩
qc.h(range(n))
qc.compose(bv_oracle(s), inplace=True)
qc.h(range(n))
qc.measure(range(n), range(n))
counts = AerSimulator().run(qc, shots=1000).result().get_counts()
return counts
s = "1011"
print(bernstein_vazirani(s)) # {'1011': 1000}
結果は {'1011': 1000}。測定した瞬間に、秘密 1011 がそのまま読み取れました。オラクル1回で完了です。
なぜ1回で全ビット？
|−⟩ の出力ビットのおかげで、内積が1のときだけ入力ビットの位相が反転します（位相キックバック）。アダマールで戻すと、その位相パターンがそのまま s のビット列として測定に現れます。
まとめ
- BVは「秘密ビット列 s」を量子なら1回のオラクル問い合わせで当てる
- 古典は n 回必要。量子は位相キックバックで一括取得
- 出力ビットを
|−⟩にするのがキモ（DJと同じ構造） - 測定結果がそのまま秘密 s になる
もう少し詳しく（背景と理論）
バーンスタイン・ヴァジラニ（BV）は Bernstein & Vazirani (1993) が導入した問題で1、秘密ビット列 s との内積を返すオラクルから s を1回の問い合わせで復元します。古典では s の各ビットを1本ずつ立てて n 回問い合わせる必要があるため、n 対 1 の分離になります。BV は量子計算量クラス BQP の下限的な例として理論的にも重要で2、その再帰版は古典に対する超多項式的な分離を与えます。実装上は位相キックバックにより、内積が1のビットだけ位相反転→アダマールで s に化ける、という点がすべてです3。
次の一歩 🌸
姉妹アルゴリズムのドイチュ・ジョザ、探索のグローバー実装、全体像は量子アルゴリズム入門へどうぞ。