IQM·Deutsche Bahn, 실제 철도 데이터에 하이브리드 양자 알고리즘 적용

문제 정의와 데이터셋

철도 차량 배분(rolling stock planning)은 물리적 열차 편성을 운행 스케줄에 배정하면서 운영 비용을 최소화하고 유지보수 제약을 충족해야 하는 복잡한 조합 최적화 문제다. 이번 연구에서 Deutsche Bahn의 IT 자회사 DB Systel이 제공한 데이터셋은 쾰른·뮌헨·베를린·프랑크푸르트·함부르크 5개 도시에 걸친 190개 운행편, 2일치 시간표로 구성됐다.

연구팀은 이 스케줄링 문제를 그래프 이론 형태인 최대 가중 독립 집합(MWIS, Maximum-Weight Independent Set) 문제로 변환했다. 그래프의 각 노드는 함부르크에서 2시간 의무 정비 정차와 4,000km 운행 거리 상한을 포함하는 실현 가능한 열차 순환 경로를 나타내며, 동일 운행편을 중복 담당하는 경로들은 엣지로 연결된다. 전체 경로를 생성하면 약 98,500개의 노드를 가진 그래프가 도출됐다.

분할 정복 프레임워크와 양자 실행

98,500개 노드 규모의 그래프는 현세대 QPU가 직접 처리하기에 지나치게 크다. 연구팀은 이를 해결하고자 양자-고전 분할 정복 프레임워크를 설계했다. 고전 외부 루프가 승객 탑승 운행편 밀도를 기준으로 관리 가능한 크기의 서브그래프(예: 노드 20개)를 반복 추출하면, 양자 서브루틴이 깊이 p=1의 QAOA(양자 근사 최적화 알고리즘)를 실행해 부분 해를 선택한다. 이후 고전 후처리 단계에서 충돌하는 선택지를 정리해 유효한 독립 집합을 확보한 뒤 전체 그래프를 갱신하는 방식으로 반복된다. 전 과정은 IQM Emerald 프로세서에서 엔드투엔드로 수행됐다.

실험 결과

연구는 세 가지 핵심 결과를 도출했다. 첫째, 내결함성 QPU 없이도 실제 기업 데이터셋에 대해 실행 가능하고 품질 높은 스케줄을 생성할 수 있음을 확인했다. 둘째, 고전 정확 해법(exact solver)을 활용한 벤치마킹에서 서브그래프 크기가 커질수록 빈 운행 거리(승객 없이 이동하는 비생산적 거리)가 통계적으로 유의하게 감소하는 관계를 확인했다(P=1.04×10⁻⁹). 셋째, QPU의 큐비트 수·연결성·게이트 충실도가 향상돼 더 큰 서브그래프를 처리할 수 있게 되면, 알고리즘 구조 변경 없이 스케줄링 성능이 자동으로 개선되는 구조적 확장성을 보였다.

의미와 한계

이번 연구는 현세대 NISQ 장치에서도 하이브리드 접근법이 실세계 산업 최적화 문제에 적용 가능함을 실증한 사례로 평가된다. 그러나 이번 연구 범위는 오프라인 결정론적 계획에 국한됐으며, 양자 서브루틴도 깊이 p=1의 얕은 QAOA에 그쳤다는 점은 현재의 한계로 남는다. 연구팀은 이 분할 정복 아키텍처가 향후 실시간 운행 장애 관리에도 적용될 수 있다고 언급했다. IQM은 2026년 7월 Nasdaq 글로벌 셀렉트 마켓과 Nasdaq 헬싱키에 IQMX 티커로 상장한 직후 이 연구를 공개했다.