Convolutional Formulation of Large-Scale Quadratic Unconstrained Binary Optimization with Dense Interactions

기술 요약: 조밀한 상호작용을 갖는 대규모 이차 무제약 이진 최적화의 컨볼루션 정식화

문제 정의
대규모 조합 최적화 문제, 특히 이차 무제약 이진 최적화(QUBO) 또는 이징(Ising) 문제로 정식화된 문제들은 하드웨어 솔버로 구현할 때 상당한 확장성 문제를 직면합니다. 공간 광학적 이징 머신(SPIM)은 광학적 공간 병렬성을 통해 조밀한 상호작용에 대해 우수한 확장성을 제공하지만, 그 원시적인 구현은 랭크-1(rank-one) 결합 행렬을 표현하는 데 국한되어 있습니다. 더 높은 랭크의 상호작용을 처리하기 위해 다중화(multiplexed) 버전이 제안되기도 했으나, 이는 구현 효율성을 저하시키는 다중화 비용을 발생시킵니다. 또한, 일반적인 QUBO를 SPIM에 매핑하는 기존 방식들은 실제 세계 문제들의 고유한 공간적 구조를 활용하지 못해, 광학 하드웨어의 공간적 부피를 비효율적으로 사용하는 경우가 많습니다. 핵심 과제는 다중화되지 않은 SPIM의 본질적인 표현 능력을 명확히 하고, 구현 효율성을 희생하지 않으면서 조밀하고 구조화된 상호작용을 효율적으로 구현할 수 있는 정식화를 식별하는 것입니다.

방법론
저자들은 변수들이 $D$-차원 정수 격자에 격자점과 연관되어 있고, 상호작용이 공간적 컨볼루션 구조에 의해 정의되는 이징 문제의 정식화인 **공간적 QUBO (spQUBO)**를 도입합니다. 이 프레임워크에서 두 변수 사이의 결합 가중치는 임의의 인덱스가 아닌, 상대적인 공간 위치에 따라 결정됩니다.

주요 방법론적 구성 요소는 다음과 같습니다:

1. spQUBO 정의: 문제는 공간 결합 함수 $f(\mathbf{d}_i - \mathbf{d}_j)$에 의해 정의되며, 여기서 $\mathbf{d}_i$는 $i$번째 변수의 격자 위치를 나타냅니다. 이 구조는 거리 기반 상호작용을 자연스럽게 포착합니다.
2. SPIM과의 등가성: 저자들은 이상적인 SPIM의 해밀토니안이 정확히 2차원 주기적 spQUBO에 대응함을 입증합니다. SPIM의 결합 계수는 광학 설정에 사용되는 참조 이미지의 이산 푸리에 변환(DFT)에 의해 결정됩니다.
3. 축소 알고리즘(Reduction Algorithm): 핵심적인 기여는 임의의 $D$-차원 spQUBO(주기적이든 아니든)를 등가적인 2차원 주기적 spQUBO로 변환하는 축소 알고리즘입니다. 이는 다음 과정을 통해 수행됩니다:
   • 주기성 충돌(서로 다른 상대적 위치가 동일한 주기적 인덱스로 매핑되는 경우)을 해결하기 위해 구성 영역을 "패딩(padding)"으로 확장합니다.
   • 컨볼루션 구조를 보존하는 특정 전단사 함수(bijection)를 사용하여 고차원 격자 좌표를 2D 격자로 매핑합니다.
   • 결과적인 공간 부피는 원래 차원의 곱과 상호작용 함수의 국부성(locality)의 곱으로 결정됩니다.
4. 계산 효율성: 논문은 spQUBO의 컨볼루션 구조가 고속 푸리에 변환(FFT)을 사용하여 해밀토니안 및 행렬-벡터 곱을 효율적으로 계산할 수 있음을 입증하며, 이를 통해 계산 복잡도를 $O(N^2)$에서 $O(V \log V)$로 줄입니다 (여기서 $V$는 공간 부피).

주요 기여

