Pauli Correlation Encoding for mRNA Secondary Structure Prediction: Problem-Aware Decoding for Dense-Constraint QUBOs

본 논문은 mRNA 이차 구조 예측을 위한 밀집 제약 QUBO를 효과적으로 디코딩하기 위해 파울리 상관 인코딩과 결합된 문제 인식 유도 디코더(PAGD)를 소개하며, 훈련된 사전 지식이 생물학적으로 의미 있는 시퀀스 크기에 대해 노이즈가 있는 초전도 하드웨어에서 거의 최적의 해를 달성할 수 있음을 보여줍니다.

핵심

이 논문은 쉬운 언어와 일상적인 비유를 사용하여 설명합니다.

큰 그림: 어둠 속에서 종이 crane 접기

상상해 보세요. 매우 길고 복잡한 종이 (mRNA 분자) 가 있는데, 이를 작동하게 하려면 특정 모양으로 접어야 합니다. 잘못 접으면 기능이 없거나 심지어 해로울 수도 있습니다. 목표는 최소한의 에너지만 사용하는 완벽한 접기를 찾는 것입니다.

짧은 종이 조각이라면 계산기로 쉽게 해결할 수 있습니다. 하지만 의학에 사용되는 것처럼 길고 복잡한 가닥의 경우, 접을 수 있는 가능한 방법의 수가 너무 방대하여 세계 최고의 슈퍼컴퓨터조차 막혀버립니다. 이는 지구의 모래알 수보다 더 많은 경로가 있는 미로에서 단 하나의 최선의 경로를 찾는 것과 같습니다.

과학자들은 이 문제를 해결하기 위해 양자 컴퓨터를 사용하려고 시도하고 있습니다. 이 컴퓨터들은 한 번에 많은 경로를 살펴볼 수 있는 초강력 탐험가와 같습니다. 하지만 큰 문제가 하나 있습니다. 이 컴퓨터들은 작고 '노이즈가 많으며' (오류 발생 경향이 있음), 전체 미로의 지도를 한 번에 담을 만큼 충분한 '방' (큐비트) 이 부족합니다.

해결책: '마법 압축' 트릭

연구자들은 파울리 상관 인코딩 (PCE) 이라는 교묘한 트릭을 사용했습니다.

• 문제: 일반적으로 100 개의 변수가 있는 문제를 매핑하려면 100 개의 양자 '방'이 필요합니다. 하지만 양자 컴퓨터에는 약 23 개의 방만 있습니다.
• 트릭: PCE 는 마법 같은 압축 알고리즘과 같습니다. 각 변수에 별도의 방을 주는 대신, 변수들이 특정한 방식으로 서로 '대화'하도록 하여 (서로 다른 주제를 논의하기 위해 하나의 전화선을 공유하는 사람들 무리와 같음) 여러 변수를 단일 방에 담습니다. 이를 통해 거대한 문제 (최대 745 개의 변수) 를 작은 양자 컴퓨터 (23 큐비트) 에 담을 수 있습니다.

도전 과제: '흐린 사진'

양자 컴퓨터가 작업을 마치면 명확한 '예' 또는 '아니오' 답을 주지 않습니다. 대신 솔루션의 흐린 사진을 제공합니다. 즉, 확률 목록 (예: "이렇게 접힐 확률 70%, 저렇게 접힐 확률 30%") 입니다.

실제 답을 얻으려면 이 흐린 사진을 선명한 흑백 결정으로 바꿔야 합니다. 이를 디코딩이라고 합니다.

• 옛 방법: 흐린 사진을 보고 약간 어두우면 '예', 약간 밝으면 '아니오'라고 단순히 추측하는 것입니다. 이는 종이를 찢는 방식 (규칙 위반) 으로 접는 등 실수를 자주 초래합니다.
• 새 방법 (PAGD): 저자들은 문제 인식 유도 디코더 (PAGD) 라는 새로운 디코더를 만들었습니다. 이는 사전에 지도를 공부한 스마트 가이드와 같습니다.
  1. 양자 컴퓨터에서 나온 흐린 사진을 봅니다.
  2. 퍼즐의 규칙 (제약 조건) 을 확인합니다.
  3. 결정을 내리지만, 막히면 약간 다른 관점 ('재시작') 으로 다시 시도합니다.
  4. 모든 규칙을 따르고 완벽에 가까운 접기를 찾을 때까지 계속 시도합니다.

