Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems

본 논문은 중성 원자 양자 하드웨어의 제약 단위 원 그래프 임베딩 문제를 해결하기 위한 신경망 기반 접근법을 제안하며, QUBO 문제를 물리적 큐비트 구성에 매핑하는 데 있어 Gurobi 솔버보다 우수한 성능을 보임을 입증합니다.

핵심

거대한 복잡 퍼즐을 풀려고 노력한다고 상상해 보세요. 하지만 조각들이 어떻게 맞물려야 하는지에 대해 매우 구체적이고 독특한 규칙 세트를 가지고 있습니다. 이것이 개별 원자 (특히 '리드베르크 원자') 를 구성 요소로 사용하는 새로운 유형의 양자 컴퓨터를 연구하는 과학자들이 직면한 과제입니다.

다음은 일상적인 비유를 사용하여 이 논문이 무엇에 관한 것인지 간단히 설명한 것입니다.

문제: "사회적 거리두기" 원자

양자 컴퓨터를 무대라고 생각하고, 무대 위의 댄서들은 원자라고 상상해 보세요. 이 원자들은 매우 구체적인 사회적 규칙을 따릅니다.

• "블로케이드" 규칙: 두 원자가 서로 너무 가까워지면 (특정 "블로케이드 반경"보다 가까워지면) "얽힘" 상태가 됩니다. 이는 두 원자가 동시에 "들뜬" 상태에 있을 수 없다는 것을 의미합니다. 마치 "당신이 이웃으로부터 5 피트 이내에 서 있다면, 동시에 점프할 수 없다"는 규칙과 같습니다.
• 목표: 과학자들은 이 원자들을 무대 위에 배치하여 그들의 "사회적 규칙"(누가 누구와 가까운지) 이 해결하고자 하는 특정 수학 문제 (QUBO 문제라고 함) 와 완벽하게 일치하도록 하려고 합니다.

하지만 함정이 있습니다:

1. 무대는 작습니다: 원자들은 작은 원형 공간 (모래알 크기 정도) 안에 머물러야 합니다.
2. 최소 거리: 원자들은 너무 가까워질 수 없습니다 (4 마이크로미터 미만). 그렇지 않으면 기계가 고장 납니다.
3. 기하학적 구조: 문제의 요구사항에 따라 두 원자가 "친구"(수학 문제에서 연결됨) 라면, "블로케이드"를 유발할 만큼 충분히 가까워야 합니다. 반면 "낯선 사람"(연결되지 않음) 이라면 "블로케이드"를 피할 만큼 충분히 멀리 떨어져 있어야 합니다.

수백 개의 원자를 한 번에 이 모든 규칙을 만족하도록 배치하는 방법을 찾는 것은 매우 어렵습니다. 마치 어떤 손님은 옆에 앉아야 하고, 어떤 손님은 멀리 떨어져 있어야 하며, 모두가 팔꿈치가 부딪히지 않도록 작은 원형 테이블에 모두 앉아야 하는 결혼식 좌석 배정을 시도하는 것과 같습니다.

구식 방법: "무차별 대입" 솔버

전통적으로 과학자들은 논문에서 언급된 Gurobi 솔버와 같은 강력한 고전 컴퓨터를 사용하여 완벽한 좌석 배정을 계산해 왔습니다.

• 문제점: 손님 (원자) 의 수가 증가함에 따라 수학이 너무 복잡해져서 가장 빠른 슈퍼컴퓨터조차 막히게 됩니다. 몇 시간이나 며칠을 실행해도 유효한 배치를 찾지 못할 수 있습니다. 마치 루빅스 큐브를 한 번에 한 번씩 모든 움직임을 추측하여 풀려고 시도하는 것과 같습니다. 결국 시간이 부족해집니다.

새로운 해결책: "신경망 건축가" (GEAN)

이 논문의 저자들은 신경망(AI 의 한 유형) 을 사용한 새로운 접근법을 제안합니다. 그들은 이 시스템을 GEAN(Graph Embedding Autoencoder Network) 이라고 부릅니다.

GEAN 을 계산기가 아니라 창의적인 건축가나 안무가로 생각하세요:

1. 시작점: AI 에게 원자들의 지저분하고 무작위적인 배치를 입력합니다. 처음에 서로 충돌하거나 너무 멀리 떨어져 있어도 상관없습니다.
2. 학습: AI 는 배치를 분석하고 "점수"(손실 함수) 를 계산합니다.
   • 페널티 1: 어떤 원자가 너무 가까워졌나요? (너무 가까움 = 나쁨).
   • 페널티 2: 어떤 원자가 너무 멀리 떨어졌나요? (너무 멀음 = 나쁨).
   • 페널티 3: "친구"들이 상호작용할 만큼 충분히 가까이 있었나요?
   • 페널티 4: "낯선 사람"들이 상호작용을 피할 만큼 충분히 멀리 떨어져 있었나요?
3. 조정: AI 는 "뇌"를 사용하여 원자들을 살짝 밀어 점수를 낮추려고 시도합니다. 이를 순간적으로 수천 번 반복합니다.
4. 결과: 막히지 않고, AI 는 양자 기계의 모든 물리적 규칙을 만족하는 완벽하고 유효한 배치로 원자들을 빠르게 재배열하는 법을 배웁니다.

그들이 발견한 것

이 논문은 이 "AI 안무가"를 도시의 안테나 배치나 단백질 접기와 같은 여러 유형의 퍼즐에 테스트했습니다.

• 속도: AI 는 매우 크고 복잡한 문제조차 2 분 미만에 유효한 배치를 찾았습니다.
• 성공률: 기존 "무차별 대입" 컴퓨터 (Gurobi) 가 포기하거나 시간 제한 내에 해답을 찾지 못한 많은 경우에서 AI 는 성공했습니다.
• 3D 기능: AI 는 구 안에 원자를 쌓는 것처럼 3 차원 공간에서도 원자를 배치할 수 있으며, 이를 통해 더 복잡한 문제들을 해결할 수 있습니다.

결론

이 논문은 아직 우주의 궁극적인 수수께끼를 해결했다고 주장하지는 않습니다. 대신 이론적인 수학 문제와 양자 컴퓨터의 물리적 현실 사이의 간극을 메울 수 있는 실용적인 도구를 제시합니다.

그것은 다음과 같이 말합니다. "우리는 이전 방법들보다 더 빠르고 신뢰할 수 있는 양자 칩 위의 원자 배치 방법을 발견했습니다." 신경망을 똑똑하고 빠르게 움직이는 안무가로 활용함으로써, 원자들을 올바른 위치에 배치하여 양자 컴퓨터가 실제로 작업을 시작할 수 있도록 합니다.

기술 요약

기술 요약: QUBO 문제를 위한 신경망 기반 단위 원반 그래프 임베딩

문제 정의
본 논문은 중성 원자 기반 양자 시뮬레이터, 특히 리드버그 원자를 활용하는 장치 (예: Pasqal Chadoq2 프로토타입) 에 Quadratic Unconstrained Binary Optimization(QUBO) 문제를 매핑하는 중요한 과제를 다룹니다. 게이트 기반 양자 컴퓨터나 고정 토폴로지의 어닐러 (D-Wave 등) 와 달리, 중성 원자 장치는 큐비트를 2 차원 또는 3 차원 공간에 임의로 배치할 수 있습니다. 그러나 이러한 큐비트 간의 물리적 상호작용은 리드버그 블로케이드 효과에 의해 지배받습니다. 즉, 특정 "블로케이드 반경"($r_b$) 보다 짧은 거리로 분리된 큐비트는 동시에 여기될 수 없으며, 이는 단위 원반 (UD) 그래프와 동등한 인접 패턴을 생성합니다.

핵심 난제는 단위 원반 그래프 임베딩 문제에 있습니다. 즉, 다음 조건을 만족하는 큐비트들의 물리적 좌표 집합을 찾는 것입니다:

1. 대상 QUBO 그래프에서 인접한 큐비트들은 블로케이드 반경 이내 ($d_{ij} \leq \tilde{r}_b$) 에 있어야 합니다.
2. 인접하지 않은 큐비트들은 블로케이드 반경 밖 ($d_{hk} > \tilde{r}_b$) 에 있어야 합니다.
3. 모든 큐비트는 물리적 레지스터 제약 (예: 50 $\mu$m 반경의 원형 영역) 내에 배치되고, 중첩을 피하기 위해 최소 분리 거리 (예: 4 $\mu$m) 를 준수해야 합니다.

저자들은 좌표로부터 인접성을 계산하는 것은 자명하지만, 특정 인접 행렬을 만족하는 좌표를 찾는 역문제 (inverse problem) 는 NP-난해 (NP-hard) 라고 지적합니다. 고전적 솔버는 종종 복잡하거나 대규모의 QUBO 인스턴스에 대해 합리적인 시간 내에 실현 가능한 임베딩을 찾지 못합니다.

방법론: GEAN (그래프 임베딩 오토인코더 네트워크)
저자들은 초기에 종종 실현 불가능한 큐비트 구성을 유효한 UD 임베딩으로 변환하도록 설계된 신경망 기반 휴리스틱인 GEAN을 제안합니다. 이 접근법은 표준 예측 작업이 아닌 도메인 변환 문제로 임베딩 작업을 취급합니다.

