Exact Spin Elimination for Quadratic and k-Local Ising Optimization

과학과 공학의 많은 난제들은 수많은 가능성 중에서 단 하나의 최적의 배열을 찾는 문제로 귀결됩니다. 누가 누구와 잘 지내는지에 대한 복잡한 규칙이 주어졌을 때, 방 안에 있는 사람들을 모두가 최대한 행복하도록 배치하는 상황을 상상해 보십시오. 컴퓨uring의 세계에서 이러한 문제들은 종종 두 가지 상태 중 하나를 선택하는 것을 나타내는, 뒤집을 수 있는 아주 작은 스위치들로 모델링됩니다. 목표는 스위치들을 딱 알맞은 방식으로 조절하여 가장 낮은 에너지 상태, 즉 완벽한 해답에 도출하는 것입니다. 그러나 이 문제들을 해결하기 위해 만들어진 기계들은 한 번에 보유할 수 있는 스위치의 개수에 엄격한 제한이 있습니다. 문제가 너무 크거나, 세 개 이상의 스위치가 동시에 상호작용하는 규칙이 포함된 경우, 기계는 전체 퍼즐을 자신의 메모리에 담아낼 수 없습니다.

이러한 큰 문제를 맞추기 위해 연구자들은 전통적으로 '이차식화(quadratization)'라고 불리는 기술을 사용해 왔습니다. 이 방법은 여러 개의 스위치가 관여하는 복잡한 규칙을 오직 두 개의 스위치만을 다루는 더 단순한 규칙으로 분해합니다. 문제는 이 과정에서 컴퓨터가 보조 역할을 할 추가적인 가상의 스위치들을 만들어내야 한다는 점입니다. 이 방식은 규칙을 단순하게 만들기는 하지만, 새로운 변수들로 인해 기계의 제한된 메모리를 채워버려 실제 문제를 풀 수 있는 공간을 남기지 않는 경우가 많습니다. 이는 트레이드오프 관계에 있습니다. 즉, 규칙은 단순해지지만, 실제로 해결할 수 있는 문제는 줄어드는 것입니다. 케임브리지 대학교의 나탈리아 G. 벨로프(Natalia G. Berloff)가 진행한 새로운 연구는 이와 다른 접근 방식을 제안합니다. 이 연구는 규칙을 단순화하기 위해 가상의 스피치를 추가하는 대신, 실제 스위치를 아예 제거하는 방법을 제안합니다. 연구진은 스위치를 제거했을 때 발생하는 현상을 정밀하게 계산함으로써, 추가적인 메모리 없이도 문제의 크기를 줄일 수 있었고, 이를 통해 이전보다 훨씬 더 큰 퍼즐을 다룰 수 있게 되었습니다.

이 새로운 방법의 핵심은 '월시 제거(Walsh elimination)'라고 불리는 과정입니다. 표준적인 컴퓨터 시뮬레이션에서는 스위치를 제거하고 싶을 때 보통 그 값을 추측하거나 무시해야 하는데, 이는 정답을 놓칠 위험이 있습니다. 이 새로운 기술은 훨씬 더 정밀하게 작동합니다. 특정 스위치를 살펴보고, 그 주변 이웃들의 모든 가능한 배치에 대해 각각의 최적의 결과를 계산합니다. 그런 다음 해당 스위치를 포함하는 복잡한 규칙을 나머지 스위치들을 설명하는 새로운 규칙 세트로 대체합니다. 이는 제거된 스위치의 영향력을 시스템에 남겨두지 않고도 효과적으로 요약하는 방식입니다. 결정적으로, 컴퓨터는 새로운 규칙과 함께 간단한 '지침서'를 저장합니다. 이 지침서는 시스템에 제거된 스위치의 위치를 나중에 어떻게 재구성할지를 정확히 알려주며, 이를 통해 최종 결과가 마치 스위치가 제거되지 않았던 것처럼 수학적으로 동일하게 유지되도록 보장합니다. 이 과정은 근사치를 구하거나 추측하는 것이 아니라 정확한 방식입니다.

연구진은 이 방법을 두 가지 유형의 어려운 문제에 테스트했습니다. 첫 번째는 각 스위치가 정확히 세 개의 다른 스위치와 상호작용하는 네트워크인 '희소 스핀 글래스(sparse spin glass)'였고, 두 번째는 세 개의 스위치가 한 그룹으로 상호작용하는 문제였습니다. 이 테스트에서 연구진은 표준적인 접근 방식과 새로운 제거 방법을 '시뮬레이티드 어닐링(simulated annealing, 금속의 냉각 과정을 모방하여 안정된 상태를 찾는 알고리즘)' 솔버를 사용하여 비교했습니다. 연구진은 고정된 시간 제한을 두고 수천 번의 시도를 수행했습니다. 결과는 놀라웠습니다. 세 개의 스위치 상호작용 문제의 경우, 최적의 해를 찾는 성공률이 약 17%에서 87.5%로 급증했습니다. 더 단순한 두 개의 스위치 문제의 경우, 성공률은 약 10%에서 거의 98%까지 치솟았습니다. 이러한 개선은 문제를 준비하는 데 걸린 시간을 고려한 후에도 유효했습니다. 실제로, 더 단순한 문제의 경우 해결 시간을 약 34배 단축했고, 더 복잡한 문제의 경우 11배 단축했습니다.

