⚛️ quantum physics

From Circuits to Hardware: Benchmarking Standard and Qubit-Efficient Quantum Optimization on Real Hardware

이 논문은 IBM Heron 프로세서를 사용하여 네 가지 NP-난해 문제에 걸친 다양한 게이트 기반 양자 최적화 알고리즘의 포괄적인 실제 하드웨어 벤치마크를 제시하며, 현재의 노이즈 수준이 대부분의 실행 가능한 결과를 무작위 확률과 구별할 수 없게 만든다는 점과 큐비트 효율적인 방법들이 실행 가능한 인스턴스 크기를 확장시키기는 하지만 엄격한 경험적 충실도 예산에 의해 여전히 제약을 받는다는 점을 밝히고 있다.

원저자: Monit Sharma, Hoong Chuin Lau

게시일 2026-07-14

📖 6 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Monit Sharma, Hoong Chuin Lau

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

당신이 아주 새롭고 매우 부서지기 쉬운 로봇 팔을 이용해 거대하고 엉클어진 퍼즐을 풀려고 노력하고 있다고 상상해 보세요. 당신에게는 여러 가지 전략이 있습니다. 어떤 것들은 퍼즐 전체를 한꺼번에 잡으려 하고, 어떤 것들은 퍼즐을 주머니에 들어갈 정도로 작게 줄이려 하며, 또 어떤 것들은 시작하기도 전에 조각들을 재배치하려고 합니다. 이 논문은 실제 양자 컴퓨터(로봇 팔)를 사용하여 단순히 컴퓨터 화면 속에서 흉내 내는 것이 아니라, 네 가지 매우 다른 유형의 퍼즐에 대해 이 로봇 팔들을 대상으로 진행한 거대한 실전 스트레스 테스트와 같습니다.

실제 하드웨어에 이 전략들을 적용했을 때 어떤 일이 일어났는지 알려드릴게요.

핵심 요약: "주머니 속 퍼즐"의 함정

주요 발견은 일종의 현실 자각 타임입니다. 오랫동안 사람들은 양자 컴퓨터에서 어려운 문제를 푸는 가장 좋은 방법이 문제를 더 작은 수의 '큐비트'(로봇의 손가락)에 맞게 작게 만드는 것이라고 생각했습니다. 그 아이디어는 이랬습니다: 손가락이 적을수록 = 풀기 쉽다.

하지만 이 논문은 이것이 항상 사실은 아니라는 점을 시사합니다. 문제를 줄이는 것(큐비트 효율적인 방식)이 더 큰 문제를 기계에 담을 수 있게 해주기는 하지만, 그것이 반드시 좋은 답을 보장하는 것은 아닙니다. 실제로 문제를 줄이면 로봇 팔이 노이즈 때문에 너무 흔들려서 조각들을 통째로 떨어뜨릴 수도 있습니다. 저자들은 실제 IBM Heron 프로세서에서 이를 측정했으며, 단순히 적은 큐비트를 사용한다고 해서 반드시 더 잘 작동하는 것은 아니라는 점을 발견했습니다. 이것은 마치 무거운 상자를 아주 작은 배낭에 담아 옮기려는 것과 같습니다. 배낭은 작지만, 상자가 너무 무거우면 결국 당신의 등은 버티지 못하고 상자를 떨어뜨리게 될 것입니다.

네 가지 퍼즐: 네 가지 문제의 이야기

연구진은 네 가지 서로 다른 유형의 "NP-hard" 문제(일반 컴퓨터로도 풀기 매우 어렵다는 뜻입니다)를 테스트했습니다. 각 문제는 서로 다르게 반응했습니다.

