피터 쇼어 인터넷을 끊으려고 시작한 것이 아닙니다. 그러나 그가 1990년대 중반에 개발한 알고리즘은 바로 그런 일을 하겠다고 위협했습니다. 안에 획기적인 종이, Shor는 양자 물리학의 기이함을 활용한 가상의 컴퓨터가 어떻게 일반 고전 기계보다 훨씬 빠르게 큰 숫자를 소인수로 분해할 수 있는지 보여주었습니다.

그 결과는 수학을 훨씬 넘어서는 의미를 지녔습니다. 당시 인터넷 보안의 핵심 구성 요소인 공개 키 암호화 큰 숫자를 인수분해하는 것은 계산적으로 너무 어려워 사실상 불가능하다는 가정에 의존했습니다. 이러한 가정은 오늘날에도 여전히 일부 중요한 프로토콜을 뒷받침하고 있습니다. Shor의 알고리즘은 강력한 힘이 있는 세상에서는 눈에 띄게 실패할 것임을 보여주었습니다. 양자 컴퓨터.

지난 30년 동안 컴퓨터 과학자들은 양자 기술이 이를 실행할 수 있을 만큼 성숙해지는 날을 대비하여 Shor의 알고리즘을 간소화했습니다. 하지만 새로운 변종, 뉴욕 대학교 컴퓨터 과학자 출신 오데드 레게브, 근본적으로 새로운 의미에서 더 빠릅니다. 인수분해되는 숫자의 크기와 이를 인수분해하는 데 필요한 양자 연산 수 간의 관계를 개선한 최초의 제품입니다.

"누군가가 수년 후에 이 결과의 복잡성을 분명히 개선할 수 있었다는 것은 정말 놀라운 일입니다."라고 말했습니다. 애슐리 몬타나로, 브리스톨 대학의 양자 컴퓨팅 연구원. “정말 신난다.”

마틴 에케로스웨덴 국립통신보안청(Swedish National Communications Security Authority)의 암호학자인 는 Regev의 논문이 흥미롭다는 데 동의했지만 실제로는 최첨단 기술을 깨기 위해서는 추가 최적화가 필요하다고 경고했습니다. "Shor의 원래 알고리즘은 이미 놀라울 정도로 효율적이므로 크게 개선하는 것은 결코 쉬운 일이 아닙니다."라고 그는 이메일에 썼습니다.

Regev는 Shor의 알고리즘을 고차원 기하학을 다루는 암호화 분야의 기술로 확장하여 새로운 알고리즘을 개발했습니다.

현재 매사추세츠 공과대학의 응용 수학자인 Shor는 "이 기본 개요를 사용하는 알고리즘은 모두 망할 것이라고 생각했습니다."라고 말했습니다. “하지만 내가 틀렸어.”

요인 찾기

양자 컴퓨터는 정보를 처리하는 독특한 방식에서 강력한 성능을 얻습니다. 클래식 컴퓨터는 비트를 사용하며, 각 비트는 항상 0과 1로 표시된 두 가지 상태 중 하나에 있어야 합니다. 양자 비트 또는 "큐비트"는 추가적으로 0과 1 상태의 조합일 수 있습니다. 이러한 현상을 중첩이라고 합니다. 여러 큐비트를 집단 중첩 상태로 동축화하는 것도 가능합니다. XNUMX큐비트 중첩에는 서로 다른 계산을 동시에 수행할 수 있는 XNUMX개의 구성 요소가 있으며, 이러한 구성 요소의 수는 큐비트 수가 증가함에 따라 기하급수적으로 증가합니다. 이를 통해 양자 컴퓨터는 기하급수적으로 다양한 계산을 병렬로 효과적으로 수행할 수 있습니다.

