M3를 사용한 Sampler 프리미티브의 판독 오류 완화

사용 시간 예상: Heron r2 프로세서에서 1분 미만 (참고: 이는 예상치이며, 실제 실행 시간은 다를 수 있습니다.)

배경

Estimator 프리미티브와 달리 Sampler 프리미티브는 오류 완화에 대한 내장 지원이 없습니다. Estimator가 지원하는 여러 방법은 기댓값에 특화되어 있어 Sampler 프리미티브에는 적용할 수 없습니다. 예외적으로 판독 오류 완화는 Sampler 프리미티브에도 적용 가능한 매우 효과적인 방법입니다.

M3 Qiskit 애드온은 판독 오류 완화를 위한 효율적인 방법을 구현합니다. 이 튜토리얼에서는 M3 Qiskit 애드온을 사용하여 Sampler 프리미티브의 판독 오류를 완화하는 방법을 설명합니다.

판독 오류란 무엇인가?

측정 직전 Qubit 레지스터의 상태는 계산 기저 상태의 중첩으로 기술되거나, 밀도 행렬로 기술됩니다. 그런 다음 Qubit 레지스터를 고전 비트 레지스터로 측정하는 과정은 두 단계로 진행됩니다. 첫 번째는 양자 측정 자체를 수행하는 것입니다. 즉, Qubit 레지스터의 상태가 $1$과 $0$의 비트열로 특징지어지는 단일 기저 상태로 투영됩니다. 두 번째 단계는 이 기저 상태를 특징짓는 비트열을 읽어 고전 컴퓨터 메모리에 기록하는 것입니다. 우리는 이 단계를 판독이라고 부릅니다. 두 번째 단계(판독)가 첫 번째 단계(기저 상태로의 투영)보다 더 많은 오류를 발생시킵니다. 이는 판독이 미시적인 양자 상태를 감지하여 거시적 영역으로 증폭시켜야 한다는 점을 생각하면 이해할 수 있습니다. 판독 공진기가 (트랜스몬) Qubit에 결합되어 매우 작은 주파수 이동을 경험합니다. 그런 다음 마이크로파 펄스가 공진기에서 반사되어 그 특성에 작은 변화가 생깁니다. 반사된 펄스는 증폭되어 분석됩니다. 이는 매우 섬세한 과정으로 다양한 오류에 취약합니다.

중요한 점은 양자 측정과 판독 모두 오류에 취약하지만, 후자에서 지배적인 오류인 판독 오류가 발생하며, 이것이 이 튜토리얼의 주제라는 것입니다.

이론적 배경

고전 메모리에 저장된 샘플링된 비트열이 투영된 양자 상태를 특징짓는 비트열과 다를 경우, 판독 오류가 발생했다고 합니다. 이러한 오류는 샘플 간에 무작위적이고 비상관적으로 관찰됩니다. 판독 오류를 _잡음이 있는 고전 채널_로 모델링하는 것이 유용한 것으로 증명되었습니다. 즉, 모든 비트열 쌍 $i$와 $j$에 대해, 진짜 값 $j$가 $i$로 잘못 읽힐 고정된 확률이 있습니다.

더 정확하게는, 모든 비트열 쌍 $(i, j)$에 대해, 진짜 값이 $j$일 때 $i$가 읽힐 (조건부) 확률 ${M}_{i,j}$가 있습니다. 즉,

$${M}_{i,j} = \Pr(\text{readout value is } i | \text{true value is } j) \text{ for } i,j \in (0,...,2^n - 1), \tag{1}$$

여기서 $n$은 판독 레지스터의 비트 수입니다. 구체적으로, $i$는 계산 기저 상태를 표시하는 비트열의 이진 표현을 갖는 십진 정수라고 가정합니다. $2^n \times 2^n$ 행렬 ${M}$을 _할당 행렬_이라고 부릅니다. 고정된 진짜 값 $j$에 대해, 모든 잡음 결과 $i$에 대한 확률의 합은 $1$이 되어야 합니다. 즉

$$\sum_{i=0}^{2^n - 1} {M}_{i,j} = 1 \text{ for all } j$$

(1)을 만족하는 음수가 아닌 항목을 가진 행렬을 _좌확률적_이라고 합니다. 좌확률적 행렬은 각 열의 합이 $1$이기 때문에 _열확률적_이라고도 불립니다. 각 기저 상태 $|j \rangle$를 반복적으로 준비한 다음 샘플링된 비트열의 출현 빈도를 계산하여 각 원소 ${M}_{i,j}$의 근사값을 실험적으로 결정합니다.

