⚛️ quantum physics

Motzkin-Straus Optimization on an Entropy-Computing Platform

이 논문은 모츠킨-스트라우스(Motzkin-Straus) 정리를 활용하여 QCi의 Dirac-3S 광자 엔트로피 컴퓨터 상에서 조합 최적화 문제를 해결하는 프레임워크를 소개하며, 이 아날로그 플랫폼이 대부분의 벤치마크 인스턴스에서 클래식 솔버와 대등하거나 이를 능가함을 입증하는 동시에 엔트로피 컴퓨팅이 비볼록(non-convex) 지형을 탐색하는 데 있어 경쟁력 있는 접근 방식임을 확립한다.

원저자: PoJen Wang, Sutapa Samanta, Yuntai Song, Mohammad-Ali Miri

게시일 2026-10-01

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: PoJen Wang, Sutapa Samanta, Yuntai Song, Mohammad-Ali Miri

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 컴퓨팅의 광활한 풍경 속에서, 어떤 문제들은 너무나 복잡하여 속도와 메모리의 한계를 거부하는 것처럼 보입니다. 이러한 문제들은 조합 최적화 문제(combinatorial optimization problems)로 알려져 있는데, 이는 엄청난 수의 가능성 중에서 단 하나의 최적의 배열을 찾는 것을 목표로 하는 도전 과제들의 부류입니다. 당신이 아주 많은 손님들 중 서로를 모두 알고 있는 그룹을 선택해야 하는 대규모 파티를 기획한다고 상상해 보십시오. 초대 명단이 늘어남에 따라 그 그룹을 형성하는 방법의 수는 폭발적으로 증가하며, 이로 인해 전통적인 컴퓨터가 모든 옵션을 일일이 확인하는 것은 거의 불가능해집니다. "최대 클리크(maximum clique)"를 찾는 것으로 알려진 이 특정 퍼즐은 단순한 수학적 호기심이 아닙니다. 이는 항공편 일정 관리, 자원 할당, 사회적 네트워크 분석과 같은 현실 세계의 작업들을 뒷받침합니다. 수십 년 동안 과학자들은 이러한 문제들을 효율적으로 해결하기 위해 고군분투해 왔으며, 종종 완벽한 답 대신 '충분히 좋은' 답에 만족해야만 했습니다.

최근 한 연구팀은 다른 종류의 기계에 의지함으로써 이러한 퍼즐을 해결하는 새로운 방법을 탐구했습니다. 일상적인 컴퓨터에서 발견되는 표준 논리 게이트에 의존하는 대신, 그들은 엔트로피 컴퓨터(entropy computer)라고 불리는 장치를 활용했습니다. 이 기계는 직관에 어긋나 보이는 원리로 작동합니다. 즉, 빛의 자연스럽고 무작위적인 변동, 구체적으로 광자(photons), 즉 빛의 입자들이 흐름 속에서 도착하는 방식을 사용하여 막다른 길에서 탈출하도록 돕습니다. 최적화의 세계에서 "지역 최솟값(local minimum)"에 갇히는 것은 산맥에서 작은 골짜기를 발견하고 그것이 세상의 바닥이라고 생각했지만, 바로 다음 능선 너머에 훨씬 더 깊은 골짜기가 있는 것과 같습니다. 전통적인 컴퓨터는 종-종 이러한 작은 골짜기들에 갇히곤 합니다. 그러나 엔트로피 컴퓨터는 양자 세계의 내재된 노이즈를 사용하여 시스템을 살짝 밀어줌으로써, 시스템이 능선을 넘어 더 자유롭게 지형을 탐색하고 진정한 최저점을 찾을 수 있도록 돕습니다.

디락-3S(Dirac-3S)라는 장치를 활용한 연구진은 이 접근 방식이 현재 표준 컴퓨터에서 사용 가능한 최선의 방법들보다 최대 클리크 문제를 더 잘 해결할 수 있는지 확인하고자 했습니다. 그들은 이 문제를 기계가 자연스럽게 이해하지 못하는 형식으로 강제로 맞추려 하지 않았습니다. 대신, 그들은 연결된 그룹을 세는 이산적인 문제를 매끄럽고 연속적인 모양으로 변환하는 1960년대의 수학적 통찰력을 사용했습니다. 이 변환은 매우 중요했는데, 왜냐하면 디락-3S는 매끄러운 모양과 제약 조건을 자연스럽게 처리하도록 설계되었기 때문입니다. 이 기계는 시간 슬롯별로 광자의 수를 세며, 광자의 개수는 음수가 될 수 없으므로 장치는 모든 값이 양수여야 한다는 규칙을 자동으로 준수합니다. 또한, 총 광자 수는 기계의 설계에 의해 고정되어 있어, 값들이 반드시 특정 합계와 일러야 한다는 요구 사항을 자동으로 충족합니다. 이는 연구진이 복잡한 우회책이나 속도를 늦추는 추가 단계 없이 문제를 하드웨어에 직접 매핑할 수 있었음을 의미합니다.