그러나 캐치가있다: 중첩에서 수행된 계산 결과를 읽으면 하나의 임의 구성 요소에 의해 계산된 부분에 대한 답만 알 수 있습니다. 중첩 컴퓨팅의 이점을 얻으려면 결과를 안전하게 읽을 수 있는 간단한 상태에 최종 결과를 매핑해야 합니다. 대부분의 경우 이는 불가능하며 처음에는 어떤 문제에 대해 이를 작동시키는 방법을 아는 사람이 아무도 없었습니다. Regev는 “양자 계산에 대해 생각할 용기를 가진 사람은 거의 없었습니다.”라고 말했습니다.

그러다가 1994년에 Shor는 다음과 같은 책을 읽었습니다. 종이 컴퓨터 과학자 Daniel Simon이 인위적인 문제를 해결하기 위해 양자 중첩을 활용하는 방법을 보여주었습니다. Shor는 Simon의 결과를 기간 찾기라는 보다 일반적이고 실용적인 문제로 확장하는 방법을 알아냈습니다. 수학 함수는 입력이 증가함에 따라 출력이 동일한 값을 반복적으로 순환할 때 주기적이라고 합니다. 단일 사이클의 길이는 함수의 주기로 알려져 있습니다.

양자 컴퓨터를 사용하여 주어진 함수의 주기를 찾으려면 각 구성 요소가 다른 입력에 대한 함수의 출력을 계산하는 매우 큰 중첩을 설정하는 것부터 시작하십시오. 그런 다음 Shor의 방법을 사용하여 큰 중첩을 더 간단한 상태로 변환하고 결과를 읽습니다. 그 시점에서는 기존 컴퓨터가 대신해서 계산을 빠르게 완료할 수 있습니다. 전반적으로 Shor의 주기 찾기 알고리즘은 중첩을 사용하여 주기 함수의 다양한 출력을 동시에 계산하기 때문에 어떤 기존 대안보다 기하급수적으로 빠르게 실행됩니다.

Shor는 양자 주기 찾기 알고리즘의 응용 프로그램을 찾다가 이전에 알려졌으나 잘 알려지지 않은 수학 정리를 재발견했습니다. 즉, 모든 숫자에는 주기가 숫자의 소인수와 관련된 주기 함수가 존재한다는 것입니다. 따라서 인수분해하려는 숫자가 있는 경우 해당 함수를 계산한 다음 기간 찾기를 사용하여 문제를 해결할 수 있습니다. Regev는 "정확히 양자 컴퓨터가 잘하는 것이 무엇인지"라고 말했습니다.

기존 컴퓨터에서 이는 많은 수를 인수분해하는 고통스럽고 느린 방법입니다. 가능한 모든 인수를 시도하는 것보다 느립니다. 그러나 Shor의 방법은 프로세스 속도를 기하급수적으로 가속화하여 빠른 양자 인수분해 알고리즘을 구성하는 이상적인 방법을 찾는 기간을 단축합니다.

Shor의 알고리즘은 양자 컴퓨팅을 이론적 컴퓨터 과학의 모호한 하위 분야에서 오늘날의 저거너트로 변화시킨 몇 가지 주요 초기 결과 중 하나였습니다. 그러나 알고리즘을 실제로 적용하는 것은 어려운 작업입니다. 왜냐하면 양자 컴퓨터는 오류에 취약하기로 악명 높기 때문입니다. 계산을 수행하는 데 필요한 큐비트 외에도 다른 작업을 수행하는 많은 사람이 필요합니다. 추가 작업 그들이 실패하지 않도록 하기 위해서입니다. ㅏ 최근 논문 작성자: Ekerå 및 Google 연구원 크레이그 기 드니 Shor의 알고리즘을 사용하여 보안 표준 2,048비트 숫자(약 600자리 길이)를 인수분해하려면 20천만 큐비트를 갖춘 양자 컴퓨터가 필요할 것으로 추정됩니다. 오늘날의 최첨단 기계에는 최대 수백 개가 있습니다.

