▲

왜 아직 양자컴퓨터는 21을 소인수분해하지 못했는가

 (algassert.com)
1P by GN⁺ 2일전 | ★ favorite | 댓글 1개
  • 2001년에 양자컴퓨터로 15를 소인수분해한 이후 진전이 없는 것처럼 보이는 현상 설명
  • 21을 소인수분해하는 회로에는 15를 소인수분해할 때보다 100배 더 많은 얽힘 게이트가 필요함
  • 이 차이는 조건부 모듈러 곱셈의 복잡성과 15에만 적용되는 특별한 최적화 덕분임
  • 양자 오류정정과 하드웨어 한계도 21 소인수분해까지의 진입 장벽을 더욱 높임
  • 현재까지 보고된 21 소인수분해는 대부분 진정한 의미의 곱셈 수행 없이 트릭을 쓴 경우임

왜 아직 양자컴퓨터는 21을 소인수분해하지 못했는가

15 소인수분해 이후 21 소인수분해가 등장하지 않은 이유

  • 2001년 양자컴퓨터로 15를 소인수분해한 실험이 있었음
  • 2025년이 되었지만 아직 21 소인수분해 성공 사례는 없음
  • 이 점을 근거로 양자컴퓨터에 진전이 전혀 없다는 인식이 퍼져있음
  • 그렇지만 실제로는 15와 21의 소인수분해 회로를 비교하면 훨씬 더 놀라운 이유가 있음

15 소인수분해 회로와 21 소인수분해 회로의 구조적 차이

  • 15 소인수분해 회로는 양자 게이트 21개(얽힘 게이트 21개) 만으로 구현됨
    • 6개의 이큐빗 얽힘 게이트(CNOT 및 CPHASE 게이트)와
    • 2개 Toffoli 게이트(각각 6개 얽힘 게이트로 분해), 합계 21개 얽힘 게이트로 구성됨
  • 21 소인수분해 회로는 191개 CNOT, 369개 Toffoli, 총 2405개 얽힘 게이트 필요
    • 15를 소인수분해할 때보다 115배 더 많은 얽힘 게이트 부담 발생
    • 회로 크기가 단순히 25%, 2배 증가가 아니라 100배 이상 비싸짐
  • 회로 최적화 수준을 감안해도 500배 차이까지도 현실적으로 가능해 보임

왜 이렇게 큰 차이가 생기는가

  • 양자 소인수분해 회로(Shor의 알고리듬) 에서 지배적인 비용은 조건부 모듈러 곱셈임
    • n비트 숫자 N에 대해, 여러 번 조건부로 누산기에 모듈러 곱셈을 수행해야 함
    • 이 때, 15의 경우 8번의 조건부 곱셈 중 6번은 1 곱셈(아무 작업 없음) 으로 처리 가능
      • 첫 번째 곱셈은 입력이 1이어서 ~공짜로 구현 가능
      • 두 번째(남은 하나)도 두 번의 CSWAP으로 저렴하게 처리 가능
      • 그 결과 실제로 2개만 비용 지불 필요
      • 이 구조는 15에만 해당하는 특별한 성질로, 1에 가까운 곱셈이 다수라서 부담이 현저히 적음
  • 하지만 21의 경우 곱셈이 모두 1이 아니고 값이 다양해서 모든 곱셈이 비용 발생
    • 곱셈 연산이 8번 모두 비용 발생, 단순히 4~5배가 아니라 20~100배 증가
    • 곱하기 4나 16 같은 곱셈은 CSWAP(조건부 스왑)으로 구현할 수 없는 구조
    • 곱셈의 복잡성이 곱셈마다 다르고, 최적화가 쉽지 않음

하드웨어 및 오류 정정의 현실적 한계

  • 과거(2001)의 15 소인수분해는 NMR 양자컴퓨터로 구현, 확장에 한계가 많음
  • 더 나아가 양자 오류정정 필요성도 커짐
    • 게이트 수가 100배 많아지면 오류율은 100배 더 낮아야 함
    • 실제로는 qubit 수도 100배 늘릴 필요까지 있어 전체 비용이 10,000배까지 상승 가능