결과: 시뮬레이션에서 실제 하드웨어로

이 팀은 길이가 다양한 여섯 가지 다른 '종이 가닥'으로 이를 테스트했습니다.

1. 시뮬레이터 (가상 컴퓨터) 에서:

   • 중간 크기의 가닥의 경우, 새로운 방법 (PAGD) 은 75% 에서 100% 의 빈도로 거의 완벽한 솔루션을 찾았습니다.
   • 옛 방법 (흐린 사진을 기반으로 추측) 은 거의 완전히 실패하여 좋은 솔루션을 0~30% 의 빈도로만 찾았습니다.
   • 양자 컴퓨터가 수행한 '훈련'이 실제로 도움이 되었음을 증명했습니다. 훈련되지 않은 컴퓨터를 사용했을 때 결과는 훨씬 나빴습니다.

2. 실제 하드웨어 (IBM 양자 컴퓨터) 에서:

   • 그들은 최고의 설정을 가져와 뉴욕과 독일의 실제 물리적 양자 컴퓨터 (IBM Heron 프로세서) 에서 실행했습니다.
   • 그들은 세 개의 매우 긴 가닥 (약 100 개의 뉴클레오타이드 길이, 거의 700 개의 변수) 을 다뤘습니다.
   • 결과: 하나의 특정 가닥에서 실제 양자 컴퓨터는 짧은 시간 실행 후 정확한 완벽한 솔루션 (0% 오류) 을 찾았습니다. 다른 가닥들에서는 가상 시뮬레이터가 예측한 것보다 더 좋은 솔루션을 찾았습니다.
   • 이는 '노이즈'가 있는 실제 세계 하드웨어에서도 컴퓨터가 받은 '훈련'이 여행을 견디고 좋은 답을 찾는 데 도움이 된다는 것을 증명하기 때문에 큰 의미가 있습니다.

결론

이 논문은 다음 세 가지를 수행하면 작은 양자 컴퓨터에서도 거대하고 복잡한 접기 퍼즐을 해결할 수 있음을 보여줍니다.

1. 문제를 지능적으로 압축합니다 (PCE).
2. 퍼즐의 특정 규칙을 이해하도록 컴퓨터를 훈련시킵니다 (특별한 '손실 함수' 사용).
3. 규칙을 아는 스마트 가이드로 결과를 디코딩합니다 (PAGD).

그들은 실제 양자 기계에서 이를 성공적으로 시연하여, 실제 의학과 관련된 생물학적 분자에 대한 최적의 접기를 찾았으며, 하드웨어가 완벽하지 않더라도 이 접근 방식이 작동함을 증명했습니다.

기술 요약

기술 요약: mRNA 이차 구조 예측을 위한 파울리 상관 인코딩

문제 정의

mRNA 의 최소 자유 에너지 (MFE) 이차 구조를 예측하는 것은 치료제 설계에 필수적입니다. 접힘 패턴이 번역 효율성, 면역원성 및 안정성을 결정하기 때문입니다. 동적 계획법은 짧은 시퀀스의 경우 이를 정확하게 해결하지만, 의사결절 (pseudoknots) 을 포함하면 치료적으로 관련 있는 길이 (수백에서 수천 개의 뉴클레오타이드) 에서 문제가 NP-난해가 됩니다.

최근 양자 접근법은 이를 2 차 무제약 이진 최적화 (QUBO) 문제로 공식화했습니다. 그러나 표준 "큐비트당 하나의 변수" 매핑은 약 $L^{2.2}$ ($L$은 뉴클레오타이드 수) 로 스케일링되어 단기간 내 하드웨어의 큐비트 수를 빠르게 초과합니다. 또한, mRNA 접힘의 밀집된 제약 조건 (특히, 교차하지 않는 염기 쌍) 은 완화된 연속 해가 실현 가능한 이진 해와 크게 달라지는 에너지 지형을 만들어 표준 디코딩 전략을 무력화시킵니다.