다차원 배낭 문제 (MDKP): 배낭 여행을 떠나는데, 짐들이 무게도 있고 부피도 차지하며 특정 칸에 꼭 들어가야 하는 상황을 상상해 보세요.
- 결과: 이 문제는 "적절한 중간 지점"이었습니다. 큰 문제부터 아주 작게 압축된 문제까지 모든 방식이 실제로 어떠한 유효한 해답이라도 찾아내는 데 성공했습니다. 압축된 방식(PCE 및 QRAO)이 여기서 잘 작동했는데, 이는 문제를 줄이는 것이 도움이 될 수 있음을 증명합니다. 단, 로봇 팔이 충분히 안정적일 때만 그렇습니다.
최대 독립 집합 (MIS): 파티를 열려고 하는데, 최대한 많은 손님을 초대하고 싶지만, 서로 적대 관계인 두 명은 같이 앉을 수 없는 상황을 상상해 보세요.
- 결과: 이 문제는 "절벽"이었습니다. 작은 파티에서는 로봇들이 아주 잘 해냈습니다. 하지만 파티가 커지자마자 로로봇들은 갑자기 작동을 멈췄습니다. 논문은 날카로운 "실행 가능성 절벽(feasibility cliff)"을 보여줍니다. 문제가 약간만 커져도 실제 하드웨어의 노이즈 때문에 유효한 손님 명단을 아예 찾을 수 없게 됩니다. 마치 허리케인 속에서 카드 집을 쌓으려는 것과 같습니다. 카드가 몇 장일 때는 괜찮지만, 어느 순간 퍽 하고 모든 것이 무너져 버립니다.
이차 할당 문제 (QAP): 10명 또는 12명의 사람을 10개 또는 12개의 책상에 배치해야 하는데, 비용은 사람들이 얼마나 멀리 떨어져 있는지, 그리고 서로 대화를 나누는지에 따라 달라지는 상황입니다.
- 결과: 이 문제는 "완전한 실패"였습니다. 논문은 실제 하드웨어에서 이 문제에 대해 테스트된 어떤 방식도 단 하나의 유효한 해답도 반환하지 못했다고 명시적으로 밝히고 있습니다. 왜일까요? 규칙이 너무 엄격해서(특정한 순열을 요구함) 유효한 답이 극도로 희귀하기 때문입니다(가능한 배치 중 약 $10^{23}$ 에서 $10^{34}$ 개 중 하나만이 정답입니다). 컴퓨터의 노이즈가 신호를 완전히 덮어버려서 로봇들은 그냥 무작위로 찍고 있는 수준이었습니다. 저자들은 이것이 단순히 "더 좋은 컴퓨터가 필요하다"는 차원의 문제가 아니라, 문제 구조 자체가 현재 기술로는 너무 밀도가 높다고 주장합니다.
시장 점유율 문제 (MSP): 피자를 나누는데, 모든 사람이 주문한 정확한 조각 크기를 가져가도록 나누는 상황을 상상해 보세요.
- 결과: 이 문제는 "압축의 역설"이었습니다. 압축된 방식(PCE 및 QRAO)은 문제를 단 7~11개의 큐비트로 아주 작게 줄였지만, 일반적인 방식은 최대 156개의 큐비트가 필요했습니다. 그런데 반전은, 이 작은 방식들의 결과가 형편없었다는 점입니다. 그들은 목표치를 맞추지 못했습니다. 오히려 일반적인 더 큰 방식들이 더 나은 결과를 냈습니다. 이는 문제를 작게 만드는 것이 자동으로 더 좋은 답을 보장하지 않는다는 것을 증명합니다.

"노이즈" 요인: 로봇이 흔들릴 때

논문은 컴퓨터가 얼마나 흔들리는지 측정하는 멋진 방법을 소개합니다. 그들은 이를 "충실도 프록시(fidelity proxy, $F_{est}$ )"라고 부릅니다. 이것은 "신호 대 잡음비" 측정기와 같습니다.

측정값이 높으면(약 0.1 또는 10%), 로봇이 명령을 들을 수 있을 만큼 안정적이라는 뜻입니다.
측정값이 0.001(0.1%) 미만으로 떨어지면, 로봇이 너무 흔들려서 그냥 제자리에서 헛돌고 있는 상태라는 뜻입니다.

저자들은 많은 "QAOA" 스타일의 방식(인기 있는 알고리즘 제품군)에 대해, 로봇이 너무 흔들려서 그 결과가 그냥 무작위로 답을 고르는 것과 구별할 수 없는 수준이라는 것을 발견했습니다. 논문은 로봇의 출력을 균등 무작위 추측(uniform random guess)과 비교하는 대조 실험을 수행했습니다. 대부분의 크고 복잡한 회로에서 로봇은 무작위 추측보다 나은 모습을 보이지 못했습니다. 실제로 한 특정 사례에서는 "웜 스타트(warm-start)" 방식이 무작위보다 약간 더 나은 결과를 보였지만, 이는 예외적인 경우일 뿐 일반적인 규칙은 아니었습니다.

이 논문이 제외하는 것들 (Rule Out)

저자들은 자신들이 발견하지 못한 것에 대해서도 매우 신중하게 언급합니다.