실험이 반복 샘플링으로 출력 비트열에 대한 확률 분포를 추정하는 것을 포함한다면, ${M}$을 사용하여 분포 수준에서 판독 오류를 완화할 수 있습니다. 첫 번째 단계는 관심 있는 고정 Circuit을 여러 번 반복하여 샘플링된 비트열의 히스토그램을 만드는 것입니다. 정규화된 히스토그램은 ${\tilde{p}} \in \mathbb{R}^{2^n}$으로 표기하는 $2^n$개의 가능한 비트열에 대한 측정된 확률 분포입니다. 비트열 $i$를 샘플링할 (추정) 확률 ${{\tilde{p}}}_i$는 $i$로 잘못 인식될 확률로 가중된 모든 진짜 비트열 $j$의 합과 같습니다. 이를 행렬 형태로 나타내면

$${\tilde{p}} = {M} {\vec{p}}, \tag{2},$$

여기서 ${\vec{p}}$는 진짜 분포입니다. 즉, 판독 오류는 비트열에 대한 이상적인 분포 ${\vec{p}}$에 할당 행렬 ${M}$을 곱하여 관측된 분포 ${\tilde{p}}$를 생성하는 효과를 가집니다. 우리는 ${\tilde{p}}$와 ${M}$을 측정했지만, ${\vec{p}}$에는 직접 접근할 수 없습니다. 원칙적으로, 회로에 대한 비트열의 진짜 분포를 방정식 (2)를 ${\vec{p}}$에 대해 수치적으로 풀어 얻을 수 있습니다.

계속 진행하기 전에, 이 단순한 접근 방식의 몇 가지 중요한 특징을 짚어볼 필요가 있습니다.

• 실제로는 방정식 (2)를 ${M}$을 역행렬로 풀지 않습니다. 소프트웨어 라이브러리의 선형 대수 루틴은 더 안정적이고 정확하며 효율적인 방법을 사용합니다.
• ${M}$을 추정할 때, 판독 오류만 발생했다고 가정했습니다. 특히, 상태 준비 및 양자 측정 오류가 없거나, 적어도 달리 완화되었다고 가정합니다. 이 가정이 유효한 범위 내에서, ${M}$은 실제로 판독 오류만을 나타냅니다. 그러나 비트열에 대한 측정된 분포를 수정하기 위해 ${M}$을 사용할 때는 이러한 가정을 하지 않습니다. 사실, 흥미로운 Circuit은 예를 들어 Gate 오류와 같은 잡음을 도입할 것으로 예상됩니다. "진짜" 분포에는 달리 완화되지 않은 오류의 효과도 여전히 포함됩니다.

이 방법은 일부 상황에서 유용하지만 몇 가지 한계가 있습니다.

${M}$을 추정하는 데 필요한 공간 및 시간 자원은 $n$에 대해 지수적으로 증가합니다:

• ${M}$과 ${\tilde{p}}$의 추정은 유한 샘플링으로 인한 통계적 오류에 영향을 받습니다. 이 잡음은 더 많은 샷(체계적 오류를 유발하는 드리프트하는 하드웨어 파라미터의 시간 척도까지)을 통해 원하는 만큼 작게 만들 수 있습니다. 그러나 완화 수행 시 관찰된 비트열에 대해 가정을 하지 않는다면, ${M}$을 추정하는 데 필요한 샷 수는 $n$에 대해 최소 지수적으로 증가합니다.
• ${M}$은 $2^n \times 2^n$ 행렬입니다. $n>10$이면, ${M}$을 저장하는 데 필요한 메모리 양이 강력한 노트북에서 사용 가능한 메모리를 초과합니다.

추가적인 한계는:

• 복원된 분포 ${\vec{p}}$에는 하나 이상의 음수 확률이 있을 수 있습니다(합이 여전히 1인 경우에도). 한 가지 해결책은 ${\vec{p}}$의 각 항목이 음수가 아니라는 제약 조건 하에 $||{M} {\vec{p}} - {\tilde{p}}||^2$를 최소화하는 것입니다. 그러나 그러한 방법의 런타임은 방정식 (2)를 직접 푸는 것보다 몇 배나 더 깁니다.
• 이 완화 절차는 비트열에 대한 확률 분포 수준에서 작동합니다. 특히, 개별적으로 관찰된 비트열의 오류는 수정할 수 없습니다.

Qiskit M3 애드온: 더 긴 비트열로 확장

표준 수치 선형 대수 루틴을 사용하여 방정식 (2)를 푸는 것은 약 10비트 이하의 비트열로 제한됩니다. 그러나 M3는 훨씬 더 긴 비트열을 처리할 수 있습니다. 이를 가능하게 하는 M3의 두 가지 핵심 특성은:

• 비트 집합 간의 3차 이상의 판독 오류 상관관계는 무시할 수 있다고 가정하고 무시합니다. 원칙적으로, 더 많은 샷을 사용하면 더 높은 상관관계도 추정할 수 있습니다.
• ${M}$을 명시적으로 구성하는 대신, ${\tilde{p}}$를 구성할 때 수집된 비트열에 대해서만 확률을 기록하는 훨씬 작은 유효 행렬을 사용합니다.

높은 수준에서, 절차는 다음과 같이 작동합니다.

먼저, ${M}$의 단순화된 유효 설명을 구성하는 데 사용할 수 있는 구성 요소를 만듭니다. 그런 다음 관심 있는 Circuit을 반복적으로 실행하여 비트열을 수집하고, 이를 사용하여 ${\tilde{p}}$와 구성 요소의 도움으로 유효한 ${M}$을 구성합니다.

더 정확하게는,

• 각 Qubit에 대해 단일 큐비트 할당 행렬을 추정합니다. 이를 위해 Qubit 레지스터를 전체 영 상태 $|0 ... 0 \rangle$과 전체 일 상태 $|1 ... 1 \rangle$에 반복적으로 준비하고, 각 Qubit가 잘못 읽힐 확률을 기록합니다.

• 3차 이상의 상관관계는 무시할 수 있다고 가정하고 무시합니다.

  대신 $n$개의 $2 \times 2$ 단일 큐비트 할당 행렬과 $n(n-1)/2$개의 $4 \times 4$ 2-Qubit 할당 행렬을 구성합니다. 이 1- 및 2-Qubit 할당 행렬은 나중에 사용하기 위해 저장됩니다.

• ${\tilde{p}}$를 구성하기 위해 Circuit을 반복적으로 샘플링한 후, ${\tilde{p}}$를 구성할 때 샘플링된 비트열만을 사용하여 ${M}$에 대한 유효한 근사를 구성합니다. 이 유효 행렬은 이전 항목에서 설명한 1- 및 2-Qubit 행렬을 사용하여 구축됩니다. 이 행렬의 선형 차원은 최대 ${\tilde{p}}$를 구성할 때 사용된 샷 수의 차수이며, 이는 전체 할당 행렬 ${M}$의 차원 $2^n$보다 훨씬 작습니다.

M3에 대한 기술적 세부 사항은 양자 컴퓨터에서의 측정 오류의 확장 가능한 완화를 참조할 수 있습니다.

양자 알고리즘에 M3 적용

우리는 숨겨진 이동 문제에 M3의 판독 완화를 적용할 것입니다. 숨겨진 이동 문제와 밀접하게 관련된 숨겨진 부분군 문제는 원래 내결함성 설정에서 고안되었습니다(더 정확히 말하면, 내결함성 QPU가 가능하다는 것이 증명되기 전에!). 하지만 현재 사용 가능한 프로세서로도 연구되고 있습니다. 127-큐비트 IBM® QPU에서 숨겨진 이동 문제의 변형에 대해 알고리즘적 지수 속도 향상을 얻은 예는 이 논문 (arXiv 버전)에서 찾을 수 있습니다.

이하에서, 모든 산술은 불리언입니다. 즉, $a, b \in \mathbb{Z}_2 = \{0, 1\}$에 대해, 덧셈 $a + b$는 논리 XOR 함수입니다. 또한, 곱셈 $a \times b$ (또는 $a b$)는 논리 AND 함수입니다. $x, y \in \{0, 1\}^n$에 대해, $x + y$는 비트 단위 XOR 적용으로 정의됩니다. 내적 $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$는 $x \cdot y = \sum_i x_i y_i$로 정의됩니다.

아다마르 연산자와 푸리에 변환

양자 알고리즘을 구현할 때 아다마르 연산자를 푸리에 변환으로 사용하는 것은 매우 일반적입니다. 계산 기저 상태는 때때로 _고전 상태_라고 불립니다. 이들은 고전 비트열과 일대일 대응 관계에 있습니다. 고전 상태에 대한 $n$-Qubit 아다마르 연산자는 불리언 하이퍼큐브에 대한 푸리에 변환으로 볼 수 있습니다:

$$H^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x,y \in {\mathbb{Z}_2^n}} (-1)^{x \cdot y} {|{y}\rangle}{\langle{x}|}.$$

