Multi-Objective Optimization by Quantum-Annealing-Inspired Algorithms

본 논문은 전체 처리 오버헤드를 고려할 때 훨씬 더 빠른 엔드투엔드 실행 시간을 달성함으로써 GPU 기반 양자 어닐링 영감 알고리즘 (QAIAs) 이 다목적 MaxCut 문제 해결에 있어 최첨단 고전적 휴리스틱과 이전에 연구된 양자 프로세서 모두보다 우수한 성능을 보임을 입증한다.

핵심

거대한 혼란스러운 파티를 조직하려고 한다고 상상해 보세요. 당신은 종종 서로 충돌하는 세 가지 목표를 가지고 있습니다: 음악은 크게, 음식은 저렴하게, 손님은 행복하게 만들고 싶습니다. 세 가지 목표를 동시에 극대화할 수는 없습니다. 음식에 더 많은 돈을 쓰면 음악은 더 작아질 수 있습니다. 당신의 목표는 하나의 '완벽한' 파티 계획을 찾는 것이 아니라, 한 가지 것을 개선하면 다른 것이 희생될 수밖에 없는 최상의 절충안 목록 (파레토 프론트) 을 찾는 것입니다.

이것이 바로 다목적 최적화입니다: 상충되는 목표 사이에서 최상의 균형을 찾는 것입니다.

이 논문은 표준 그래픽 카드 (GPU) 에서 실행되는 '양자 영감을 받은' 컴퓨터 프로그램을 사용하여 이러한 절충안을 찾는 새로운 초고속 방법에 관한 것입니다. 간단한 용어로 정리하면 다음과 같습니다:

문제: '파티 기획자' 딜레마

과거 연구자들은 이러한 문제를 해결하기 위해 두 가지 주요 도구를 사용했습니다:

1. 실제 양자 컴퓨터: 이들은 한 번에 많은 가능성을 탐색할 수 있는 마법 같은 신비한 블랙박스처럼 작동합니다. 최근 연구들은 이들이 파티 계획을 찾는 데 유용함을 보여주었지만, 설정하는 데 시간이 많이 걸리고 결과를 정리하는 데 많은 추가 작업이 필요했습니다.
2. 고전 컴퓨터: 우리가 매일 사용하는 표준 컴퓨터입니다. 이들은 신뢰할 수 있지만 때로는 최상의 절충안을 찾는 데 느릴 수 있습니다.

이 논문의 저자들은 두 도구를 비교한 이전 연구들이 불공평했다고 지적했습니다. 그들은 '마법 상자'가 원시 아이디어 목록을 내어놓는 데 걸린 시간만 계산했을 뿐, 문제를 구축하고, 기계를 실행하며, 실제 승자를 찾기 위해 목록을 정리하는 데 걸린 시간을 무시했습니다.

해결책: '양자 영감을 받은' 스피드스터

저자들은 QAIA(Quantum-Annealing-Inspired Algorithm, 양자 어닐링 영감 알고리즘) 라는 새로운 알고리즘을 개발했습니다. 이는 실제 양자 컴퓨터가 아니라, 일반 컴퓨터 내부의 강력한 비디오 카드 (GPU) 에서 실행되는 매우 영리한 양자 컴퓨터 시뮬레이션으로 생각하세요.

이 시뮬레이션을 더 다양한 파티 계획을 찾는 데 더 효과적으로 만들기 위해, 그들은 약간의 **"가우시안 노이즈"**를 추가했습니다.

• 유사성: 안개가 낀 산맥에서 가장 높은 봉우리를 찾으려 하는 등산가 그룹을 상상해 보세요. 표준 알고리즘은 처음 보는 언덕에 갇히는 등산가와 같습니다. 저자들의 방법은 등산가들을 편안한 자리에서 부드럽게 밀어내는 '바람'(노이즈) 을 추가하여, 다른 골짜기와 봉우리를 탐험하도록 강제합니다. 이를 통해 한두 개가 아닌 더 다양한 최상의 절충안을 찾을 수 있습니다.