그들은 "적은 큐비트 = 더 나은 성능"이라는 아이디어를 부정합니다. 데이터를 보면 문제를 줄이는 것이 오히려 다른 문제(예: 변환 후 더 깊어지는 회로)를 유발하여 이점을 상쇄한다는 것을 알 수 있습니다.
그들은 현재의 QAOA 방식들이 이러한 어려운 문제들에 투입될 준비가 되었다는 생각을 부정합니다. 컴퓨터가 명령을 자신의 언어로 번역(컴파일/트랜스파일)한 후에, 회로는 너무 거대하고 노이즈가 심해져서 제대로 작동하지 않습니다. 설령 라우팅(로봇의 손가락이 움직이는 경로)을 최적화하더라도, 회로는 여전히 너무 흔들려서 작동하기 어려울 것입니다.
그들은 시뮬레이션 결과(완벽한 컴퓨터에서 흉내 내는 것)가 전체 이야기를 다 해준다는 생각을 부정합니다. "완벽한 시뮬레이션"과 "실제 하드웨어" 사이의 간극은 매우 큽니다. 시뮬레이션에서는 좋아 보이는 방식이라도, 이를 실제로 작동시키기 위해 필요한 추가 단계들 때문에 실제 하드웨어에서는 처참하게 실패할 수 있습니다.

얼마나 확신하나요?

저자들은 자신들이 측정한 내용에 대해 매우 확신하고 있습니다. 그들은 단순히 추측한 것이 아니라, 실제 IBM Heron 프로세서(r1 및 r2 버전)를 사용하여 247개의 서로 다른 방법과 문제 조합을 테스트했습니다. 그들은 코드가 어떻게 번역되었는지부터 최종 결과에 이르기까지 모든 단계를 기록했습니다.

그들은 로봇이 수행해야 하는 정확한 게이트(단계)의 수를 측정했습니다.
그들은 사용된 특정 칩의 오류율을 측정했습니다.
기준점을 잡기 위해 일부 부분은 시뮬레이션했지만, 시뮬레이션 결과는 단지 참조용일 뿐 최종 답변이 아님을 분명히 했습니다.

그들은 양자 컴퓨터가 쓸모없다고 주장하는 것이 아닙니다. 그들은 이러한 특정 문제들과 현재의 특정 기계들에 대해서는 "크기를 줄이는" 전략에 한계가 있으며, QAP와 같은 일부 문제는 현재 너무 어렵다는 것을 말하고 있습니다. 그들은 단순히 큐비트 개수만 셀 것이 아니라, 문제의 크기, 노이즈, 그리고 코드가 어떻게 번역되는지 등 전체적인 그림을 봐야 한다고 제안합니다.

호기심 많은 십 대를 위한 요약

양자 최적화를 노이즈가 심한 방에서 메시지를 전달하는 과정이라고 생각해 보세요.

"표준적인" 방식은 메시지 전체를 명확하게 크게 외치는 것입니다. 소리는 크지만, 방이 너무 크면 노이즈에 묻혀버립니다.
"압축된" 방식은 암호화된 메시지를 작게 속삭이는 것입니다. 조용하고 좁은 공간에 딱 맞지만, 암호가 너무 복잡하거나 방이 너무 시끄러우면 아무도 해독할 수 없고 그냥 횡설수설하는 소리가 되어버립니다.

이 논문은 이렇게 말합니다: "이봐요, 속삭이는 것이 항상 정답은 아니에요! 때로는 방이 너무 시끄러워서 최고의 암호라도 길을 잃을 수 있습니다. 그리고 QAP처럼 정말 까다로운 퍼즐의 경우, 현재의 로봇들에게는 방이 너무 시끄러워서 도저히 풀 수 없는 곳입니다."

저자들은 포기하라고 말하는 것이 아닙니다. 그들은 "문제를 작게 만들었다고 해서 해결된 것이라고 착각하지 마세요. 노이즈, 번역 과정, 그리고 실제 결과라는 전체적인 혼란스러운 상황을 살펴봐야 진짜 무엇이 작동하고 있는지 알 수 있습니다"라고 말하고 있는 것입니다.

제목: 회로에서 하드웨어까지: 실제 하드웨어에서의 표준 및 큐비트 효율적 양자 최적화 벤치마킹

저자: Monit Sharma 및 Hoong Chuin Lau
출판: IOP Publishing (Journal of Quantum Science and Technology, 출간 예정)

문제 정의

