⚛️ quantum physics

Can PCE solve the factorisation problem via optimisation?

이 논문은 계산적 우위를 주장하지 않으면서 근미래 양자 하드웨어에 대한 잠재력과 한계에 대한 예비 분석을 제공하며, 큐비트 요구량을 획기적으로 줄이기 위한 방법으로서 파울리 상관 인코딩(PCE) 알고리즘을 정수 인수분해 문제에 적응시키는 것의 타당성을 탐구한다.

원저자: Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

게시일 2026-07-28

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신의 은행 계좌, 이메일, 그리고 온라인에서 하는 거의 모든 것을 보호하는 비밀 코드를 해독하려고 한다고 상상해 보십시오. 이 코드는 단순하지만 까다로운 수학 게임에 의존합니다. 바로 두 개의 거대한 소수(1과 자기 자신으로만 나누어지는 숫자)를 골라, 그 둘을 곱한 뒤 그 결과값을 세상에 공개하는 것입니다. 이 둘을 곱하는 것은 쉽지만, 만약 당신이 최종적인 거대한 숫자만을 가지고 있다면, 어떤 두 소수가 그 숫자를 만들어냈는지 알아내는 것은 마치 케이크를 다시 '역으로 굽는(un-bake)' 과정에서 정확히 몇 개의 달걀과 몇 컵의 밀가루가 들어갔는지 찾아내는 것만큼이나 어렵습니다. 현재의 컴퓨터들에게 이 작업은 매우 큰 숫자에 대해서는 거의 불가능에 가깝습니다. 이것이 바로 "정수 인수분해(integer factorization)" 문제이며, 현대 디지털 보안의 근간입니다.

이제, 단순히 계산만 하는 것이 아니라 양자 물리학의 기묘한 법칙을 사용하여 동시에 수많은 가능성을 탐색하는 새로운 종류의 컴퓨터를 상상해 보십시오. 과학자들은 이 "역으로 굽는" 문제를 해결하도록 이 양자 기계들을 가르치기 위해 노력해 왔습니다. 피터 쇼어(Peter Shor)가 발명한 유명한 방법은 이론적으로는 완벽하지만, 아직 우리가 구축할 기술력이 없는, 매우 강력하고 정숙한 양자 컴퓨터를 필요로 합니다. 그래서 연구자들은 오늘날 우리가 가진 노이즈가 많고 불완전한 기계에서도 실행할 수 있는, 약간의 양자 마법을 사용하면서도 양자 방식의 통찰력을 빌려온 "양자 영감(quantum-inspired)" 지름길을 찾고 있습니다. 핵심 질문은 이것입니다. "우리는 이 거대한 수학 문제를 현재의 양자 컴퓨터가 실제로 해결할 수 있을 만큼 작고 관리 가능한 퍼즐로 압축할 수 있을까?"

이 논문은 **파울리 상관 인코딩(Pauli Correlation Encoding, PCE)**이라는 영리한 새로운 기술을 사용하여 바로 이 질문을 탐구합니다. PCE를 매우 효율적인 압축 알고리즘이라고 생각하십시오. 보통 많은 변수(거대한 숫자의 비트들 같은)를 가진 복잡한 문제를 표현하려면 매우 많은 양자 비트(큐비트)가 필요합니다. PCE는 마법의 지퍼처럼 작동하여, 연구자들이 수천 개의 변수를 훨씬 적은 수의 큐비트에 담을 수 있게 해줍니다. 갈리시아 슈퍼컴퓨팅 센터의 페르난도 알론소(Fernando Alonso)와 그의 팀은 다음과 같이 물었습니다. "만약 우리가 이 지퍼를 사용하여 인수분해 문제를 압축한다면, 최적화 기법을 사용하여 답을 찾을 수 있을까?"

그들은 단순히 추측만 한 것이 아니라, 탐색을 안내할 두 가지 서로 다른 "지도"를 만들었습니다. 첫 번째 지도는 **기본 접근법(Basic approach)**으로, 두 소수의 이진 코드를 직접 추측하여 인수를 찾는 방식이었습니다. 그들은 이를 최대 25비트 길이의 숫자까지 테스트했습니다. 결과는 다소 엇갈렸습니다. 작은 숫자에는 괜찮게 작동했지만, 숫자가 커질수록 성공률이 떨어졌고, 컴퓨터는 종종 "사소한(trivial)" 해답(예를 들어 어떤 숫자를 자기 자신과 1의 곱이라고 말하는 것)에 갇히곤 했습니다.

두 번째 지도인 **DoTS (Difference of Two Squares, 두 제곱의 차)**는 더 똑똑한 전략이었습니다. 이 방식은 인수를 직접 찾아 헤매는 대신, 두 수의 제곱의 차가 대상 숫자의 배수가 되는 경우를 찾았습니다. 이는 마치 두 사람이 체중계 위에 섰을 때, 그들의 몸무게 차이가 특정 패턴과 완벽하게 일치하는 경우를 찾는 것과 같습니다. 이 접근 방식은 훨씬 더 성공적이었습니다. 시뮬레이션에서 DoTS 방식은 최대 36비트 길이의 숫자를 성공적으로 인수분해했습니다.

