Experimental Workflows for Combinatorial Optimization: Towards Quantum Advantage

본 논문은 고전적 전처리, IBM 의 156 큐비트 Heron r2 프로세서에서의 QAOA 실행, 그리고 고전적 후처리를 결합하여 고전적으로 해결하기 어려운 그래프 최적화 문제를 해결하는 엔드투엔드 하이브리드 양자 - 고전 워크플로우를 위한 샌드박스 플랫폼을 소개함으로써 실용적인 양자 유용성을 입증하고 양자 우월성으로 가는 길목의 병목 현상을 규명합니다.

핵심

거대한, 매우 복잡한 퍼즐을 풀려고 한다고 상상해 보세요. 퍼즐 조각들은 엉켜 있고, 그림은 흐릿하며, 상자에는 인간이 일생 동안이나 걸릴지도 모른다고 적혀 있습니다. 이것이 컴퓨터 과학자들이 '조합 최적화 문제'라고 부르는 것입니다. 이는 배송 트럭의 경로를 최적화하거나, 단백질 구조를 조직화하거나, 항공편 일정을 조정하는 가장 좋은 방법을 찾는 데 사용되는 수학의 한 종류입니다.

이 논문은 고전 컴퓨터(매일 사용하는 컴퓨터)와 양자 컴퓨터(정보를 처리하기 위해 물리의 기이한 법칙을 사용하는 미래지향적 기계)가 팀을 이루어 이러한 퍼즐을 해결하는 새로운 방법에 관한 것입니다.

다음은 그들의 실험 이야기를 쉽게 설명한 것입니다:

1. 문제: "너무 어려운" 퍼즐

연구자들은 세 가지 특정 유형의 그래프 퍼즐 (점들이 선으로 연결된 것을 상상해 보세요) 에 집중했습니다:

• 최소 정점 덮개 (Minimum Vertex Cover): 모든 선을 터치하는 데 필요한 최소한의 점 그룹을 찾는 것.
• 최대 독립 집합 (Maximum Independent Set): 서로 아무것도 터치하지 않는 최대의 점 그룹을 찾는 것.
• 최대 클릭 (Maximum Clique): 모든 점이 서로 연결된 최대의 점 그룹을 찾는 것.

이들은 유명한 "어려운" 문제들입니다. 일반 컴퓨터로 해결하려고 하면 막히거나 영원히 걸릴 수 있습니다. 양자 컴퓨터만으로 해결하려고 하면, 현재 기계가 너무 작고 너무 노이즈가 많아서 (오류에 취약함) 퍼즐 전체를 한 번에 처리할 수 없습니다.

2. 해결책: 3 단계 조립 라인

양자 컴퓨터에게 모든 일을 맡기는 대신, 팀은 안전 테스트 환경인 "샌드박스"를 구축하여 3 단계 공장 조립 라인처럼 작동하게 했습니다. 그들은 이를 하이브리드 워크플로우라고 부릅니다.

1 단계: 고전 전처리기 ("준비 셰프")
퍼즐이 양자 컴퓨터에 닿기 전에, 고전 컴퓨터가 준비 작업을 위한 중노동을 수행합니다. 스마트한 규칙을 사용하여 퍼즐의 쉬운 부분을 잘라냅니다.

• 비유: 거대하고 지저분한 세탁물 더미가 있다고 상상해 보세요. "준비 셰프"는 모든 양말과 수건 (쉽고 예측 가능한 부분) 을 접어서 서랍에 넣습니다. 이렇게 하면 처리해야 할 어려운 물건들만 남은 훨씬 작고 지저분한 더미가 남습니다.
• 이유: 이는 문제를 축소하여 오늘날의 양자 컴퓨터가 가진 작은 메모리에 맞도록 만듭니다.

2 단계: 양자 솔버 ("마법 주사위 굴리기")
축소된 더 작은 퍼즐이 양자 컴퓨터로 전송됩니다. 연구자들은 QAOA라는 알고리즘을 사용했습니다.

• 기법: 보통 이러한 퍼즐은 양자 컴퓨터가 따르기 어려운 엄격한 규칙 (제약 조건) 을 가지고 있습니다. 팀은 SCOOP라고 불리는 교묘한 수학적 기법을 사용하여 퍼즐을 다시 작성했습니다. 양자 컴퓨터에게 엄격한 규칙을 따르도록 강요하는 대신, 컴퓨터가 점수를 극대화하려는 "이익" 게임으로 바꾸었습니다.
• 결과: 양자 컴퓨터는 하나의 답을 주지 않습니다. 대신, 그것은 마법 주사위 굴리기처럼 작동하여 한 번에 많은 가능한 답들의 구름을 만들어냅니다. 일부는 좋고, 일부는 훌륭하며, 일부는 나쁩니다.