양자 최적화 알고리즘의 급격한 발전에도 불구하고, 이 분야에는 다양한 클래스의 고전적으로 어려운 조합 최적화 문제들을 통일된 프로토콜에 따라 여러 알고리즘 계열과 비교하는 광범위한 실하드웨어 벤치마크가 부족하다. 기존의 평가들은 단일 문제 클래스, 단일 알고리즘 계열, 또는 컴파일 오버헤드, 큐비트 연결성, 게이트 노이즈, 실행 가변성과 같은 실제적인 제약 조건을 고려하지 못하는 시뮬레이터 기반 설정에 국한되는 경우가 많다. 결과적으로, 서로 다른 전략(표준 변분법 vs. 큐비트 효율적 인코딩)이 실제 장치에 매핑되었을 때 어떻게 비교되는지, 또는 큐비트 효율적 정식화가 명목상의 폭(width) 감소 이상의 진정한 실질적 이점을 제공하는지 판단하기가 어렵다.

방법론

저자들은 탄소성 레벨-2(resilience-level-2) 완화 기술이 적용된 IBM Heron r1 및 r2 프로세서(초전도 트랜스몬 장치) 상에서 수행된 하드웨어 인식 벤치마킹 연구를 제시한다. 이 연구는 네 가지 NP-난해(NP-hard) 조합 문제 클래스에 대해 게이트 기반 양자 최적화 방법을 평가한다:

다차원 배낭 문제 (MDKP): 패킹 유형의 제약 조건.
최대 독립 집합 (MIS): 그래프 기반의 독립 구조.
이차 할당 문제 (QAP): 조밀하고 강하게 결합된 이차 할당.
시장 점유율 문제 (MSP): 애플리케이션 중심의 균형 제약 조건.

테스트된 알고리즘 계열:

변분 에너지 최소화: 변분 양자 고유값 솔버(VQE) 및 조건부 가치 위험 VQE (CVaR-VQE).
QAOA 스타일: 표준 QAOA, 웜 스타트 QAOA (WS-QAOA), 다중 각도 QAOA (MA-QAOA).
큐비트 효율적 인코딩: 파울리 상관관계 인코딩 (PCE) 및 양자 무작위 액세스 최적화 (QRAO).

실험 프로토콜:

워크플로우: 모든 문제는 이차 페널티를 사용하여 이차 무제약 이진 최적화(QUBO) 형태로 변환된 후, Ising 해밀토니안으로 매핑되었다.
실행: 본 연구는 실제 하드웨어 상에서 고정된 샷(fixed-shot) 변분 최적화 프로토콜(COBYLA 옵티마이저, 200회 반복, 평가당 1,000 샷)을 활용하였다.
지표: 벤치마크는 솔루션 품질(최적성 격차 또는 목표 편차), 실행 가능성, 알고리즘 수준의 회로 폭, 트랜스파일된 회로 깊이, 2-큐비트 게이트 수( $N_{2Q}$ ), 컴파일 오버헤드, 실행 견고성을 보고한다.
충실도 모델링: 신호 보존 실행 영역과 노이즈 지배 실행 영역을 구분하기 위해 백엔드 교정 데이터로부터 독립적인 에러 게이트 수 충실도 프록시( $F_{est} \approx (1 - \epsilon_{2Q})^{N_{2Q}}$ )를 도출하였다.

주요 기여

통합된 교차 계열 벤치마크: 공통된 실험 프로토콜 하에서 네 가지 구조적으로 구별되는 NP-난해 문제들에 대해 변분, QAOA 스타일, 큐비트 효율적 방법들을 평가하는 최초의 통합 벤치마크이다.
하드웨어 인식 평가: 이상적인 자원 추정에서 벗어나 컴파일 오버헤드, 트랜스파일된 회로 특성, 실행 견고성을 주요 벤치마크 차원으로 취급하는 프로토콜로 전환하였다.
정량적 노이즈 임계값: 노이즈 지배 실행으로의 전이를 나타내는 경험적 근거 기반 충실도 임계값( $F_{est} \approx 0.1$ , Heron-r2 기준 약 770개의 2-큐비트 게이트에 해당)을 확립하였다.
재현 가능한 베이스라인: 소프트웨어 스택, 백엔드 메타데이터, 트랜스파일 정책 및 인스턴스별 진단을 포함하는 완전히 재현 가능한 경험적 베이스라인을 제공하며, 모든 코드와 인스턴스는 공개되어 있다.

주요 결과

