Qudit-based scalable quantum algorithm for solving the integer programming problem

최적화는 방대한 선택지 중에서 가능한 최선의 해결책을 찾는 예술이며, 이는 항공편 스케줄링부터 금융 포트폴리오 관리까지 모든 분야의 근간이 되는 도전 과제입니다. 이러한 선택들이 정수(whole numbers)와 엄격한 규칙들을 포함할 때, 이 문제는 정수 계획법(integer programming)으로 알려지게 됩니다. 수십 년 동안 이러한 문제들을 해결하는 것은 고전 컴퓨터에게 매우 힘겨운 과제였습니다. 변수의 수가 증가함에 따라 완벽한 답을 찾는 데 필요한 시간은 급격히 늘어나며, 이로 인해 가장 강력한 슈퍼컴퓨터조차 인간의 수명 내에 모든 가능성을 확인하지 못한 채 갇혀버릴 수 있습니다. 이러한 어려움은 오랫동안 다른 종류의 컴퓨팅, 즉 이 복잡성을 더 효율적으로 탐색할 수 있는 컴퓨팅이 필요함을 시사해 왔습니다.

최근 몇 년 동안 연구자들은 고전적인 기계가 할 수 없는 방식으로 정보를 처리하기 위해 물리학의 기묘한 법칙을 사용하는 양자 컴퓨터를 탐구하기 시작했습니다. 초기 양자 접근 방식의 상당수가 큐비트(qubit)라고 불리는 단순한 두 상태 단위를 사용했던 반면, 큐디트(qudit)라고 알려진 더 복적인 단위를 사용하는 새로운 사고방식이 등장했습니다. 이 단위들은 동시에 여러 상태로 존재할 수 있어, 정보를 저장하고 조작할 수 있는 훨씬 더 넓은 공간을 제공합니다. 이제 한 물리 학자 팀이 이러한 다중 상태 단위를 사용하여 정수 계획법 문제를 해결하는 새로운 방법을 제안했습니다. 그들의 연구는 오랫동안 이러한 어려운 과제들을 괴롭혀온 계산의 안개를 걷어내는 방법을 제시하며, 전통적인 방식보다 더 빠르게 최적의 해를 찾을 수 있는 경로를 제안합니다.

독일과 미국의 연구 기관에서 협력한 연구진은 정수 계획법을 다루기 위해 설계된 특정 양자 알고리즘을 개발했습니다. 그들의 접근 방식은 사람이 복잡한 퍼즐을 푸는 방식과 유사한 2단계 과정에 기반합니다. 즉, 첫째로 불가능한 옵션들을 걸러내고, 둘째로 남은 것들 중에서 가장 좋은 것을 고르는 것입니다. 첫 번째 단계에서 알고리션은 각 변수가 큐디트로 표현되는 많은 변수를 포함하는 양자 시스템을 준비합니다. 그런 다음, 이 변수들이 주어진 모든 규칙이나 제약 조건을 만족하는지 확인하기 위해 일련의 연산을 적용합니다. 이는 변수들을 플래그(flag) 역할을 하는 보조 비트들과 얽히게 함으로써 수행됩니다. 만약 변수의 조합이 규칙을 어기면 플래그가 변하고, 규칙을 준수하면 플래그는 그대로 유지됩니다.

시스템이 모든 제약 조건을 확인하고 나면, 알고리즘은 진폭 증폭(amplitude amplification)이라고 불리는 기술을 사용합니다. 이 과정은 유효한 조합을 찾을 확률을 효과적으로 높이는 동시에 무효한 조합의 확률은 억제합니다. 마치 붐비는 방 안에서 사람들이 소리를 지르고 있지만, 당신은 오직 올바른 언어로 말하는 사람들만 듣고 싶어 하는 상황을 상상해 보십시오. 이 단계는 올바른 목소리의 볼륨은 높이고 나머지 목소리의 볼륨은 낮춥니다. 보조 비트를 측정함으로써 시스템은 유효한 해들만 남는 상태로 붕괴됩니다. 이 단계는 매우 중요한데, 왜냐하면 가능한 답의 대다수를 고려 대상에서 제외하여 실행 가능한 옵션들을 훨씬 작고 관리 가능한 그룹으로 남겨두기 때문입니다.

