Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique

본 논문은 소수성을 얽힘 역학과 연결하고, NISQ 장치에서 소수와 합성수를 구별하는 능력을 향상시키기 위해 새로운 분석적 경계를 활용하며, 잡음을 완화하기 위한 새로운 전역 재조정 기법을 사용하여 IBM 프로세서에서 소수를 식별하기 위한 양자 프로토콜을 제시합니다.

핵심

이 논문은 간단한 언어와 창의적인 비유를 사용하여 설명합니다.

큰 그림: 양자 파동으로 소수 찾기

마법 같은 북이 있다고 상상해 보세요. 이 북을 특정 방식으로 치면, 그 소리는 당신이 '생각'하고 있는 숫자에 따라 완전히 달라집니다. 만약 그 숫자가 소수(2, 3, 5, 7, 11 과 같은)라면, 북은 매우 조용하고 뚜렷한 윙윙거리는 소리를 냅니다. 반면 그 숫자가 합성수(4, 6, 8, 9, 10 과 같은)라면, 북은 훨씬 더 시끄럽고 혼란스러운 소음을 냅니다.

이 논문은 실제 양자 컴퓨터 (IBM 의 프로세서) 를 사용하여 이 '마법 북'의 디지털 버전을 구축한 과학자 팀에 대해 설명합니다. 그들의 목표는 양자 얽힘의 '소리'를 사용하여 소수와 비소수를 구별할 수 있는지 확인하는 것이었습니다.

문제: 양자 북은 시끄럽습니다

하지만 함정은 현재의 양자 컴퓨터가 허리케인 속에서 연주되는 북과 같다는 점입니다. 그들은 '시끄럽습니다'. 바람 (실험 오차) 이 소리를 왜곡하여, 조용한 소수 윙윙거리는 소리를 시끄러운 포효처럼 만들거나, 시끄러운 합성수 포효 소리를 둔탁하게 만듭니다. 기계가 너무 많이 흔들릴 때 두 가지의 차이를 구분하기는 어렵습니다.

해결책: '글로벌 리스케일링' 트릭

이를 해결하기 위해 저자들은 **CFE (보정 계수 외삽법)**라고 부르는 새로운 잡음 제거 방법을 고안했습니다.

이것을 다음과 같이 생각하세요:

1. 보정: 그들은 먼저 작은 쉬운 숫자들 (차원 4, 8, 16) 로 북을 테스트했습니다. 그들은 '완벽한' 소리가 수학 이론에서 어떻게 되어야 하는지 정확히 알고 있었습니다.
2. 왜곡 측정: 그들은 실제 기계에서 나오는 '시끄러운' 소리와 '완벽한' 소리를 비교했습니다. 그들은 기계가 일관되게 소리를 특정 양만큼 너무 작게 또는 너무 크게 만든다는 사실을 깨달았습니다.
3. 마법 공식: 그들은 그 작은 숫자들을 위한 '보정 계수'(승수) 를 계산했습니다.
4. 외삽: 모든 숫자를 테스트하여 각자의 보정 계수를 찾는 대신, 그들은 패턴을 발견했습니다. 숫자가 커질수록 보정 계수가 매끄럽고 예측 가능한 곡선을 따른다는 사실을 깨달은 것입니다.
5. 수정: 그들은 이 곡선을 사용하여 아직 테스트하지 않은 더 크고 어려운 숫자들의 보정 계수를 추측했습니다. 그들은 이 '마법 승수'를 시끄러운 데이터에 적용하여 볼륨 노브를 올바른 설정으로 되돌렸습니다.

결과: 이 수정을 적용한 후, '시끄러운' 데이터는 거의 완벽하게 '완벽한' 이론적 데이터와 같아졌습니다. 소수들은 조용한 지점으로, 합성수들은 시끄러운 지점으로 명확하게 두드러졌습니다.

새로운 이론: 더 나은 안전망

