Neural optimization for quantum architectures: graph embedding problems with Distance Encoder Networks

본 논문은 중성 원자 기반 양자 하드웨어의 큐비트 배치에 대한 제약 단위 원판 문제를 효율적으로 해결하기 위해 수정된 거리 인코더 네트워크와 맞춤형 임베딩 손실 함수를 활용한 신경망 강화 최적화 프레임워크를 소개하며, 이는 동등한 계산 시간 내에서 기존 고전 솔버보다 우수한 성능을 발휘합니다.

핵심

파티에서 사람들을 배치하려고 한다고 상상해 보세요. 당신은 특정 규칙집을 가지고 있습니다: 어떤 사람들은 서로 하이파이브를 할 수 있을 만큼 가까이 서 있어야 합니다 (그들은 친구입니다), 반면 다른 사람들은 실수로 부딪히지 않도록 충분히 멀리 떨어져 있어야 합니다 (그들은 낯선 사람들입니다).

이제 이 파티가 매우 작고 원형인 방 안에서 벌어지고 있으며, 모든 사람이 축소할 수 없는 개인적인 "버블"을 가지고 있다고 상상해 보세요. 두 친구의 버블이 겹치면 하이파이브를 할 수 있습니다. 두 낯선 사람의 버블이 닿으면 재앙입니다.

이것은 본질적으로 해당 논문이 다루는 문제이지만, 사람 대신 중성 원자로 만들어진 **양자 비트 (큐비트)**가 등장하고, 파티 방 대신 양자 컴퓨터 칩이 등장합니다.

연구자들이 무엇을 했는지 간단히 설명해 드리겠습니다:

1. 문제: "불가능한" 좌석 배치도

양자 컴퓨팅 (특히 중성 원자를 사용하는 기계) 의 세계에서 과학자들은 복잡한 수학 문제를 해결하기 위해 2 차원 또는 3 차원 공간에 원자들을 배치해야 합니다.

• 목표: 특정 쌍은 상호작용할 수 있을 만큼 가까이, 다른 쌍은 멀리 떨어지도록 원자들을 배치해야 합니다.
• 문제점: 원자들은 엄격한 물리적 한계를 가지고 있습니다. 너무 가까우면 충돌하고, 너무 멀면 상호작용하지 않습니다. 게다가 전체 그룹은 작은 원형 영역 안에 들어 있어야 합니다.
• 어려움: 소수의 원자라도 완벽한 배치를 찾는 것은 엄청난 수학적 두통입니다. 조각들이 계속 모양을 바꾸고 규칙이 극도로 엄격한 퍼즐을 푸는 것과 같습니다. 전통적인 컴퓨터 프로그램 (고전 솔버라고 함) 은 종종 막히거나, 시간이 너무 오래 걸리거나, 퍼즐이 너무 커지면 단순히 포기해 버립니다.

2. 해결책: "스마트 건축가" (신경망)

저자들은 **거리 인코더 네트워크 (DEN)**라는 새로운 도구를 개발했습니다. 이를 계산기가 아니라 시행착오를 통해 배우는 스마트 건축가로 생각하세요.

• 시작점: 건축가에게는 사람들이 잘못된 곳에 서 있는 (너무 가깝거나 너무 먼) 지저분하고 무작위적인 좌석 배치도가 주어집니다. 이것이 "수행 불가능한" 해결책입니다.
• 훈련: 건축가는 규칙 (손실 함수) 을 봅니다. 두 친구가 너무 멀면 건축가는 "페널티"를 받습니다. 두 낯선 사람이 너무 가까우면 그들도 "페널티"를 받습니다.
• 마법: 건축가는 신경망 (인공지능의 일종) 을 사용하여 사람들을 어떻게 밀고 당길지 학습합니다. 단순히 무작위로 움직이는 것이 아니라, 공간적 변환을 학습합니다. 건축가는 이렇게 깨닫습니다. "아, 이 전체 그룹을 약간 왼쪽으로 밀고 늘려보면, 갑자기 모두가 만족하는구나!"
• 결과: 수천 번의 시도 (epoch) 후, 건축가는 모든 규칙을 만족하는 새로운 좌석 배치도를 만들어냅니다.

