Utility-scale QAOA

Olivia Lanes의 유틸리티 규모 QAOA에 관한 비디오를 시청하거나, YouTube에서 별도 창으로 영상을 열어보세요.

강의 개요:

이 과정에서 지금까지 양자 컴퓨터에서 유틸리티 규모 문제를 해결하는 데 필요한 프레임워크와 도구에 대한 견고한 기초를 제공했기를 바랍니다. 이제 마침내 이러한 도구들을 실제로 작동하는 모습을 보게 될 것입니다.

이 강의에서는 Max-Cut 문제의 유틸리티 규모 예제를 실제로 다뤄봅시다. Max-Cut은 그래프를 두 부분으로 최적으로 분할하는 방법에 관한 그래프 이론의 유명한 문제입니다. 먼저 5개 노드 그래프로 시작하여 양자 컴퓨터가 이 문제를 해결하는 데 어떻게 도움이 될 수 있는지에 대한 직관을 구축한 다음, 이를 유틸리티 규모 버전의 문제에 적용할 것입니다.

이 강의는 이 문제를 해결하기 위해 사용하는 접근 방식의 광범위한 개요가 될 것입니다. 이것은 코드 안내가 아닙니다. 하지만 이 강의를 함께하는 튜토리얼에는 양자 컴퓨터에서 Max-Cut 문제를 해결하기 위해 실행할 수 있는 실제 코드가 있습니다.

문제

상기하시듯이, 모든 계산 문제가 양자 컴퓨팅에 적합한 것은 아닙니다. "쉬운 문제들"은 고전 컴퓨터가 이미 완벽하게 해결할 수 있기 때문에 이 기술로부터 어떤 이점도 얻지 못할 것입니다.

우리가 탐색하기에 가장 낙관적인 세 가지 사용 사례는 다음과 같습니다:

1. 자연 시뮬레이션
2. 복잡한 구조를 가진 데이터 처리
3. 최적화

오늘은 세 번째 사용 사례인 최적화에 초점을 맞춥시다. 최적화 문제에서 우리는 일반적으로 주어진 함수에 대한 최댓값 또는 최솟값을 찾고 있습니다. 고전 방법으로 이러한 극값을 찾는 어려움은 문제 크기가 증가함에 따라 지수적으로 증가할 수 있습니다.

오늘 관심 있는 최적화 문제를 Max-Cut이라고 부르며, 이를 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA)이라는 알고리즘을 사용하여 해결할 것입니다.

Max-Cut이란 무엇인가요?

그래프로 시작합니다. 그래프는 정점(또는 노드) 모음으로 구성되며, 그 중 일부는 간선(Edge)으로 연결됩니다. 문제에서 우리는 간선을 "절단"하여 그래프의 노드를 두 개의 부분 집합으로 나누도록 요청받습니다. 이렇게 절단된 간선의 개수를 최대화하는 분할을 찾고 싶습니다. 따라서 이름이 "Max-Cut"입니다.

예를 들어, 위의 그림은 5개 노드 그래프와 오른쪽의 Max-Cut 솔루션을 보여줍니다. 이는 5개의 간선을 절단하는데, 이것이 이 그래프에서 할 수 있는 최선입니다.

5개 노드 그래프는 매우 작기 때문에 머리로 또는 종이에 몇 가지 절단을 시도하여 Max-Cut을 계산하는 것이 그리 어렵지 않습니다. 하지만 상상할 수 있듯이, 정점 수가 증가하면서 문제는 점점 더 어려워집니다. 일부는 고려할 수 있는 절단의 개수가 노드 수에 대해 지수적으로 증가하기 때문입니다. 그리고 어느 시점에서는 이것이 알려진 고전 알고리즘으로도 슈퍼컴퓨터로 하기 어려워집니다.