3 단계: 고전 후처리기 ("품질 관리 검사원")
양자 컴퓨터는 자신의 "답의 구름"을 넘겨줍니다. 그런 다음 고전 컴퓨터가 개입하여 그것들을 정리합니다.

• 역할: 그것은 양자 답들을 살펴보고, 작은 실수들을 수정하며, "이익" 점수를 원래 퍼즐에 대한 실제 해결책으로 되돌립니다.
• 비유: 양자 주사위 굴리기가 약간 구부러진 동전 더미를 주었다면, "검사원"은 그것들을 곧게 펴고 총 가치를 계산하여 유효한 돈 더미인지 확인합니다.

3. 실험: 조립 라인 테스트

팀은 세 가지 유형의 퍼즐에 대해 이 조립 라인을 테스트했습니다:

1. 가짜 퍼즐: 통제된 조건 하에서 시스템이 어떻게 작동하는지 보기 위해 무작위 그래프를 만들었습니다.
2. 표준 벤치마크: 다른 방법들과 비교하기 위해 알려진 어려운 문제들 (QOBLIB) 의 라이브러리를 사용했습니다.
3. 실제 세계 데이터: 과학자들 간의 사회적 연결이나 단백질의 생물학적 네트워크와 같은 실제 네트워크를 사용했습니다.

이러한 테스트는 캐나다 퀘벡에 위치한 156 개의 "큐비트"(비트의 양자 버전) 를 가진 실제 양자 컴퓨터인 IBM Quantum System One에서 수행되었습니다.

4. 발견: 무엇이 작동했는가?

• "준비 셰프"는 필수적입니다: 고전 컴퓨터가 먼저 문제를 축소하지 않으면, 양자 컴퓨터는 퍼즐의 크기를 처리할 수 없었습니다. 코끼리 전체를 신발 상자에 넣으려는 것과 같습니다; 먼저 코끼리를 잘라내야 합니다.
• 양자 부분은 가치를 더합니다: 양자 컴퓨터가 노이즈가 많음에도 불구하고, 이러한 특정 어려운 사례들에 대해 고전 컴퓨터가 단독으로 찾을 수 있는 것과 경쟁하거나 때로는 더 나은 고품질 해결책을 찾을 수 있었습니다.
• "검사원"은 결정적입니다: 양자 답들을 정리하는 마지막 단계는 필수적이었습니다. 그것은 원시적이고 노이즈가 많은 양자 데이터를 사용 가능하고 고품질인 해결책으로 변환했습니다.

5. 큰 그림

저자들은 이미 세상에서 가장 어려운 문제들을 해결했다고 주장하지는 않습니다. 대신, 그들은 이렇게 말합니다: "바로 오늘 양자 컴퓨터를 사용하는 실용적인 청사진이 여기 있습니다."

그들은 "양자 우위"(양자 컴퓨터가 고전 컴퓨터보다 실제로 더 나은 상태) 를 얻기 위해서는 양자 알고리즘만 고립되어 보지 말아야 한다고 주장합니다. 우리는 전체 워크플로우를 살펴봐야 합니다: 데이터를 어떻게 준비하고, 양자 부분을 어떻게 실행하며, 결과를 어떻게 정리하는지.

간단히 말해: 그들은 고전 컴퓨터가 준비와 정리를 하고, 양자 컴퓨터가 중간에 무겁고 까다로운 들기를 하는 팀을 구축했습니다. 이 팀워크는 현재 이용 가능한 제한된 양자 하드웨어를 사용하여 그렇지 않으면 불가능했을 그래프 퍼즐들을 해결할 수 있게 해줍니다.

기술 요약

Angara 외의 논문 "Experimental Workflows for Combinatorial Optimization: Towards Quantum Advantage"에 대한 상세한 기술 요약입니다.

1. 문제 제기

이 논문은 최소 정점 덮개 (MINVC), 최대 독립 집합 (MAXIS), 최대 클릭 (MAXCL) 과 같은 제약이 있는 그래프 문제를 대상으로 양자 우위 (quantum advantage) 를 입증하는 데 직면한 과제를 다룹니다.