3. 테스트 방법

연구자들은 다양한 수의 손님 (10 개에서 100 개의 원자까지) 을 가진 200 개의 서로 다른 "파티 시나리오" (그래프 문제) 를 만들었습니다.

• 그들은 **스마트 건축가 (DEN)**가 이를 해결하도록 했습니다.
• 또한 **전통적인 계산기 (Ipopt)**가 이를 해결하도록 했습니다.

결과:

• 속도와 성공: 스마트 건축가는 특히 큰 그룹의 경우 유효한 좌석 배치도를 찾는 데 훨씬 더 뛰어났습니다. 전통적인 계산기는 종종 포기하거나 시간이 너무 오래 걸렸습니다.
• 3 차원 이점: 흥미롭게도 건축가는 2 차원 공간 (평평한 탁자처럼) 보다 3 차원 공간 (입방체처럼) 에서 손님을 배치하는 것이 더 쉬웠습니다. 이는 평평한 바닥보다 천장이 있는 방에서 기동할 공간이 더 많은 것과 같습니다.
• 트레이드오프: 건축가는 어떤 유효한 해결책이든 찾는 데 뛰어나지만, 전통적인 계산기는 때로는 낯선 사람들 사이의 공간을 최대화하는 데 약간 "더 나은" 해결책을 찾기도 했습니다. 그러나 전통적인 계산기가 아무 해결책도 찾지 못하는 경우가 많았기 때문에, 건축가가 단순히 "해결해 내는" 능력이 더 큰 승리였습니다.

4. 왜 이것이 중요한가

이 논문은 아직 질병을 치료하거나 주가를 예측할 수 있는 양자 컴퓨터를 구축했다고 주장하지 않습니다. 대신 매우 구체적이고 기초적인 장애물을 해결합니다: 양자 컴퓨터가 실제로 작동하도록 원자들을 물리적으로 어떻게 배치할 것인가?

신경망을 "스마트 건축가"로 사용하여, 그들은 이전보다 훨씬 효율적으로 이러한 양자 원자들을 배치할 수 있음을 보여주었습니다. 이는 과학자들이 원하는 프로그램을 실제로 실행할 수 있는 더 복잡한 양자 기계를 구축하는 길을 열어줍니다.

간단히 말해: 그들은 인공지능에게 공간 조직의 대가가 되도록 가르쳐, 물리 법칙의 규칙이 극도로 엄격한 세계에서 양자 컴퓨터가 발을 붙일 수 있도록 도왔습니다.

기술 요약

"Distance Encoder Networks 를 이용한 그래프 임베딩 문제를 다루는 양자 아키텍처를 위한 신경 최적화"라는 논문에 대한 상세한 기술적 요약은 다음과 같습니다.

문제 정의

본 논문은 중성 원자 기반 양자 하드웨어에 조합 최적화 문제를 매핑하는 과제를 다룹니다. 구체적으로 제약 단위 원 그래프 (Constrained Unit Disk Graph, CUDG) 문제에 초점을 맞춥니다. 중성 원자 양자 아키텍처에서 큐비트는 2 차원 또는 3 차원 레지스터에 배치된 리드버그 원자로 표현됩니다. 이들의 상호작용은 "블로케이드 효과 (blockade effect)"에 의해 지배되며, 이는 단위 원 그래프 (UDG) 와 동등한 연결 패턴을 생성합니다.

핵심 난제는 임베딩 작업에 있습니다. 즉, $n$개의 큐비트에 대한 공간 좌표를 찾아, 결과적인 물리적 상호작용 (원자 간 거리에 의해 결정됨) 이 원하는 인접 행렬 (연결 패턴) 을 재현하면서도 엄격한 하드웨어 제약을 만족하도록 하는 것입니다:

1. 최소 거리 ($D_{min}$): 트위저 (tweezers) 의 한계로 인해 원자들은 특정 임계값 (예: 4 $\mu$m) 보다 가까이 배치될 수 없습니다.
2. 최대 상호작용 반경 ($D_{adj}$): 상호작용하는 큐비트들은 특정 거리 범위 (예: $\approx$10.26 $\mu$m) 내에 있어야 합니다.
3. 레지스터 크기 ($L$): 모든 원자는 반지름 $L$ (예: 50 $\mu$m) 인 원형 영역 내에 있어야 합니다.
4. 인접 간극 최대화: 솔루션은 비인접 쌍의 최소 거리와 인접 쌍의 상호작용 반경 사이의 차이를 최대화하여 견고성을 보장해야 합니다.

이 문제는 NP-난해 (NP-hard) 이며 비볼록 (non-convex) 합니다. 기존 솔버 (혼합 정수 2 차 제약 프로그래밍 또는 비선형 프로그래밍 등) 는 확장성 측면에서 어려움을 겪으며, 합리적인 시간 내에 더 큰 그래프 인스턴스에 대한 실현 가능한 솔루션을 찾지 못하는 경우가 많습니다.

방법론

저자들은 Distance Encoder Network (DEN) 이라는 맞춤형 아키텍처와 특수한 임베딩 손실 함수 (Embedding Loss Function, ELF) 를 중심으로 한 신경 강화 최적화 프레임워크를 제안합니다.

1. Distance Encoder Network (DEN)

DEN 은 비선형 공간 변환을 학습하도록 설계된 수정된 오토인코더입니다.

• 입력: 전처리 단계를 통해 생성된 그래프 정점의 초기 좌표 ($\vec{p}_i$).
• 아키텍처:
  • 학습 가능한 오토인코더: ReLU 활성화 함수와 드롭아웃을 가진 완전 연결 계층을 통해 입력 좌표를 압축한 후, 새로운 좌표 집합 ($\vec{p}^f_i$) 으로 재구성합니다.
  • 고정 가중치 거리 계산기: 재구성된 좌표를 받아 모든 정점 쌍 간의 유클리드 거리의 제곱 ($||\vec{p}^f_i - \vec{p}^f_j||^2$) 을 계산하는 비학습 구성 요소입니다. 이 계층은 벡터 뺄셈과 제곱을 수행하기 위해 고정 가중치 ($\pm 1, 0$) 를 사용하여 네트워크가 유효한 거리 지표를 출력하도록 보장합니다.
• 전처리 초기화: 초기 좌표를 생성하기 위해 두 가지 방법이 사용됩니다:
  • 스케일링: 무작위 좌표를 도메인 반지름 $L$에 맞게 스케일링합니다.
  • Fruchterman-Reingold: 그래프의 인접 행렬을 기반으로 인력/척력력을 사용하는 힘 기반 레이아웃 알고리즘입니다.

2. 임베딩 손실 함수 (ELF)

정적 데이터셋에 대한 표준 역전파를 사용하는 대신, 네트워크는 CUDG 제약을 직접 인코딩하는 맞춤형 손실 함수를 최소화하도록 훈련됩니다. ELF 는 마진 순위 손실 (Margin Ranking Loss) 에 기반하여 두 가지 구성 요소를 결합합니다:

• $ELF_{min}$: 하한을 강제합니다. 인접 정점이 너무 멀리 있거나 비인접 정점이 너무 가까운 경우 (비상호작용 쌍의 최소 분리 위반) 를 패널티로 부과합니다.
• $ELF_{max}$: 상한을 강제합니다. 인접 정점이 상호작용 반경을 초과하거나 비인접 정점이 너무 가까운 경우를 패널티로 부과합니다.
• 목적: 총 손실은 네트워크가 거리 제약을 만족하는 좌표 (실현 가능성) 를 찾도록 유도하면서, 암묵적으로 "인접 간극 (feasible 과 infeasible 거리 사이의 마진)"을 최대화합니다.

3. 훈련 전략

이 프레임워크는 각 그래프 인스턴스를 독립적인 훈련 작업으로 취급합니다. 네트워크는 AdamW 옵티마이저를 사용하여 고정된 에포크 수 (예: 3000) 동안 훈련됩니다. 이 과정은 최적의 실현 가능한 임베딩을 찾기 위해 반복되며, 더 나은 실현 가능한 솔루션이 발견될 때마다 목표 "인접 간극" 매개변수 ($\alpha$) 를 업데이트합니다.