소인수분해 시도 논란 및 잘못된 결과들

  • 최근 몇몇 논문들에서 양자컴퓨터로 21 소인수분해에 성공했다고 주장하지만
    • 실제로는 알고리듬의 곱셈 수행을 생략하거나 결과를 미리 알고 회로를 단순화한 경우가 많음
    • 진짜 곱셈 연산을 하지 않는 한, 이는 소인수분해라고 볼 수 없음
    • 단순한 "주기 찾기"와 소인수분해의 본질적 차이를 무시한 체적 결과임
  • 일부 논문은 노골적으로 트릭을 쓰거나, 해당 연구에 대해 풍자 논문이 나오기도 함
    • 소인수분해 챔피언 기록 복제 실험 등 여러 풍자 논문 존재
    • Variational factoring 등 규모 확장 근거가 없는 벤치마크만 계속 등장

제대로 된 양자컴퓨터 진전의 지표는 무엇인가

  • 현 시점에서 소인수분해는 양자컴퓨터 진전의 주요 벤치마크가 아님
    • 15를 넘어서면 비용 폭증으로 실용적 검증이 어려움
  • 오히려 양자 오류정정 도입(예: surface code 개선) 이나
    • 스케일링 문제를 해결하는 하드웨어 아키텍처 변화(예: 중성원자 지속적 교체 등) 가
    • 실질적 진전을 보여주는 더 중요한 관측 지점임
