피터 쇼어

1. 개요[편집]

---

피터 쇼어(peter shor, 1959 8/14~)은 미국의 컴퓨터과학자이다. 연구분야는 응용수학, 이론 컴퓨터 과학, 이론물리학이다. RSA 암호화를 무력화하는 양자 알고리즘인 쇼어 알고리즘의 고안으로 유명하다.

2. 약력[편집]

---

2.1. 대학 진학 이전[편집]

---

1977년에 미국수학올림피아드에 출전해서 전체 3등을 기록했고, 동년 유고슬라비아에서 열린 IMO에서 은메달을 수상했다. 1년뒤 미국 학부 수준 수학경시대회인 윌리엄 로웰 퍼트넘 수학경시대회에서 fellow 자격[1]을 획득했다.

2.2. 양자 컴퓨팅으로의 접근[편집]

---

1981년 쇼어가 캘리포니아 공과대학교에 재학중이었을때 음의 확률에 대한 리처드 파인만의 강의를 들은적이 있었다. 강의는 대략적으로 벨의 이론이 EPR 역설을 보이고 양자역학과 맞지 않자 0보다 작고 1보다 큰 모든 실수라는 숨은 가정을 찾아내어 확률을 더해가면 확률의 합은 0,1사이에 존재한다는 내용이었다. 하지만 파인만은 원래의 가정을 고려하지 않았고, 몇년뒤 음의 확률에 대한 논문에서도 벨의 부등식을 언급하기보다는 무한의 모순을 피하는 동기에 대해 언급했다. 쇼어는 파인만의 방법이 잘못된 것을 인정하기보다는 감추는 것에 신경썻고 모순에 대한 결과를 낼수가 없었다고 생각했다.

1986년 즈음 벨 연구소에서 찰리 베넷을 통해 본격적으로 양자 컴퓨팅을 알게 되었다. 찰리는 쇼어에게 수학적 공리로 설계한 BB84 key distribution protocol이라는 보안 시스템을 소개했다. 쇼어는 맨 처음 보안 시스템을 풀지 못했다.[2]BB84는 일반 컴퓨터로 해결하기에는 너무나 복잡했던 것이었다.

1992년 우메시 바자라니라는 컴퓨터 과학자가 벨 연구소를 방문했을때 양자 튜링 머신을 번슈타인-바지라니 문제라는 수학적으로 복잡한 문제에 대입해 알고리즘을 얻었고 양자 튜링 머신을 활용한 알고리즘은 그 문제를 고전적인 컴퓨터보다 빨리 연산하는 것을 보여주었다. 쇼어는 그때 고전적인 컴퓨터 연산보다 양자컴퓨팅이 매우 편리하고 빠른 연산 방식이었음을 깨달았다.

2.3. RSA 암호화에 대한 접근[편집]

---

양자 컴퓨팅에 대한 확고한 생각은 n차원 다면체의 꼭짓점들의 주기를 찾으라는 시몬 문제와 이산로그 문제의 논문을 보고들었다. 한 예를 들자면 수백차원의 다면체를 상상하면 쉽게 가늠이 가지 않는다. 하지만 시몬 문제는 다면체가 수평으로 이동하면 특징이 같은 꼭짓점을 볼수있다는 것을 나타내기 때문에 시몬 문제를 활용하면 함수에 대한 주기를 이진법의 벡터를 연산하면 특성이 같은 다른 꼭짓점을 얻게되고 일종의 힌트로써 추론이 가능한 주기를 찾는 것이다. 시몬이 이를 증명한 방법이 이진 벡터 공간에 푸리에 변환을 적용시킨 것이다. 쇼어는 여기서 푸리에 변환이 이진 벡터를 연산하는데에 유용하다는 힌트를 얻게되었다. 이산로그 문제는 시몬 문제보다 더 간단한 주기 문제다. 두개의 임의의 꼭짓점을 오른쪽으로 이동시키고 한 꼭짓점을 아래로 이동시킬때, 특징이 같은 또 다른 꼭짓점을 볼수 있다. 그러므로 큰 torus의 주기를 찾는게 가능하다.[3]. 쇼어는 푸리에 변환이 주기를 찾는데 중요한 것임을 알았고 넓은 주기 범위에서 양자 컴퓨터에 푸리에 변환을 어떻게 적용시키는지 생각하기 시작했다.

2.4. 쇼어 알고리즘 고안&발표[편집]

---

쇼어는 “소인수분해에 관한 이산 지수 주기성”을 주제로 양자 알고리즘에 관한 자신의 아이디어와 노하우를 논문으로 정리해서 1994년 제 35차 IEEE 컴퓨터 과학 심포지엄에 쇼어 알고리즘을 발표했다.