⚛️ quantum physics

Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

이 논문은 139개의 인스턴스에 걸친 Max-Cut 문제에 대해 양자, 고전 및 하이브리드 솔버를 벤치마킹하여, 하이브리드 및 고전적 시뮬레이티드 어닐링 방식이 규모가 작은 인스턴스에서는 일관되게 전역 최적해를 찾아내는 반면, 전역 최적해를 알 수 없는 규모가 큰 인스턴스에서는 시뮬레이티드 바이퍼케이션 머신과 더 느린 고전적 변형들이 더 우수한 해의 품질을 제공한다는 것을 밝혀냈다.

원저자: Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh

게시일 2026-07-07

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 거대하고 믿을 수 없을 정도로 복잡한 퍼즐을 풀려고 노력하고 있다고 상상해 보세요. 목표는 연결된 점들의 집단(사회적 네트워크나 회로 기판 같은)을 두 개의 별개 그룹으로 나누되, 그룹 사이의 연결 수가 최대한 많도록 만드는 것입니다. 이것은 Max-Cut 문제라고 불립니다. 이는 컴퓨터가 완벽하게 해결하기 매우 어렵기로 유명한 유형의 퍼즐이며, 특히 퍼즐이 거대해질수록 더욱 그렇습니다.

이 논문은 본질적으로 하나의 "경주 보고서"입니다. 저자들은 누가 이 퍼즐들을 가장 잘, 그리고 가장 빠르게 해결하는지 알아보기 위해 다양한 "경주자들"(컴퓨터 알고리즘)을 모았습니다. 그들은 세 가지 유형의 경주자를 테스트했습니다:

양자 경주자 (D-Wave QPU): 양자 역학의 기이한 법칙(예: 벽을 통과하는 터널링 현상)을 사용하여 답을 찾아내는 브랜드 뉴한 하이테크 기계입니다.
하이브리드 경주자 (D-Wave Hybrid): 양자 기계가 어려운 부분을 담당하게 하고 나머지는 고전 컴퓨터에 의존하는 똑똑한 팀장입니다.
고전적 경주자 (Simulated Annealing & SBM): 수년간 다듬어진, 검증된 구식 방법들입니다. 이는 매우 숙련되고 체계적인 등산객을 떠올리게 합니다.

경주는 다음과 같이 퍼즐의 크기에 따라 진행되었습니다:

작은 퍼즐 (100 ~ 151개의 점)

이 작은 퍼즐들의 경우, 저자들은 사전에 매우 정밀하고 느린 계산기로 문제를 풀었기 때문에 완벽한 해답(전역 최적해, Global Optimum)을 알고 있었습니다.

결과: 하이브리드 경주자와 고전적 경주자들은 완벽했습니다. 그들은 매번 정확한 답을 찾아냈습니다.
양자 경주자: 비틀거렸습니다. 매우 빨랐지만, 그들이 내놓은 답은 종종 완벽한 답에서 멀리 떨어져 있었습니다. 이는 마치 매우 빠르게 달리지만 자신의 신발 끈에 계속 걸려 넘어지며 결승선을 몇 걸음 놓치는 단거리 선수와 같았습니다.

중간 크기 퍼즐 (250 ~ 500개의 점)

이 퍼즐들은 너무 커서 양자 경주자가 경주에 참여조차 할 수 없었습니다.

결과: 하이브리드 경주자와 고전적 경주자들이 계속해서 압도적인 모습을 보였으며, 과학적으로 알려진 최고의 답들을 찾아냈습니다. 그들은 마치 잘 기름칠 된 기계처럼 매번 목표를 명중시켰습니다.

거대 퍼즐 (800 ~ 10,000개의 점)

이 퍼즐들은 너무 거대해서 아무도 완벽한 답을 알지 못했습니다. 저자들은 이전 연구에서 발견된 "최선의 추측"에 의존해야 했습니다.

결라: 여기서 흥미로운 일이 벌어졌습니다.
- Toshiba SBM(특화된 고전적 기계)과 **느리고 신중한 고전적 경주자(SA2)**가 챔피언이었습니다. 그들은 가장 높은 품질의 솔루션을 찾아내며 다른 모든 이들을 이겼습니다. 하지만 이 "느린" 경주자는 모든 수를 계산하는 체스 그랜드마스터처럼 생각하는 데 오랜 시간이 걸렸습니다.
- 하이브리드 경주자는 품질 면에서 근소한 2위를 차지했지만 훨씬 빨랐으며, Toshiba 기계와 비슷한 시간 안에 경주를 마쳤습니다.
- **빠른 고전적 경주자(SA1)**는 속도는 빨랐지만 품질을 포기했으며, 눈에 띄게 낮은 품질의 솔루션을 찾아냈습니다.
- 양자 경주자는 이 경주를 아예 뛸 수 없었습니다. 퍼즐이 현재의 하드웨어로 감당하기에는 너무 컸습니다.

