번스타인-바지라니 알고리즘

번스타인-바지라니 문제를 해결하는 번스타인-바지라니 알고리즘은 1997년 에단 번스타인과 우메시 바지라니가 발명한 양자 알고리즘입니다.^[1] 두 가지 다른 클래스의 함수를 구별하는 대신 함수에 인코딩된 문자열을 학습하는 Deutsch-Jozsa 알고리즘의 제한된 버전입니다.^[2] 번스타인-바지라니 알고리즘은 복잡도 클래스 BQP와 BPP 사이의 오라클 분리를 증명하기 위해 설계되었습니다.^[1]

문제문

Given an oracle that implements a function ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$ in which ${\displaystyle f(x)}$ is promised to be the dot product between ${\displaystyle x}$ and a secret string ${\displaystyle s\in \{0,1\}^{n}}$ modulo 2, ${\displaystyle f(x}$) ${\displaystyle =}$ ${\displaystyle {}_{}\cdot }$ $s$ = x 1 ${\displaystyle s}$ 1 ⊕ x 2 ${\displaystyle \mathrm{s\; 2\; \oplus }}$ ⋯ ⊕ x n {\displaystyle f${\displaystyle (}$x) = x\cdo${\displaystyle t}$ s = x_{1}s_{1}\opplus x_{2}s_{2}\opplus \cdots \opplus x_{n}s_{n}}, {\displaystyle s}를 찾습니다.

알고리즘.

일반적으로 비밀 문자열을 찾는 가장 효율적인 방법은 $함수$ n ${\displaystyle$ n$}$을 모든 i ∈ {${\displaystyle {}^{}}$, 1, ..., n - 1} {\displaystyle i\in \{0, 1, ..., n-1\}에 대해 입력 값 $x$ = ${\displaystyle {2i}^{}}$$displaystyle$ x = 2^{$i}}$로 평가하는 것입니다.

${\displaystyle {\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}}$

${\displaystyle s}$을(를) 찾기 위해 $함수$의 ${\displaystyle n}$개$$ 이상의 쿼리가 필요한 고전적인 솔루션과 달리 양자 컴퓨팅을 사용하면 하나의 쿼리만 필요합니다$.$ 양자 알고리즘은 다음과 같습니다.

Hadamard $변환$을$$n {\$displaystyle$n} ${\displaystyle 큐비트}$ 상태$$ ⟩ ⊗n${\displaystyle 0\rangle ^{\$otimes n}에 적용하면 다음을 얻을 수 있습니다.

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1} x\rangle .}$

${\displaystyle \mathrm{그런}}$ 다음 x ⟩ →${\displaystyle {}^{}}$( -${\displaystyle 1^{}}$) f ( $x$ ) x ⟩ ${\displaystyle$ x\rangle \ to (-1)^{f(x)} x\rangle }를 변환하는 오라클 Uf ${\displaystyle U_{f}}$를 적용합니다. 이는 ${\displaystyle 이}$$오라클을 0$⟩ -$1$⟩$$2$$x ⟩ {\${\displaystyle frac}$ {0\rangle - 1\rangle } {\sqrt {$2$} ⊕$f$ (x) ⟩ x ⟩${\displaystyle$ b$\rangle$ x${\displaystyle \frac{\backslash }{}}$rangle}을$($$x$) b\opplus f(x)\${\displaystyle \frac{rangle}{}}$ x\${\displaystyle \frac{rangle}{}}$}을(를) 변환하는 표준 오라클을 통해 시뮬레이션할 수 있습니다. ( ${\displaystyle$\opplus } ⊕는 addition mod 2를 나타냅니다.) 이것은 중첩을 다음과 같이 변형시킵니다.

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)} x\rangle .}$

또 다른 하다마드 변환이 각 큐비트에 적용되어 ${\displaystyle si}$ = 1 ${\$displaystyle s_${i$}=1}인 큐비트의 경우 상태가 - ⟩ {\displaystyle -\rangle }에서 ⟩ {\displaystyle 1\rangle }로 변환되고 si = 0 {\displaystyle s_{i}=0}인 큐비트의 경우 상태가 변환됩니다. its state is converted from ${\displaystyle +\rangle }$ to ${\displaystyle 0\rangle }$. To obtain ${\displaystyle s}$, a measurement in the standard basis (${\displaystyle \{ 0\rangle , 1\rangle \}}$) is performed on the qubits.

그래픽으로 알고리즘은 다음 다이어그램으로 나타낼 수 있습니다. 여기서 ${\displaystyle H^{}}$ ⊗ n {\displaystyle $H^{\otimes$ n}}은 n${\displaystyle$ n} 큐비트의 하다마드$변환$을 나타냅니다.

${\displaystyle 0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}} x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)} x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y} y\rangle = s\rangle }$

${\displaystyle 마지막}$ $상태가$⟩ {\$displaystyle$ s$\$rangle}인 이유는$특정$ ${\displaystyle$에 대해,

${\displaystyle {\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ if }}s\oplus y={\vec {0}},\,0{\text{ otherwise}}.}$

${\displaystyle s}$ ⊕ y = $0$ → {\$displaystyle$ s\opplus y = ${\$$vec$ {0}}은 $s$ = y {\$displaystyle$ s= y}일 때만 참이므로 0이 아닌 진폭만 s ⟩ {\displaystyle s\rangle }에 있음을 의미합니다. 따라서 계산 기반에서 회로의 출력을 측정하면 비밀 문자열 {\displaystyle s}이 생성됩니다.

확률적 오라클을 사용하여 하나 이상의 비밀 키를 찾는 것을 포함하는 번스타인-바지라니 문제의 일반화가 제안되었습니다. ^[3] 이것은 양자 알고리듬이 일반적인 경우에 문제를 해결하는 데 완전히 실패하는 반면, 양자 알고리듬이 확실하거나 높은 신뢰도로 효율적인 해결책을 제공할 수 있는 흥미로운 문제입니다.

참고 항목

• 숨겨진 선형 함수 문제

참고문헌