Penalty-free quantum optimization applied to lattice protein folding

본 논문은 이차 펜티티(quadratic penalty)를 피하기 위해 최대 독립 집합 문제용으로 설계된 QAOA 믹서를 활용하여 격자 단백질 접힘(lattice protein folding)에 대한 펜티티가 없는 양자 최적화 접근 방식을 제안하며, 소규모 단백질에 대한 고전 시뮬레이션을 통해 해당 방법을 성공적으로 검증하고 휴리스틱 반복 국소 탐색 기법을 통해 더 큰 시스템(길이 $N=14$까지)으로 확장하였다.

핵심

개요: 퍼즐처럼 단백질 접기

구슬로 된 길고 유연한 줄이 있다고 상상해 보세요. 어떤 구슬은 "끈적끈적"(소수성)하고, 어떤 구슬은 "미끄러움"(친수성)을 가집니다. 여러분의 목표는 이 줄을 조밀한 모양으로 접어서, 물을 피해 끈적한 구슬들이 가운데로 모이게 만드는 것입니다. 이것을 **단백질 접기(protein folding)**라고 부릅니다.

현실 세계에서 이 일은 자연스럽게 일어납니다. 하지만 컴퓨터 상에서 아주 짧은 줄이라도 완벽한 모양을 찾는 것은 매우 어렵습니다. 이는 마치 수십억 가지의 방식으로 배치할 수 있는 거대한 직소 퍼즐 조각들을 가지고, 에너지를 가장 적게 사용하는 단 하나의 특정 배치를 찾아내야 하는 것과 같습니다.

기존 방식의 문제점

과학자들은 이를 해결하기 위해 **양자 컴퓨터(Quantum Computers)**를 사용하려고 시도해 왔습니다. 보통 양자 컴퓨터에게 퍼즐을 풀라고 요청할 때는 다음과 같은 규칙을 알려주어야 합니다:

1. "줄은 끊어지지 않고 이어져 있어야 한다."
2. "줄은 스스로 교차할 수 없다."
3. "모든 구슬은 반드시 특정 위치에 있어야 한다."

과거에는 컴퓨터가 이 규칙들을 따르게 만들기 위해, 과학자들은 점수에 "벌칙 점수(penalty points)"를 더하는 방식을 사용했습니다. 만약 컴퓨터가 실수(예: 끊어진 줄)를 하면 엄청난 벌칙을 받는 식입니다. 이는 규칙을 어길 때마다 벌금을 내는 게임을 하는 것과 같습니다. 문제는 이러한 벌칙들이 수학적으로 매우 복잡(이차식 형태)하여, 양자 컴퓨터의 작업을 훨씬 더 어렵고 느리게 만든다는 점입니다.

새로운 아이디어: "벌칙 없는" 구역

이 논문은 이러한 복잡한 벌칙을 완전히 피할 수 있는 영리한 트릭을 소개합니다.

비유: "충돌 그래프(Conflict Graph)"
퍼즐 조각들을 파티에 온 사람들이라고 상상해 보세요.

• 어떤 사람들은 서로 싫어합니다 (이는 같은 위치에 있거나 서로 옆에 있을 수 없는 구슬들을 나타냅니다).
• 우리는 서로 싫어하는 사람들 사이에 선을 긋습니다. 이것이 "충돌 그래프"를 만듭니다.

파티의 규칙은 간단합니다: 누구도 서로 싫어하지 않는 경우에만 VIP 구역에 초대할 수 있습니다. 수학적으로 말하면, 여러분은 독립 집합(Independent Set)(선으로 연결되지 않은 사람들의 집단)을 찾고 있는 것입니다.

이 그래프를 사용함으로써, 연구진은 컴퓨터에게 "이 두 구슬이 닿지 않게 해!"라고 말할 필요가 없다는 것을 깨달았습니다. 왜냐하면 그래프 자체가 그것을 금지하고 있기 때문입니다. 만약 컴퓨터가 유효한 그룹(독립 집합)을 선택한다면, 규칙은 자동으로 준수됩니다. 벌칙이 필요 없습니다!

도구: QAOA-MIS

연구진은 QAOA(양자 근사 최적화 알고리즘)라는 특정 양자 알고리즘을 사용했습니다.