주요 시사점

속도 vs 정확도: 새로운 양자 기계는 빠르지만, 이러한 특정 퍼즐들에 대해서는 아직 충분히 정확하지 않습니다. 이는 마치 빠르게 달릴 수는 있지만 코너를 잘 돌지 못하는 스포츠카와 같습니다.
"블랙 박스" 문제: 하이브리드 솔버(팀장)는 매우 효과적이며 거대한 퍼즐도 빠르게 처리할 수 있습니다. 그러나 이것은 "블랙 박스"입니다. 연구자들은 내부가 어떻게 작동하는지, 혹은 언제 양자 부분을 사용하는지 정확히 이해할 수 없습니다. 그것은 그저 훌륭한 답을 내놓을 뿐이지만, 그 "방법"은 미스터리로 남아 있습니다.
구식 기술의 저력: 고전적인 방식(Simulated Annealing)은 주의 깊게 조정될 경우, 여전히 최고의 답을 찾는 데 있어 화려한 양자 하드웨어를 앞섭니다. 때로는 빠르고 화려한 방식보다 느리고 신중한 접근 방식(SA2)이 더 나은 결과를 냅니다.

요약하자면: 논문은 양자 기술이 흥미롭고 발전하고 있지만, 현재 이러한 Max-Cut 퍼즐을 해결하는 특정 작업에 있어서는 고전 컴퓨팅과 스마트한 하이브리드 전략의 조합이 순수 양자 기계보다 정확도와 대규모 문제 처리 능력 모두에서 더 뛰어난 성능을 보인다고 결론지었습니다. 양자 기계는 유망한 단거리 선수이지만, 아직 마라톤을 완벽하게 달리는 법을 배우지 못했습니다.

기술 요약: Max-Cut 문제에 대한 양자, 고전 및 하이브리드 솔버의 정확도 및 성능 평가

문제 정의
본 연구는 NP-난해(NP-hard) 문제인 Max-Cut 문제와 그와 동등한 정식화인 이차 무제약 이진 최적화(QUBO) 문제를 다룬다. 목표는 가중치가 있는 무방향 그래프의 정점들을 두 개의 서로 소인 집합으로 분할하여, 두 집합을 연결하는 간선의 가중치 합을 최대화하는 것이다. 본 논문은 다양한 솔버들이 전역 최적해(global optimum)에 근접한 해를 찾는 능력을 평가하며, 대규모 인스턴스의 경우 정확한 해를 찾는 것이 계산적으로 불가능한 경우가 많으므로 근사 휴리스틱이 필요하다는 점을 인정한다.

방법론 및 실험 설정
저자들은 100에서 10,000 사이의 노드 크기를 가진 139개의 문제 인스턴스로 구성된 세 가지 별도의 데이터셋을 사용하여 종합적인 벤치마킹 연구를 수행하였다.

데이터셋:
1. Billionnet 및 Elloumi (be): $n \in \{101, 121, 151\}$ 인 50개의 인스턴스. 전역 최적해는 정확한 솔버인 BiqBin과 MADAM을 사용하여 계산되었다.
2. Beasley 컬렉션 (bqp): $n \in \{251, 501\}$ 인 20개의 인스턴스. $n=251$ 에 대한 최적해는 정확하게 계산되었으며, $n=501$ 의 경우 문헌의 최적 알려진 값(best-known values)을 사용하였다.
3. G-데이터셋 (G): $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$ 인 69개의 인스턴스. 전역 최적해는 알려져 있지 않으며, 문헌의 최적 알려진 값을 벤치마크로 사용하였다.
평가된 솔버:
- 양자 어닐링 (QPU): 큐비트를 환경적 효과로부터 격리하기 위해 "fast annealing" 기능을 사용하는 D-Wave Advantage 시스템. $n \le 151$ 인 인스턴스로 제한됨.
- 하이브리드 솔버: 클래식 방법(중단 가능한 simulated annealing, tabu search, parallel tempering)과 QPU 호출을 반복적으로 결합하는 D-Wave의 클라우드 기반 "LeapHybridSampler". 모든 인스턴스 크기를 처리할 수 있음.
- 고전적 시뮬레이티드 어닐링 (SA): [3]의 두 가지 변형 알고리즘을 구현함:
  - SA1: 공격적인 스텝 사이즈, 초기 온도 10,000 (QPU와 유사한 실행 시간에 최적화됨).
  - SA2: 보수적인 스텝 사이즈, 초기 온도 40,000 (해의 품질에 최적화됨).