연구팀은 이 지도를 탐색하기 위해 세 가지 다른 "검색 엔진(최적화 도구)"을 사용했습니다: 차분 진화(Differential Evolution, DE), 입자 군집 최적화(Particle Swarm Optimization, PSO), 그리고 양자 영감 버전인 QDPSO입니다. 결과는 DE 최적화 도구가 명확한 승자임을 보여주었으며, 다른 도구들이 고전하는 곳에서도 일관되게 정답을 찾아냈습니다.

하지만 저자들은 자신들의 방법이 코드를 "깨뜨렸다"고 주장하지 않도록 매우 주의를 기울입니다. 그들은 자신들의 방법이 다른 양자 접근 방식보다 훨씬 적은 큐비트를 사용한다는 점(이는 현재의 하드웨어에서도 실행 가능하다는 의미임)을 강조하면서도, 이것이 여전히 고전 컴퓨터에서 실행되는 시뮬레이션임을 명시합니다. 그들은 숫자가 36비트를 넘어가면 현재의 방식이 실패하기 시작한다는 것을 발견했으며, 이는 수학을 더 효과적으로 포착하기 위해 "비용 함수(cost function, 즉 컴퓨터를 위한 규칙서)"를 다시 작성해야 할 수도 있음을 시사합니다. 또한, 만약 이 작업을 실제 양자 하드웨어에서 실행한다면, 노이즈가 컴퓨터가 막다른 길에서 탈출하는 데 도움을 줄 수도 있고, 혹은 계산 자체를 망쳐버릴 수도 있다고 언급했습니다.

요약하자면, 이 논문은 PCE가 인수분해 문제를 훨씬 더 작고 관리하기 쉽게 만들어 양자 컴퓨터에 전달할 수 있는 유망한 도구임을 시사합니다. 이 방법이 아직 실제 암호화에 사용되는 거대한 숫자들을 해결하는 것은 아니지만, 새로운 문을 열어주고 있습니다. 적절한 압축과 적절한 탐색 전략이 있다면, 우리가 생각했던 것보다 더 빨리 양자 컴퓨터가 본격적인 숫자 계산을 수행할 수 있게 될 수도 있음을 보여줍니다. 비록 세상에서 가장 큰 케이크를 역으로 굽기까지는 아직 갈 길이 멀지만 말입니다.

기술 요약: PCE가 최적화를 통해 인수분해 문제를 해결할 수 있는가?