우리는 이러한 더 크고 복잡한 그래프에 대해 Max-Cut 문제를 해결하는 방법을 원합니다. 왜냐하면 이 문제는 금융 사기 탐지, 그래프 클러스터링, 네트워크 설계 및 소셜 미디어 분석을 포함한 많은 실제 응용이 있기 때문입니다. Max-Cut은 더 큰 문제에 대한 특정 접근 방식 내에서 부분 문제로 자주 나타납니다. 따라서 우리가 순진하게 생각할 수 있는 것보다 훨씬 더 일반적입니다.

해결책

이제 양자 컴퓨터에서 Max-Cut 문제를 해결하기 위해 사용하는 접근 방식을 자세히 설명할 것입니다. 단순한 5개 노드 그래프로 이를 수행합니다. Python 노트북 튜토리얼을 따라가실 수 있습니다. 이 간단한 예제 이후, 튜토리얼은 문제의 유틸리티 규모 예제를 안내할 것입니다.

첫 번째 단계는 노드 수와 두 노드를 연결하는 간선을 정의하여 그래프를 생성하는 것입니다. 튜토리얼에서 보여주듯이 rustworkx라는 패키지를 가져와서 이를 수행할 수 있습니다. 결과는 다음과 같은 그래프가 될 것입니다:

우리는 Qiskit 패턴 프레임워크를 사용하여 양자 컴퓨터에서 이 그래프에 대한 Max-Cut 솔루션을 찾을 것입니다.

Map (매핑)

문제를 양자 컴퓨터에 매핑해야 합니다. 이를 하기 위해 먼저 그래프에서 절단의 개수를 최대화하는 것을 수학적으로 다음과 같이 쓸 수 있다는 점을 주목합시다:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

여기서 $i$와 $j$는 그래프의 노드이고, $x_i$와 $x_j$는 각 노드가 분할의 어느 쪽에 있는지에 따라 0 또는 1입니다(한 그룹은 "0"로, 다른 그룹은 "1"로 표시됨). $x_i$와 $x_j$가 분할의 같은 쪽에 있을 때, 합의 표현식은 0과 같습니다. 그들이 반대쪽에 있을 때, 즉 그들 사이에 절단이 있을 때, 표현식은 1과 같습니다. 따라서 절단의 개수를 최대화하면 합을 최대화합니다.

또한 이를 뒤집어서 각 값에 음수를 곱하여 최솟값을 찾을 수 있습니다.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

이제 매핑할 준비가 되었습니다. 그려진 그래프 같은 것에서 양자 회로로 어떻게 가는지 생각하는 것이 겁날 수 있습니다. 하지만 우리는 한 번에 한 단계씩 이를 수행합니다.

기억하세요, 우리는 QAOA를 사용하여 Max-Cut을 해결하려고 합니다. QAOA 방법론에서 우리는 궁극적으로 하이브리드 알고리즘의 비용 함수를 나타내는 데 사용될 연산자(다시 말해 해밀턴)를 원하며, 문제에 대한 가능한 해결책을 나타내기 위해 사용할 매개변수화된 회로(ansatz)를 원합니다.

QUBO

이러한 후보 솔루션들에서 표본을 추출한 다음 비용 함수를 사용하여 평가할 수 있습니다. 이를 하기 위해 우리는 이차 제약 없는 이진 최적화 표기법(Quadratic Unconstrained Binary Optimization notation) - 또는 QUBO(줄여서) - 을 포함한 일련의 수학적 재공식화를 활용합니다. QUBO에서 우리는 다음을 찾고 싶습니다:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

여기서 $Q$는 실수의 $n\times n$ 행렬이고, $n$은 우리 그래프의 노드 개수에 해당합니다(여기서는 5입니다).

QAOA를 적용하려면 우리의 문제를 해밀턴으로 공식화해야 합니다. 해밀턴은 시스템의 총 에너지를 나타내는 함수 또는 행렬입니다. 구체적으로, 우리는 기저 상태가 함수의 최솟값에 해당하는 성질을 가진 비용 함수 해밀턴을 만들고 싶습니다. 따라서 우리의 최적화 문제를 해결하려면, 양자 컴퓨터에서 $H$의 기저 상태를 준비하려고 할 것입니다. 그러면 이 상태에서 표본을 추출하면 높은 확률로 $\min f(x)$의 해결책을 얻을 것입니다.