레이스: 누가 더 빠른가?

팀은 새로운 방법, 실제 양자 컴퓨터, 그리고 최고의 고전 방법 사이에서 레이스를 치렀습니다.

1. 샘플링 속도 (후보 찾기):

   • 결과: GPU 기반 방법은 원시 솔루션 목록을 생성하는 데 실제 양자 컴퓨터보다 100 배 더 빠릅니다.
   • 비유: 양자 컴퓨터가 엔진을 시동하고 한 바퀴 도는 데 10 초가 걸리는 레이싱카라면, 새로운 방법은 이미 가동 중인 포뮬러 1 카로, 한 바퀴를 1 초도 채 걸리지 않는 시간으로 완주합니다.

2. 종단 간 시간 (전체 작업):

   • 여기에는 문제 구축, 시뮬레이션 실행, 결과 정리가 포함됩니다.
   • 결과: 모든 것을 계산할 때, 그들의 방법은 최고의 고전 알고리즘보다 여전히 10 배 더 빠르며 양자 컴퓨터보다 훨씬 빨랐습니다.
   • 비유: 차를 싣고 트랙까지 운전하는 데 걸리는 시간을 고려한 후에도, GPU 방법은 전체 여정을 다른 방법들보다 훨씬 일찍 마쳤습니다.

함정: 품질 대 양

새로운 방법이 숫자를 만들어내는 데 놀라울 정도로 빠르긴 했지만, 논문은 작은 절충안이 있음을 지적합니다:

• 실제 양자 컴퓨터는 완벽한 절충안 목록을 찾는 데 필요한 총 추측 횟수가 적어 매우 '효율적'이었습니다.
• 새로운 방법은 동일한 목록을 찾기 위해 약간의 추가 추측 (샘플) 이 필요했지만, 이러한 추측을 만드는 속도가 매우 빨랐기 때문에 전체적으로 여전히 레이스에서 승리했습니다.

결론

이 논문은 그들이 테스트한 특정 유형의 문제 (다중 목표를 가진 MaxCut) 에 대해 이 새로운 '양자 영감을 받은' 코드를 실행하는 표준 컴퓨터가 현재 이용 가능한 최고의 도구라고 주장합니다. 이는 비싸고 느린 실제 양자 컴퓨터와 전통적인 고전 방법 모두를 속도와 전체 성능 면에서 능가합니다.

그들은 실제 양자 컴퓨터가 유망하지만, 현재 이러한 복잡한 균형 작업을 해결하는 데 있어서는 일반 하드웨어에서의 '양자 영감을 받은' 접근 방식이 챔피언이라고 결론지었습니다.

기술 요약

Tao, Mosharev, Yung 의 논문 "Multi-Objective Optimization by Quantum-Annealing-Inspired Algorithms"에 대한 상세한 기술적 요약입니다.

1. 문제 정의

이 논문은 다목적 최적화 (Multi-Objective Optimization, MOO), 구체적으로 다목적 MaxCut (MO-MaxCut) 문제를 다룹니다.

• 배경: 단일 목적 최적화와 달리, MOO 는 한 목적을 저하시키지 않고는 다른 목적을 개선할 수 없는 파레토 최적 해 (Pareto-optimal solutions) 집합인 파레토 프론트를 찾는 것을 목표로 합니다.
• 과제: 게이트 기반 QAOA 와 양자 어닐링과 같은 양자 솔버를 기존 휴리스틱과 비교하는 기존 연구들은 종종 샘플링 속도에만 초점을 맞추고, 모델 구축, 회로 컴파일, 그리고 원시 샘플에서 비우세 집합을 추출하는 데 필요한 계산 집약적인 파레토 필터링 (후처리) 과 같은 상당한 오버헤드를 간과합니다.
• 목표: 모델링 + 샘플링 + 필터링을 포함한 총 실행 시간을 고려하여 양자 및 고전 솔버에 대한 엄격한 엔드 - 투 - 엔드 (end-to-end) 비교를 제공하고, 현재 양자 하드웨어가 최첨단 고전 "양자 영감" 알고리즘보다 실용적인 이점을 제공하는지 평가하는 것입니다.

