현대 인프라의 복잡한 세계에서, 대륙을 가로지르는 전력의 흐름부터 글로벌 네트워크를 통한 데이터 라우팅에 이르기까지, 연결을 효율적으로 조직해야 할 지속적인 필요성이 존재합니다. 수많은 출발점에서 수많은 목적지로 교통량을 이동시켜야 하지만, 교차로에서 두 차량이 서로 충돌하지 않도록 해야 하는 거대한 도로망을 상상해 보십시오. 수학과 컴퓨터 과학에서 이 과제는 매칭 문제(matching problem)로 알려져 있습니다. 즉, 끝점이 겹치지 않는 가능한 가장 큰 연결 집합을 찾는 것입니다. 복잡하고 무질서한 네트워크를 가장 적은 수의 깨끗하고 중복되지 않는 집합으로 분해하는 것이 목표일 때, 이 작업은 표준 컴퓨터가 빠르게 해결하기에 매우 어렵습니다. 이는 조합 최적화(combinatorial optimization)의 영역이며, 이곳에서 완벽한 배치를 찾는 것은 종종 우주의 원자 수보다 더 많은 가능성을 확인해야 하는 일을 요구합니다. 이러한 문제를 해결하기 위해 과학자들은 한 번에 많은 가능성을 탐색하기 위해 양자 역학의 기묘한 규칙을 사용하는 기계인 양자 컴퓨터에 주목하고 있습니다. 그러나 현재의 양자 기계는 여전히 작고 취약하여 불과 몇 백 비트의 정보만을 보유하고 있는 반면, 이들이 해결하고자 하는 실제 세계의 문제들은 종종 수천 개의 변수를 포함합니다. 연구자들의 핵심 질문은 거대한 문제를 더 작은 조각으로 나누어 오늘날의 제한된 하드웨어에서 그 조각들을 해결한 다음, 그 답들을 다시 엮어 전체 퍼즐을 풀 수 있는지 여부입니다.

한 연구팀은 대규모 에너지 그리드 시뮬레이션에 하이브리드 접근 방식을 성공적으로 적용함으로써 그 질문에 대한 답을 찾는 중요한 발걸음을 내디뎠습니다. 그들은 최소 비르코프 분해(Minimum Birkhoff Decomposition)라고 불리는 특정 과제에 집중했는데, 이는 가능한 한 적은 가중치 매칭(weighted matchings)을 사용하여 복잡한 수요 그래프를 어떻게 재구성할 것인가를 묻는 문제입니다. 매칭의 수가 적다는 것은 현실 세계에서 전환과 재구성을 덜 한다는 것을 의미하며, 이는 에너지 거래나 네트워크 스케줄링과 같은 분야에서 비용 절감과 효율성 향상으로 직결됩니다. 연구진은 유럽 고전압 송전 네트워크의 현실적인 모델인 PEGASE-1354 케이스에 이 방법을 테스트했습니다. 이 모델은 1,354개의 연결 지점과 1,710개의 송전선을 가진 그리드를 나타냅니다. 만약 누군가 이 문제를 양자 컴퓨터에서 직접 해결하려 한다면, 1,710개의 큐비트(양자 정보의 기본 단위)를 가진 기계가 필요할 것입니다. 오늘날 사용 가능한 가장 진보된 양자 프로세서들도 이보다 훨씬 적은 수의 큐비트를 가지고 있기 때문에, 연구팀은 필수적인 양자 이점을 잃지 않으면서 문제를 축소할 방법을 찾아야 했습니다.

이를 가능하게 하기 위해, 연구팀은 거대한 네트워크를 관리 가능한 작은 덩어리로 나누는 워크플로우를 개발했습니다. 그들은 네트워크를 가장 밀접하게 연결된 부분들을 묶어내되 그 사이의 연결은 최소한으로 끊어내는 스마트 지도 제작자 역할을 하는 스펙트럼 분할(spectral partitioning) 기법을 사용했습니다. 이를 통해 1,710개의 선으로 이루어진 문제를 현재의 양자 하드웨어에 적합한 크기인 수십 개의 작은 하위 문제로 나눌 수 있었습니다. 구체적으로, 그들은 기존 초전도 양자 프로세서의 역량 범위 내에 들어오는 약 50 큐비트 규모의 분할을 목표로 삼았습니다. 각 작은 조각에 대해, 그들은 가능성의 지형을 탐색하여 좋은 후보 솔루션을 찾도록 설계된 QAOA라는 양자 샘플링 알고리즘을 실행했습니다. 각 조각에 대해 단 하나의 완벽한 답을 찾는 대신, 양자 컴퓨터는 다양한 잠재적 매칭의 풀(pool)을 생성했습니다. 이후 이 후보들은 감독관 역할을 하는 클래식 컴퓨터로 전달되었습니다. 클래식 컴퓨터는 솔루션의 오류를 점검하고, 연결이 부적절하게 교차하는 충돌을 수정하며, 서로 다른 분할로부터 얻은 최선의 조각들을 결합하여 글로벌 솔루션을 구축했습니다. 이 점검 및 수정 과정은 탐욕적 실행 가능성 복구(greedy feasibility repair)로 알려져 있으며, 최종 결과가 유효하고 작동 가능한 구성이 되도록 보장합니다.