이러한 성과가 특정 테스트 케이스에 국한된 우연이 아님을 확인하기 위해, 연구진은 고정된 프로토콜을 사용하여 새로운 문제 세트를 생성하고 설정을 변경하지 않은 채 다시 테스트를 수행했습니다. 개선 효과는 지속되었습니다. 정답을 알고 있는 모든 새로운 문제에 대해, 축소된 모델이 축소되지 않은 원래 모델보다 더 자주 정답을 찾아냈습니다. 또한 연구진은 샘플링된 데이터를 기반으로 스위치의 값을 고정하려는 다른 기술과도 비교했습니다. 기존 방식은 잘못된 추측을 하여 완벽한 해답 자체를 제거해 버리는 경우가 있었습니다. 반면, 새로운 제거 방식은 결코 잘못된 추측을 하지 않았으며, 매 경우마다 최적의 답이 존재할 가능성을 보존하면서 30~40%의 스위치를 제거하면서도 문제를 해결 가능한 상태로 유지했습니다.

이 연구는 단순히 기존 기계를 더 잘 작동하게 만드는 것을 넘어, 얼마나 더 큰 문제를 다룰 수 있는지에 대한 이론적 한계를 입증했습니다. 모든 스위치가 정확히 세 개의 연결을 가진 특정 클래스의 네트워크에 대해, 연구진은 제거법을 사용하면 규칙을 단순한 쌍(pairwise) 형태로 유지하면서도 항상 최소 3분의 1의 스위치를 제거할 수 있음을 증명했습니다. 이는 16개의 스위치 용량을 가진 기계가 이론적으로 원래 24개의 스위치가 필요했던 문제를 해결할 수 있음을 의미합니다. 이는 하드웨어를 더 크게 만들지 않고도 가능한 범위를 크게 확장하는 중요한 성과입니다. 이 방법은 스위치를 제거할 때 생성되는 새로운 규칙들이 지나치게 복잡해지지 않도록 보장함으로써 작동합니다. 연구진은 남은 스위치가 가질 수 있는 연결 수를 엄격히 제한하여, 문제가 현재의 솔버 역량 내에 머물도록 했습니다.

하지만 연구는 이 방법이 도움이 되지 않는 지점도 명시했습니다. 만약 스위치 간의 연결이 너무 밀집되어 있거나, 네 개 이상의 스위치가 한꺼번에 상호작용하는 문제라면, 스위치를 제거하는 과정에서 처리하기 너무 복잡한 새로운 규칙들이 생성됩니다. 이 경우, 축소된 문제를 준비하는 데 드는 시간이 작은 문제를 푸는 데 절약되는 시간보다 더 커지게 됩니다. 이 방법은 연결이 적고 드문드문한 희소한 문제에서 가장 빛을 발합니다. 연구진은 네 방향 상호작용 문제의 경우, 준비 시간이 너무 길어져서 원래의 축소되지 않은 접근 방식이 오히려 더 빠르다는 것을 발견했습니다. 이는 스위치를 제거하는 것의 이점이 문제의 구조와 생성되는 새로운 규칙의 비용에 전적으로 달려 있음을 보여줍니다.

이 연구의 함의는 단순히 이러한 특정 테스트에만 국한되지 않습니다. 이는 문제를 컴퓨터에 표현하는 방식이 컴퓨터의 원시적인 성능만큼이나 중요하다는 것을 보여줍니다. 기계가 문제의 복잡성에 적응하도록 강요하기보다, 기계의 자원에 맞춰 표현 방식을 변경함으로써 연구자들은 더 크고 어려운 퍼즐을 풀 수 있습니다. 이 연구는 수학적으로 정확한 축소가 실질적인 최적화를 개선할 수 있음을 확인시켜 주었으며, 사용 가능한 하드웨어보다 더 큰 문제를 해결할 수 있는 경로를 제시했습니다. 연구진은 다른 이들이 자신의 과제에 이 정확한 제거 기술을 적용할 수 있도록 소프트웨어를 공개했습니다. 이 결과는 적절한 수학적 도구가 있다면, 더 큰 기계를 만드는 것이 아니라 우리가 가진 기계를 더 영리하게 사용하는 방법을 통해 현재 컴퓨팅 하드웨어의 한계를 더 멀리 밀어낼 수 있음을 시사합니다.