• 핵심 이슈: 현재의 양자 알고리즘 (QAOA 등) 은 종종 제약이 있는 문제를 해결하는 데 어려움을 겪습니다. 표준 접근법은 제약 조건을 강제하기 위해 (예: 해가 유효한 정점 덮개임을 보장) 페널티 항 (penalty terms) 을 필요로 하기 때문입니다. 이러한 페널티는 조정이 어려운 하이퍼파라미터를 도입하고, 에너지 지형을 왜곡하며, 종종 실행 불가능한 해나 낮은 근사 비율을 초래합니다.
• 격차: 실제 세계 및 벤치마크 인스턴스에서 실용적인 양자 유틸리티를 평가하기 위해 고전적 전처리, 양자 실행, 고전적 후처리를 통합하는 종단 간 (end-to-end) 실험 프레임워크가 부족합니다.

2. 방법론

저자들은 모듈식 샌드박스 플랫폼 내에서 구현된 하이브리드 양자 - 고전 종단 간 파이프라인을 제안합니다. 워크플로우는 세 가지 명확한 단계로 구성됩니다.

A. 고전적 전처리 샌드박스

• 목표: 현재 하드웨어 (특히 IBM 의 156 큐비트 Heron r2 프로세서) 의 큐비트 제한에 맞춰 문제 크기를 축소합니다.
• 기법: 입력 그래프 $G$에 매개변수화 복잡도 이론의 다항 시간 축소 규칙을 적용합니다.
  • 단일/매달린 정점: 차수가 0 인 정점을 제거하고 차수가 1 인 정점을 처리합니다.
  • 차수 2 축소: 삼각형에 있는 정점을 처리하거나 차수가 2 인 정점을 접습니다.
  • 고차 축소: 상한에 기반하여 덮개에 고차 정점을 포함시킵니다.
  • 선형 계획법 (LP) 축소: 완화된 LP 형식을 풀어 정점을 안전하게 포함하거나 제외할 수 있는 집합으로 분할합니다.
• 결과: 축소된 그래프 $G'$와 해의 일부로 사전 결정된 "안전한" 정점 집합 ($V_{safe}$) 을 생성합니다.

B. 양자 솔버 샌드박스 (제약 없는 문제에 대한 QAOA)

• 핵심 혁신: 제약이 있는 MINVC/MAXIS/MAXCL 을 직접 해결하는 대신, SCOOP 프레임워크를 사용하여 문제를 제약 없는 변형으로 변환합니다.
  • 변환: MINVC 를 최대 이익 덮개 (MAXPC) 로 매핑합니다.
  • 이점: MAXPC 는 제약 없는 이진 최적화 문제입니다. 이는 해밀토니안에서 페널티 파라미터의 필요성을 제거하여 "페널티 조정" 병목 현상을 피합니다.
• 알고리즘: 양자 근사 최적화 알고리즘 (QAOA) 을 MAXPC 형식에 적용합니다.
  • 하드웨어: 156 큐비트 Heron r2 프로세서를 사용하여 IBM Quantum System One(ibm_quebec) 에서 실행됩니다.
  • 학습: barren plateaus 를 완화하기 위해 순차적 계층별 학습 전략 (1 계층 학습, 파라미터 고정, 그 후 2 계층 학습) 을 사용합니다.
  • 오류 완화: 측정 트위링 (measurement twirling) 과 동적 디커플링 시퀀스를 활용하여 노이즈를 억제합니다.

C. 고전적 후처리 샌드박스

• 목표: 양자 출력 ("이익 덮개"를 나타내는 비트열) 을 원래의 제약이 있는 문제에 대한 고품질 실행 가능한 해로 변환합니다.
• 기법:
  • 변환: 정리 1 을 사용하여 MAXPC 해를 다시 MINVC, MAXIS 또는 MAXCL 로 매핑합니다.
  • 정제: 덮지 않은 간선을 덮기 위해 탐욕적 휴리스틱을 적용하고 덮개에서 중복된 정점을 제거합니다.
  • 재구성: $G'$에서 정제된 해와 전처리된 $V_{safe}$ 집합을 결합하여 원래 그래프 $G$에 대한 최종 해를 형성합니다.

3. 주요 기여