• 아키텍처:
  • 입력/출력: 네트워크는 $n$개의 큐비트에 대한 초기 2 차원 또는 3 차원 좌표 $(x_i, y_i, z_i)$를 입력받아 변환된 좌표 $(x'_i, y'_i, z'_i)$를 출력합니다.
  • 오토인코더 구성 요소: 대칭적인 완전 연결 네트워크 (입력 $\to$ 은닉층 $\to$ 출력) 가 좌표를 변환합니다. 출력층은 물리적 도메인 ($\pm 50$ $\mu$m) 에 맞게 스케일링된 tanh 활성화 함수를 사용합니다.
  • 미분 가능한 거리 계층: 변환된 좌표를 기반으로 모든 큐비트 쌍 간의 유클리드 거리를 계산하는 특수한 비학습형 희소 계층이 포함됩니다. 이를 통해 네트워크는 훈련 중 기하학적 제약을 "볼" 수 있습니다.
• 손실 함수: 훈련 목표는 예측 오차를 최소화하는 것이 아니라 네 가지 물리적 제약을 동시에 만족시키는 것입니다. 손실 함수는 네 가지 페널티 항의 합입니다:
  1. 전역 경계: 최대 레지스터 반경 (100 $\mu$m) 을 초과하는 쌍을 페널티화합니다.
  2. 최소 분리: 최소 물리적 거리 (4 $\mu$m) 보다 가까운 쌍을 페널티화합니다.
  3. 인접성 제약: 너무 멀리 떨어진 ($> \tilde{r}_b$) 인접 큐비트를 페널티화합니다.
  4. 비인접성 제약: 너무 가까운 ($\leq \tilde{r}_b + \epsilon$) 비인접 큐비트를 페널티화합니다.
• 최적화: 모델은 AdamW 옵티마이저를 사용하여 훈련됩니다. 훈련 데이터셋은 단일 샘플 (특정 QUBO 인스턴스) 로 구성되며, 네트워크는 해당 그래프에 대한 임베딩 문제를 효과적으로 해결하는 손실을 최소화하는 좌표 집합을 찾기 위해 반복합니다.

주요 기여

1. NP-난해 임베딩을 위한 신경 휴리스틱: 본 논문은 오토인코더의 새로운 응용을 통해 제약 단위 원반 그래프 임베딩 문제를 해결하여, 더 크거나 복잡한 그래프에 대한 정확한 고전 솔버의 한계를 우회합니다.
2. 물리적 제약 통합: 이 방법론은 중성 원자 하드웨어의 물리적 한계 (블로케이드 반경, 최소 분리, 레지스터 크기) 를 신경망의 손실 함수와 아키텍처에 명시적으로 통합합니다.
3. 차원 유연성: 이 접근법은 2 차원과 3 차원 모두에서 입증되었습니다. 저자들은 네트워크를 3 차원으로 확장하면 기하학적 패킹 한계로 인해 2 차원에서는 임베딩이 불가능한 더 높은 연결성 (더 큰 클릭과 차수) 을 가진 그래프를 임베딩할 수 있음을 보여줍니다.
4. 이론적 경계: 본 논문은 원형 패킹에 관한 Thue 정리에 기반하여 2 차원 임베딩에 필요한 조건을 식별하여, 특정 머신 파라미터 ($\tilde{r}_b \approx 10.26$ $\mu$m) 하에서 2 차원 임베딩의 최대 클릭 크기는 7 이고 최대 차수는 18 임을 확립합니다.

결과
저자들은 세 가지 유형의 QUBO 인스턴스에 대해 GEAN 을 최첨단 고전적 2 차 솔버인 Gurobi 와 비교 평가했습니다:

• QUBO MIS 안테나: 토리노의 안테나 위치에서 얻은 실제 데이터입니다. GEAN 은 2 분 시간 제한 내에 Gurobi 가 실현 가능한 해를 찾지 못한 연결 구성 요소 (3 차원에서 최대 87 개 큐비트) 를 성공적으로 임베딩했습니다.
• 단백질 접힘: 최대 독립 집합 문제로 모델링된 인스턴스들입니다. GEAN 은 테스트된 모든 인스턴스에 대해 실현 가능한 임베딩을 찾았으며, 반면 Gurobi 는 $G_{17,7}$ 인스턴스에서 실패했습니다.
• 그래프 채색: 21 개 큐비트 그래프로 매핑된 3-채색 문제입니다. GEAN 은 767 에포크 내에 실현 가능한 3 차원 임베딩을 찾았으나, Gurobi 는 수렴하지 못했습니다.

성능 지표:

• 속도: GEAN 은 가장 복잡한 87 개 큐비트 3 차원 인스턴스조차 표준 소비자용 하드웨어에서 2 분 이내에 일관되게 해를 찾았습니다.
• 실현 가능성: Gurobi 가 시간 제한 내에 어떤 실현 가능한 임베딩도 찾지 못한 경우, GEAN 은 성공했습니다.
• 품질: 변환된 좌표는 모든 물리적 제약 (최소 거리, 최대 거리, 블로케이드 반경 분리) 을 만족하여, 종종 Fruchterman-Reingold 레이아웃에서 파생된 "실현 불가능한" 초기 구성을 유효한 하드웨어 준비 레이아웃으로 효과적으로 변환했습니다.

의의 및 주장
본 논문은 GEAN 이 이론적 QUBO 공식과 중성 원자 양자 하드웨어의 물리적 현실 사이의 실용적인 가교를 제공한다고 주장합니다. 신경망을 활용하여 큐비트 배치를 최적화함으로써 이 방법은 다음과 같은 이점을 가집니다:

• 고전적 한계 극복: 복잡한 그래프에 대한 실현 가능한 임베딩을 합리적인 시간 내에 찾는 데 있어 Gurobi 와 같은 전통적인 정확한 솔버보다 성능이 뛰어납니다.
• 리소스 오버헤드 최소화: 보조 "와이어" 원자나 고정 격자 구조가 필요한 접근법과 달리, GEAN 은 레지스터의 전체 유연성을 활용하여 문제에 필요한 최소 수의 물리적 큐비트만을 요구합니다.
• 확장성 가능: 이러한 임베딩 문제를 빠르게 해결할 수 있는 능력은 연구자들이 임베딩 과정 자체에 병목 현상이 발생하지 않도록 현재 제한된 큐비트 수를 가진 하드웨어에서 비자명한 QUBO 문제를 테스트할 수 있게 합니다.

저자들은 현재 모델이 특정 머신 파라미터에 맞게 조정되었지만, 프레임워크는 다른 하드웨어 제약에 적응 가능하며 임베딩을 넘어 더 넓은 범주의 최적화 문제를 해결하는 길을 열 수 있을 것이라고 결론지었습니다. 향후 연구는 실현 가능한 UD 임베딩의 한계를 더 자세히 규명하고 실제 양자 하드웨어에서 이러한 발견을 검증하는 것을 제안합니다.