시스템을 테스트하기 위해 연구팀은 75개의 까다로운 그래프 문제 세트에 대해 디락-3S를 두 개의 매우 정교한 고전 컴퓨터 프로그램과 대조 실험했습니다. 이 문제들은 28개의 노드를 가진 작은 네트워크부터 4,000개의 노드를 가진 거대한 구조까지 다양했습니다. 결과는 놀라웠습니다. 테스트 케이스의 5분의 4 이상에서 엔트로피 컴퓨터는 고전적 프로그램의 성능과 일치하거나 이를 능가했습니다. 가장 크고 복잡한 사례 중 다수에서 디락-3S는 두 고전적 경쟁자보다 더 나은 해답을 찾아냈으며, 종종 수년간의 선행 연구를 통해 확립된 최선의 답변에 도달하기도 했습니다. 이 기계는 문제의 거칠고 울퉁불퉁한 지형을 항해하는 데 특히 능숙해 보였으며, 고전적 방법들이 여러 유망하지 않은 영역에 시도를 분산시키는 것과 달리 최적의 해답 근처에 탐색 노력을 훨씬 더 효과적으로 집중시켰습니다.

하지만 이 이야기가 완전한 승리를 의미하는 것은 아닙니다. 연구진은 해답이 소음 속에 숨겨져 있는 "플랜티드 클리크(planted clique)" 사례와 같이 특정 유형의 어려운 문제에서는 고전 컴퓨터 프로그램이 여전히 우위를 점한다는 것을 발견했습니다. 다양한 시작 지점에서 검색을 여러 번 재시작하는 전략을 사용하는 이 프로그램들은 이러한 특정 사례에서 숨겨진 해답을 찾는 데 더 뛰어났습니다. 이는 엔트로피 컴퓨터가 복잡한 지형을 탐색하는 강력한 새로운 방법을 제공하지만, 아직 모든 사례를 완벽하게 해결하는 마법의 탄환은 아님을 시사합니다. 연구진은 성능 차이가 종종 작았으며, 때로는 그룹 내의 단 하나의 노드 차이에 불과했다는 점에 주목했습니다. 그러나 엔트로피 컴퓨터가 매우 다양한 문제에 대해 최고의 고전 알고리즘들과 이토록 밀접하게 경쟁할 수 있다는 사실은 중요한 진전입니다.

이 연구는 컴퓨팅의 미래를 향한 유망한 경로를 강조합니다. 빛의 자연스러운 행동을 사용하여 전통적인 기계에게는 매우 어려운 문제를 해결함으로써, 엔트로피 컴퓨터는 비전통적인 하드웨어가 진지한 경쟁자가 될 수 있음을 보여줍니다. 연구진은 미래의 가장 강력한 접근 방식이 고전적 방법과 양자적 방법 중 하나를 선택하는 것이 아니라, 이 둘을 결합하는 것이 될 것이라고 제안합니다. 그들은 엔트로피 컴퓨터가 유망한 영역을 빠르게 스캔하고, 그 후 고전 컴퓨터가 정확한 정점을 찾아 답을 정교화하는 하이브리드 시스템을 구상하고 있습니다. 이 연구는 엔트로피 컴퓨팅이 현실 세계의 최적화 문제의 까다로운 비볼록(non-convex) 지형을 탐색하는 데 있어 실행 가능하고 경쟁력 있는 접근 방식임을 입증하며, 우리 시대의 가장 어려운 퍼즐들을 풀어내야 하는 과학자와 엔지니어들에게 새로운 도구를 제공합니다.

기술 요약: 엔트로피 컴퓨팅 플랫폼 상의 모츠킨-스트라우스 최적화