비용 함수 해밀턴으로 매핑

운이 좋게도, QUBO 문제는 물리학에서 가장 유명하고 널리 사용되는 해밀턴 중 하나인 Ising 해밀턴과 매우 밀접하게 관련되어 있으며, 실제로 계산상 동등합니다.

QUBO 문제를 Ising 해밀턴으로 쓰기 위해 우리가 실제로 해야 할 일은 간단한 변수 변환입니다:

$$x_i = \frac{1-z_i}{2}.$$

우리는 여기서 모든 단계를 거치지 않을 것이지만, 그들은 첨부된 노트북에서 설명됩니다. 결국, QUBO 표현식의 최소화는 이 표현식의 최소화와 같습니다:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

다시 조금 다시 쓰면 우리의 비용 함수 해밀턴이 있습니다. 여기서 표현식의 최솟값은 기저 상태를 나타내고, Z는 Pauli Z 연산자이며, $b$는 실수 스칼라 계수입니다:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

이제 해밀턴이 있으므로, 우리의 양자 회로에서 두 개의 큐빗 게이트로 쉽게 변환할 수 있는 2-로컬 Pauli ZZ 연산자로 다시 작성해야 합니다. 우리는 6개의 개체 - 또는 Pauli 문자열 - 을 얻게 될 것입니다. 각각은 그래프의 각 간선에 해당합니다. 문자열의 5개 요소 각각은 노드에 대한 연산을 나타냅니다. 노드가 그 특정 간선에 연결되지 않았으면 항등 연산, 연결되었으면 Pauli Z 연산자입니다. Qiskit에서 큐빗을 나타내는 비트 문자열은 역순으로 인덱싱됩니다. 예를 들어, 노드 0과 1 사이의 간선은 IIIZZ로 인코딩되고, 노드 2와 4 사이의 간선은 ZIZII로 인코딩됩니다.

양자 회로 구성

Pauli 연산자로 작성된 해밀턴을 사용하여 양자 컴퓨터를 사용하여 좋은 해결책을 표본 추출할 수 있는 양자 회로를 구성할 준비가 되었습니다:

QAOA 알고리즘은 단열 정리(Adiabatic Theorem)에서 영감을 받습니다. 이는 시간 의존적 해밀턴의 기저 상태에서 시작하고, 해밀턴이 충분히 천천히 진화하고, 충분한 시간이 주어지면, 최종 상태는 최종 해밀턴의 기저 상태가 될 것이라고 말합니다. QAOA는 양자 단열 알고리즘의 이산, 트로터화된 버전으로 생각할 수 있으며, 각 트로터 스텝은 QAOA 알고리즘의 한 계층을 나타냅니다. 따라서 한 상태에서 다른 상태로 진화하는 대신, 각 계층에서 우리의 비용 함수 해밀턴과 소위 "믹서" 해밀턴(이 강의에서 나중에 다룰 예정) 사이를 앞뒤로 전환합니다.

QAOA의 장점은 양자 단열 알고리즘보다 빠르지만 최적이 아닌 근사 솔루션을 반환한다는 것입니다. 계층 수가 무한대로 갈 때 QAOA는 QAA 경우로 수렴하지만, 물론 이는 계산상 매우 비용이 많이 듭니다.

양자 회로를 생성하려면, $\gamma$와 $\beta$에 의해 매개변수화된 교대 연산자를 적용할 것입니다. 이는 시간 진화의 이산화를 나타낼 것입니다.

따라서 QAOA 회로의 세 가지 주요 부분은:

1. 회색의 초기 시험 상태. 이는 모든 큐빗에 적용된 Hadamard 게이트를 적용하여 생성된 믹서의 기저 상태입니다.
2. 짙은 보라색의 비용 함수 진화. 우리가 이전에 논의했습니다.
3. 밝은 보라색의 믹서 해밀턴 아래의 진화. 우리가 아직 다루지 않았습니다.