▲
GN⁺ 2일전  [-]
Hacker News 의견

  • 아직까지 더 작은 수를 실제로 인수분해한 적이 없었음에 기인함. 만약 프로그램의 컴파일 과정이 이미 답을 알고 있어야만 돌아가는 형태라면, 그건 진짜 인수분해가 아니라 "3을 출력"하는 것에 불과하다는 생각임

  • 실제로 암호적으로 의미 있는 수를 인수분해하려면 몇 개의 quantum gate가 필요한지 궁금함. 이번 세기 내에 쓸 만한 양자 컴퓨터가 나올 가능성에 대한 실질적인 경로가 있는지도 알고 싶음

    • 2048비트 RSA 인수분해에 약 70억 개의 Toffoli gate가 필요하다는 논문 Table 5의 추정치를 예시로 들 수 있음(논문 링크). 수십억 개의 연산을 달성하기 위한 방법은 바로 양자 오류 보정이며, distance 25 surface code가 충분하다고 논문은 밝힘. 이 경우 논리적 큐빗 1,400개에서 실제 노이즈가 있는 큐빗 약 100만 개로 확장됨. PQCrypto에서 했던 Samuel Jacques의 강연도 참고할만함(유튜브). 본인은 이 블로그와 관련 논문의 저자임
    • 이 질문이 어려운 이유가 두 가지 있음. 첫째, '암호적으로 유의미한'이란 경계를 그릴 수 없음. 둘째, 실제 이 연산을 할 수 있는 QC의 구조가 아직 명확하게 알려지지 않았음. 마치 1985년에 신경망을 만들기 위해 필요한 전통 논리 게이트 수를 추정하는 것과도 비슷함. 그래도 수백만 개 이상의 게이트는 필요함이 확실해 보임. 세 번째로, 양자 오류 보정에서의 더 낮은 원시 큐빗 오류율과 신뢰성 있는 오류 보정 가상 큐빗 구축에 필요한 gate 수 사이의 트레이드오프가 존재함. 앞으로 원시 큐빗의 오류율이 어디까지 낮아질지 지금은 알 수 없음. 지난 75년간의 컴퓨터 발전과 비슷한 발전이 양자 컴퓨터에도 일어나면 2100년쯤엔 기존 암호는 완전히 무력화될 것이라 추정함. 트랜지스터 같은 단 한 번의 혁신이 등장할 때까지는 예측이 어려움. 기술 발전은 늘 불가능해 보여도, 누군가 최초로 방법을 찾으면 바뀌는 것임. (UNIVAC I 설명)
    • 최근 관련 트윗도 참고함(트윗 링크). 일반인의 입장에서는 해당 경로가 거대한 재료과학적 혁신 여러 번에 가려져 있는 듯함
    • RSA 4096의 경우 10^7 큐빗에 오차율 10^-4가 대략적으로 필요함. 이미 100여 개의 큐빗만으로 유용한 양자화학 계산이 가능하며, 포스트양자 알고리즘이 점차 확산되면서 암호 해독용 양자 컴퓨터 개발 동기는 줄고 있음. 양자컴퓨팅은 암호와 무관한 방향에서 더 빠르게 발전할 것으로 생각함
    • 최신 수치는 오차율 1e-4에서 큐빗 약 1백만 개가 필요하다는 것임(논문 링크). gate 수는 코드 수준에서 실제 연산에 따라 다르게 측정되고, 1MHz "클럭"(코드 사이클 타임) 기준으로 전체 계산 시간이 약 일주일임. 큐빗 수보다 계산 시간 달성이 더 어려운 메트릭임. 양자 오류 정정의 마법적 효과(에러율이 더 낮아질수록 큐빗 수가 크게 감소) 덕분에 큐빗 품질이 한 단계 향상되면 요구 큐빗 수가 급감함. 반면, 여러 시스템에 연산을 분할해야 하면 상황이 매우 악화됨

  • 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' 논문이 흥미로움(논문 읽기)

  • RSA1024 같은 암호적으로 유의미한 숫자의 인수분해 회로 크기 및 실현 가능성에 관심 있음

    • RSA1024의 비용 추정치는 작은 수(4비트 등)에서 단순 확장하지 않고, 실제 규모에 맞는 회로 설계를 통해 산출됨. 즉, 이번 글에서 언급된 불연속성 문제를 이미 암묵적으로 반영하고 있음. 따라서 이 포스팅은 기존 비용 추정에 영향이 없음
    • (참고: 21 인수분해 회로의 최적화는 큰 수를 인수분해할 때에는 적용이 힘들 것임. 15 인수분해 회로 대비 500배 비용이 더 현실적일 수 있음. 물론 100배 오버헤드도 논지를 설명하기엔 충분함. Noah Shutty가 해당 회로 최적화를 위해 고가의 컴퓨터 탐색을 해준 점에 특별히 감사를 표함)
    • 주제에서 살짝 벗어나지만, 최근 초대형 데이터센터에서도 RSA1024를 인수분해하는 게 실질적으로 불가능하다는 점에 암호학자들이 확신하는지 궁금함. 현재로선 가장 빠른 알고리즘도 현실적 시간 내에 인수분해할 수 없음. 그러나 조만간 이 알고리즘에 획기적 개선이 없으리라는 데에는 합의가 있는 건지 의견이 궁금함

  • 언젠가 양자 컴퓨터가 post-quantum RSA를 겨냥할 수 있을지 궁금함(관련 논문). 일반적인 RSA 연산(키 생성, 암호화, 복호화)이 Shor 알고리즘에 대해 비대칭적으로 유리하므로, 충분히 큰 키만 쓰면 된다는 견해도 있음. 이는 마치 Merkle 퍼즐과 비슷한 효과이며, 공격자는 반드시 양자 컴퓨터로 공격해야 한다는 조건이 추가됨. 예전에 기가비트 RSA 공개키를 만들어본 적 있음(키 파일). 포맷은: 4바이트 리틀엔디언 키 바이트 수, 이어서 키, 그리고 키 역수(256^bytes로 mod). 공개 지수는 3임

    • Post-Quantum RSA는 djb가 "큰 키만 쓰면 안전하지 않냐"는 질문 대응용으로 만든 농담임. 1TB 키로 암호화 1회당 100시간 걸리게 설계되어 있음. 양자 컴퓨터로도 뚫을 수 없음

  • "error corection" 오타를 보고 참 재미있었음

  • "인수분해-15와 비교해 500배 회로 비용" 부분을 이해하기 힘듦. 저자가 이미 115배 사례를 냈는데, 추가 최적화가 어떻게 더 나쁜 결과를 초래하는지 궁금함

    • 소규모 숫자 인수분해 회로 제작에 투입된 엄청난 최적화 작업량은 큰 숫자에선 현실적으로 불가능하다는 점을 의미함. 즉, 일반적으론 인수분해할 숫자가 커질 때 대략 500배 게이트 증가가 필요하다는 것이 직관적임(115배처럼 적지 않음)
    • 실제로 큰 규모에선 최적화 효과가 줄고, N=21 회로처럼 이익이 크지 않을 것임
    • 최소한의 구현은 불안정하고 신뢰성을 보장하기 어려움. 실용적 회로 개발엔 안정적인 큐빗 확보를 위한 많은 연구가 필요하고, "데코히런스 타임" 같은 개념도 언급됨. 따라서 큐빗 수가 폭발적으로 증가할 수밖에 없음
    • 115배는 (현실적이지 않은) 많은 최적화를 가한 결과임

  • 이 게시물 요지는 Schorr's 인수분해에 Big-O 회로 필요량이 슈퍼 다항식임을 시사하는지 의문임

    • 글 내용에 따르면, 게이트 비용은 O(n)번의 모듈러 곱셈 연산에서 주로 나오고, 각 연산이 O(n^2) 게이트로 구현될 수 있음. 전체적으로 최악의 경우라도 대략 3차(큐빅) 복잡도로 보임

  • PQ(포스트양자) 암호 기술의 도입 이유는 반드시 QC가 곧 나온다고 확신해서가 아님. 기술 개발 속도에 따라 QC가 언제 나올지는 불확실함. 암호 기술의 목표는 이론적으로도 거의 깨지지 않을만한 방법을 찾는 것이고, 이론적으로 공격이 가능하다면 물리적으로도 가능성이 있으므로 반드시 대비함. ECC, RSA는 이론적 경로가 확인된 바 있어, 실재하는 장비가 없어도 공격이 가능하다고 봄. 따라서 QC가 없을 때 미리 대비해두는 것이 충분히 합리적인 전망임. 반면 SHA2, AES, ChaCha 등은 현실적 공격 경로가 보이지 않으므로 당장 대체 계획은 없음. 암호화는 QC의 유일한, 혹은 가장 중요한 응용 방향이 아님. 물리적 계, 단백질 폴딩, 기계학습 등 다양한 영역에서 아직 모르는 혁신이 나올 수 있으리라는 기대가 있음

    • 단백질 폴딩 등 분야에서 앞으로 더 발전 가능성이 있는지 궁금함(AlphaFold 이후에도). (참고 기사)

    • 대칭키 암호 (AES, ChaCha, SHA-2) 경우엔 양자 공격이 사실상 키 길이 절반으로 약화되는 효과가 있음(3DES와 2DES 사례처럼). 실제로는 실제 양자 컴퓨터의 성능이 비등하거나 동일하지 않으므로 단순 절반이라고 단정지을 순 없지만, AES-256으로 대체가 가능해 문제 없음. 그런데 집중해야 할 곳은 Key Exchange임. 이유는 Key Exchange가 비밀 키를 양쪽에서 직접 내놓지 않고 합의하는 데 사용되기 때문임. Quantum Computer가 있다면, 과거 대화를 기록해둔 것도 읽을 수 있게 됨. 따로 서명 알고리즘을 뚫는다고 과거로 돌아가 서명할 수는 없지만, Key Exchange는 한번 뚫리면 과거 대화도 모두 노출되기 때문에 중요함. Key Exchange의 안전한 대체가 시급함
답변달기