1994년에 한 수학자가 양자 컴퓨터가 일반적인 고전 컴퓨터로는 할 수 없는 일을 하도록 만드는 방법을 알아냈습니다. 이 작업은 원칙적으로 양자 역학의 규칙에 기반한 기계가 많은 수를 소인수로 효율적으로 분해할 수 있음을 보여주었습니다. 이는 오늘날 인터넷 보안의 기반을 형성하는 고전적인 컴퓨터로는 매우 어려운 작업입니다.
낙관론이 급증했습니다. 아마도 연구자들은 우리가 다양한 문제를 해결할 수 있는 양자 알고리즘을 발명할 수 있을 것이라고 생각했습니다.
그러나 진전이 멈췄습니다. "그것은 약간 실망스러운 궤적이었습니다."라고 말했습니다. 라이언 오도넬 카네기멜론대학교 출신. “사람들은 '이거 정말 놀랍다. 우리가 다른 온갖 놀라운 알고리즘을 얻게 될 거라고 확신해'라고 말했습니다. 아니요." 과학자들은 표준 세트 내에서 단 하나의 좁은 문제 종류에 대해서만 극적인 속도 향상을 발견했습니다. NP라고 함, 이는 인수 분해와 같은 효율적으로 검증 가능한 솔루션을 가지고 있음을 의미합니다.
거의 XNUMX년 동안 그랬습니다. 그러다가 XNUMX월에 연구자들은 발명 양자 컴퓨터가 기존 컴퓨터보다 기하급수적으로 빠르게 해결할 수 있어야 하는 근본적으로 새로운 종류의 문제입니다. 여기에는 뒤죽박죽된 출력만을 기반으로 복잡한 수학적 프로세스에 대한 입력을 계산하는 작업이 포함됩니다. 문제가 단독으로 발생하는지, 아니면 다른 많은 새로운 영역에서 첫 번째 문제인지는 아직 결정되지 않았습니다.
“흥분감이 있다”고 말했다. 비 노드 바이 쿠툰 타나 단, MIT의 컴퓨터 과학자입니다. "많은 사람들이 저 밖에 무엇이 있는지 생각하고 있습니다."
컴퓨터 과학자들은 양자 컴퓨터를 대표하는 수학적 모델을 연구함으로써 양자 컴퓨터가 무엇을 더 잘하는지 이해하려고 노력합니다. 종종 그들은 오라클이라고 불리는 이상적인 계산 기계와 결합된 양자 또는 고전 컴퓨터 모델을 상상합니다. 오라클은 단순한 수학적 함수나 컴퓨터 프로그램과 같아서 입력을 받고 미리 결정된 출력을 내보냅니다. 입력이 특정 임의 범위(예: 12~67)에 속하면 "예"를 출력하고 그렇지 않으면 "아니오"를 출력하는 임의의 동작을 가질 수 있습니다. 또는 주기적일 수 있으므로 1~10 사이의 입력은 "예"를 반환하고, 11~20은 "아니요"를 반환하고, 21~30은 다시 "예"를 반환하는 식으로 계속됩니다.
당신이 이러한 주기적인 오라클 중 하나를 가지고 있고 그 주기를 모른다고 가정해 봅시다. 당신이 할 수 있는 일은 숫자를 입력하고 출력 내용을 확인하는 것뿐입니다. 이러한 제약 조건을 사용하면 컴퓨터가 기간을 얼마나 빨리 찾을 수 있습니까? 1993년 당시 몬트리올 대학교의 다니엘 사이먼(Daniel Simon)은 양자 알고리즘이 어떤 기존 알고리즘보다 기하급수적으로 빠르게 밀접하게 관련된 문제에 대한 답을 계산할 수 있음을 발견했습니다.
그 결과 사이먼은 양자 컴퓨터의 극적인 우월성을 기대할 수 있는 첫 번째 힌트 중 하나를 결정할 수 있었습니다. 그러나 그가 주요 학회에 논문을 제출했을 때 거절당했습니다. 그러나 그 신문은 컨퍼런스 프로그램 위원회의 후배 위원에게 관심을 보였습니다. 피터 쇼어, 당시 뉴저지의 벨 연구소에 있었습니다. Shor는 계속해서 Simon의 알고리즘을 적용하여 신탁이 있는 경우 신탁의 기간을 계산할 수 있다는 사실을 발견했습니다. 그런 다음 그는 주기적인 오라클과 유사하게 동작하는 방정식, 즉 주기적인 인수분해를 설명하는 방정식을 풀기 위해 알고리즘을 다시 한 번 적용할 수 있다는 것을 깨달았습니다.
Shor의 결과는 역사적이었습니다. 그가 발견한 양자 알고리즘은 거대한 숫자를 구성 소인수로 신속하게 줄일 수 있는데, 이는 알려진 기존 알고리즘이 할 수 없는 일입니다. 그 후 몇 년 동안 연구자들은 다른 효율적인 양자 알고리즘을 발견했습니다. Shor의 알고리즘과 같은 일부는 지수적 이점을 제공하기까지 했지만 주기적이지 않은 NP 문제에 대해서는 누구도 극적인 양자 이점을 증명할 수 없었습니다.
이러한 진전의 부족으로 인해 두 명의 컴퓨터 과학자가 스콧 론슨 텍사스대학교 오스틴캠퍼스와 안드리스 암바이니스 라트비아 대학교의 관찰 결과입니다. 양자적 이점의 증명은 항상 주기성과 같은 일종의 비무작위 구조를 갖는 오라클에 의존하는 것처럼 보였습니다. 2009년에 그들은 추측 무작위적이거나 구조화되지 않은 NP 문제에는 극적인 속도 향상이 있을 수 없습니다. 누구도 예외를 찾을 수 없었습니다.
그들의 추측은 양자 컴퓨터의 성능에 한계를 두었습니다. 그러나 특정 유형의 구조화되지 않은 NP 문제, 즉 예 또는 아니요로 대답하는 문제에 대해서는 극적인 속도 향상이 없다고만 말했습니다. 좀 더 구체적이고 정량적인 답변을 찾는 문제(검색 문제라고 함)의 경우에는 추측이 적용되지 않았습니다.
이를 염두에 두고 연구자들은 야마카와 다카시 NTT 사회 정보학 연구소 및 마크 잔드리 NTT Research와 Princeton University는 2005년에 소개된 특정 검색 문제를 실험하기로 결정했습니다. 오데드 레게브.
모두 같은 방향을 가리키는 풍향계 세트를 상상해 보세요. 그들 각각에게 신중하게 밀고 나서 돌풍이 그들의 방향에 영향을 미치도록 하십시오. Regev는 최종 방향을 기반으로 처음에 모두가 가리키는 곳을 결정하고 싶었습니다. 밀림과 바람이 원래 방향에서 무작위 오류의 원인처럼 작용하기 때문에 이와 같은 문제를 "오류가 있는 학습"이라고 부르게 되었습니다. 고전 알고리즘과 양자 알고리즘 모두 해결하기 어렵다는 증거가 있습니다.
Yamakawa와 Zhandry는 설정을 조정했습니다. 그들은 선발 올인의 강도를 수정하여 더 예측 가능하게 만들었습니다. 그들은 또한 바람이 임의의 신탁에 의해 결정되도록 하여 어떤 경우에는 훨씬 더 무작위였지만 다른 경우에는 완전히 휴면 상태가 되도록 했습니다.
연구진은 이러한 수정을 통해 양자 알고리즘이 초기 방향을 효율적으로 찾을 수 있음을 발견했습니다. 그들은 또한 모든 기존 알고리즘이 지수적 요인에 의해 더 느려진다는 것을 증명했습니다. Shor와 마찬가지로 그들은 문제의 실제 버전을 해결하기 위해 알고리즘을 조정했으며, 이는 오라클을 실제 수학 방정식으로 대체했습니다.
컴퓨터 과학자들은 여전히 이 문제를 이해하고 발전시키기 위해 노력하고 있습니다. Vaikuntanathan은 이를 데이터 압축 시 발생하는 다른 현상과 비교합니다. 즉, 정보를 압축할 때 두 비트가 실수로 같은 위치에 압축되어 덮어쓰일 수 있습니다. 이러한 충돌을 미리 예측하여 이를 방지하는 문제는 어느 정도 유사합니다. “이것은 기본적으로 다음과 같은 종류의 문제입니다.”라고 그는 말했습니다. "아마도 이러한 문제는 양자적으로 해결될 수 있을 것입니다."
새로운 문제와 같은 구조화되지 않은 문제는 오늘날의 초기 버전의 양자 컴퓨터에서도 해결 가능하여 이를 테스트할 수 있는 수단을 제공할 수 있다는 희망이 있었습니다. 구조화되지 않은 문제는 이미 무작위이기 때문에 프로그래밍하는 데 더 적은 리소스가 필요하거나 노이즈에 덜 민감할 수 있다고 생각했습니다. 그러나 지금까지 새로운 문제는 기존 양자 컴퓨터가 해결하기에는 너무 발전된 것으로 보입니다. “이상한 문제네요. 나는 그것을 정의할 생각이 없었다”고 Aaronson은 말했다. "하지만 돌이켜보면 아주 좋은 기능이 몇 가지 있었습니다."
결과는 구조화되지 않은 NP 문제에 대한 극적인 양자 이점의 첫 번째 예를 제공합니다. 양자 세계가 실질적으로 해결 불가능한 문제에서 해결 가능한 문제로 바뀌는 데는 다른 많은 문제가 있을 수 있을까요? 이제 그렇게 생각할 이유가 더 많아졌습니다.
O'Donnell은 “양자 컴퓨터가 어떤 종류의 문제를 잘 풀 수 있는지에 대한 우리의 믿음이 다소 뒤집혔습니다.”라고 말했습니다.