2. 방법론

저자들은 시뮬레이션 분기 (Simulated Bifurcation, SB) 기반의 GPU 가속 양자 어닐링 영감 알고리즘 (QAIA) 을 제안하고 평가합니다.

A. 수학적 형식화

• 해밀토니안: MO-MaxCut 문제는 이징 모델 (Ising model) 로 매핑됩니다. $K$개의 목적에 대해 시스템은 $H(s) = (H_1, \dots, H_K)$ 해밀토니안 벡터를 최소화합니다.
• 스칼라화: 단일 목적 솔버를 사용하여 다목적 문제를 해결하기 위해, 저자들은 가중 합 방법 (Weighted Sum Method) 을 사용합니다. Das–Dennis 심플렉스-격자 설계를 사용하여 가중치 벡터를 생성하여 스칼라화된 해밀토니안 $H_{total}(s; c) = \sum c_k H_k(s)$를 만듭니다.
• 파레토 필터링: 원시 샘플은 우세한 해를 필터링하고 최종 파레토 프론트 근사치를 구성하기 위해 고전적인 비우세 정렬 (Non-dominated Sorting) 알고리즘을 통해 처리됩니다.

B. 제안된 알고리즘: 노이즈 주입 시뮬레이션 분기 (NI-SB)

핵심 솔버는 비선형 진동자의 고전적 해밀토니안 역학을 시뮬레이션하여 저에너지 상태를 찾는 시뮬레이션 분기 (SB) 알고리즘의 변형입니다.

• 탄도형 (bSB) 대 이산형 (dSB): 저자들은 연속 (탄도형) 과 이산 SB 변형 모두를 활용합니다.
• 가우시안 노이즈 주입: 결정론적 SB 가 종종 동일한 해로 수렴하여 다양성이 부족하다는 문제를 해결하기 위해, 저자들은 운동량 방정식에 가우시안 백색 노이즈를 도입합니다:
  $$\dot{y}_i = -[a_0 - a(t)]x_i + c_0 \sum J_{ij}\phi(x_j) + \alpha \eta_i$$
  여기서 $\eta_i \sim \mathcal{N}(0, 1)$입니다. 이 "합성 열 노이즈"는 궤적이 해 공간의 다양한 영역을 탐색할 수 있게 하여, 파레토 프론트를 효과적으로 커버하는 데 필수적입니다.
• 하드웨어 구현: 이 알고리즘은 GPU(NVIDIA RTX 4090) 에서 구현되어, 반정밀도 (float16) 연산을 사용하여 수천 개의 후보 해를 동시에 처리하는 대규모 병렬성을 활용합니다.

3. 주요 기여

1. 엔드 - 투 - 엔드 벤치마킹: 이 논문은 평가 지표를 "샘플링 시간"에서 총 엔드 - 투 - 엔드 실행 시간으로 전환하여, 양자 우위 주장에서 종종 생략되는 모델 구축 및 파레토 필터링 오버헤드를 명시적으로 포함합니다.
2. 강력한 고전 기준선: 저자들은 GPU 가속 QAIA 가 강력한 고전 기준선 역할을 하여 양자 하드웨어와 기존 고전 휴리스틱 모두를 능가함을 입증합니다.
3. 노이즈 주입 SB: SB 에 가우시안 노이즈를 도입함으로써 MOO 를 위한 샘플 다양성이 크게 향상되어, QAOA 에 비해 더 적은 총 샘플로 완전한 파레토 집합을 복원할 수 있게 됩니다.
4. 종합적 비교: 이 연구는 제안된 방법을 다음과 비교합니다:
   • 양자: D-Wave Advantage/Advantage2(QA) 및 IBM Fez(QAOA).
   • 고전 휴리스틱: DCM, DPA-a, MOEA/D, NSGA-II, NSGA-III, RVEA.