MDKP (균형 잡힌 영역): 모든 방법 계열이 실행 가능한 솔루션을 반환했다. 큐비트 효율적 방법(PCE, QRAO)은 큐비트 요구 사항을 크게 줄였으나, 솔루션 품질 면에서 풀-폭(full-width) 방법들을 일관되게 능가하지는 못했다. CVaR-VQE는 특정 인스턴스에서 강력한 성능을 보였다.
MIS (실행 가능성 절벽): 인스턴스 크기가 증가함에 따라 급격한 실행 가능성 붕괴가 관찰되었다. 작은 인스턴스들은 격차 없이 해결되었으나, 더 큰 인스턴스(64+ 큐비트)에서는 대부분의 방법에서 실행 가능성이 붕괴되었으며, 테스트된 가장 큰 그래프에서는 Warm-Start QAOA만이 실행 가능성을 유지했다.
QAP (구조적 장벽): 테스트된 어떤 하드웨어 방법도 QAP 인스턴스에 대해 실행 가능한 할당을 반환하지 못했다. 조밀한 상호작용, 엄격한 원-핫(one-hot) 제약 조건, 그리고 극도로 희소한 실행 가능 다양체( $10!/2^{100} \approx 10^{-23.54}$ )의 결합은 가장 작은 인스턴스에 대해서도 현재의 하드웨어에서 모든 테스트된 파이프라인을 실행 불가능하게 만들었다.
MSP (압축 대 품질): 큐비트 효율적 인코딩은 극적인 폭 감소(7~~11 큐비트 대 48~~156 큐비트)를 달로 달성했으나, 풀-폭 방법들에 비해 현저히 낮은 솔루션 품질(큰 목표 편차)을 초래했다.
컴파일 오버헤드: 트랜스파일은 문제 계열 전반에 걸쳐 2-큐비트 게이트 수를 4.5배에서 6.2배까지 증가시켰다. QAOA 계열 회로의 경우, 트랜스파일된 2-큐비트 수는 종종 20,000개를 초과하여 $F_{est}$ 를 $10^{-30}$ 미만으로 떨어뜨렸다.
노이즈 지배: 일치된 균등 무작위 제어(matched uniform-random control) 결과, 저충실도 QAOA 계열 실행( $F_{est} < 10^{-3}$ )에서 대부분의 실행 가능한 결과가 경험적 무작위 범위 내에 존재했으며, 이는 신호가 노이즈에 의해 지배되고 있음을 시사한다.
시뮬레이터-하드웨어 간극: 시뮬레이터의 순위가 하드웨어로 일관되게 전이되지 않았다. 일부 MDKP 사례에서는 하드웨어 실행이 시뮬레이터보다 낮은 격차를 달성하기도 했으나(유한한 샷의 확률적 특성 때문일 수 있음), 다른 경우에는 하드웨어 성능이 크게 저하되었다.

의의 및 주장

본 논문은 고전적 솔버에 대한 실질적인 양자 우위를 주장하는 것이 아니다. 대신, 현실적인 제약 조건 하에서의 양자 최적화를 평가하기 위한 체계적인 경험적 베이스라인을 구축하는 것을 목적으로 한다.

큐비트 수는 충분하지 않음: 본 연구는 큐비트 수(압축을 통한)가 낮다고 해서 반드시 최종 성능의 향상으로 이어지지는 않는다는 것을 입증한다. 폭 감소를 통한 이점은 종종 트랜스파일 오버헤드, 증가된 유효 회로 깊이, 또는 견고성 저하에 의해 상쇄된다.
문제 의존적 생존 가능성: 실질적인 성능은 문제 구조, 인코딩 선택, 그리고 하드웨어 제약 사이의 상호작용에 크게 의존한다. 한 문제 클래스(예: MDKP)에서 경쟁력 있는 방법이 다른 클래스(예: QAP)에서는 완전히 실패할 수 있다.
컴파일을 제1의 지표로: 양자 최적화 방법의 정체성은 트랜스파일 이후 실질적으로 변화한다. 벤치마크는 배포 가능성을 온전히 보여주기 위해 단순히 알고리즘 수준의 폭뿐만 아니라 트랜스파일된 회로 특성(깊이, $N_{2Q}$ )을 보고해야 한다.
충실도 임계값: 도출된 $F_{est}$ 임계값은 실행 가능한 가이드를 제공하며, 현재의 하드웨어가 깊은 QAOA 회로 및 조밀한 할당 문제에 대해 노이즈 지배 상태일 가능성이 높음을 나타내어, 양자 방법이 신뢰성 있게 테스트될 수 있는 영역을 제한한다.

저자들은 근시일 내의 벤치마킹이 단일한 "최고" 알고리즘을 찾는 것보다 트레이드오프(폭 대 품질, 알고리즘 설계 대 컴파일 비용)를 특징짓는 데 집중해야 하며, 실질적 이점에 대한 주장은 시뮬레이터 결과나 명목상의 큐비트 수가 아닌, 하드웨어로 구현된 솔루션 품질과 실행 진단에 의해 뒷받침되어야 한다고 결론짓는다.