Programming Quantum Computers의 QFT 이후 그래프 (241 페이지)에서 흥미로운 스파이크는 무엇입니까?

Dec 05 2020

저는 Shor의 알고리즘을 이해하기 위해 Programming Quantum Computers를 읽고 있습니다. 나는 우리가 상태를 준비하는 것을 배웠다.$|x^i \bmod N\rangle$, 그런 다음이 상태에 QFT를 적용합니다. QFT는 진폭을 균일 중첩에서 일정 기간 동안 균등하게 배치 된 큰 진폭으로 변경합니다.$x^i \bmod N$. 예를 들어, 다음은 QFT를 적용한 후의 진폭 그래프입니다.$N = 35$. 241 페이지에 있습니다.

이 책은 12 개의 스파이크가 균등하게 간격을두고 있다고 말합니다. 12 개 이상의 스파이크가 균등하게 간격을두고 있습니다. 가장 높은 것만 세고 12를 세었을 때 멈춰야합니까? 그러나 그것은 주관적이지 않습니까? 정답을 모른 채이 그래프를 보면 숫자가 실제로 12라는 것을 어떻게 알 수 있습니까? (즉, 어떻게 12 개를 얻습니까?)

답변

3 MarkS Dec 06 2020 at 05:07

재현 한 그래프를 보면 왼쪽 그래프는 $2^x\bmod 35$ ...에 대한 $x\in\{0,\dots 63\}$ 오른쪽 그래프는에 대한 이산 푸리에 변환의 진폭을 보여줍니다. $\hat{x}\in\{0,\dots 63\}$. "12 개의 균일 한 간격 스파이크"가 있다는 주석은 오른쪽 그래프의 로컬 최대 값이 매번 반복됨을 나타냅니다.$64/12=5.33$ 가치.

당신은 맞습니다, 당신은 액세스 할 수 없습니다 $\hat{x}$ 이 주기성을 관찰 할 수있는 방식으로 $\hat{x}$바로; 그러나, 당신이 에 액세스 할 수있는 것은 샘플 방법입니다$\hat{x}_i$ 여러 $i$ 반환하는 방식으로 $\hat{x}_i$ 각각의 높이 (의 제곱)에 의해 주어진 확률로 $\hat{x}_i$.

예를 들어, 모듈 식 지수 (왼쪽 그래프)와 QFT (오른쪽 그래프)를 실행하고 첫 번째 레지스터를 샘플링하면 다음과 같은 값을 얻을 수 있습니다. $0$ 보다 높은 확률로 $5$,보다 높은 확률로 $32$,보다 높은 확률로 $11$,보다 높은 확률로 $6$

이러한 각각의 샘플링에서 $\hat{x}_i$, Shor 알고리즘의 고전적인 부분 (연속 분수 부분)을 실행하여 실제로 12 개의 균일 한 간격의 스파이크가 있음을 추론 할 수 있습니다. $\hat{x}$, 기간 제공 $12$$2^x\bmod 35$. 제가 잊고있는 많은 세부 사항이 있지만 요점은 QFT의 샘플을이 고전적인 부분에 대한 입력으로 사용한다는 것입니다.