4. 결과

실험은 변수 수 ($n$) 와 목적 수 ($K=3, 4$) 가 다양한 MO-MaxCut 인스턴스에서 수행되었습니다.

• 샘플링 속도:

  • QAIA는 이전에 연구된 양자 프로세서 (QA 및 QAOA) 보다 후보 해를 샘플링하는 속도가 약 두 자릿수 (two orders of magnitude) 빠릅니다.
  • QAIA 는 $10^{-2}$초에서 $10^{-1}$초 내에 최적의 초부피 (Hypervolume) 평탄기에 도달하는 반면, QA 시스템은 수 초에서 수 분이 소요됩니다.

• 샘플 효율성 및 품질:

  • QAIA 대 QAOA: QAIA 는 QAOA 보다 약 10 배 적은 후보로 완전한 파레토 집합을 복원합니다.
  • QAIA 대 QA: QA 는 평균적으로 파레토 집합을 찾는 데 더 적은 샘플이 필요하지만, QAIA 는 압도적으로 우수한 샘플링 속도로 이를 상쇄합니다.

• 엔드 - 투 - 엔드 성능:

  • 양자 대비: QAIA 는 총 실행 시간 (필터링 포함) 에서 QA 보다 약 1 자릿수, QAOA 보다 약 4 자릿수 빠릅니다.
  • 고전 휴리스틱 대비: $n=200$까지의 밀집 3 목적 인스턴스에서 QAIA 는 실행 시간과 해 품질 (초부피) 모두에서 MOEA/D, NSGA-II, NSGA-III, RVEA 를 능가합니다.
    • 예시: $n=200$의 경우, QAIA 는 1 초 미만에 최적 초부피의 약 99% 를 달성한 반면, 고전 휴리스틱은 약 9~11 초가 소요되었고 더 낮은 초부피 비율 (60~93%) 을 달성했습니다.

• 확장성:

  • 이 방법은 완전 그래프인 $n=200$을 성공적으로 처리하여 D-Wave 의 Pegasus 및 Zephyr 토폴로지 (약 180~193 노드) 의 현재 임베딩 한계를 초과했습니다.

5. 의의 및 결론

• 양자 우위의 재정의: 이 논문은 현재 MO-MaxCut 벤치마크에 대해 GPU 가속 양자 영감 솔버가 현재 이용 가능한 양자 하드웨어보다 더 강력한 엔드 - 투 - 엔드 기준선을 제공한다고 주장합니다. 샘플링 속도에서의 "양자 우위"는 양자 실행의 오버헤드와 현대 GPU 의 우수한 병렬성으로 인해 상쇄됩니다.
• 실용적 유용성: 결과는 실용적인 다목적 최적화 작업의 경우, 고전 이징 솔버 (특히 NI-SB) 가 현재 빠른 수렴과 높은 해 품질을 제공하는 가장 효율적인 도구임을 시사합니다.
• 향후 방향: 저자들은 샘플링 속도와 샘플 품질(예: 비우세 수율, 파레토 집합 재현율) 을 분리하는 지표의 필요성을 강조합니다. 또한 MaxCut 을 넘어 더 넓은 MOO 문제에서 이러한 방법을 테스트하고 다른 QAIA 변형 (예: 열 보조 SB) 을 탐구할 것을 제안합니다.

요약하자면, 이 연구는 양자 하드웨어가 발전하고 있지만, 총 해 도출 시간과 확장성 측면에서 현재 GPU 에서 실행되는 고전 양자 영감 알고리즘이 다목적 최적화 분야에서 지배적인 위치를 차지하고 있음을 보여줍니다.