사이먼의 문제

계산 복잡도 이론과 양자 컴퓨팅에서 사이먼의 문제는 고전적인 (즉, 전통적인) 컴퓨터보다 양자 컴퓨터에서 기하급수적으로 더 빨리 해결되는 것으로 증명된 계산 문제입니다. 쇼어의 알고리즘은 보통 사이먼의 알고리즘이라고 불리는 사이먼의 문제를 푸는 양자 알고리즘에 영감을 주었습니다.^[1] 두 문제 모두 현재 효율적인 양자 알고리즘을 가진 것으로 알려진 아벨리안 은닉 부분군 문제의 특수한 경우입니다.

문제는 의사결정 나무 복잡성 또는 질의 복잡성의 모델에서 설정되며 Daniel R에 의해 구상되었습니다. 1994년 사이먼.^[2] 사이먼은 최고의 확률적(또는 결정론적) 고전적 알고리즘보다 기하급수적으로 적은 질의로 사이먼의 문제를 기하급수적으로 빠르게 해결하는 양자 알고리즘을 보여주었습니다. 특히 사이먼의 알고리즘은 선형적인 수의 쿼리를 사용하며 고전적인 확률적 알고리즘은 기하급수적인 수의 쿼리를 사용해야 합니다.

이 문제는 복잡도 클래스 BPP(경계 오류 고전 쿼리 복잡도)와 BQP(경계 오류 양자 쿼리 복잡도) 사이의 오라클 분리를 산출합니다.^[3] 이는 Bernstein-Vazirani 알고리즘이 달성하는 것과 동일한 분리이며, P와 EQP를 분리하는 Deutsch-Jozsa 알고리즘이 제공하는 분리와는 다릅니다. 사이먼의 알고리즘은 번스타인-바지라니 알고리즘과 달리 지수함수적으로 분리됩니다.

이 문제는 속도 향상을 위해 고도로 구조화된 "블랙박스" 오라클의 존재를 가정하기 때문에 실질적인 가치가 거의 없습니다.^[4] 그러나 이러한 오라클이 없으면 지수 속도 향상이 쉽게 증명되지 않습니다. 이는 P가 PSPACE와 다르다는 것을 증명하기 때문입니다.

문제설명

Given a function (implemented by a black box or oracle) ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ with the promise that, for some unknown ${\displaystyle s\in \{0,1\}^{n}}$, for all ${\displaystyle x,y\in \{0,1\}^{n}}$,