문제 정의
본 논문은 조합 최적화 문제, 특히 NP-난해(NP-hard) 문제인 최대 독립 집합(Maximum Independent Set, MIS) 및 최대 클리클(Maximum Clique) 문제를 해결하는 과제를 다룹니다. 전통적인 정확한 방법론(exact methods)은 문제의 규모가 커짐에 따라 계산 비용이 기하급급수적으로 증가하며, 휴리스틱 방법론은 종종 최적성 보장을 희생합니다. 최대 클리클 문제는 비볼록(non-convex) 최적화 지형으로 인해 특히 어려운데, 이 지형은 결정론적 경사 하강 알고리즘을 가두는 수많은 가짜 지역 최적점(spcial local optima)으로 가득 차 있습니다. 모츠킨-스트라우스(Motzkin-Straus) 정리는 이산적인 최대 클리클 문제를 확률 심플렉스(probability simplex) 상의 연속적인 이차 계획법으로 매핑하는 수학적 가교를 제공하지만, 이 연속적 정식화를 푸는 것은 복잡한 지형과 특화된 솔버 또는 과도한 파라미터 튜닝의 필요성 때문에 여전히 도전적인 과제로 남아 있습니다.

방법론
저자들은 최대 클리클 문제의 연속적인 이차 정식화를 해결하기 위해 광자 엔트로피 컴퓨터인 Quantum Computing Inc.(QCI)의 Dirac-3S를 활용하는 프레임워크를 제안합니다.

이론적 토대: 모츠킨-스트라우스 정리는 그래프 $G$ 에서의 최대 클리클 크기 $\omega(G)$ 가 표준 확률 심플렉스 $\Delta_n$ 상의 이차 형식 $\frac{1}{2}x^T Ax$ 의 최댓값과 직접적으로 연관되어 있음을 명시합니다. 저자들은 이를 통해 이산적인 클리클 문제를 다음과 같은 연속적 최적화 문제로 변환합니다: $\max \frac{1}{2}x^T Ax$ (단, $\sum x_i = 1$ 및 $x_i \ge 0$ ).
하드웨어 구현 (Dirac-3S): Dirac-3S 플랫폼은 다른 양자 접근 방식(예: 페널티 항을 요구하는 이징 모델)에서 나타나는 인코딩 오버헤드 없이 이 최적화를 네이티브하게 구현합니다.
- 이차 목적 함수: 이차 항은 광자 하드웨어의 2-바디 상호작용(two-body interaction) 항으로 직접 매핑됩니다.
- 심플렉스 제약 조건: 하드웨어는 피드백 루프 내의 광자 보존을 통해 합 제약 조건( $\sum v_i = R$ )을 강제함으로써 심플렉스 요구 사항을 자연스럽게 충족합니다.
- 비음성(Non-negativity): 광자 계수는 본질적으로 비음수이므로, 슬랙 변수(slack variables) 없이 $x_i \ge 0$ 제약 조건을 만족합니다.
작동 메커니즘: 시스템은 제어된 소산(dissipation) 및 측정-피드백 루프로 조건화된 양자 저장소(quantum reservoir)를 사용하여 비용 함수를 최소화합니다. 결정적으로, 시스템은 양자 샷 노이즈(광자 계수의 포아송 통계)를 계산 자원으로 활용합니다. 이 노이즈는 솔루션 공간의 확률적 탐색을 유도하며, 이는 물리적 양자 요동으로부터 발생하는 시뮬레이티드 어닐링(simulated annealing)의 온도와 기능적으로 유사한 방식으로 지역 최솟값(local minima)을 탈출하게 합니다.
솔루션 추출: 연속적인 솔루션은 정수가 아닌 클리클 수 추정치를 제공하므로, 저자들은 가장 가까운 정수로 반올림하거나, 솔루션 벡터의 서포트(support)를 식별한 후 그리디(greedy) 클리클 구축 또는 열거를 수행하는 등의 추출 방법을 사용합니다.

주요 기여

프레임워크 설계: 엔트로피 컴퓨팅 플랫폼 상에 모츠킨-스트라우스 오라클을 구현함으로써, 최대 클리클 문제의 수학적 구조를 직접적인 물리적 실체로 구축하였습니다.
벤치마킹: 두 가지 독립적으로 구현된 클래식 베이스라인인 Armijo-PGD(Armijo 백트래킹 및 멀티 리스타트를 포함한 투영 경사 하강법) 및 Hexaly(상용 범용 수학 프로그래밍 솔버)와 엄격한 비교 성능 분석을 수행하였습니다.
경험적 검증: 다양한 구조적 패밀리(Brock, C-fat, Hamming, Johnson, planted-clique 인스턴스 등)를 포함하는 75개의 표준 DIMACS 벤치마크 그래프에 대해 광범위한 테스트를 실시하였습니다.