그렇기 때문에 일부 중요한 인터넷 프로토콜은 여전히 ​​큰 숫자를 인수분해하는 것이 얼마나 어려운지에 의존하지만 연구자들은 너무 안주하고 싶어하지 않습니다. 이론상의 기술 혁신으로 필요한 큐비트 수를 더욱 줄일 수 있으며 Shor의 알고리즘이 최적이라는 증거는 없습니다. 아무도 발견하지 못한 더 나은 양자 인수분해 알고리즘이 있을 수 있습니다.

그렇다면 Regev는 "너무 늦기 전에 가능한 한 빨리 알아야 한다"고 말했습니다.

나무에서 길을 잃다

Regev는 암호화 전문가들이 Shor의 알고리즘에 취약하지 않은 새로운 형태의 공개 키 암호화를 찾고 있던 1990년대 후반에 학문적 경력을 시작했습니다. 가장 유망한 접근 방식은 격자 기반 암호화, 점 또는 격자의 고차원 배열과 관련된 계산 문제의 명백한 어려움에 의존합니다. 그러한 문제 중 하나는 숲의 임의 지점에 가장 가까운 나무를 찾는 작업과 유사합니다.

"XNUMX차원 숲이라면 XNUMX차원 숲보다 훨씬 더 복잡합니다."라고 말했습니다. 그렉 쿠퍼버그, 캘리포니아 대학 데이비스 캠퍼스의 수학자.

Regev는 처음에는 공격자로서 박사후 연구원으로 격자 기반 암호화를 연구하기 시작했습니다. 그는 양자 컴퓨터가 이용할 수 있는 약점을 찾아 새로운 접근 방식을 스트레스 테스트하고 싶었습니다. 그러나 그는 아무런 진전도 이룰 수 없었고, 곧 그보다 더 깊은 이유가 있는지 궁금해졌습니다. 2005년에 그는 실패한 공격을 하나의 전략으로 활용하는 방법을 찾았습니다. 격자 기반 암호화 형태 다른 모든 변형보다 우수합니다.

Kuperberg는 “Oded는 격자에 있어서 정말 뛰어난 인물입니다.”라고 말했습니다.

수년에 걸쳐 Regev는 Shor의 알고리즘을 다음 세대의 학생들에게 가르치면서 격자 기반 암호화를 공격하는 데 사용한 기술이 실제로 인수분해 알고리즘에 유용할 수 있는지 궁금해했습니다. 이는 Shor 알고리즘의 마지막 고전 단계의 한 단계가 XNUMX차원 격자에서 가장 가까운 점을 찾는 것이기 때문입니다. 그 XNUMX차원 문제는 사소하게 쉽지만, 격자 기반 암호화를 뒷받침하는 경도가 있는 수백 차원의 유사한 문제와 유사점은 틀림이 없습니다.

"나처럼 격자를 만드는 사람이라면 '여기에 격자가 있다'고 생각할 것입니다"라고 Regev는 말했습니다. "그러나 그것을 어떻게 활용해야 할지 명확하지 않았습니다." 수년 동안 그는 새로운 양자 인수분해 알고리즘에 대한 다른 아이디어를 생각해 보았지만 아무 성과도 얻지 못했습니다. 그런 다음 지난 겨울 그는 문제로 돌아와서 인수분해와 격자 기반 암호화 사이의 흥미로운 연관성을 찾아내기로 결심했습니다. 이번에 그는 성공을 거두었습니다.

추가 치수

Regev는 Shor 알고리즘의 핵심인 주기 함수를 한 차원에서 여러 차원으로 일반화하는 것부터 시작해야 한다는 것을 알고 있었습니다. Shor의 알고리즘에서 해당 함수에는 난수를 반복적으로 곱하는 작업이 포함됩니다. g, 그 자체로. 하지만 이 함수의 주기는 곱해야 하는 횟수입니다. g 함수의 출력이 반복되기 전에 —은 매우 클 수 있으며, 이는 양자 컴퓨터가 주기 함수를 계산하는 데 사용하는 중첩의 일부 구성 요소에 큰 숫자를 곱해야 함을 의미합니다. 이러한 큰 곱셈은 Shor의 알고리즘에서 계산 비용이 가장 많이 드는 부분입니다.