1. 인스턴스 인식 하이브리드 파이프라인: 고전 및 양자 자원 간 작업 부하를 동적으로 분할하는 모듈식 프레임워크입니다. 고전적 방법으로 처리 가능한 하위 구조를 해결하고 "어려운" 잔여 인스턴스만 양자 프로세서로 오프로드합니다.
2. 페널티 없는 형식화: SCOOP 프레임워크를 활용하여 제약이 있는 문제를 제약 없는 MAXPC 로 변환함으로써, 페널티 기반 QUBO 형식화와 관련된 확장성 문제를 피합니다.
3. 종단 간 벤치마킹: 이 연구는 세 가지 다른 데이터셋에서 전체 파이프라인 (양자 솔버뿐만 아니라) 을 평가합니다.
   • 합성 그래프: 회로 깊이 및 수렴에 대한 통제된 분석을 위해 사용됩니다.
   • QOBLIB 벤치마크: 표준 어려운 인스턴스 (최대 128 정점).
   • 실제 네트워크: 생물학적 및 사회적 협력 네트워크 (최대 4,941 정점, 양자 실행을 위해 <156 으로 축소됨).
4. 실용적 지침: 단일 결정론적 출력뿐만 아니라 양자 출력을 해석하기 위한 지표 (예: 최적에 가까운 해에 대한 확률 질량, 근사 비율) 를 도메인 전문가에게 제공합니다.

4. 결과

• 하드웨어 실행: 최대 128 정점의 그래프에서 최대 13,555 개의 2 큐비트 게이트가 포함된 회로로 실험이 수행되었습니다.
• 합성 데이터 성능:
  • 제약 없는 QAOA 솔버는 회로 깊이 ($p$) 가 증가함에 따라 확률 질량이 고품질 (최적에 가까운) 해에 집중됨을 보여주었습니다.
  • 제약 없는 MAXPC 의 근사 비율은 페널티 기반 접근법에서 실행 불가능한 해가 인위적으로 점수를 높일 수 있는 것과 달리 해의 품질에 대한 신뢰할 수 있는 지표였습니다.
• 실제 데이터 및 벤치마크 데이터 성능:
  • 전처리 효율성: 많은 실제 그래프의 경우, 고전적 전처리가 문제 크기를 크게 축소하여 양자 실행 없이도 인스턴스를 완전히 해결하기도 했습니다.
  • 양자 유틸리티: 양자 실행이 필요한 인스턴스의 경우, 하이브리드 파이프라인은 Network Repository 에 보고된 기존 가장 좋은 고전적 휴리스틱과 경쟁하거나 더 나은 해를 생성했습니다.
  • 확장성: 이 접근법은 대규모에서 정확한 고전 솔버로는 처리 불가능한 인스턴스를 성공적으로 처리하여 "축소 후 해결 (reduce-then-solve)" 전략의 가치를 입증했습니다.
• 오류 완화: 순차적 학습 및 오류 억제 기술 (트위링/동적 디커플링) 의 사용은 잡음이 있는 중규모 양자 (NISQ) 하드웨어에서의 성공적인 실행을 가능하게 했습니다.

5. 의의

• 양자 우위의 재정의: 이 논문은 최적화 분야에서의 양자 우위가 독립적인 알고리즘 속도 향상에서 오는 것이 아니라, 더 큰 고전적 프레임워크 내에서 양자 프로세서가 특정하고 어려운 하위 문제를 처리하는 통합 워크플로우에서 비롯될 것이라고 주장합니다.
• 실용적 로드맵: 하이브리드 파이프라인을 구성하는 방법에 대한 구체적인 청사진을 제공하며, 고전적 전처리가 문제를 현재 하드웨어에 적합하게 만드는 데 필수적이고, 고전적 후처리가 해의 실행 가능성과 품질을 보장하는 데 필수적임을 강조합니다.
• 방법론적 전환: 페널티 기반 제약에서 변환을 통한 제약 없는 동등 문제 (SCOOP) 로의 전환을 통해, QAOA 를 실제 세계의 제약 최적화 문제에 적용하기 위한 더 견고한 경로를 제시합니다.
• 실험 플랫폼: "샌드박스" 개념은 문제 형식화, 하드웨어 제약, 알고리즘 설계 간의 상호작용을 체계적으로 연구하는 데 필수적인 도구로 작용하며, 이를 통해 해당 분야를 고립된 장난감 예제를 넘어 현실적인 사례 연구로 발전시킵니다.