결과
연구는 28개에서 4,000개의 정점을 가진 75개의 그래프 인스턴스에 대해 Dirac-3S 플랫폼을 클래식 솔버들과 평가하였습니다.

전반적인 성능: Dirac-3S는 75개 인스턴스 중 62개 인스턴스(5분의 4 이상)에서 두 클래식 솔버의 성능을 대등하게 유지하거나 능가하였습니다.
대규모 인스턴스: 1,000개 이상의 정점을 가진 14개의 가장 큰 그래프들에 대해, Dirac-3S는 13개 인스턴스에서 다른 솔버들과 대등하거나 높은 수준을 보였습니다. 특히 몇몇 대규모 구조적 그래프(예: $C_{1000.9}$ , $C_{2000.9}$ , $keller6$)에서는 독보적인 선두를 기록했습니다.
구조적 vs. 난해한 인스턴스:
- 구조적 패밀리(Hamming, Johnson, $c$ -fat, $p\_hat$ )의 경우, 모든 솔버가 높은 근사 비율(95–99%)을 달성했습니다.
- 연속 최적화에 어렵기로 알려진 planted-clique 패밀리(gen 및 san 인스턴스)의 경우, 잘 튜닝된 클래식 솔버인 Armijo-PGD가 멀티 리스타트 전략을 통해 지형을 효과적으로 탐색함으로써 명확한 우위(평균 비율 86.5% vs. Dirac-3S의 71.0%)를 점했습니다.
- Brock 시리즈 그래프의 경우 모든 솔버가 고전하는 모습을 보였는데, 이는 하드웨어 특유의 결함이라기보다 해당 구조에 대한 모츠킨-스트라우스 지형 자체의 난이도 때문임을 시사합니다.
솔루션 분포: 에너지 히스토그램 분석(예: $C_{125.9}$ 및 $C_{250.9}$ 상에서) 결과, Dirac-3S의 솔루션은 Armijo-PGD 리스타트의 넓은 분포와 비교하여 이론적 최적값 근처에 더 날카롭게 집중되어 나타났습니다. 이는 엔트로피 컴퓨팅 역학에 의한 효과적인 지형 탐색을 나타냅니다.

의의 및 주장
본 논문은 이 연구가 네이티브 아날로그, 비전통적 컴퓨팅 플랫폼을 사용하여 조합 최적화 문제를 해결하는 실행 가능한 경로를 확립하는 기초적인 실험임을 강조합니다.

경쟁적 패러다임: 엔트로피 컴퓨팅이 비볼록 지형을 탐색하는 데 있어 경쟁력 있는 접근 방식이며, 게이트 기반 양자 알고리즘이나 클래식 휴리스틱에 대한 뚜ack적인 대안을 제공함을 입증합니다.
하드웨어 네이티브의 이점: 밀집 그래프(dense graphs)에 대해 양자 어닐링(예: D-Wave)과 비교했을 때의 중요한 실질적 이점을 강조합니다. 심플렉스 제약 조건과 비음성 조건이 하드웨어 수준에서 충족되므로, 미세한 임베딩으로 인한 솔루션 품질 저하를 방지할 수 있습니다.
겸허한 주장: 저자들은 planted-clique 인스턴스에서의 현재 성능 격차가 근본적인 장벽이라기보다는 알고리즘 설계의 문제임을 인정합니다. 저자들은 모든 경우에 대해 "양자 우위"를 확언하는 것이 아니라, 엔트로피 컴퓨팅의 물리적 역학이 경사 하강법 기반 방식에 보완적인 강점을 제공한다고 제안합니다.
향후 전망: 본 논문은 이 패러다임의 진정한 잠재력이 하이브리드 양자-클래식 알고리즘에 있다고 보고 있습니다. 여기서 엔트로피 컴퓨터는 유망한 탐색 영역을 식별하는 오라클 역할을 수행하고, 이후 클래식 솔버가 이를 정교화하는 방식입니다. 이는 엔로피 컴퓨팅을 미래의 결함 허용(fault-tolerant) 양자 시스템을 보완하는 근시적이고 반복적인 벤치마킹 도구로 위치시킵니다.

유사한 논문