우리의 시작 해밀턴은 믹서라고 불리는데, 그 기저 상태는 모든 가능한 비트 문자열의 중첩이기 때문입니다. 따라서 시작 부분에서 가능한 모든 솔루션의 혼합을 강제합니다.

믹서 해밀턴은 그래프의 각 노드에 대한 Pauli-X 연산의 간단한 합입니다. Qiskit은 원하면 다른 사용자 정의 믹서 연산자를 사용할 수 있게 해줍니다. 하지만 우리는 여기서 표준 하나를 사용할 것입니다. 따라서 다시 한 번, Qiskit을 사용하면 믹서 해밀턴과 시작 상태를 생각해내는 많은 작업이 제거되어 자명합니다. 우리가 해야 할 유일한 작업은 비용 함수를 찾는 것입니다.

이러한 연산자의 각 반복을 계층이라고 합니다. 이러한 계층은 이전에 설명한 것처럼 시스템의 시간 진화 이산화로 볼 수 있습니다. 교대 패턴은 트로터 분해에서 나오며 비교환 행렬의 지수 함수를 근사합니다. 일반적으로 우리가 포함하는 계층 또는 스텝 수가 많을수록, 우리는 QAA와 같은 연속 시간 진화에 더 가까워질 것입니다. 따라서 이론상으로 결과는 더 정확할 것입니다. 하지만 이 예제에서는 한 계층으로만 표본을 추출하여 시작합니다. 기억하세요, 비용 함수 해밀턴과 믹서 모두 매개변수화되어 있습니다. 우리는 여전히 $\gamma$와 $\beta$에 대한 최적값을 구해야 합니다.

최적화

우리가 방금 만든 회로는 꽤 단순하고 직관적인 이해를 구축하는 데 유용하지만, 양자 칩은 QAOA 게이트가 무엇인지 이해하지 못합니다. 우리는 이를 하드웨어에서 직접 수행할 수 있는 단일 및 2-큐빗 "네이티브" 게이트의 일련으로 변환해야 합니다. 네이티브 게이트는 큐빗에서 직접 수행할 수 있는 게이트입니다. 이러한 회로는 백엔드의 명령어 집합 구조(Instruction Set Architecture, ISA)로 작성되어 있다고 합니다.

Qiskit 라이브러리는 광범위한 회로 변환을 충족하는 일련의 트랜스필레이션 패스를 제공합니다. 회로가 우리의 목적에 맞게 최적화되어 있는지 확인하고 싶습니다.

이전 강의에서 상기하시듯이, 트랜스필레이션 프로세스는 여러 단계를 포함합니다:

• 회로의 큐빗(즉, 의사결정 변수)을 장치의 물리적 큐빗에 초기 매핑합니다.
• 양자 회로의 명령어를 백엔드가 이해하는 하드웨어 네이티브 명령어로 언롤링합니다.
• 회로에서 상호작용하는 큐빗을 인접한 물리적 큐빗으로 라우팅합니다.

그리고 항상, 이에 대한 더 자세한 내용은 문서에서 찾을 수 있습니다.

트랜스필레이션하기 전에, 우리는 회로를 어느 Backend에서 실행할지 선택해야 합니다. 트랜스필러는 다른 프로세서에 대해 다르게 최적화하기 때문입니다. 이것이 자동 트랜스필러를 사용하는 것이 중요한 또 다른 이유입니다. 실제로는 다른 프로세서에서 회로를 실행하고 싶다는 것을 깨닫기 전에 수동으로 회로를 최적화하는 시간 소비 프로세스를 거치고 싶지 않을 것입니다.

원하는 Backend를 트랜스필러 함수에 전달하고 최적화 수준을 지정합니다. 튜토리얼에서 레벨 3(최상위이고 가장 철저한 수준)을 선택할 것입니다.