유효한 해들이 격리되면, 알고리즘은 두 번째 단계인 '최선의 해 찾기'로 넘어갑니다. 연구진은 목표값(종종 비용 함수라고 불림)을 양자 상태에 인코딩합니다. 그들은 양자 위상 추정(quantum phase estimation)이라는 방법을 사용하여 각 해의 수치적 값을 양자 시스템 내의 특정 위상, 즉 타이밍으로 변환합니다. 이 위상은 다시 확률로 변환됩니다. 그들 설계의 영리한 점은 가장 높은 값을 가진 해가 측정될 확률을 가장 높게 부여한다는 것입니다. 시스템이 최종적으로 관측될 때, 그것은 모든 규칙을 만족하면서 목적 함수를 극대화하는 단 하나의 최적의 숫자 배열을 드러낼 가능성이 가장 높습니다.

연구팀은 5개의 변수가 각각 3개의 서로 다른 값을 가질 수 있고 4개의 복잡한 제약 조건을 따르는 특정 비선형 문제를 대상으로 그들의 방법을 시뮬레이션했습니다. 각 연산자가 수학적으로 잘 정의된 파이썬(Python)을 사용하여 알고리즘을 구현한 결과, 시뮬레이션에서 최적의 해를 성공적으로 찾아냈습니다. 그들은 결과를 모든 가능성을 일일이 확인하는 브루트 포스(brute-force) 방식과 분기 한정법(branch and bound)이라 불리는 더 정교한 기법을 포함한 고전적 방법들과 비교했습니다. 고전적인 분기 한정법은 답을 찾는 데 수백 단계가 필요했고, 브루트 포스 방식은 수백 개의 조합을 확인해야 했던 반면, 양자 접근 방식은 문제의 크기가 커짐에 따라 필요한 단계 수의 현저한 감소를 보여주었습니다. 연구진은 이러한 유형의 문제에 대해 그들의 방법이 고전적 알고리즘보다 훨씬 더 잘 확장되며, 이차적 가속(quadratic speed-up)을 제공한다는 것을 발견했습니다. 이는 문제가 커짐에 따라 필요한 시간이 훨씬 더 느리게 증가함을 의미합니다.

이 작업은 단순히 이론적인 연습이 아닙니다. 이는 양자 컴퓨터가 실제 데이터를 처리할 때 겪는 실질적인 병목 현상을 다룹니다. 기존의 대부분의 최적화 양자 알고리즘은 정수를 이진 코드로 변환하는 비효율성 때문에 자원을 낭비하는 문제로 어려움을 겪습니다. 큐디트를 직접 사용함으로써, 이 새로운 알고리즘은 문제를 하드웨어에 더 자연스럽게 매핑하여 회로의 복잡성을 줄입니다. 연구진은 현재의 양자 하드웨어가 여전히 노이즈가 많고 오류가 발생하기 쉽다는 점을 인정하며, 지금까지의 결과는 시뮬레이션을 바탕으로 한 것이라고 밝혔습니다. 그러나 그들은 이 알고리즘이 다중 상태 단위를 지원할 수 있는 트랩 이온(trapped ions), 광자(photons) 또는 기타 양자 시스템을 사용하는 미래의 기기에서 어떻게 구현될 수 있는지에 대한 개요를 제시했습니다.

이 연구의 함의는 단 하나의 수학적 기교를 넘어섭니다. 정수 계획법은 물류, 엔지니어링, 금융 분야의 근본적인 도구이며, 이 분야들은 가장 효율적인 해결책을 찾는 것이 수백만 달러나 수많은 시간을 절약할 수 있는 곳들입니다. 만약 이 방법이 물리적 하드웨어에서 실현될 수 있다면, 산업계가 현재는 다루기 너무 어려운 문제들을 해결할 수 있게 될 것입니다. 논문은 이 방법이 모든 최적화 문제를 해결했다고 주장하거나 양자 컴퓨터가 즉각적으로 고전 컴퓨터를 대체할 것이라고 제안하는 것이 아닙니다. 대신, 이는 특정하고 중요한 어려운 문제들에 대해 진정한 이점을 제공하는 확장 가능하고 자원 효율적인 경로를 제시합니다. 규칙을 확인하는 작업과 최선의 답을 찾는 작업을 분리함으로써, 연구진은 강력하면서도 실용적인 양자 알고리즘의 청사진을 만들었으며, 양자 우위(quantum advantage)의 약속을 현실에 한 걸음 더 가깝게 가져왔습니다.