문제 정의
정수 인수분해, 특히 준소수(semiprime, $N = p \cdot q$ )의 인수분해는 계산 정수론의 기초적인 문제이자 RSA 암호화의 보안 기반입니다. 쇼어 알고리즘(Shor's algorithm)은 다항 시간 내의 양자 해법을 제공하지만, 현재의 노이즈가 있는 중간 규모 양자(NISQ) 하드웨어는 실질적인 구현에 필요한 큐비트 수와 결맞음(coherence)이 부족합니다. 인수분해를 이진 최적화 문제로 변환하는 변분 양자 알고리즘(VQA)과 같은 대안적 접근 방식은 일반적으로 이진 변수의 수에 비례하여 큐비트 수가 늘어나는 확장성 문제에 직면합니다. 이러한 선형적 확장은 대규모 인스턴스를 현재의 하드웨어에서 실행하는 것을 불가능하게 만듭니다. 본 논문은 $m$ 개의 이진 변수를 다항식 개수의 큐비트( $n \ll m$ )를 사용하여 인코딩할 수 있는 프레임워크인 **파울리 상관 인코딩(Pauli Correlation Encoding, PCE)**이 제한된 자원으로 인수분해 문제를 해결하기 위해 최적화 방식으로 적응될 수 있는지 조사합니다.

방법론
본 연구는 인수분해 문제를 이진 최적화 작업으로 재구성하고, 큐비트 요구량을 줄이기 위해 PCE를 적용합니다. 방법론은 다음과 같습니다:

인코딩 전략: 인수분해 제약 조건을 비용 함수(cost function)로 매핑하기 위해 두 가지 구별된 접근 방식을 개발했습니다:
- 기본 접근 방식(Basic Approach): 미지의 인수인 $p$ 와 $q$ 의 이진 표현을 직접 인코딩합니다. 비용 함수는 대상 정수 $N$ 과 후보 곱 $x_p \cdot x_q$ 사이의 제곱 해밍 거리(squared Hamming distance)를 최소화하며, 자명한 해(예: $N \cdot 1$ )를 피하기 위한 페널티를 포함합니다.
- 두 제곱의 차(Difference of Two Squares, DoTS) 접근 방식: $a^2 \equiv b^2 \pmod N$ (단, $a \not\equiv \pm b$ )을 만족하는 정수 $a, b$ 를 찾는 문제로 재구성합니다. 인수는 $\gcd(a-b, N)$ 및 $\gcd(a+b, N)$ 을 통해 복구됩니다. 비용 함수는 모듈로 합동(modular congruence)을 강제하는 항과 결과적인 인수분해를 검증하는 항을 결합합니다.
양자 회로: 단일 큐비트 회전( $R_X, R_Y, R_Z$ )과 얽힘 게이트( $R_{XX}, R_{YY}, R_{ZZ}$ )가 교대로 나타나는 하드웨어 효율적인 "브릭워크(brickwork)" 안사츠(ansatz)를 채택했습니다. PCE 압축 차수 $k$ 는 회로 깊이와 필요한 큐비트 수( $n \approx m/k$ )를 결정합니다.
최적화: 매개변수화된 양자 회로는 Qiskit Aer를 사용하여 클래식하게 시뮬레이션되었습니다. 최적화에는 차분 진화(Differential Evolution, DE), 입자 군집 최적화(Particle Swarm Optimisation, PSO), 양자 델타 입자 군집 최적화(Quantum Delta Particle Swarm Optimisation, QDPSO)의 세 가지 그래디언트 프리(gradient-free) 알고리즘이 사용되었습니다. 무한한 실수 해를 방지하기 위해 하이퍼볼릭 탄젠트 완화 대신 부호 함수(sign function)를 사용하여 이진 변수를 근사했습니다.

주요 기여 및 결과

자원 감소: 본 연구는 PCE가 인수분해에 필요한 큐비트 수를 획기적으로 줄일 수 있음을 보여줍니다. 일반적인 RSA 키 길이에 대해 필요한 큐비트는 현재 또는 근미래의 하드웨어에서 "감당 가능한" 범위 내에 머물며, 압축 차수 $k > 2$ 인 경우 문제는 양자 회로 에뮬레이션을 통해 클래식 컴퓨터에서 완전히 해결될 수 있습니다.
성능 비교:
- DoTS vs. Basic: DoTS 접근 방식이 기본 접근 방식보다 일관되게 우수한 성능을 보였습니다. 두 제곱의 차 관계의 산술적 구조를 포착하는 DoTS 비용 함수는 더 높은 성공률과 더 유리한 최적화 지형(optimisation landscape)을 제공했습니다.
- 최적화 도구 민감도: 차분 진화(DE)가 가장 견고한 최적화 도구임이 증명되었으며, 다양한 비트 길이에서 성공적인 인수분해를 달로 달성했습니다. 군집 기반 방법(PSO, QDPSO)은 현저히 낮은 성공률을 보였으며, 이는 해당 알고리즘들이 특정 문제 지형에 대해 도전적임을 시사합니다.
- 확장성 한계: 본 방법은 $k=4$ 와 DE를 사용한 DoTS 접근 방식을 통해 최대 36비트의 준소수를 성공적으로 인수분해했습니다. 25~36비트보다 큰 정수에 대해서는 성공률이 감소하였는데, 이는 현재의 비용 함수 공식에 내재된 한계를 나타냅니다.
탐색 효율성: 목적 함수 평가 횟수 분석 결과, 알고리즘이 무차별 대입(brute-force) 탐색에 의존하지 않음을 보여줍니다. 평가 횟수는 조합 탐색 공간( $2^n$ )보다 몇 차수(orders of magnitude) 낮게 유지되었으며, 이는 유도된 탐색(guided search) 과정임을 나타냅 most.

의의 및 주장
본 논문은 이 작업을 확정적인 해결책이나 기존 알고리즘에 대한 계산적 우위의 주장이 아닌, 예비적이고 탐색적인 기여로 규정합니다.

실행 가능성: 주요 발견은 PCE 기반 알고리즘이 제한된 양자 자원을 사용하여 인수분해를 연구하기 위한 타당한 프레임워크라는 점입니다. 이는 변수의 수를 큐비트 수와 분리함으로써 VQF 및 QAOA와 같은 기존 방법론에 대한 대안적 관점을 제공합니다.
한계점: 저자들은 현재의 공식이 암호학적으로 유의미한 정수 크기(예: 2048비트 RSA)로 성공적으로 확장되지 못함을 명시적으로 밝힙니다. 방법의 성공 여부는 클래식 비용 함수의 설계와 최적화 도구의 선택에 크게 의존합니다.
향후 연구 방향: 연구는 다음 사항에 집중할 것을 제안합니다:
- 인수분해의 산술적 구조를 더 잘 포착할 수 있는(잠재적으로 올림(carry) 변수를 포함하는) 더 정보가 풍부한 비용 함수 설계.
- 변수 수를 줄이기 위한 균형 잡힌 인수의 가정(RSA에서 흔함) 탐구.
- 웜 스타트(warm-start) 전략 및 대안적인 안사츠 아키텍처 조사.
- 실제 노이즈 모델 하에서의 성능 평가.

결론적으로, 이 방법이 현재 RSA 보안을 위협하지는 않지만, 양자 영감을 받은 최적화를 통한 인수분해 연구를 위한 실행 가능하고 자원 효율적인 프레임워크를 구축하였으며, 이는 비용 함수 설계와 알고리즘 개선에 대한 추가 연구의 가치가 있음을 입증합니다.

기술 요약: PCE가 최적화를 통해 인수분해 문제를 해결할 수 있는가?

유사한 논문