이 논문은 수학적인 안전망에 새로운 층을 추가했습니다.

• 옛 규칙: "소리가 매우 조용하면 아마 소수일 것입니다. 시끄럽다면 합성수일 것입니다."
• 문제: 때로는 합성수 (예: $2 \times 3$과 같은 반소수) 가 우연히 조금 조용하게 들려 시스템을 속일 수 있습니다.
• 새 규칙: 저자들은 새로운 수학적인 '바닥'을 증명했습니다. 그들은 대부분의 합성수에 대해 소리가 너무 조용해질 수 없음을 보였습니다. 소리는 반드시 그 이상으로 유지되어야 하는 최소 볼륨이 있습니다.
• 이점: 이로 인해 '안전 구역'이 생깁니다. 어떤 숫자의 소리가 특정 선 아래로 떨어지면, 그것은 거의 확실히 소수입니다. 만약 그것이 '안전 구역'(소수 선과 새로운 합성수 바닥 사이) 에 있다면, 컴퓨터는 2 나 3 으로 나누어지는지 확인하는 것과 같은 빠르고 간단한 확인만 수행하면 됩니다. 이로 인해 전체 과정이 훨씬 더 신뢰할 수 있게 됩니다.

그들이 실제로 한 일 (하고 하지 않은 일)

• 그들이 한 일: 작은 시스템 크기 (차원 4, 8, 16) 에 대해 실제 IBM 양자 하드웨어에서 이 알고리즘을 실행했습니다. 그들의 새로운 보정 방법 덕분에 하드웨어의 잡음에도 불구하고 소수를 성공적으로 식별했습니다.
• 그들이 한 일: 이 방법이 단순히 추측하는 것보다 더 잘 작동하며, 소수와 합성수 사이에 명확한 분리를 만든다는 것을 수학적으로 증명했습니다.
• 그들이 하지 않은 일: 실제 세계의 암호화 코드 (예: 은행 보안 깨기) 를 해독하는 데 이를 사용하지 않았습니다. 이 논문은 소수인지 식별하는 것에만 엄격히 초점을 맞추고 있으며, 암호학을 위한 큰 수의 소인수분해에 관한 것은 아닙니다.
• 그들이 하지 않은 일: 이것이 아직 거대한 숫자에도 작동한다고 주장하지 않았습니다. 현재의 실험은 양자 컴퓨터가 여전히 초기 단계인 '시끄러운' 단계에 있기 때문에 작은 차원으로 제한되었습니다.

요약 비유

폭풍 속에서 새의 노래로 특정 새를 식별하려고 한다고 상상해 보세요.

1. 알고리즘: 새의 노래는 '소수 새'인지 '합성수 새'인지에 따라 음정이 변합니다.
2. 잡음: 폭풍 (하드웨어 오차) 이 모든 노래를 난해하게 만듭니다.
3. CFE 방법: 과학자들은 몇 마리 알려진 새들에게 폭풍의 영향을 기록했습니다. 그들은 "폭풍은 항상 음정을 X 만큼 낮춘다"는 규칙을 찾아냈습니다. 그들은 이 규칙을 사용하여 아직 연구하지 않은 다른 새들의 녹음을 조정하여 정적을 제거했습니다.
4. 새로운 이론: 그들은 또한 '합성수 새'들에게는 규칙이 있음을 깨달았습니다: 그들은 절대 너무 조용히 노래할 수 없습니다. 만약 새가 그 한계보다 더 조용히 노래한다면, 그것은 반드시 소수 새입니다 (매우 구체적이고 희귀한 유형의 새가 아닌 한, 그들도 어떻게 확인해야 하는지 알아냈습니다).

이 논문은 올바른 '잡음 제거' 수학을 통해, 오늘날의 불완전한 양자 컴퓨터로 오래된 수론 퍼즐을 풀기 시작할 수 있음을 보여줍니다.

기술 요약