유사한 XNUMX차원 함수는 대신 숫자 쌍을 사용합니다. g₁ 과 g₂. 곱셈이 포함됩니다 g₁ 그 자체로 여러 번 그런 다음 반복적으로 곱합니다. g₂. 이 함수의 주기도 XNUMX차원입니다. 즉, 다음과 같은 개수로 정의됩니다. g₁ 곱셈과 g₂ 함수의 출력이 반복되기 시작하는 곱셈입니다. 다양한 조합이 많이 있어요 g₁ 과 g₂ 트릭을 수행하는 곱셈.

Regev는 기술적 세부 사항을 통해 알고리즘을 단지 XNUMX차원이 아닌 임의의 수의 차원으로 일반화했지만 그의 초기 결과는 고무적이지 않았습니다. 여러 차원의 주기 함수를 계산하려면 양자 컴퓨터는 여전히 많은 숫자를 곱해야 합니다. 각 숫자는 XNUMX차원의 경우처럼 여러 번 곱해질 필요는 없지만 곱할 수 있는 고유한 숫자가 더 많았습니다. 모든 것이 씻겨진 것 같았습니다.

Regev는 "'좋아요. 제가 모든 것을 높은 차원에서 수행했는데 실행 시간이 Shor의 것과 정확히 똑같습니다'라고 생각합니다"라고 말했습니다. “나는 한동안 그것에 갇혀 있었어요.” 그러다가 그는 곱셈의 순서를 바꾸면 문제를 해결할 수 있다는 것을 깨달았습니다. 그는 양자 계산 과정에서 점점 더 커지는 단일 제품에 반복적으로 숫자를 붙이는 대신 작은 숫자 쌍으로 시작하여 결과 제품을 곱하고 위쪽으로 진행했습니다. 총 곱셈 횟수는 크게 변하지 않았지만 이제 거의 모든 곱셈에 상대적으로 작은 숫자가 포함되어 계산이 더 빨라졌습니다.

“그것이 세상을 완전히 변화시킵니다.”라고 말했습니다. 비 노드 바이 쿠툰 타나 단, MIT의 암호학자.

처음에는 Regev가 한 문제를 다른 문제로 대체한 것처럼 보였습니다. 그는 차원 수를 늘려 주기 함수의 양자 계산 속도를 높였지만, 주기를 추출하는 데 필요한 후속 고전적 계산은 이제 고차원 공간에서 가장 가까운 격자점을 찾는 것과 유사했습니다. 힘들어. 그의 새로운 접근 방식에 동기를 부여한 격자 기반 암호화에 대한 비유는 실패할 운명인 것처럼 보였습니다.

XNUMX월의 어느 추운 아침, 프린스턴 대학교 세미나에 참석하기 전 Regev는 함께 카풀을 하던 동료를 기다리고 있었습니다. 그는 “나는 일찍 도착했는데 그 사람이 차를 픽업하는 데 늦었다”고 말했다. 그가 앉아서 기다리고 있는 동안, 갑자기 퍼즐의 마지막 조각이 그에게 다가왔습니다. "그것은 모든 것이 제자리에 있던 순간이지만 한동안 굽고있었습니다."

모든 것이 올바른 차원 수로 내려졌습니다. 격자 차원이 너무 낮으면 그의 알고리즘은 더 작은 숫자를 곱함으로써 발생하는 속도 향상을 최대한 활용할 수 없었습니다. 너무 높으면 양자 계산이 빨라졌지만 고전적인 부분에서는 엄청나게 어려운 격자 문제를 해결해야 했습니다. Regev는 성공의 희망을 가지려면 그 사이 어딘가에서 일해야 한다는 것을 처음부터 알고 있었지만 최적의 지점이 존재하는지 여부는 확실하지 않았습니다. XNUMX월의 그날 아침, 그는 알고리즘의 세부 사항을 조정하여 수십 개의 차원에서 빠르게 실행될 수 있는 방법을 깨달았습니다.