${\displaystyle f}$( ${\displaystyle x}$) = ${\displaystyle f}$( y ) $displaystyle$ f${\displaystyle (}$x) = f(y)${\displaystyle \}}$ x ⊕ y가 {0 n, s} {\displaystyle x\opplus y\in \{0^{n}s\}인 경우에만,

$여기서$⊕ ${\displaystyle$\opplus}은(는) 비트 단위의 XOR을 나타냅니다. 가능한$$ $한{\displaystyle \mathrm{적은}}$ 수의$$쿼리를 f(x) {\displaystyle $f(x)}$에 적용하여$$ ${\displaystyle$ s$}$을(를) 식별하는 것이 목표입니다. 주의:

${\displaystyle a}$ ${\displaystyle \oplus }$ ${\displaystyle b^{}}$ $=$ $0$n {\$displaystyle$ a\opplu${\displaystyle s}$ b = 0^{n}}인 경우에${\displaystyle 만}$ a = b {\displaystyl${\displaystyle e}$ a = b}

Furthermore, for some ${\displaystyle x}$ and ${\displaystyle s}$ in ${\displaystyle x\oplus y=s}$, ${\displaystyle y}$ is unique (not equal to ${\displaystyle x}$) if and only if ${\displaystyle s\n$$eq$ 0$^{n$ $즉$, ${\displaystyle s^{}}$가 ≠ 0${\displaystyle$ s\n일 때 f ${\displaystyle$ f$}$는 2대1임을 의미합니다.$eq 0^{n$ $s$ $=$ ${\displaystyle {}^{}}$n {\$displaystyle$ s $=$ 0^{$n$}일 때 일대일입니다. 또한 x $⊕$ y $=$ s {\displaystyle x\opplus y $=$s}가 y $=$ s $⊕$ x {\display y $=$s\opplus x}를 의미하는 경우도 있습니다.

$이$는$$f {\$displaystyle$ f$}$가 주기적으로$$ 수행되는 방식을 보여줍니다.

사이먼 문제의 관련 결정 문제 공식은 $s$ = ${\displaystyle 0^{}}$ n${\$$displaystyle$ s = 0^{n}}(f ${\displaystyle$ f}가 일대일일 때와 $s$ ≠ 0 n {\displaystyle s\n)를 구별하는 것입니다.$eq 0^{n}}($$f {\displaystyle$ f$}$는 2대1)입니다.

예

$다음$ 함수는 n = ${\$displaystyle n = 3}에 대해 필요한 속성을 만족하는 함수의 예입니다.

${\displaystyle x}$	${\displaystyle f(x)}$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

이 경우 $s$ = ${\$displaystyle s = 110} (즉, 해). $f$ ${\displaystyle f}$의 모든 출력은 두 번 발생하며, 주어진 출력 중 하나에 해당하는 두 입력 문자열의 비트 단위 ${\displaystyle \mathrm{XOR}}$은 s =$110$ {\displaystyle s = 110}입니다.

예를 들어, 입력 ${\displaystyle \mathrm{문자열}}$ 010$${\$displaystyle 010}$ ${\displaystyle \mathrm{및}}$ 100$${\$displaystyle 100}$은 모두$동일$한 출력 $문자열$ 000$${\$displaystyle 000}$에 매핑됩니다$$$.$ 즉, $f{\displaystyle {\displaystyle (010)}}$ = ${\$$displaystyle$ ${\displaystyle$ f$(010$)=000}, f(100) = 000 {\$displaystyle$f($100$)=000}입니다. 010과 100에 XOR을 적용하면 $110$, 즉 010 ⊕ 100 = 110 = s를 얻는다. {\displaystyle {\displaystyle 010\opplus 100 =$110$ = s}

${\displaystyle s}$ = ${\displaystyle 110}${\displaystyl${\displaystyle e}$ s = 110} 또한 동일한 출력 문자열 010에 (f로) 매핑된 입력 문자열 001 및 111을 사용하여 확인할 수 있습니다. 001 및 111에 XOR을 적용하면 110, 즉 ${\displaystyle 001}$ ⊕ ${\displaystyle 111}$ = $110$ ${\displaystyle s}${\display001\opplus 111 = 110 = s}를 얻을 수 있습니다. $이$는 이전과 동일한 솔루션 = ${\displaystyle 110}$ ${\$displaystyle s= 110}을 제공합니다.

이 예제에서 함수 f는 ${\displaystyle {\displaystyle {실제로}^{}}}$ ≠ 0 n ${\displaystyle {\displaystyles$\n$eq$ 0$^{n$

문제경도

직관적으로 임의성을 사용하고 오류의 확률을 조금만 받아들인다 하더라도 이는 "고전적인" 방식으로 해결하기 어려운 문제입니다. 고전적으로 문제를 해결하려면 두 개의 다른 입력 x {\$displaystyle$ x$}$와 y ${\displaystyle$ $y$$}$를 찾아야 합니다. $f{\displaystyle (x)}$ = ${\displaystyle f(}$y$)$ {\displaystyle f(x) = f(y)} 함수 $f{\displaystyle }$ ${\displaystyle f}$에 두 가지 입력을 찾는 데 도움이 되는$$ 구조가 반드시 있는 것은 아닙니다. 보다 구체적으로, 두 가지 다른 입력에 대해 동일한 출력을 얻을 때만 $f{\displaystyle }$ ${\displaystyle f}($또는 그 동작)에 대해 무언가를 발견할 수 있습니다. ${\displaystyle {\displaystyle \sqrt{{어쨌든}^{}}}}$생일 문제처럼 f ${\displaystyle$ ${\displaystyle \Omega({\sqrt$ {2$^{$n$$}})}}$개$의 다른 입력을 추측해야 합니다. 고전적으로 100% 확실성으로 찾으려면${\displaystyle {\displaystyle \sqrt{{}^{}}}}$θ(2$$n) ${\displaystyle {\displaystyle \Theta({\sqrt$ {2$^{$n}}}}} 입력을 확인해야 하기 때문에 사이먼의 문제는 이 고전적인 방법보다 더 적은 쿼리를 사용하여 찾으려 합니다.

사이먼의 알고리즘

전체적으로 알고리즘은 서브루틴을 사용하여 다음 두 단계를 실행합니다.

1. 예상되는 $O{\displaystyle (n)}$ ${\displaystyle$ O$(n)}$번$$ 양자 서브루틴을 실행하여 ${\displaystyle {선형}_{}}$ 독립 비트열 $sy{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{},}$ ...,${\displaystyle }$y${\displaystyle {}_{}}$- ${\displaystyle 1_{}}$ ${\$ ...,$y_{n-1}}$의 목록을 가져옵니다$.$
2. 각 ${\displaystyle y_{}}$ ${\displaystyle y_{k}}$는 y ${\displaystyle k}$ ⋅ = $0$ ${\$displaystyle y_{k}\cdots s=0}을 만족하므로 이것이 생성하는 방정식 체계를 풀어서 {\displaystyle s}을 얻을 수 있습니다.

양자 서브루틴

양자 회로(사진 참조)는 사이먼의 알고리즘의 양자 부분을 구현한 것입니다. 하다마드 변환을 이용한 알고리즘의 양자 서브루틴

여기서 ${\displaystyle k}$ ⋅ ${\displaystyle j_{}}$ =${\displaystyle {}_{}}$k$$1$$j $1$ ⊕ … ⊕ k n n {\displaystyle k\cdot j=k_{1}j_{1}\opplus \ldots \opplus k_{n}j_{n}}, 여기서 ⊕ {\displaystyle \opplus }은 XOR을 나타냅니다.

먼저, 알고리즘은 ${\displaystyle 0{}^{}}$⟩ ⊗ n $0$ ⟩ ⊗ n ${\displaystyle 0\rangle ^{\otimes n}$0$\rangle$otimes n}로 초기화된 두 레지스터로 시작합니다. 그런 다음 상태를 제공하는 첫 번째 레지스터에 하다마드 변환을 적용합니다.

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

오라클 ${\displaystyle {Uf}_{}}$ ${\$를 쿼리하여$$ 상태를 가져옵니다.

${\displaystyle \frac{\mathrm{}}{\sqrt{12}}}$ ${\displaystyle \frac{\mathrm{n}}{}}$ ${\displaystyle \frac{\sqrt{{}^{}}}{}}$ ${\displaystyle \underset{}{\overset{}{k^{}}}}$ ${\displaystyle \underset{}{\overset{}{{}^{}}}}$ $n$ ${\displaystyle \frac{\mathrm{-}}{}}$ 1 k ⟩ f${\displaystyle \frac{\mathrm{}}{}}$( k) ⟩ {\displaystyle {\frac {1}{\sqrt {2^{n}}}\s${\displaystyle \frac{\mathrm{u}}{}}$m _{k=0}^{2^{n}-1} k\rangle f (k)\rangle }.

첫 번째 레지스터에 다른 하다마드 변환을 적용합니다. 이것은 주를 생산할 것입니다.

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k} j\rangle \right] f(k)\rangle =\sum _{j=0}^{2^{n}-1} j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k} f(k)\rangle \right].}$

마지막으로 첫 번째 레지스터를 측정합니다(두 번째 레지스터가 첫 번째 레지스터보다 먼저 측정되면 알고리즘도 작동하지만 이는 불필요합니다). $상태$ ${\displaystyle j}$ ⟩ {\$displaystyle$ j$\$rangle}을(를) 측정할 확률은 다음과 같습니다.

이 벡터의 크기를 제곱하여 첫 번째 레지스터를 $j$⟩ {\$displaystyle$ j$\backslash$rangle}로 가져야 하는 두 번째 레지스터에서 가능한 모든 측정 확률을 합산하기 때문입니다. 측정에는 두 가지 경우가 있습니다.

1. ${\displaystyle s}$ = ${\displaystyle {}^{}}$n {\$displaystyl$${\displaystyle e}$ s = 0^{n}}이고 f {\displaystyle f}는 일대일입니다.
2. $≠$$eq 0^{n}}$이고 $f{\displaystyle }$ ${\displaystyle$ f$}$는 2대1입니다.

첫 번째 경우는.

이 경우 $f{\displaystyle }$ ${\displaystyle f}$는 일대일이므로$$ $f{\displaystyle }$ ${\displaystyle f}$의 범위는 $\{{\displaystyle 0,}$ 1 ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$\{$0,1\}^{n}$이며$,$ 이는 합산이 모든 기저 벡터에 걸쳐 있음을 의미합니다. For the second case, note that there exist two strings, ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$, such that ${\displaystyle f(x_{1})=f(x_{2})=z}$, where ${\displaystyle z\in \mathrm {range} (f)}$. 따라서, 또한 $x$ ${\displaystyle 1_{}}$ ⊕ x ${\displaystyle 2}$ = s${\$$displaystyle x_${1}\opplus x_{2}=s}, x 2 = x 1 ⊕s {\displaystyle x_{2}= x_{1}\opplus s}이므로,이 표현은 이제 쉽게 평가할 수 있습니다. Recall that we are measuring ${\displaystyle j}$. When ${\displaystyle j\cdot s=1}$, then this expression will evaluate to ${\displaystyle 0}$, and when ${\displaystyle j\cdot s=0}$, then this expression will be ${\displaystyle 2^{-n+1}}$.

따라서 $s$ = 0 ${\displaystyle n^{}}${\$displaystyle$s = 0^{$n$}}일 때와 s ≠ 0 n {\displaystyle s\n$eq 0^{n$ $측정$된 j ${\displaystyle j}$는 $j$ $⋅$ $=$ $0${\displaystyle j\cdots s $=$ 0}을 만족합니다.

고전적인 후처리

저희는 선형 독립적인 비트 문자열 ${\displaystyle {sy}_{}}$ 1${\displaystyle {}_{}\dots ,}$ ${\displaystyle {\mathrm{y}}_{}}$- ${\displaystyle 1_{}}$ ${\displaystyle y_{1},\ldots, y_{n-1}}$ 목록이 될 때까지 알고리즘의 양자 부분을 실행하고$,$ 각 ${\displaystyle y_{}}${\$displaystyle y_{k}}$는 ${\displaystyle y{}_{}}$⋅s = $0${\displaystyle y_{k}\cdots s= 0}을 만족합니다. 따라서 이 방정식 체계를 고전적으로 효율적으로 풀어서 ${\displaystyle s}$를 찾을 수 있습니다$.$

${\displaystyle {y\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}\dots ,}$ ${\displaystyle y_{}}$- ${\displaystyle 1_{}}$ ${\$가 선형적으로 독립적일 확률은 적어도

방정식 체계를 풀고 해 $'{\displaystyle$ s$'}$를 만들면$$f${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ = ${\displaystyle f}$ ${\displaystyle (}$s$')$ $displaystyle$ f(0^{n}) = f(s')}를 테스트할 수 있습니다. 이것이 사실이면 = s' = {\displaystyle s' = s', $f$${\displaystyle }$(${\displaystyle 0^{}}$ n${\displaystyle {}^{}}$ = ${\displaystyle f}$($0$ ${\displaystyle n}$ ⊕ s ) = f ( s ) {\$displaystyle$ f (0^{n}) = f (0^{n}\opplus s) = f(s)} 이므로, 만약 f (0 n)이 ≠ f (s') {\displaystyle f (0^{n})\n인 경우라면$equf(s$ 그렇다면 $s$ $=$ ${\displaystyle {}^{}}$n {\displaystyle s $=$ 0^{n}}, ${\displaystyle {}^{}}$ f${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ≠ f ($s$') ${\displaystyle$f ($0$^{n})\n$f{\displaystyle }$ ${\displaystyle f}$이(가) 일대일이므로$$ $equf(s')}$입니다.

우리는 사이먼의 알고리즘을 일정한 횟수 반복하여 임의로 성공 확률을 높이면서도 동시에 동일한 시간 복잡도를 가질 수 있습니다.

몇 큐비트에 대한 사이먼의 알고리즘의 명시적인 예

원큐빗

${\displaystyle \mathrm{n}}$ = 1 ${\$displaystyle n = 1}인 알고리즘의 가장 간단한 인스턴스를 생각해 보십시오. 이 경우 Hadamard 게이트를 통해 입력 상태를 진화시키고 오라클은 (재규격화까지) 상태를 만듭니다.

${\displaystyle 0\rangle f(0)\rangle + 1\rangle f(1)\rangle .}$

$s$ = ${\$$displaystyle$ s = 1}, 즉 f (0 ) = f (1) {\displaystyle f(0) = f(1)}인 경우 두 번째 레지스터를 측정하면 항상 f (0) ⟩ {\displaystyle f(0)\rangle }가 나오고 첫 번째 레지스터는 항상 상태(재규격화까지)로 축소됩니다.

${\displaystyle 0\rangle + 1\rangle .}$

따라서 Hadamard를 적용하고 첫 번째 레지스터를 측정하면 항상 ${\displaystyle 결과}$ 0$$⟩ ${\$$displaystyle$0$\$rangle }가 됩니다$.$ $반면$ f {\$displaystyle$ f}가 일대일인 경우, $즉$ $s$ = 0 {\$displaystyle s$= 0}, 그런 다음 두 번째 Hadamard 이후에 첫 번째 레지스터를 측정하면 ${\displaystyle 동일}$한 확률로 0$$⟩ ${\$$displaystyle$ 0$\$rangle } 및 1 ⟩ {\displaystyle 1\rangle }가 모두 발생할 수 있습니다.

We recover ${\displaystyle s}$ from the measurement outcomes by looking at whether we measured always ${\displaystyle 0\rangle }$, in which case ${\displaystyle s=1}$, or we measured both ${\displaystyle 0\rangle }$ and ${\displaystyle 1\rangle }$ with equal probability, 이 경우 $s$ = ${\displaystyle 0}${\displaystyle s = 0} 이라고 추론합니다. $이$ 방식은 ${\displaystyle \mathrm{s}}$= 0 {\displaystyle s = 0}인 경우 실패하지만, 그럼에도 불구하고 항상 $결과$ 0 ⟩ {\displaystyle 0\rangle }을(를) 찾았지만, 이 이벤트의 확률은 2 - N {\displaystyle 2^{-N}이며, 수행된 측정 횟수는 N {\displaystyle N}입니다. 따라서 통계를 증가시킴으로써 기하급수적으로 작게 만들 수 있습니다.

투 큐빗

$이제$ n = ${\$displaystyle n = 2}인 경우를 생각해 보십시오. 알고리즘의 초기 부분은 (재규격화까지) 상태를 초래합니다.

If ${\displaystyle s=(00)}$, meaning ${\displaystyle f}$ is injective, then finding ${\displaystyle f(x)\rangle }$ on the second register always collapses the first register to ${\displaystyle x\rangle }$, for all ${\displaystyle x\in \{0,1\}^{2}}$. 즉, 하다마드 게이트를 적용하고 첫 번째 레지스터를 측정하면 4개의 결과 ${\displaystyle 00,}$ ${\displaystyle 01,}$ ${\displaystyle 10,}$ ${\displaystyle 11}$ ${\displaystyle 00, 01, 10, 11}$가 동일한 확률로 발견됩니다$$.

${\displaystyle \mathrm{반면}}$에${\displaystyle }$≠$$($00$) ${\displaystyles$\n이라고 가정합니다.$eq(00$ 예를 들어 $s$ $=$ ${\displaystyle (}$01$)$ {\displaystyle s $=$ (01)}입니다. Then measuring ${\displaystyle f(00)\rangle }$ on the second register collapses the first register to the state ${\displaystyle 00\rangle + 10\rangle }$. And more generally, measuring ${\displaystyle f(xy)\rangle }$ gives ${\displaystyle x,y⟩+x,}$${\displaystyle \mathrm{y}\oplus }$ ${\displaystyle 1⟩}$ ${\displaystyle =}$x$⟩$ (0${\displaystyle }$⟩ +${\displaystyle }$⟩) {\displaystyle x,y\rangle + x,y\opplus 1\rangle${\displaystyle }$= x\rangle (0\rangle + 1\rangle )} 첫 번째 레지스터에 있습니다. 따라서 하다마드 게이트를 적용하고 첫 번째 레지스터에서 측정하면 동일한 확률로$$ ${\displaystyle 00}$ ${\displaystyle 00}$ 및$$ ${\displaystyle 10}$ ${\displaystyle 10}$의 결과를 얻을 수 있습니다.

Similar reasoning applies to the other cases: if ${\displaystyle s=(10)}$ then the possible outcomes are ${\displaystyle 00}$ and ${\displaystyle 01}$, while if ${\displaystyle s=(11)}$ the possible outcomes are ${\displaystyle 00}$ and ${\displaystyle 11}$, 일반적인 경우에 논의된 ${\displaystyle j}$ ⋅$s$= 0 {\displaystyle j\cdots = 0} 규칙과 호환됩니다.

따라서 ${\displaystyle}$을(를) 복구하려면 이$$ 네 가지 경우를 구별하기만 하면 됩니다. 따라서 한 결과 확률 분포를 다른 결과 확률 분포로 오인할 확률이 충분히 작다는 것을 보장할 수 있는 충분한 통계를 수집합니다.

복잡성

사이먼의 알고리즘에는 블랙박스에 $O{\displaystyle (n)}$ ${\displaystyle O(n)}$ 쿼리가 필요한 반면, 고전적인 알고리즘에는 최소${\displaystyle {}^{}}$ω${\displaystyle {2n}^{}}$ $/$ 2) ${\displaystyle \Omega($2^{n/2})} 쿼리가 필요합니다. 또한 이 문제를 해결하기 위한 모든 양자 알고리듬에는$$ω(n) ${\displaystyle \Omega($n)} 쿼리가 필요하다는 점에서 사이먼의 알고리듬이 최적인 것으로 알려져 있습니다.

참고 항목

• Deutsch–Jozsa 알고리즘

참고문헌