고정 비트열 $s$에 해당하는 상태 ${|{s}\rangle}$를 고려해 봅시다. $H^{\otimes n}$을 적용하고, ${\langle {x}|{s}\rangle} = \delta_{x,s}$를 사용하면, ${|{s}\rangle}$의 푸리에 변환을 다음과 같이 쓸 수 있습니다

$$H^{\otimes n} {|{s}\rangle} = \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

아다마르는 자신의 역원, 즉 $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$입니다. 따라서, 역 푸리에 변환은 동일한 연산자 $H^{\otimes n}$입니다. 명시적으로 나타내면,

$${|{s}\rangle} = H^{\otimes n} H^{\otimes n} {|{s}\rangle} = H^{\otimes n} \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

숨겨진 이동 문제

우리는 _숨겨진 이동 문제_의 간단한 예를 고려합니다. 문제는 함수의 입력에서 일정한 이동을 식별하는 것입니다. 우리가 고려하는 함수는 내적입니다. 이것은 숨겨진 이동 문제에 대해 아래에서 제시하는 것과 유사한 기법을 통해 양자 속도 향상을 허용하는 대형 함수 집합의 가장 단순한 구성원입니다.

$x,y \in {\mathbb{Z}_2^m}$을 길이 $m$의 비트열이라 합시다. ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$을 다음과 같이 정의합니다

$${f}(x, y) = (-1)^{x \cdot y}.$$

$a,b \in {\mathbb{Z}_2^m}$을 길이 $m$의 고정된 비트열이라 합시다. 또한 $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$을 다음과 같이 정의합니다

$$g(x, y) = {f}(x+a, y+b) = (-1)^{(x+a) \cdot (y+b)},$$

여기서 $a$와 $b$는 (숨겨진) 파라미터입니다. $f$를 구현하는 블랙박스와 $g$를 구현하는 블랙박스, 두 개가 주어집니다. 우리는 이들이 위에서 정의한 함수를 계산한다는 것은 알지만, $a$도 $b$도 알지 못한다고 가정합니다. 목표는 $f$와 $g$에 쿼리하여 숨겨진 비트열(이동) $a$와 $b$를 결정하는 것입니다. 이 게임을 고전적으로 플레이하면 $a$와 $b$를 결정하기 위해 $O(2m)$번의 쿼리가 필요합니다. 예를 들어, 한 원소가 전체 0이고 다른 원소가 정확히 하나의 원소가 $1$인 쌍의 모든 문자열 쌍으로 $g$에 쿼리할 수 있습니다. 각 쿼리에서 $a$ 또는 $b$의 하나의 원소를 알 수 있습니다. 그러나 블랙박스가 양자 Circuit으로 구현된다면 $f$와 $g$ 각각에 단 한 번의 쿼리로 $a$와 $b$를 결정할 수 있습니다.

알고리즘 복잡도의 맥락에서, 블랙박스를 _오라클_이라고 합니다. 불투명하다는 것 외에도, 오라클은 입력을 받아 출력을 즉시 생성하여 그것이 내장된 알고리즘의 복잡도 예산에 아무것도 추가하지 않는 특성이 있습니다. 실제로, 우리의 경우 $f$와 $g$를 구현하는 오라클은 효율적임을 알 수 있습니다.

$f$와 $g$를 위한 Quantum Circuit

$f$와 $g$를 양자 Circuit으로 구현하기 위해 다음 재료가 필요합니다.

단일 큐비트 고전 상태 ${|{x_1}\rangle}, {|{y_1}\rangle}$ ($x_1,y_1 \in \mathbb{Z}_2$)에 대해, 제어-$Z$ Gate ${CZ}$는 다음과 같이 쓸 수 있습니다

$${CZ} {|{x_1}\rangle}{|{y_1}\rangle}{x_1} = (-1)^{x_1 y_1} {|{x_1}\rangle}{x_1}{|{y_1}\rangle}.$$

$(x_1, y_1)$에 하나, $(x_2, y_2)$에 하나, 이런 식으로 $(x_m, y_m)$까지 $m$개의 CZ Gate로 작동합니다. 우리는 이 연산자를 ${CZ}_{x,y}$라고 부릅니다.

$U_f = {CZ}_{x,y}$는 ${f} = {f}(x,y)$의 양자 버전입니다:

$$U_f {|{x}\rangle}{|{y}\rangle} = {CZ}_{x,y} {|{x}\rangle}{|{y}\rangle} = (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

비트열 이동도 구현해야 합니다. $x$ 레지스터에 대한 연산자 $X^{a_1}\cdots X^{a_m}$을 $X_a$로, 마찬가지로 $y$ 레지스터에 대해 $X_b = X^{b_1}\cdots X^{b_m}$으로 표기합니다. 이 연산자는 단일 비트가 $1$인 곳에 $X$를 적용하고, $0$인 곳에 항등원 $I$를 적용합니다. 그러면 다음을 얻습니다

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

두 번째 블랙박스 $g$는 유니타리 $U_g$로 구현됩니다:

$$U_g = X_aX_b {CZ}_{x,y} X_aX_b.$$

이를 확인하기 위해, 상태 ${|{x}\rangle}{|{y}\rangle}$에 연산자를 오른쪽에서 왼쪽으로 적용합니다. 먼저

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

그런 다음,

$${CZ}_{x,y} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle}.$$

마지막으로,

$$X^a X^b (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x}\rangle}{|{y}\rangle},$$

이것이 실제로 $f(x+a, y+b)$의 양자 버전입니다.

숨겨진 이동 알고리즘

이제 숨겨진 이동 문제를 풀기 위해 조각들을 맞춥니다. 전체 영 상태로 초기화된 레지스터에 아다마르를 적용하는 것으로 시작합니다.

$$H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

다음으로, 오라클 $g$에 쿼리하여

$$U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{(x+a) \cdot (y+b)} {|{x}\rangle}{|{y}\rangle}$$ $$\approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y + x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

마지막 줄에서 상수 전역 위상 인자 $(-1)^{a \cdot b}$를 생략하고, 위상까지의 등식을 $\approx$로 표기합니다. 다음으로, 오라클 $f$를 적용하면 $(-1)^{x \cdot y}$의 또 다른 인자가 도입되어 이미 있던 것을 취소합니다. 그러면 다음을 얻습니다:

$$U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

최종 단계는 역 푸리에 변환 $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$을 적용하는 것으로, 결과는

$$H^{\otimes 2m} U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx {|{b}\rangle}{|{a}\rangle}.$$

Circuit이 완성되었습니다. 잡음이 없는 경우, 양자 레지스터를 샘플링하면 비트열 $b, a$가 확률 $1$로 반환됩니다.

불리언 내적은 소위 벤트 함수의 예입니다. 여기서 벤트 함수를 정의하지는 않겠지만, "입력의 선형 부분 공간에 대한 출력의 의존성을 이용하려는 공격에 최대한 저항성을 가집니다." 이 인용문은 기사 고도로 비선형인 불리언 함수에 대한 양자 알고리즘에서 가져온 것으로, 여러 종류의 벤트 함수에 대한 효율적인 숨겨진 이동 알고리즘을 제공합니다. 이 튜토리얼의 알고리즘은 기사의 3.1절에 나옵니다.

더 일반적인 경우, 숨겨진 이동 $s \in \mathbb{Z}^n$을 찾는 Circuit은

$$H^{\otimes n} U_{\tilde{f}} H^{\otimes n} U_g H^{\otimes n} {|{0}\rangle}^{\otimes n} = {|{s}\rangle}.$$

일반적인 경우, $f$와 $g$는 단일 변수의 함수입니다. 내적의 예는 $f(x, y) \to f(z)$로 두면 이 형태를 가지며, 여기서 $z$는 $x$와 $y$의 연결이고, $s$는 $a$와 $b$의 연결입니다. 일반적인 경우는 정확히 두 개의 오라클이 필요합니다: $g$에 대한 오라클과 $\tilde{f}$에 대한 오라클, 후자는 벤트 함수 $f$의 _쌍대_로 알려진 함수입니다. 내적 함수는 자기 쌍대 속성 $\tilde{f}=f$를 가집니다.

내적에 대한 숨겨진 이동 Circuit에서 우리는 일반적인 경우의 Circuit에 나타나는 중간 레이어의 아다마르를 생략했습니다. 일반적인 경우에는 이 레이어가 필요하지만, 출력이 원하는 ${|{a}\rangle}{|{b}\rangle}$ 대신 ${|{b}\rangle}{|{a}\rangle}$이라는 약간의 후처리 비용으로 깊이를 조금 줄였습니다.

요구 사항

이 튜토리얼을 시작하기 전에 다음이 설치되어 있는지 확인하세요:

• Qiskit SDK v2.1 이상 (시각화 지원 포함)
• Qiskit Runtime v0.41 이상 (pip install qiskit-ibm-runtime)
• M3 Qiskit addon v3.0 (pip install mthree)

설정

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib mthree qiskit qiskit-ibm-runtime