그리고 이렇게 우리는 하드웨어에서 실행할 준비가 된 트랜스필된 회로가 있습니다!

실행

지금까지 우리는 gamma와 beta 매개변수를 그대로 두고 회로를 트랜스필했습니다. 하지만 실제로 이 매개변수를 지정하지 않고는 회로를 실행할 수 없습니다. QAOA 워크플로우에서 최적 QAOA 매개변수는 반복 최적화 루프에서 찾아집니다. 우리는 일련의 회로 평가를 실행한 다음 고전 옵티마이저를 사용하여 최적의 β와 γ 매개변수를 찾습니다. 하지만 우리는 어딘가에서 시작해야 하므로 $\gamma=\pi/2$와 $\beta=\pi$의 초기 추정을 합니다.

실행 모드

이제 거의 회로를 실행할 준비가 되었습니다. 약속합니다! 하지만 먼저 작업을 다양한 방식으로 보낼 수 있다는 점을 주목하는 것이 중요합니다. 이를 실행 모드라고 합니다.

• Job 모드: 컨텍스트 관리자 없이 Estimator 또는 Sampler의 단일 Primitive 요청이 이루어집니다. 회로와 입력은 Primitive Unified Blocs(PUBs)로 패키징되고 양자 컴퓨터에서 실행 작업으로 제출됩니다.

• Batch 모드: 독립적인 Job의 번들로 구성된 실험을 효율적으로 실행하기 위한 다중 Job 관리자입니다. Batch 모드를 사용하여 여러 Primitive Job을 동시에 제출합니다.

• Session 모드: 다중 Job 워크로드 실행을 위한 전용 창입니다. 이를 통해 사용자가 더 예측 가능한 방식으로 변이 알고리즘을 실험할 수 있으며, 심지어 여러 실험을 동시에 실행하여 스택의 병렬성을 활용할 수 있습니다. Session을 반복 워크로드 또는 전용 액세스가 필요한 실험에 사용합니다. 예제는 Session에서 Job 실행을 참고하세요.

QAOA 실험의 경우, 액세스 권한이 있다면 Session은 진행하기에 좋은 선택입니다. 최적값을 찾기 위해 다양한 매개변수 값으로 회로를 여러 번 표본 추출해야 하기 때문입니다.

최적화 문제로 돌아갑니다. 우리는 초기 추정치보다 더 나은 gamma와 beta 값을 찾아야 합니다. 우리는 우리의 비용 함수와 이러한 초기 추정값을 scipy 옵티마이저 COBYLA에 대입하여 이를 수행할 것입니다.

여기에서 반복에 따른 비용 함수의 값을 볼 수 있습니다. 처음에는 조금 불규칙하고 위아래로 움직이지만, 그러면 낮은 값으로 안정화됩니다. 우리는 scipy가 찾은 값 중 비용 함수의 최저 평가에 해당하는 값을 사용할 것입니다.

이제 우리의 매개변수에 대한 더 나은 값을 찾아서 비용 함수를 줄일 수 있었습니다. 우리는 gamma와 beta에 대해 찾은 새 값을 사용하여 최적화된 회로를 실행할 것입니다. 나는 여기서 사용하고 있는 구체적인 값을 나열했지만, 기억하세요. 이것을 시도하거나 동일한 튜토리얼 노트북을 다시 실행할 때 이 값들은 약간 변할 수 있습니다. 이제 우리는 이 값들과 함께 최적화된 회로를 실행하고 Max-Cut 문제에 대한 우리의 후보 해결책을 찾을 것입니다.

후처리 단계에서 우리는 데이터를 분석하고 이러한 결과를 표시하여 우리의 양자 알고리즘이 올바른 해결책을 찾았는지 확인합니다.

후처리

이제 최종 솔루션을 보기 위해 데이터의 히스토그램을 그려봅시다:

비트 문자열은 각 노드가 절단에 의해 두 개 그룹(라벨 "0"과 "1")으로 분할된 방식을 나타냅니다. 모두 절단된 간선의 최댓값을 주는 4개의 솔루션이 있어야 합니다. 이 4개는 보라색으로 표시됩니다. 4개의 솔루션이 다른 것보다 훨씬 더 가능성 높다는 것을 바로 볼 수 있습니다. 가장 높고, 따라서 가장 가능성 높은 비트 문자열 솔루션은 0,1,0,1,1입니다. (기억하세요 - 플롯 비트 문자열에서 큐빗의 순서는 역순입니다!)

이 플롯에서 우리는 가장 가능성 높은 비트 문자열을 가져와 5개의 간선이 지나가는 절단이 있는 분할된 그래프로 나타낼 수 있습니다:

따라서 이것은 확실히 Max-Cut 솔루션입니다. 하지만 유일한 것은 아닙니다! 이 그래프의 대칭성 때문에 여러 올바른 솔루션이 있습니다. 노드 0과 3이 절단 안에 있는 대신, 노드 2와 4가 포함될 수 있습니다. 모두 제가 한 것은 절단을 회전하여 이 새 점들을 포함하는 것입니다. 절단된 간선의 수는 5로 유지됩니다. 각 우리가 주목한 두 솔루션이 "반대" 파트너를 가지므로 4개의 Max-Cut 솔루션이 있다는 것으로 나타났습니다. 보라색 노드는 회색이고 회색 노드는 보라색입니다. 절단은 동일하게 유지되지만 각 노드는 사실상 분할의 반대쪽으로 전환됩니다.

히스토그램과 4개의 가장 가능성 높은 솔루션을 다시 한번 봅시다. 이상적으로 이들은 4개의 참인 Max-Cut 솔루션이 될 것입니다. 문제는 알고리즘이 실제로 4번째 최종 솔루션을 상위 4개의 가장 가능성 높은 답변 중 하나로 식별하지 않았다는 것입니다. 5번째로 가능성이 높았습니다. 알고리즘이 식별한 4번째 솔루션은 잘못된 것입니다. 이를 그려본다면, 솔루션이 4개의 절단만 가지고 있다는 것을 알 것입니다.

하지만 기억하세요: 이것은 근사 알고리즘입니다. 그것은 항상 정확하지 않으며, 100% 시간 정확하지 않습니다. 솔루션을 검증하기 위해 자신의 지식과 이해를 어느 정도 사용해야 합니다.

이 오류는 여러 곳에서 발생할 수 있습니다:

1. 알고리즘 자체의 근사 특성일 수 있으며, 내가 사용한 작은 수의 계층입니다.
2. 유한 표본 오류일 수 있습니다. 실험의 표본 수를 증가시키면 이를 줄일 수 있습니다.
3. 또한 읽기 오류일 수 있습니다. 4번째 실제 솔루션은 단 1비트만 다릅니다.

이러한 종류의 오류 분석은 양자 컴퓨팅 실무자가 되기 위해 필요한 것입니다. 하드웨어의 성능과 이것이 특정 유형의 오류에 어떻게 기여할 수 있으며 이를 수정하는 방법을 이해해야 합니다.

그러나 32개의 가능한 비트 문자열이 있었고 4개의 실제 솔루션이 상위 5개의 최고 후보에 포함되었다는 사실을 잊지 맙시다. 그리고 우리는 이를 찾기 위해 2개의 계층만 사용했습니다. 일반적으로, 최고의 Max-Cut을 매번 찾을 기회를 증가시키려면 계층 깊이를 증가시킬 수 있습니다. 이에 대한 몇 가지 미묘함이 있지만, 그것은 나중 강의를 위한 것입니다.

유틸리티 규모에서

양자 컴퓨터에서 작은 Max-Cut 문제를 푸는 과정을 맛본 후, 이를 규모 있게 수행하도록 도전합니다. 연결된 튜토리얼을 따라가서 125-노드 그래프에서 몇 개의 절단을 얻을 수 있는지 확인해보세요.