s41928-023-01021-y_240419_152231_240419_155522.pdf
Received: 19 December 2022 Accepted: 27 July 2023 Published online: 31 August 2023
Hao Lo, William Moy , Hanzhao Yu, Sachin Sapatnekar & Chris H. Kim
양자에서 영감을 얻은 컴퓨팅 시스템을 사용하여 조합 최적화 문제를 효율적으로 해결할 수 있습니다.
이러한 시스템을 개발할 때 핵심 과제는 임의의 문제 그래프를 하드웨어에 직접 매핑할 수 있는 전체 노드 연결을 갖춘 대규모 하드웨어 토폴로지를 생성하는 것입니다.
여기에서는 표준 1.2V, 65nm 상보형 금속-산화물-반도체 기술로 제작된 물리학 기반 Ising 솔버 칩에 대해 작성했습니다.
이 칩은 48개의 스핀을 갖춘 all-to-all 아키텍처와 -14에서 +14까지의 정수 가중치를 갖는 매우 균일한 결합 회로를 특징으로 합니다. all-to-all 아키텍처는 수평 진동자(oscillator)와 수직 진동자(oscillator)를 강력하게 결합하여 각 수평-수직 진동자 쌍이 교차스타일(corssbar-style) 배열의 다른 모든 쌍과 교차하고 최대 48개의 노드가 있는 그래프를 직접 매핑할 수 있도록 합니다. 하드웨어. 우리는 Ising 솔버 칩을 사용하여 다양한 문제 크기, 그래프 밀도, 작동 온도 및 문제 인스턴스에 대한 통계 측정을 수행합니다.
Ising 솔버는 제약 없는 2차 이진법에 대한 솔루션을 찾을 수 있습니다. 최적화(QUBO) 문제1 진동자 의해 여기로 전송됨) 바닥 상태로 이완됩니다. 관찰 가능한 자연스러운 상호 작용에서 영감을 받은 Ising 솔버는 복잡한 알고리즘이 사용되는 시뮬레이션 어닐링과 같은 소프트웨어 접근 방식과 다릅니다. 회전 상태를 교란시키고 목적 함수의 변화를 추적하는 데 사용됩니다. 물리 기반 Ising 솔버는 바닥 상태로 완화되는 자연의 능력을 활용하여 복잡한 알고리즘 없이도 QUBO 문제에 대한 경쟁력 있는 솔루션을 찾을 수 있으며, 이로 인해 훨씬 더 나은 time-to-solution 및 energy-to-solution 결과를 얻을 수 있습니다.
Ising 솔버의 단순화된 계산 흐름은 [그림 1]에 나와 있습니다.
첫째, 대규모 조합 최적화 문제는 스핀 상태를 나타내는 꼭지점과 결합 가중치를 나타내는 모서리를 갖는 무방향 그래픽 표현을 사용하여 공식화됩니다. 스핀 si(si = ±1)의 상태는 Ising Hamiltonian 함수에 의해 제공되는 최소화할 목적 함수를 결정합니다.
$$ H = - \sum_{i,j} J_{ij} s_i s_j - \sum_i h_i s_i
$$
결합 강도 $J_{ij}$는 스핀 $i$와 $j$ 쌍 사이의 친화력을 모델링하는 반면, $h_i$는 스핀 $i$에 작용하는 로컬 필드 매개변수를 나타냅니다. 직관적으로 두 개의 스핀이 양의 결합 가중치 $J_{ij}$와 결합되면 에너지가 최소화되므로 해당 상태가 동일한 위상으로 해결되는 경향이 있습니다. 마찬가지로, 음으로 결합된 스핀은 자연스럽게 반대 위상으로 수렴하여 에너지를 최소화합니다. 일반화된 시나리오에서 스핀은 다양한 극성과 결합 강도를 갖는 여러 결합 스핀에 의해 작용할 수 있으며, 집합적으로 스핀은 $H(s)$를 최소화하는 최적의 균형을 찾습니다.
공식화된 조합 최적화 문제는 일반적으로 원래의 QUBO 문제를 여러 하위 QUBO 문제로 분해한 후 하드웨어에 의해 반복적으로 해결되는 소프트웨어 알고리즘이 필요한 단일 하드웨어 인스턴스에 적합하지 않습니다(이 인스턴스는 [그림 1a]에서 생략됨). 예를 들어 실제 문제는 수천 개 이상의 스핀으로 구성될 수 있지만 단일 Ising 솔버의 스핀 수는 하드웨어 기술의 물리적 한계로 인해 100개 미만으로 제한될 수 있습니다. 문제 스핀 수가 솔버 스핀 보다 클 때 양자 어닐러를 사용하여 얼마나 큰 QUBO 문제를 해결할 수 있는지 보여줍니다.