이 실험의 결과는 고무적이었으며, 상당한 제약이 있는 기계에서도 양자 지원 방식이 전통적인 방법보다 뛰어난 성능을 보일 수 있음을 보여주었습니다. 연구진이 양자 생성 후보를 표준 클래스 최적화 기법인 시뮬레이티드 어닐링(simulated annealing) 및 균등 무작위 샘플링(uniform random sampling)과 비교했을 때, 양자 방식은 일관되게 더 나은 결과를 만들어냈습니다. 양자 프로세서로부터 복구된 샘플은 더 낮은 오류율을 달성했는데, 이는 최종 재구성된 네트워크가 베이스라인이 된 클래식 방식의 솔루션보다 이상적인 수요에 더 가까웠음을 의미합니다. 또한, 연구팀은 분할의 크기가 매우 중요하다는 것을 발견했습니다. 단 20 큐비트의 매우 작은 조각으로 문제를 나누었을 때 솔루션의 품질이 크게 떨어졌는데, 이는 양자 컴퓨터가 유용하기 위해 일정 수준의 복잡성을 필요로 함을 시사합니다. 조각이 너무 작으면 클래식 컴퓨터가 시뮬레이션하기 쉬워져 양자 기계의 필요성이 사라집니다. 그러나 분할 크기를 약 50 큐비트 정도로 크게 유지했을 때, 시스템은 클래식 방식이 따라잡기 어려운 고품질의 솔루션을 찾는 능력을 유지했습니다. 이는 양자 이점이 변수 간의 상관관계가 단순한 클래식 휴리스틱으로는 효과적으로 탐색하기 어려울 만큼 정교한 특정 수준의 복잡성을 다룰 때 발생한다는 것을 암시합니다.

또 다른 주요 발견은 양자 회로가 물리적 하드웨어에 배치되는 방식의 영향이었습니다. 연구진은 여러 개의 독립적인 양자 문제를 동일한 프로세서의 서로 다른 부분에서 동시에 실행할 수 있게 해주는 공간 회로 패킹(spatial circuit packing) 기술을 활용했습니다. 이러한 과업들을 신중하게 배치함으로써, 그들은 과업을 차례대로 실행할 때보다 총 실행 시간을 3분의 1로 단축할 수 있었습니다. 이러한 속도 향상은 실용적인 응용 분야에서 매우 중요한데, 이는 대규모 최적화 문제를 합리적인 시간 내에 해결하는 과정을 훨씬 더 용이하게 만들기 때문입니다. 연구팀은 실제 양자 프로세서인 IBM Heron 장치로 시스템을 테스트했으며, 하드웨어 결과가 고충실도 시뮬레이션의 성능을 밀접하게 추적한다는 것을 발견했습니다. 실제 하드웨어에는 노이즈와 오류가 발생했지만, 양자 샘플링과 클래식 복구의 결리합은 이러한 결함을 극복할 만큼 견고했습니다. 연구는 단순히 문제를 작게 만드는 것이 최선의 전략이라는 생각을 명시적으로 부정했습니다. 즉, 공격적인 분할을 통해 문제를 아주 작은 파편으로 줄이는 것은 오히려 솔루션의 품질을 저하시킨다는 것을 발견했습니다. 대신, 양자 행동을 유지할 만큼 충분히 크면서도 기계에 적합할 만큼 작은 크기가 최적의 지점(sweet spot)으로 밝혀졌습니다.

연구진은 또한 양자 '얽힘(entanglement)', 즉 큐비트 간의 깊은 연결이 성공에 얼마나 필요한지도 조사했습니다. 그들은 계산에서 유지되는 양자 상관관계를 제어할 수 있는 방법을 사용하여 이 과정을 시뮬레이션했습니다. 테스트 결과, 이 연결을 인위적으로 너무 많이 차단하면 후보 솔루션의 품질이 저하되는 것으로 나타났습니다. 이는 양자 프로세서가 단순히 난수 생성기로 작동하는 것이 아니라, 클래식 컴퓨터가 쉽게 복제할 수 없는 방식으로 솔루션 공간을 탐색하기 위해 고유한 특성을 진정으로 활용하고 있음을 나타냅니다. 이 연구는 양자 우위(quantum advantage) 문제를 확정적으로 해결했다고 주장하거나, 이 방법이 즉각적인 상업적 배포를 위한 준비가 되었다고 제안한 것이 아닙니다. 오히려 실현 가능한 경로를 제시한 것입니다. 스펙트럼 분할, 공간 패킹, 그리고 클래식 복구를 결합함으로써, 연구팀은 현재의 하드웨어를 사용하여 수천 개의 변수를 가진 제약 최적화 문제를 실행할 수 있음을 보여주었습니다. 이 작업은 분할을 충분히 크게 유지하여 가치 있는 양자 행동을 보존할 수 있다면, 분산 양자 샘플링이 확장될 수 있다는 개념 증명 역할을 합니다.

앞으로 연구진은 다음 논리적인 단계로, 이 분할의 크기를 최소 100 큐비트로 늘리고 하드웨어에서 실행 가능하도록 밀도를 세심하게 관리하는 것을 보고 있습니다. 그들은 이미 더 큰 벤치마크에 이 접근 방식을 테스트하기 시작했으며, 초기 결과에 따르면 이 방법은 합리적인 단계 내에서 목표 정확도에 일관되게 도달할 수 있고, 클래식 그리디(greedy) 방식보다 훨씬 더 희소하고 효율적인 분해를 생성할 수 있음을 보여주었습니다. 궁극적인 목표는 전체 문제가 커짐에 따라 각 분할 내에서 유용한 양자 기여도를 유지하여, 양자 컴퓨터가 단순한 참신함이 아닌 솔루션의 필수적인 부분이 되도록 하는 것입니다. 이 연구는 오늘날 기계의 한계를 인정하면서도, 클래식 컴퓨팅의 범위를 넘어서는 거대하고 실제적인 최적화 과제를 해결하기 위해 어떻게 효과적으로 사용할 수 있는지에 대한 명확한 경로를 제시하는 실용적인 접근 방식을 강조합니다.