- 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 개선) 이나
- 스케일링 문제를 해결하는 하드웨어 아키텍처 변화(예: 중성원자 지속적 교체 등) 가
- 실질적 진전을 보여주는 더 중요한 관측 지점임