• 표준 QAOA: 퍼즐을 풀려고 노력하지만, 규칙 위반 여부를 끊임없이 확인해야 합니다.
• 새로운 버전 (QAOA-MIS): 오직 유효한 그룹 사이에서만 이동하도록 설계된 특수한 "믹서(mixer)"(가능성을 섞어주는 양자 도구)를 사용합니다. 이는 마치 클럽의 보안 요원이 이미 유효한 그룹에 속한 사람들만 입장시키는 것과 같습니다. 만약 규칙을 어기려 한다면, 보안 요원은 그곳으로의 이동을 허용하지 않습니다.

이는 컴퓨터가 유효하지 않은 해결책이 아닌, 유효한 해결책을 찾는 데에만 시간을 쓰도록 만듭니다.

결과: 작은 퍼즐 vs 큰 퍼즐

연구팀은 이를 2D 격자(체크판 같은 평면)와 두 종류의 구슬을 사용하여 테스트했습니다.

1. 작은 퍼즐 (4~6개 구슬):
   그들은 일반 슈퍼컴퓨터로 양자 컴퓨터를 시뮬레이션했습니다. 그 결과, 새로운 "벌칙 없는" 방식이 매우 잘 작동한다는 것을 발견했습니다. 가장 작은 퍼즐의 경우, 매우 단순한 설정만으로도 거의 즉시 완벽한 해답을 찾아냈습니다.

2. 큰 퍼즐 (최대 14개 구슬):
   실제 양자 컴퓨터와 시뮬레이션은 퍼즐이 커질수록 빠르게 과부하가 걸립니다. 14개 구슬 퍼즐을 풀려면 현재 기술로는 너무 많은 부품을 가진 양자 컴퓨터가 필요합니다.

해결책: "지역 탐색(Local Search, QLS)"
큰 문제를 해결하기 위해 그들은 **양자 지역 탐색(Quantum Local Search, QLS)**이라는 전략을 발명했습니다.

• 비유: 거대하게 엉킨 실타래를 푸는 것을 상상해 보세요. 전체를 한꺼번에 풀려고 하는 대신, 3인치 정도의 작은 구간으로 줌인하여 그 부분만 먼저 풀고, 그다음 구간으로 이동하는 방식입니다.
• 그들은 큰 단백질 문제를 작은 "이웃(neighborhoods)"(작은 구슬 그룹)으로 나누었습니다. 그리고 양자 컴퓨터를 사용하여 딱 그 작은 이웃만을 해결한 뒤 다음 단계로 넘어갔습니다.
• 또한 "고정(pinning)" 기법도 사용했습니다: 일단 구슬이 올바르게 배치되면, 다음 구역을 해결하는 동안 컴퓨터가 실수로 그 구슬을 움직이지 않도록 고정해 두었습니다.

결과:
이 "줌인" 방식을 사용하여, 연구진은 최대 14개의 구슬 길이까지의 단백질의 올바른 모양을 성공적으로 찾아냈습니다. 이는 현재의 전체 규모 양자 컴퓨터 시뮬레이션으로는 불가능한 크기입니다.

요약

• 목표: 단백질 사슬의 최적의 모양을 찾는 것.
• 기존 방식: 양자 컴퓨터를 사용하되, 규칙을 어길 때마다 무거운 "벌칙 점수"를 부여하여 속도를 늦추는 방식.
• 새로운 방식: 규칙을 "충돌 그래프"에 매핑하여 유효한 움직임만 가능하게 함. 이를 통해 벌칙의 필요성을 제거함.
• 전략: 큰 문제를 다룰 때는 한꺼번에 해결하지 말고, 양자 컴퓨터를 사용하여 작은 지역적 이웃을 하나씩 차례대로 해결함.
• 결과: 이 "벌칙 없는" 방식이 양자 컴퓨터를 사용하는 강력하고 새로운 방법임을 입증하며, 작은 단백질을 완벽하게 접고 더 큰 단백질(최대 14개 구슬)까지 성공적으로 해결함.

기술 요약

기술 요약: 격자 단백질 폴딩에 적용된 페널티 프리 양자 최적화