기술 요약: 새로운 재스케일링 기반 노이즈 완화 기법을 활용한 양자 프로세서를 통한 소수 식별 시연

문제 제기
소수의 식별 및 분류는 암호학과 계산 복잡성에 중대한 함의를 지닌 수론의 근본적인 과제로 남아 있습니다. 고전 알고리즘이 발전해 왔지만, 양자 접근법은 수론적 속성을 양자 관측 가능량에 인코딩함으로써 대안적인 방법을 제공합니다. 구체적으로, 이론적 연구에서 제안된 바 있는 "얽힘 역학을 통한 소수 식별 (PIED)" 알고리즘은 정수의 소수성을 이분 양자 시스템의 축소된 순도 (얽힘) 의 푸리에 스펙트럼 내 특정 서명과 연관시킵니다. 그러나 이 알고리즘을 고전 시뮬레이션에서 노이즈가 있는 중간 규모 양자 (NISQ) 장치의 실제 하드웨어로 전환하는 것은 실험적 노이즈로 인해 큰 도전에 직면합니다. 이러한 노이즈는 측정된 푸리에 모드에서 소수와 합성수 사이의 미묘한 구분을 흐릴 수 있기 때문입니다.

방법론
저자들은 IBM 양자 프로세서 (특히 Heron r2 "Aachen" 장치) 에서 시스템 차원 $d = 4, 8,$ 및 $16$에 대해 PIED 알고리즘을 구현했습니다. 프로토콜은 다음과 같습니다:

1. 시스템 설정: 균일하게 간격을 둔 에너지 준위를 가진 대각 해밀토니안 하에서 진화하는, 동일한 차원 $d$를 가진 두 개의 부분 시스템 $AB$로 구성된 이분 시스템.
2. 상태 준비: 시스템은 균일 중첩 상태로 초기화 (하드마드 게이트를 통해 준비됨) 되고 해밀토니안에서 유도된 유니타리 연산자 하에서 진화합니다.
3. 측정: 두 개의 동일한 시스템 사본과 보조 큐비트가 필요한 SWAP 테스트 프로토콜을 사용하여 시간 경과에 따른 부분 시스템 $A$의 축소된 순도 $\gamma_A(t)$를 측정합니다.
4. 신호 추출: 시간 의존적 순도를 푸리에 변환하여 모드 $\alpha_n$을 추출합니다. 이론적으로 소수들은 이러한 모드의 최소값에 해당하며, 합성수들은 더 큰 값을 생성합니다.

하드웨어 노이즈를 해결하기 위해 저자들은 보정 인자 외삽 (CFE) 기법을 개발하고 적용했습니다. 이 방법은 다음과 같습니다:

• 보정: 푸리에 모드의 이상적인 분석적 값이 알려진 시스템 차원 ($d=4, 8, 16$) 의 부분 집합에 대해 회로 실행을 수행합니다.
• 최적화: 노이즈가 있는 실험 데이터와 분석적 참조 간의 편차를 최소화하여 각 차원에 대한 최적의 전역 재스케일링 인자 $\Lambda_{opt}(d)$를 계산합니다.
• 외삽: 계산된 $\Lambda_{opt}(d)$ 값에 함수 형태 (구체적으로 $\Lambda_{opt}(d) = \Lambda_0 + \kappa d^\eta$) 를 적합시켜 다른 구성에 대한 보정 인자를 예측하거나 추세를 검증합니다. 이는 회로 인스턴스당 여러 노이즈 수준 측정이 필요하지 않은 (Zero-Noise Extrapolation 과 같이) 노이즈가 있는 푸리에 모드를 재스케일링하여 체계적 편향을 완화할 수 있게 합니다.

주요 기여