- 시뮬레이티드 바이퍼케이션 머신 (SBM): Toshiba의 하드웨어 솔버. 저자들이 솔버에 직접 접근할 수 없었기에 기존 문헌 [4]의 결과를 사용함.

주요 결과

소규모 인스턴스 ( $n \le 151$ ): 하이브리드 솔버와 두 가지 SA 변형(SA1, SA2) 모두 모든 인스턴스에서 전역 최적해를 일관되게 달면했다. 그러나 QPU는 전역 최적해로부터 상당히 떨어진 해를 지속적으로 생성했다.
중규모 인스턴스 ( $n = 251, 501$ ): 하이브리드 솔버와 SA 변형들은 다시 전역 최적해( $n=251$ 의 경우) 또는 최적 알려진 값( $n=501$ 의 경우)과 일치하는 결과를 보였다. QPU는 용량 제한으로 인해 테스트할 수 없었다.
대규모 인스턴스 ( $n \ge 800$ ):
- 해의 품질: SBM과 SA2가 가장 높은 품질의 해를 생성하였으며, 종종 최적 알려진 값을 찾아냈다. 하이브리드 솔버는 SBM 및 SA2보다 눈에 띄게 낮은 성능을 보였으며, SA1은 테스트된 방법 중 가장 낮은 품질의 해를 생성했다.
- 계산 시간: 하이브리드 솔버와 SBM은 효율적인 계산 시간(수 초에서 수십 초)을 보여주었다. SA2는 우수한 해의 품질을 달 Achieve 하기 위해 훨씬 더 많은 시간(수백 초, 일부 비교에서 Hybrid/SBM보다 약 1000배 느림)이 소요되었다. SA1은 하이브리드 솔버와 유사한 실행 시간을 가졌으나 열등한 해를 생성했다.

의의 및 주장
본 논문은 표준화되고 공개적으로 사용 가능한 Max-Cut 인스턴스 세트에서 최첨단 고전적 방법들과 새로운 D-Wave fast annealing QPU 및 하이브리드 솔버를 엄격하게 테스트함으로써 양자 보조 최적화에 대한 이해를 진전시킨다고 주장한다.

저자들은 다음과 같이 결론짓는다:

QPU의 한계: D-Wave QPU는 fast annealing을 사용하더라도 테스트된 인스턴스들에 대해 최적의 해를 찾는 데 실패하며, 문제 크기( $n \le 151$ )에 의해 제한된다.
하이브리드의 효용성: D-Wave 하이브리드 솔버는 속도와 확장성 측면에서 매우 효율적이며(최대 10,000개 노드 처리), 작은 인스턴스에 대해 근사 최적해를 생성한다. 그러나 가장 큰 인스턴스들에 대해서는 해의 품질 면에서 고전적 SA(특히 SA2) 및 SBM에 의해 뒤처진다.
고전적 방법의 경쟁력: 투명한 고전적 시뮬레이티드 어닐링 알고리즘(특히 SA2 변형)은 더 높은 계산 비용에도 불구하고, 해의 품질 면에서 블랙박스 형태인 하이브리드 솔버를 종종 능가하며 매우 경쟁력 있는 성능을 유지한다.
투명성 격차: 저자들은 하이브리드 솔버의 내부 워크플로우와 양자 자원 활용에 대한 통찰력이 부족하여 과학적 분석을 저해한다는 점을 언급하며, 이 "블랙박스" 특성에 대해 불만을 표했다.

본 연구는 특정 솔버와 문제 인스턴스에 대해 양자 우위(quantum advantage)를 주장하지 않는다. 오히려 Max-Cut 문제의 경우, 현재의 고전적 휴리스틱(특히 품질을 위해 튜닝된 경우)과 SBM 같은 특화된 하드웨어가 테스트된 양자 및 하이브리드 접근 방식의 성능을 능가하거나 대등할 수 있음을 강조한다.

작은 퍼즐 (100 ~ 151개의 점)

중간 크기 퍼즐 (250 ~ 500개의 점)

거대 퍼즐 (800 ~ 10,000개의 점)

주요 시사점

유사한 논문