문제 정의
격자 단백질의 최소 에너지 구조를 식별하는 것은 NP-완전(NP-complete)으로 알려진 까다로운 이산 최적화 문제이다. 본 연구에서 조사된 특정 모델은 2차원 소수성-극성(Hydrophobic-Polar, HP) 모델로, 여기서 단백질은 정사각형 격자 위의 H 및 P 잔기들로 구성된 자기 회피 사슬(self-avoiding chains)로 표현된다. 목표는 비인접 소수성(H-H) 접촉을 최소화하는 사슬 컨포메이션(conformation)을 찾는 것이다.

QAOA(Quantum Approximate Optimization Algorithm) 및 QA(Quantum Annealing)와 같은 전통적인 양자 접근 방식은 일반적으로 이 문제를 이차 무제약 이진 최적화(QUBO) 형식으로 매핑한다. 이러한 표준 매핑은 물리적 제약 조건을 강제하기 위해 이차 페널티 항을 포함해야 한다. 즉, 각 아미노산은 정확히 하나의 격자 지점을 점유해야 하며(자기 회피), 비드(beads)들이 연속적인 사슬을 형성해야 한다. 이러한 페널티 항은 문제 해밀토니안의 복잡성을 증가시키며 세심한 라그랑주 승수(Lagrange multiplier) 튜닝을 요구한다.

방법론
저자들은 이차 페널티에 의존하는 대신, 충돌 그래프(conflict graph)의 구조를 활용하여 유효한 구성으로 탐색 공간을 제한하는 QAOA$_{MIS}$라고 명명된 페널티 프리 QAOA 변형 방식을 제안한다.

1. 충돌 그래프와 독립 집합(Independent Sets):
   문제는 아미노산의 위치를 나타내는 이진 변수(큐비트)를 노드로 하는 충돌 그래프로 매핑된다. 에지는 유효한 사슬 구조를 위해 필요한 페널티 에너지($E_1, E_2, E_3$)로부터 유도된 이차 제약을 나타낸다. 비트 구성은 활성화된 비트(값 1)의 집합이 이 그래프에서 **독립 집합(independent set)**을 형성할 때에만 유효한 사슬이 된다(즉, 활성화된 두 노드가 에지로 연결되지 않음). 전체 길이의 사슬은 최대 독립 집합(Maximum Independent Set, MIS)에 해당한다.

2. QAOA$_{MIS}$ 공식:
   표준 트랜스버스 필드 믹서($X$-mixer)나 XY-믹서 대신, 저자들은 MIS 문제에 특화된 믹서를 사용한다. 이 믹서는 독립 집합의 부분 공간을 보존한다. 결과적으로 목적 함수는 다음과 같이 단순화된다:
   $$E_{MIS} = E_{HP} - \lambda_1 \sum_{i,n} b_{i,n}$$
   여기서 $E_{HP}$는 단백질 에너지이며, 두 번째 항은 전체 길이 사슬 형성을 장려하는 단순한 선형 바이어스(linear bias)이다. 결정적으로, 이차 페널티 항이 제거된다.

3. 더 큰 시스템을 위한 양자 국소 탐색(Quantum Local Search, QLS):
   사슬 길이 $N > 6$인 경우 큐비트 및 게이트 수의 지수적 증가로 인해 전체 규모의 QAOA 시뮬레이션이 실행 불가능해지므로, 저자들은 휴리스틱한 양자 국소 탐색(QLS) 기법을 도입한다.

• 국소 이웃(Local Neighborhoods): 알고리즘은 충돌 그래프의 국소 이웃(서브그래프)을 반복적으로 선택하며, 이는 26개 이하의 큐비트로 제한된다.
• 피닝 메커니즘(Pinning Mechanism): 시스템이 국소 최솟값에 갇히는 것을 방지하기 위해, 동적인 "피닝(pinning)" 전략을 사용한다. 새로운 위치로 성공적으로 이동한 아미노산은 특정 확률로 "피닝(고정)"되는 반면, 다른 것들은 탐색을 허용하기 위해 "언피닝(해제)"된다.
• 준비 실행(Preparatory Run): 준비 단계의 QAOA 실행은 전체 사슬 최적화가 시작되기 전, 소수성(H) 잔기들을 낮은 에너지 코어로 패킹하는 데 집중한다.
• 하이브리드 처리: 26-큐비트 제한을 초과하는 이웃에 대해서는, 저자들은 하이브리드 접근 방식을 테스트하여 해당 특정 서브 문제를 클래식하게 해결한다.