1. 하드웨어 구현: 시뮬레이션에서 NISQ 장치로의 성공적인 전환을 이루는 PIED 알고리즘의 실제 양자 하드웨어 상 최초 시연.
2. 노이즈 완화 전략 (CFE): 계산 비용이 적게 드는 재스케일링 기반 오류 완화 기법의 도입. 다양한 노이즈 수준에서 반복적인 회로 실행이 필요한 전통적인 방법과 달리, CFE 는 서로 다른 시스템 차원에 걸쳐 알고리즘의 알려진 분석적 행동을 활용하여 보정 인자를 구성합니다.
3. 정교화된 이론적 경계: 합성수의 푸리에 모드에 대한 새로운 분석적 하한 $P_n$의 유도 (구체적으로 $n=k^2$ 형태인 정수, 여기서 $k$는 소수). 이 경계는 이전에 알려진 자명한 경계 $B_n$보다 소수와 합성수 서명 사이의 더 엄격한 분리를 제공합니다. 저자들은 이 경계의 예외가 특정 하구간 내에서 인자 2 와 3 을 포함하는 특정 반소수에서만 발생함을 엄격하게 규명하여 더 견고한 분류 프레임워크를 가능하게 했습니다.
4. 대체 초기 상태: 초기 조건으로 스핀 일관 상태 (spin coherent states) 의 사용을 탐구한 수치 시뮬레이션. 준비가 더 복잡하지만, 이러한 상태는 균일 중첩 상태에 비해 정확한 푸리에 적분을 위해 필요한 시간 분할 수를 줄일 잠재력을 보여주었습니다.

결과

• 소수/합성수 분리: 하드웨어 구현은 소수가 푸리에 모드 최소값에 해당한다는 이론적 추세를 성공적으로 재현했습니다. CFE 방법의 적용은 실험 데이터와 분석적 예측 간의 일치도를 크게 향상시켜, 원시 데이터에서 노이즈에 의해 가려졌던 소수와 합성수 서명 간의 분리를 효과적으로 복원했습니다.
• CFE 성능: 보정 인자 $\Lambda_{opt}(d)$는 차원 $d$에 따라 단조 증가하며 점근적으로 포화되는 것으로 나타났습니다. 재스케일링된 데이터는 제안된 함수 모델과 탁월한 일치를 보였습니다.
• 이론적 검증: 새로운 경계 $P_n$은 대부분의 합성수에 대해 성립함이 입증되었습니다. 분석은 오직 특정 반소수 ($2k$ 또는 $3k$ 형태) 만이 이 경계 아래 값을 생성할 수 있음을 확인하여, 해당 영역에서 특정 나눗셈 검사가 필요함을 보여주었습니다.
• 스핀 일관 상태: 시뮬레이션은 스핀 일관 상태가 준비하기 어렵지만 푸리에 적분에 필요한 시간 샘플 수에 대해 더 유리한 스케일링을 제공할 수 있음을 시사하여, 잠재적으로 계산 오버헤드를 줄일 수 있음을 나타냈습니다.

의의
이 논문은 이러한 결과들이 NISQ 장치에서 실용적인 수론적 응용을 향한 한 걸음이라고 주장합니다. 현실적인 하드웨어 조건 하에서 PIED 알고리즘을 검증하고 특수화된 저오버헤드 노이즈 완화 전략 (CFE) 을 시연함으로써, 이 연구는 분석적 통찰과 하드웨어 기반 구현의 결합 가능성을 강조합니다. 저자들은 그들의 접근법이 노이즈가 있는 양자 역학에서 구조화된 정보를 추출할 수 있는 실현 가능한 경로를 제공하며, 물리 관측 가능량의 스펙트럼 서명에 의존하는 다른 양자 알고리즘에도 더 넓은 적용 가능성을 시사한다고 강조합니다. 이 연구는 대규모 정수 소인수분해를 해결한다고 주장하는 것이 아니라, 얽힘 역학을 사용하여 소형 양자 시스템에서 소수 서명을 식별하는 실현 가능성을 시연하는 것입니다.