방법론

저자들은 큐비트 부족과 밀집된 제약 조건을 해결하기 위해 **파울리 상관 인코딩 (PCE)**을 새로운 훈련 손실 및 **문제 인식 유도 디코더 (PAGD)**와 통합하는 파이프라인을 제안합니다.

1. 파울리 상관 인코딩 (PCE)

PCE 는 변수를 작은 레지스터의 가환 파울리 상관자 (예: $XX, YY, ZZ$) 에 매핑함으로써$m$개의 이진 변수를$n = O(m^{1/k})$개의 큐비트 (압축 차수$k \ge 2$) 로 압축합니다. 이를 통해 약 20 개의 큐비트에 수천 개의 변수를 인코딩할 수 있습니다. 회로는$[-1, 1]$ 범위의 연속 기대값 (EV) 을 생성하며, 이를 이진 해로 디코딩해야 합니다.

2. 문제 정보 기반 안사츠 (Informed-k)

저자들은 일반적인 토폴로지 (이웃 간 또는 완전 연결 등) 대신 QUBO 구조에 기반한 안사츠 토폴로지를 구성합니다.

• 중요도 점수 매기기: QUBO 커플링은 에너지 지형에 대한 기여도에 따라 가중치가 부여됩니다.
• 연결성: 크루스칼 최대 신장 트리 알고리즘이 이러한 중요도 점수를 기반으로 상위 $k$개의 큐비트 쌍을 선택합니다.
• 하드웨어 인식: QPU 배포를 위해 선택은 SWAP 게이트를 피하기 위해 장치 그래프의 네이티브 엣지로 제한되며, "SWAP 할인" 중요도 점수를 사용합니다.

3. 훈련 손실: QUBO 공간 시그모이드

저자들은 밀집 제약 QUBO 에 대한 표준 아이징 공간 손실에서 "선형 편향 문제"를 확인했습니다. 여기서 패널티 항이 선형 편향으로 누적되어 최적화기를 자명한 해로 유도합니다.

• 해결책: 저자들은 QUBO 공간 시그모이드 손실을 도입합니다. 소프트 이진 변수는 $\tilde{x}_i = \sigma(-\alpha e_i)$로 정의됩니다. 손실은 $L_{QUBO} = \tilde{x}^T Q \tilde{x}$입니다.
• 메커니즘: 이는 충돌하는 파트너가 비활성 상태일 때 패널티 기울기가 소멸되도록 하여, 최적화기가 일정한 선형 편향에 압도되지 않고 에너지에 유리한 활성화를 탐색할 수 있게 합니다.

4. 문제 인식 유도 디코더 (PAGD)

연속 EV 를 실현 가능한 이진 해로 디코딩하기 위해 저자들은 고전적 탐욕 휴리스틱과 양자 훈련된 사전 지식을 결합한 PAGD 를 제안합니다.

• 점수 매기기: 각 후보 변수에 대해 한계 QUBO 에너지 감소($-\Delta_i$)와 훈련된 EV 사전 지식($\tilde{x}_i^\beta$)의 곱으로 점수가 계산됩니다.
• 제약 조건 인식 가지치기: 변수는 이 점수에 따라 탐욕적으로 확정되며, 모든 제약 위반 변수는 즉시 가지치기됩니다.
• 재시작 (PAGD-K): 지역 최적점에서 벗어나기 위해, 점수 매기기 전에 EV 벡터에 작은 가우스 섭동을 추가하여 이 과정을 $K$번 반복합니다.

주요 기여