모래에 쓰기

개선은 심오했습니다. Regev 알고리즘의 양자 부분에서 기본 논리 단계의 수는 다음에 비례합니다. n^1.5 인수분해할 때 n-비트 수보다는 n² Shor의 알고리즘과 같습니다. 알고리즘은 해당 양자 부분을 수십 번 반복하고 결과를 결합하여 고차원 격자를 매핑하고, 이로부터 주기를 추론하고 숫자를 인수분해할 수 있습니다. 따라서 알고리즘 전체가 더 빠르게 실행되지 않을 수 있지만 필요한 단계 수를 줄여 양자 부분의 속도를 높이면 실제로 적용하기가 더 쉬워질 수 있습니다.

물론 양자 알고리즘을 실행하는 데 걸리는 시간은 여러 고려 사항 중 하나일 뿐입니다. 마찬가지로 중요한 것은 필요한 큐비트 수입니다. 이는 일반적인 클래식 계산 중에 중간 값을 저장하는 데 필요한 메모리와 유사합니다. Shor의 알고리즘이 인수분해하는 데 필요한 큐비트 수 n-비트 수는 다음에 비례합니다. n, 원래 형태의 Regev 알고리즘에는 다음에 비례하는 여러 큐비트가 필요합니다. n^1.5 — 2,048비트 숫자의 경우 큰 차이가 있습니다.

클래식 컴퓨팅에서는 일반적으로 메모리보다 속도가 더 중요한 고려 사항입니다. 클래식 비트는 매우 강력하기 때문입니다. 컴퓨터에 파일을 저장하면 나중에 다시 열 때 무작위로 변경되는 것에 대해 걱정할 필요가 없습니다. 양자 컴퓨팅 연구자들이 항상 운이 좋은 것은 아닙니다.

Gidney는 “우리의 큐비트는 끊임없이 무너지려고 노력하고 있으며, 우리는 큐비트가 무너지는 것을 막으려고 노력하고 있습니다.”라고 말했습니다. “모래 위에 글을 쓰려고 하는데 바람이 불어서 날아가는 것과 같습니다.” 이는 Regev의 알고리즘에 필요한 추가 큐비트가 주요 단점이 될 수 있음을 의미합니다.

그러나 Regev의 논문이 이야기의 끝은 아닙니다. XNUMX주 전, Vaikuntanathan과 그의 대학원생인 Seyoon Ragavan은 알고리즘의 메모리 사용을 줄이는 방법을 찾았습니다. 그들의 변종 Shor의 원래 알고리즘과 마찬가지로 Regev의 알고리즘에는 다음에 비례하는 여러 큐비트가 필요합니다. n 보다는 n^1.5. Ekerå는 이메일을 통해 이 작업을 통해 "실제로 더욱 효율적인 구현에 훨씬 더 가까워질 수 있게 되었습니다"라고 썼습니다.

인수분해에 대한 의미를 넘어서 Regev의 새로운 알고리즘이 주는 더 넓은 교훈은 양자 컴퓨팅 연구자들이 수십 년 동안 연구된 문제에서도 항상 놀라움에 열려 있어야 한다는 것입니다.

Shor는 "내 알고리즘의 이 변형은 30년 동안 발견되지 않았으며 갑자기 나타났습니다."라고 말했습니다. "아직도 발견해야 할 다른 양자 알고리즘이 많이 있을 것입니다."

편집자 주: Oded Regev는 시몬스 재단, 또한이 편집 독립 잡지에 자금을 지원합니다. Simons Foundation 기금 결정은 우리의 보장에 영향을 미치지 않습니다. 자세한 내용은 여기를 클릭하십시오..

콴타 에서는 청중에게 더 나은 서비스를 제공하기 위해 일련의 설문조사를 실시하고 있습니다. 우리의 컴퓨터 과학 독자 설문조사 그러면 당신은 무료로 승리할 수 있는 자격을 얻게 될 것입니다 콴타 판매