양자 컴퓨팅 혁신 특허 등록 – 제5부: 쇼어 알고리즘 및 결론

By Sinan Utku

예시 4: Shor’s Algorithm

Shor’s algorithm은 문제를 주기 찾기 작업으로 변환함으로써 큰 정수를 소인수로 효율적으로 분해하며, 이는 고전 컴퓨터보다 양자 컴퓨터에서 훨씬 더 효율적으로 해결될 수 있습니다. 이 알고리즘은 입력의 양자 중첩을 준비하고 모듈러 지수 함수를 평가하기 위한 양자 게이트를 준비하는 과정을 포함합니다. 그런 다음 양자 위상 추정을 적용하여 이 함수의 주기를 추출합니다. 여기에는 모듈러 지수 변환을 위한 양자 게이트의 제어된 거듭제곱을 적용한 다음, 역 양자 푸리에 변환을 수행하여 주기에 대한 정보를 얻는 과정이 포함됩니다. 주기가 결정되면, 고전 알고리즘을 사용하여 정수의 소인수를 비교적 쉽게 계산합니다. Shor’s algorithm은 알려진 최고의 고전 소인수 분해 알고리즘보다 기하급수적으로 빠르기 때문에, 큰 정수 분해의 어려움에 의존하는 RSA와 같이 널리 사용되는 공개 키 암호 시스템에 심각한 위협이 됩니다.

키의 도움 없이 RSA로 암호화된 통신을 복호화하는 양자 컴퓨터는 다음과 같은 Shor’s algorithm을 수행할 수 있습니다:

• 계산 기저 상태로 초기화된 고유값 큐비트들이 있는 첫 번째 양자 레지스터와, 소인수 분해하고자 하는 곱 숫자에 대응하는 고유벡터 큐비트들로 초기화된 두 번째 양자 레지스터를 준비합니다;
• 각 고유값 큐비트에 Hadamard 게이트를 적용하여 중첩 상태로 둡니다;
• 모듈러 지수 변환과 관련된 유니터리 연산의 일련의 거듭제곱을 두 번째 양자 레지스터에 적용합니다. 여기서 각 유니터리 연산의 거듭제곱 적용은 대응하는 고유값 큐비트에 의해 제어되며, 고유값 큐비트는 위상 킥백(phase kick-back)을 통해 수정됩니다;
• 첫 번째 양자 레지스터에 역 양자 푸리에 변환을 수행하여 양자 위상 추정을 실시하고, 두 번째 양자 레지스터에 작용하는 기본 유니터리 연산자 U에 대응하는 위상의 추정치를 얻습니다;
• 위상 추정치로부터 주기 파라미터를 도출하고, 도출된 주기 파라미터를 사용하여 곱 숫자에 대응하는 소인수를 결정합니다; 그리고
• 결정된 소인수, 관련 공개 키 및 곱 숫자를 사용하여 암호화된 메시지를 복호화합니다.

이 발명의 특허 적격성은 도전받을 가능성이 높습니다. 구체적으로, 적어도 초기에는 기계에 대한 기술적 개선보다는 수론적 문제를 해결하기 위한 수학적 방법에 관한 것이라는 점에서 추상적이라고 판단될 가능성이 큽니다. Shor’s algorithm의 알고리즘 구성 요소는 양자 위상 추정 및 역 양자 푸리에 변환을 통한 주기 찾기와 같은 일련의 수학적 연산으로 구성됩니다. 양자 컴퓨터 자체의 작동에 대한 구체적인 개선 사항이 없는 한, 양자 컴퓨터에서 이러한 수학적 연산을 수행하는 것만으로는 특허 적격성이 부여되지 않을 가능성이 높습니다. 논쟁의 여지가 있지만, 이 알고리즘의 유일한 개선 사항은 수학적 처리, 즉 양자 컴퓨터를 사용하여 숫자를 더 효율적으로 소인수 분해하는 것에 불과합니다. 비판적인 PTO 심사관은 이 발명을 중첩, 제어된 유니터리 게이트 및 양자 푸리에 변환과 같은 관습적이고 알려진 양자 컴퓨팅 프로세스를 사용하여 개선된 수학적 방법을 수행하는 것으로 특징지을 가능성이 큽니다. 또한 그러한 PTO 심사관은 이러한 발명의 특허화로 인해 발생할 수 있는 기초적인 수학적 원리 사용에 대한 광범위한 선점 위험을 강조할 것입니다. 따라서 이 발명은 현재 법률하에서 궁극적으로 부적격 판정을 받을 가능성이 높습니다.