1. 문제 정보 기반 안사츠: QUBO 중요도로 큐비트 쌍을 순위 매기는 "Informed-k" 토폴로지는 밀집 제약 인스턴스, 특히 더 큰 문제 크기의 경우 이웃 간 및 완전 연결 토폴로지보다 우수한 성능을 보입니다.
2. PAGD 디코더: 훈련된 EV 를 사전 지식으로 활용하여 탐욕적 확정의 순서를 재배열하는 디코딩 방식으로, 표준 부호 반올림 및 지역 검색 기준선보다 훨씬 우수한 성능을 보입니다.
3. 훈련된 사전 지식의 검증: PCE 훈련이 유용한 구조 정보를 인코딩한다는 실증적 증명. $m=240$ 인스턴스에서 훈련된 PAGD 는 $K=200$에서 50% 의 준최적 복구 ($P(\text{gap}<1\%)$) 를 달성하여 훈련되지 않은 회로보다 10% 포인트, 무작위 EV 기준선보다 40 포인트 더 높은 성능을 보였습니다.
4. 하드웨어 규모 실증: 세 개의 mRNA 시퀀스 (약 100 개 뉴클레오타이드, $m=694\text{--}745$개 변수, $n=23$개 큐비트) 에 대해 IBM Heron 프로세서에서 성공적으로 배포되었습니다. 회로는 SWAP 없이 480 개의 네이티브 2 큐비트 게이트로 변환되었습니다.

결과

시뮬레이션 벤치마크

• 준최적 복구: $m=152$까지의 시퀀스의 경우, 100 회 재시작 (PAGD-K100) 을 사용한 PAGD 는 75–100% 의 준최적 복구 ($P(\text{gap}<1\%)$) 를 달성했습니다. 반면, Sign+Local Search 기준선은 0–30% 였습니다.
• 회로 깊이: 최적 성능은 작은 $m$의 경우 깊이 $p=2$에서 더 큰 $m$ ($195, 240$) 의 경우$p=6$으로 이동하여 압축이 증가함에 따라 더 큰 표현력이 필요함을 나타냅니다.
• 디코더 성능: $m=240$에서 PAGD-K100 은 재시작 예산에 제한되어 15–40% 의 준최적 복구에 도달한 반면, Sign+LS 는 완전히 실패했습니다 (0%).

하드웨어 결과 (IBM Heron)

• 시퀀스: 102–105 개의 뉴클레오타이드로 구성된 세 가지 시퀀스 ($m=694, 715, 745$) 가 $n=23$개의 큐비트에서 실행되었습니다.
• 성능:
  • seq_694: PAGD-K200 을 사용한 단일 100 회 반복 QPU 실행은 CPLEX 최적값을 정확히 복구했습니다 (0.0% 갭). $K=10$에서 갭은 7.4% 였습니다.
  • seq_715 및 seq_745: $K=200$에서 QPU 는 각각 5.9% 와 18.0% 의 갭을 달성하여 동일한 회로에 대한 평균 시뮬레이션 결과를 모두 능가했습니다.
• 결론: 훈련된 PCE 사전 지식은 잡음이 있는 초전도 하드웨어로 이동해도 생존하여 잡음이 없는 시뮬레이션과 비교할 수 있거나 더 나은 해의 품질을 유지했습니다.

중요성 및 주장

이 논문은 제약 문제가 있는 컴팩트 양자 인코딩의 성능이 훈련 손실, 문제 구조, 그리고 디코더 사이의 정렬에 결정적으로 의존한다고 주장합니다.

• 규모에서의 실현 가능성: 이 연구는 PCE 가 한 변수당 하나의 큐비트 매핑으로는 처리 불가능한 생물학적으로 관련 있는 문제 크기 (23 개 큐비트에서 최대 약 745 개 변수) 를 처리할 수 있음을 보여줍니다.
• 사전 지식의 유용성: QUBO 공간 손실로 변이 회로를 훈련하면 하드웨어 잡음이 존재하더라도 디코딩을 위한 의미 있는 사전 지식으로 작용하는 기대값을 생성함을 확립합니다.
• 적당한 범위: 저자들은 하드웨어 결과를 양자 우월성 주장이 아닌 "실현 가능성 실증"으로 제시합니다. 이 방법은 인스턴스에 의존적이며, 고전적 탐욕 방법이 갇히지만 훈련된 사전 지식이 탈출을 유도할 수 있는 중간 난이도 수준에서 가장 큰 이점을 보인다고 지적합니다.
• 향후 방향: 이 논문은 더 큰 규모에서 관찰된 재시작 횟수 병목 현상이 제한 요인일 수 있다고 제안하며, 이 훈련 - 디코딩 파이프라인을 다른 밀집 제약 클래스 (예: 스케줄링, 그래프 색칠) 에 적용할 것을 제안합니다.