주요 결과
본 연구는 양자 회로의 클래식 시뮬레이션을 통해 접근 방식을 검증하였다:

• 짧은 사슬 ($N=4, 6$):

  • QAOA$_{MIS}$를 표준 QAOA ($X$-mixer) 및 QAOA$_{XY}$와 비교하였다.
  • $N=4$의 경우, QAOA$_{MIS}$는 단일 레이어($p=1$)에서 1.0에 가까운 성공 확률을 달성하여 낮은 깊이에서 다른 변형 방식들을 능가했다.
  • $N=6$의 경우, QAOA$_{MIS}$는 $p=5$에서 약 0.77의 성공 확률에 도달했다. 성능은 이봉 분포(0 또는 1 근처)를 보였는데, 이는 이 방법이 강력하지만 파라미터 공간의 차원이 증가함에 따라 파라미터 최적화가 어려워짐을 시사한다.
  • 초기 상태의 선택은 작은 $p$ 값에서 결과에 큰 영향을 미쳤다. "비어 있는 비드" 상태($I_0$) 또는 특정 전체 사슬 상태($I_1, I_2$)에서 시작하는 것은 해밍 거리(Hamming distance)와 에너지 경관(energy landscape) 내의 다운힐 경로 존재 여부에 따라 서로 다른 성공률을 보였다.

• 더 긴 사슬 ($N=4$ ~ $14$):

  • 26-큐비트로 캡이 씌워진 국소 이웃을 사용하는 QLS 기법을 사용하여, 저자들은 $N=14$까지의 서열을 성공적으로 폴딩했다.
  • 이 방법은 테스트된 모든 서열($N \le 14$)에 대해 적어도 한 번의 실행에서 바닥 상태(ground state)를 찾아냈다(성공률 $\ge 0.1$).
  • 서열 $S_{12}$는 가장 낮은 성공률(1/10 실행)을 보였으며, 저자들은 이를 해당 서열의 평균 이웃 크기가 크기 때문이라고 분석했다.
  • 26-큐비트보다 큰 이웃을 클래식하게 처리했을 때, 성공률이 크게 향상되었다(예: $N \le 14$에 대해 $\ge 0.6$). 또한 $N \le 18$까지의 서열에 대해서도 바닥 상태를 찾아냈다.
  • QLS 접근 방식은 전체 시스템 시뮬레이션에 비해 유효 큐비트 수를 약 한 자릿수 감소시켰다 (예: $N=14$의 경우, 전체 시스템은 188개의 큐비트가 필요하지만, QLS는 평균 14~19개의 이웃 큐비트를 사용함).

의의 및 주장
본 논문은 충돌 그래프에서의 독립 집합으로 탐색 공간을 제한함으로써 격자 단백질 폴딩에서 이차 페널티 항을 제거하고, 목적 함수를 선형 바이어스와 물리적 에너지로 단순화할 수 있다고 주장한다. 이러한 "페널티 프리" 접근 방식은 외판원 문제(Traveling Salesman Problem)와 같이 유사한 QUBO 구조를 가진 최적화 문제에 대한 유효한 전략으로 제시된다.

저자들은 QAOA$_{MIS}$ 변형이 작은 시스템에는 효과적이지만, 더 큰 단백질로 확장하기 위해서는 제안된 QLS 휴리스틱이 필수적임을 강조한다. 그들은 현재의 하드웨어가 요구되는 국소 이웃 크기(현재 $\le 26$ 큐비트)를 처리할 수 있다면, 이 국소 탐색 접근 방식이 전체 규모의 QAOA가 도달할 수 있는 범위를 훨씬 넘어서는 격자 단백질 폴딩 문제를 해결할 수 있을 것이라고 결론짓는다. 본 연구는 그래프 기반의 제약 조건이 페널티 튜닝의 오버헤드 없이도 양자 최적화의 제약 조건을 효과적으로 관리할 수 있음을 입증한다.