from collections.abc import Iterator, Sequence
from random import Random
from qiskit.circuit import (
    CircuitInstruction,
    QuantumCircuit,
    QuantumRegister,
    Qubit,
)
from qiskit.circuit.library import CZGate, HGate, XGate
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import QiskitRuntimeService
import timeit
import matplotlib.pyplot as plt
from qiskit_ibm_runtime import SamplerV2 as Sampler
import mthree

1단계: 고전적 입력을 양자 문제로 매핑하기

먼저, 은닉 이동(hidden shift) 문제를 QuantumCircuit으로 구현하는 함수를 작성합니다.

def apply_hadamards(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply a Hadamard gate to every qubit."""
    for q in qubits:
        yield CircuitInstruction(HGate(), [q], [])

def apply_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply X gates where the bits of the shift are equal to 1."""
    for i, q in zip(range(shift.bit_length()), qubits):
        if shift >> i & 1:
            yield CircuitInstruction(XGate(), [q], [])

def oracle_f(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply the f oracle."""
    for i in range(0, len(qubits) - 1, 2):
        yield CircuitInstruction(CZGate(), [qubits[i], qubits[i + 1]])

def oracle_g(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply the g oracle."""
    yield from apply_shift(qubits, shift)
    yield from oracle_f(qubits)
    yield from apply_shift(qubits, shift)

def determine_hidden_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Determine the hidden shift."""
    yield from apply_hadamards(qubits)
    yield from oracle_g(qubits, shift)
    # We omit this layer in exchange for post processing
    # yield from apply_hadamards(qubits)
    yield from oracle_f(qubits)
    yield from apply_hadamards(qubits)

def run_hidden_shift_circuit(n_qubits, rng):
    hidden_shift = rng.getrandbits(n_qubits)

    qubits = QuantumRegister(n_qubits, name="q")
    circuit = QuantumCircuit.from_instructions(
        determine_hidden_shift(qubits, hidden_shift), qubits=qubits
    )
    circuit.measure_all()
    # Format the hidden shift as a string.
    hidden_shift_string = format(hidden_shift, f"0{n_qubits}b")
    return (circuit, hidden_shift, hidden_shift_string)

def display_circuit(circuit):
    return circuit.remove_final_measurements(inplace=False).draw(
        "mpl", idle_wires=False, scale=0.5, fold=-1
    )

간단한 예제로 시작해 보겠습니다:

n_qubits = 6
random_seed = 12345
rng = Random(random_seed)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

display_circuit(circuit)

Hidden shift string 011010

2단계: 양자 하드웨어 실행을 위한 Circuit 최적화

job_tags = [
    f"shift {hidden_shift_string}",
    f"n_qubits {n_qubits}",
    f"seed = {random_seed}",
]
job_tags

['shift 011010', 'n_qubits 6', 'seed = 12345']

# Uncomment this to run the circuits on a quantum computer on IBMCloud.
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=100
)

# from qiskit_ibm_runtime.fake_provider import FakeMelbourneV2
# backend = FakeMelbourneV2()
# backend.refresh(service)

print(f"Using backend {backend.name}")

def get_isa_circuit(circuit, backend):
    pass_manager = generate_preset_pass_manager(
        optimization_level=3, backend=backend, seed_transpiler=1234
    )
    isa_circuit = pass_manager.run(circuit)
    return isa_circuit

isa_circuit = get_isa_circuit(circuit, backend)
display_circuit(isa_circuit)

Using backend ibm_kingston

3단계: Qiskit 프리미티브를 사용하여 Circuit 실행하기

# submit job for solving the hidden shift problem using the Sampler primitive
NUM_SHOTS = 50_000

def run_sampler(backend, isa_circuit, num_shots):
    sampler = Sampler(mode=backend)
    sampler.options.environment.job_tags
    pubs = [(isa_circuit, None, NUM_SHOTS)]
    job = sampler.run(pubs)
    return job

def setup_mthree_mitigation(isa_circuit, backend):
    # retrieve the final qubit mapping so mthree knows which qubits to calibrate
    qubit_mapping = mthree.utils.final_measurement_mapping(isa_circuit)

    # submit jobs for readout error calibration
    mit = mthree.M3Mitigation(backend)
    mit.cals_from_system(qubit_mapping, rep_delay=None)

    return mit, qubit_mapping

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

Step 4: 고전적 형식으로 결과를 후처리하고 반환하기

위의 이론적 논의에서, 입력 $ab$에 대해 출력 $ba$를 예상한다고 확인했습니다. 추가적인 복잡성은, 더 단순한(사전 트랜스파일된) Circuit을 갖기 위해 인접한 Qubit 쌍 사이에 필요한 CZ 게이트를 삽입했다는 점입니다. 이는 비트 문자열 $a$와 $b$를 $a1 b1 a2 b2 \ldots$와 같이 교차 배열하는 것과 같습니다. 출력 문자열 $ba$도 유사한 방식으로 교차 배열됩니다: $b1 a1 b2 a2 \ldots$. 아래의 unscramble 함수는 출력 문자열을 $b1 a1 b2 a2 \ldots$에서 $a1 b1 a2 b2 \ldots$로 변환하여 입력 문자열과 출력 문자열을 직접 비교할 수 있게 합니다.

# retrieve bitstring counts
def get_bitstring_counts(job):
    result = job.result()
    pub_result = result[0]
    counts = pub_result.data.meas.get_counts()
    return counts, pub_result

counts, pub_result = get_bitstring_counts(job)

두 비트 문자열 사이의 해밍 거리(Hamming distance)는 비트가 다른 인덱스의 수입니다.

def hamming_distance(s1, s2):
    weight = 0
    for c1, c2 in zip(s1, s2):
        (c1, c2) = (int(c1), int(c2))
        if (c1 == 1 and c2 == 1) or (c1 == 0 and c2 == 0):
            weight += 1

    return weight

# Replace string of form a1b1a2b2... with b1a1b2a1...
# That is, reverse order of successive pairs of bits.
def unscramble(bitstring):
    ps = [bitstring[i : i + 2][::-1] for i in range(0, len(bitstring), 2)]
    return "".join(ps)

def find_hidden_shift_bitstring(counts, hidden_shift_string):
    # convert counts to probabilities
    probs = {
        unscramble(bitstring): count / NUM_SHOTS
        for bitstring, count in counts.items()
    }

    # Retrieve the most probable bitstring.
    most_probable = max(probs, key=lambda x: probs[x])

    print(f"Expected hidden shift string: {hidden_shift_string}")
    if most_probable == hidden_shift_string:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their probabilities:")
    display(
        {
            k: (v, hamming_distance(hidden_shift_string, k))
            for k, v in sorted(
                probs.items(), key=lambda x: x[1], reverse=True
            )[:10]
        }
    )

    return probs, most_probable

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'011010': (0.9743, 6),
 '001010': (0.00812, 5),
 '010010': (0.0063, 5),
 '011000': (0.00554, 5),
 '011011': (0.00492, 5),
 '011110': (0.00044, 5),
 '001000': (0.00012, 4),
 '010000': (8e-05, 4),
 '001011': (6e-05, 4),
 '000010': (6e-05, 4)}

M3를 사용한 판독 오류 완화를 적용하기 전에 가장 확률이 높은 비트 문자열의 확률을 기록해 둡시다.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

이제 M3가 학습한 판독 보정을 카운트에 적용합니다. apply_corrections 함수는 준확률 분포(quasi-probability distribution)를 반환합니다. 이는 합이 $1$이 되는 float 객체의 목록입니다. 단, 일부 값은 음수일 수 있습니다.

def perform_mitigation(mit, counts, qubit_mapping):
    # mitigate readout error
    quasis = mit.apply_correction(counts, qubit_mapping)

    # print results
    most_probable_after_m3 = unscramble(max(quasis, key=lambda x: quasis[x]))

    is_hidden_shift_identified = most_probable_after_m3 == hidden_shift_string
    if is_hidden_shift_identified:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their quasi-probabilities:")
    topten = {
        unscramble(k): f"{v:.2e}"
        for k, v in sorted(quasis.items(), key=lambda x: x[1], reverse=True)[
            :10
        ]
    }
    max_probability_after_M3 = float(topten[most_probable_after_m3])
    display(topten)

    return max_probability_after_M3, is_hidden_shift_identified

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'011010': '1.01e+00',
 '001010': '8.75e-04',
 '001000': '7.38e-05',
 '010000': '4.51e-05',
 '111000': '2.18e-05',
 '001011': '1.74e-05',
 '000010': '6.42e-06',
 '011001': '-7.18e-06',
 '011000': '-4.53e-04',
 '010010': '-1.28e-03'}

M3 보정 적용 전후의 숨겨진 시프트 문자열 식별 비교

def compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
):
    is_probability_improved = (
        max_probability_after_M3 > max_probability_before_M3
    )
    print(f"Most probable probability before M3: {max_probability_before_M3}")
    print(f"Most probable probability after M3: {max_probability_after_M3}")
    if is_hidden_shift_identified and is_probability_improved:
        print("Readout error mitigation effective! 😊")
    else:
        print("Readout error mitigation not effective. ☹️")

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.9743
Most probable probability after M3: 1.01
Readout error mitigation effective! 😊

M3에 필요한 CPU 시간이 샷 수에 따라 어떻게 확장되는지 플롯하기

# Collect samples for numbers of shots varying from 5000 to 25000.
shots_range = range(5000, NUM_SHOTS + 1, 2500)
times = []
for shots in shots_range:
    print(f"Applying M3 correction to {shots} shots...")
    t0 = timeit.default_timer()
    _ = mit.apply_correction(
        pub_result.data.meas.slice_shots(range(shots)).get_counts(),
        qubit_mapping,
    )
    t1 = timeit.default_timer()
    print(f"\tDone in {t1 - t0} seconds.")
    times.append(t1 - t0)

fig, ax = plt.subplots()
ax.plot(shots_range, times, "o--")
ax.set_xlabel("Shots")
ax.set_ylabel("Time (s)")
ax.set_title("Time to apply M3 correction")

Applying M3 correction to 5000 shots...
	Done in 0.003321983851492405 seconds.
Applying M3 correction to 7500 shots...
	Done in 0.004425413906574249 seconds.
Applying M3 correction to 10000 shots...
	Done in 0.006366567220538855 seconds.
Applying M3 correction to 12500 shots...
	Done in 0.0071477219462394714 seconds.
Applying M3 correction to 15000 shots...
	Done in 0.00860048783943057 seconds.
Applying M3 correction to 17500 shots...
	Done in 0.010026784148067236 seconds.
Applying M3 correction to 20000 shots...
	Done in 0.011459112167358398 seconds.
Applying M3 correction to 22500 shots...
	Done in 0.012727141845971346 seconds.
Applying M3 correction to 25000 shots...
	Done in 0.01406092382967472 seconds.
Applying M3 correction to 27500 shots...
	Done in 0.01546052098274231 seconds.
Applying M3 correction to 30000 shots...
	Done in 0.016769016161561012 seconds.
Applying M3 correction to 32500 shots...
	Done in 0.019537431187927723 seconds.
Applying M3 correction to 35000 shots...
	Done in 0.019739801064133644 seconds.
Applying M3 correction to 37500 shots...
	Done in 0.021093040239065886 seconds.
Applying M3 correction to 40000 shots...
	Done in 0.022840639110654593 seconds.
Applying M3 correction to 42500 shots...
	Done in 0.023974396288394928 seconds.
Applying M3 correction to 45000 shots...
	Done in 0.026412792038172483 seconds.
Applying M3 correction to 47500 shots...
	Done in 0.026364430785179138 seconds.
Applying M3 correction to 50000 shots...
	Done in 0.02820305060595274 seconds.

Text(0.5, 1.0, 'Time to apply M3 correction')

플롯 해석하기

위 플롯은 M3 보정을 적용하는 데 필요한 시간이 샷 수에 비례하여 선형적으로 증가함을 보여줍니다.

규모 확장하기

n_qubits = 80
rng = Random(12345)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

Hidden shift string 00000010100110101011101110010001010000110011101001101010101001111001100110000111

isa_circuit = get_isa_circuit(circuit, backend)

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

counts, pub_result = get_bitstring_counts(job)

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': (0.50402,
  80),
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': (0.0396,
  79),
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': (0.0323,
  79),
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': (0.01936,
  79),
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': (0.01432,
  79),
 '00000010100110101011101110010001010000110011101001101010101001011001100110000111': (0.0101,
  79),
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': (0.00924,
  79),
 '00000010100110101011101110010001010000010011101001101010101001111001100110000111': (0.00908,
  79),
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': (0.00888,
  79),
 '00000010100110101011101110010001010000110011101001100010101001111001100110000111': (0.0082,
  79)}

올바른 숨겨진 이동 문자열이 발견되었음을 확인할 수 있습니다. 또한 다음으로 확률이 높은 아홉 개의 비트 문자열은 단 한 위치에서만 틀렸습니다. 가장 높은 확률을 기록합니다:

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.50402

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': '9.85e-01',
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': '6.84e-03',
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': '3.87e-03',
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': '3.42e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': '3.30e-03',
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': '3.28e-03',
 '00000010100010101011101110010001010000110011101001101010101001111001100110000111': '2.62e-03',
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': '2.43e-03',
 '00000010100110101011101110010000010000110011101001101010101001111001100110000111': '1.73e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001000110000111': '1.63e-03'}

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.54348
Most probable probability after M3: 0.99
Readout error mitigation effective! 😊

결과는 판독 오류가 오류의 주된 원인이었으며 M3 완화가 효과적이었음을 보여줍니다.