• spQUBO의 정식화: 본 논문은 SPIM의 물리적 능력과 명시적으로 연결되는, 공간적 컨볼루션 구조를 특징으로 하는 새로운 QUBO 클래스를 정의합니다.
• 이론적 축소: 모든 spQUBO가 컨볼루션 구조를 보존하면서 2D 주기적 spQUBO로 축소될 수 있음을 증명함으로써, 다중화 없이 단일 샷(single-shot) SPIM에 구현할 수 있게 합니다.
• 확장성 분석: 저자들은 spQUBO를 공간 다중화 및 스핀-쌍 매핑(spin-pair mapping)과 비교하는 확장성 분석을 제공합니다. 공간적 구조와 조밀한 상호작용을 가진 문제의 경우, spQUBO 접근 방식이 제너릭 매핑 방식에 비해 훨씬 작은 공간 부피(SLM 크기)를 요구함을 보여줍니다. 이는 상호작용의 국부성이 증가함에 따라 더욱 두드러집니다.
• 수치적 검증: 연구는 배치 문제(거리 기반 페널티를 고려한 효용 극대화)와 클러스터링 문제(클러스터 내 거리 최소화)의 수치적 예제를 통해 프레임워크의 적용 가능성을 입증합니다. 이러한 문제들은 성공적으로 2D spQUBO로 매핑되어 모멘텀 어닐링(momentum annealing)을 통해 해결되었습니다.

결과

• 구현 가능성: 축소 알고리즘은 복잡한 고차원 문제(예: 3D 클러스터링)를 SPIM 하드웨어에 적합한 2D 주기적 형태로 성공적으로 변환합니다.
• 성능 비교: 수치 실험에서 제안된 spQUBO 접근 방식은 클러스터링 인스턴스에 대해 약 $1.4 \times 10^5$의 공간 부피를 필요로 했던 반면, 공간 다중화는 $2.4 \times 10^7$, 스핀-쌍 매핑은 약 $1.2 \times 10^7$을 필요로 했습니다.
• 계산 속도: 해밀토니안 계산 시간에 대한 수치적 비교 결과, spQUBO의 FFT 기반 방식이 직접적인 행렬-벡터 곱보다 문제 크기($N$)에 따라 훨씬 더 나은 확장성을 보임을 확인하여 이론적 효율성 이득을 입증했습니다.
• 해의 품질: 배치 및 클러스터링 문제에 대해 얻은 근사해는 시설이 효용 손실을 피하기 위해 간격을 유지하거나, 데이터 포인트가 뚜렷한 클러스터로 그룹화되는 것과 같은 기대되는 동작을 보여주었습니다.

의의 및 주장
본 논문은 SPIM이 효율성과 확장성 측면에서 독특한 이점을 갖는 특정 클래스의 최적화 문제를 이해하는 데 진전이 있다고 주장합니다. SPIM의 본질적인 힘이 조밀한 상호작용과 컨볼루션 구조를 처리하는 데 있다는 점을 명확히 함으로써, 본 연구는 다중화의 오버헤드 없이 랭크-1 행렬의 한계를 넘어섭니다.

저자들은 spQUBO 정식화가 시설 배치, 클러스터링, 이미지 복원과 같이 공간적 또는 거리 기반 특성을 가진 실질적이고 현실적인 문제들에 대한 SPIM의 적용 가능성을 높이는 기초적인 단계라고 주장합니다. 또한, 본 연구가 공간 부피 제약을 분리하기 위해 이상적인 SPIM에 초점을 맞추었지만, 이 프레임워크는 조밀한 고차원 문제를 광학 하드웨어에 구현하는 체계적인 방법을 제공한다고 강조합니다. 나아가 spQUBO의 효율성은 광학 하드웨어에 국한되지 않고, 컨볼루션 구조가 FFT를 통한 디지털 컴퓨터에서의 효율적인 계산을 가능하게 한다는 점에서 하드웨어와 소프트웨어 솔버 모두에 폭넓은 유용성을 시사합니다. 결론적으로, 본 연구는 향후 연구가 spQUBO와 다중화 기술의 통합, 그리고 조밀한 상호작용 모델의 감소된 자유도를 활용하기 위한 통계적 머신러닝의 적용을 탐구해야 한다고 밝히고 있습니다.