2016 년 과학 논문 ” 확장 가능한 Shor 알고리즘의 실현 “[ 1 ]에서 저자는 5 qubits만으로 15를 인수하여 [ 2 ] 의 표 1 과 [ 3의 표 5에 따라 “필수”인 8 qubit보다 적습니다. ]. 8 큐빗 요구 사항은 [ 4 ] 의 끝에서 온다 . 이것은 비트 수 를 인수 분해하는데 필요한 큐 비트의 수가 이고 15의 경우 임을 나타낸다 .1.5 n + 2 1.5 ⋅ 4 + 2 = 8
5 qubits만을 사용하는 논문은 그들의 알고리즘이 M 큐빗에 작용하는 QFT를 단일 큐 비트에 반복적으로 작용하는 준 클래식 QFT로 대체한다고 언급하지만 , 알고리즘 의 복잡성 에 대한 결과 는 결코 논문에서 언급되지 않았습니다.
이제이 있었다 가혹한 비판 그들이 쇼어의 알고리즘의 복잡성 인수가 더 이상 유지하는 것이 제 2 말할 같은 “확장”방식으로 요소 (15)에 주장하는 종이. 그러나 이러한 비판은 어느 곳에서도 확증되지 않았으며 과학 논문은 Shor 알고리즘의 “확장 가능한”버전으로 계속 유명 해지고 있습니다. “확장 가능한”Shor 알고리즘의 복잡성은 무엇입니까?
답변
Cao와 Luo의 주장에 대한 주요 견해는 구현 된 알고리즘의 변형에서 첫 번째 레지스터 (결과적으로 출력을 포함)는 1 비트 만 포함한다는 것입니다. 그리고 알고리즘에서 1 비트의 출력 만 얻는다면 인수 분해에 충분하지 않습니다. (한 가지, 이것이 그들의 주장은 아니지만, 1 비트에는 요인을 결정하기에 충분한 정보가 명확하게 포함되어 있지 않습니다.)
Cao와 Luo가 인식하지 못하는 것은 첫 번째 레지스터에서 1 비트만으로 푸리에 변환의 변형 에 대해 표준 인수 분해 알고리즘에서 와 동일한 값 이 출력 된다는 것입니다 . 한 번에 한 비트 만 출력 됩니다.
이 변경 사항은 O ( log 3 N ) 실행 시간에 영향을 미치지 않습니다 .
Cao와 Luo에게 공정하게 노력하기 위해 그들은이 알고리즘이 작동한다고 생각하지 않으며 작동하면 원래 인수 분해 논문에 설명 된 알고리즘과 정확하게 일치하지 않기 때문에 Shor의 알고리즘이 아닙니다 . 그들의 논문에서 인용 :
마지막으로, 우리는 구현이 실제로 신뢰할 만하다면, 원래 Shor 알고리즘의 모든 요구 사항이 충족되지 않기 때문에 Shor 알고리즘이 아닌 새로운 양자 인수 알고리즘이 될 것이라고 강조하고 싶습니다.
그리고 실제로, 그것은 내 원래 팩토링 논문의 알고리즘이 아닙니다. Kitaev의 인수 분해 알고리즘의 위상 추정 절차와 Griffiths와 Niu (파커와 Plenio가 아닌이 답변의 이전 편집에서 언급 한)가 발견 한 변형을 사용하여 알고리즘이 위상의 추정값을 출력하도록합니다. 한 번에 한 비트.