주요 기여

1. 새로운 프레임워크: 중성 원자 양자 아키텍처의 CUDG 문제에 특화된 신경 강화 최적화 접근법의 도입.
2. Distance Encoder Network (DEN): 고정 가중치 거리 계산기를 통합하여 직접 유클리드 거리의 제곱을 출력하는 특수한 오토인코더 아키텍처로, 제약 조건을 기하학적 속성에 직접 적용할 수 있게 합니다.
3. 임베딩 손실 함수 (ELF): 거리에 대한 불평형과 같은 하드 기하학적 제약을 미분 가능한 최적화 목표로 변환하는 맞춤형 손실 공식으로, 네트워크가 실현 가능한 공간 구성을 학습할 수 있게 합니다.
4. 비볼록성 처리: 기존 솔버가 종종 실패하는 CUDG 문제의 비볼록 솔루션 공간에서 신경망의 근사 능력을 활용하는 접근법.

실험 결과

저자들은 200 개의 그래프 인스턴스 ($n=10$부터 $n=100$ 정점까지) 데이터셋에 대해 기존 Ipopt 솔버와 비교하여 프레임워크를 평가했습니다.

• 실현 가능성: DEN 기반 프레임워크는 실현 가능한 임베딩을 찾는 데 있어 Ipopt 를 크게 능가했습니다. Ipopt 는 많은 인스턴스 (특히 $n$이 증가함에 따라) 에서 솔루션을 찾지 못했지만, DEN 모델은 데이터셋의 훨씬 더 큰 비율에서 실현 가능한 임베딩을 성공적으로 찾았으며, 3 차원 공간에서 최대 100 개의 정점을 가진 인스턴스도 포함했습니다.
• 차원성: 모델은 2 차원 ($N=2$) 보다 3 차원 ($N=3$) 에서 실현 가능한 솔루션을 더 쉽게 찾았는데, 이는 아마도 증가된 자유도 때문일 것입니다.
• 계산 시간: DEN 모델의 훈련 시간은 정점 수에 따라 선형적으로 확장되었습니다. Ipopt 에게 DEN 훈련 시간보다 훨씬 많은 시간 (10 배) 을 부여하더라도, DEN 이 빠르게 해결한 인스턴스를 여전히 해결하지 못했습니다.
• 인접 간극: DEN 모델은 실현 가능한 솔루션을 찾는 데 뛰어났지만, 기존 솔버 (성공한 경우) 는 때때로 더 큰 인접 간극을 가진 임베딩을 생성했습니다. 저자들은 간극 최적화가 신경 접근 방식에 여전히 과제라고 지적합니다.

의의 및 주장

본 논문은 제안된 프레임워크가 비볼록성과 확장성 문제로 인해 기존 방법들이 어려움을 겪는 양자 하드웨어의 임베딩 문제에 대해 기존 솔버에 대한 실현 가능한 대안을 제공한다고 주장합니다.

• 실용적 영향: 복잡한 QUBO 문제를 중성 원자 아키텍처에 매핑할 수 있게 하여, 이러한 양자 머신을 활용하는 데 필수적인 단계를 가능하게 합니다.
• 일반화 가능성: 저자들은 DEN 아키텍처와 ELF 전략이 유클리드 거리 제약 및 부등식 모델링을 포함하는 다른 최적화 문제에 일반화될 수 있다고 제안합니다.
• 향후 작업: 논문은 인접 간극 최대화와 하이퍼파라미터 튜닝 필요성과 관련된 한계를 겸손하게 인정합니다. 향후 작업으로는 미니배칭을 통한 GPU 활용도 개선 및 인접 간극 매개변수 최적화 정비를 제안합니다.

저자들은 현재 접근 방식이 최적의 인접 간극을 보장하지는 않지만, 기존 방법으로는 이전보다 더 넓은 범위의 그래프 인스턴스에 대해 실현 가능한 솔루션을 찾을 수 있다는 점이 주요 기여라고 강조합니다.