조건과 검사
부호 상태를 , 이라 하자. 이 증명에서는 본문의 를 순서대로 1, 2, 3번 큐비트라고 부른다. 오류는 중 하나라고 가정한다. 검사 연산자는 , 이다.
두 부호 기저 상태는 모두 두 검사의 고윳값이 +1이다. 따라서 임의의 논리 중첩도 같은 고윳값을 갖는다. 여기서 측정하는 것은 개별 큐비트의 값이 아니라 두 큐비트의 홀짝성(패리티)이다.
A: 학회 사전 표제 확인 · B: 기관 전문 문헌의 용례 확인 · C: 문맥에 따른 편집 선택. C 항목을 공식 권고라고 주장하지 않는다.
| 원어·개념 | 채택한 표현 | 근거 |
|---|---|---|
| disjunctive normal form | 논리합 표준형 | A |
| rank (matrix) | 행렬의 계수(rank) | A |
| trace | 대각합 | A |
| normalizer | 정규화 부분군 | A |
| centralizer | 중심화 부분군 | A |
| genus | 종수 | A |
| singular value | 특잇값 | C |
| singular value decomposition | 특잇값분해 | C |
| orthonormal basis | 정규직교기저 | A |
| normalization | 정규화 | A |
| sample | 표본 | A |
| Abelian group | 가환군 | A |
| coherence | 결맞음 | B |
| fidelity | 충실도 | B |
| recovery | 복구 | C |
| partial trace | 부분 대각합 | C |
| promise | 사전 조건(promise) | C |
| generator (group) | 생성원 | C |
| generator (continuous transformation) | 생성자 | C |
| quiescent state | 검사 고윳값이 유지되는 상태 | C |
rank의 계수는 오역이 아니다. coefficient와 혼동되는 곳에 원어를 병기한다. 생성원과 생성자, 검출·정정·복호화·복구도 구별한다. 본문에서는 한국어 음역을 쓰되 참고문헌의 원문 인명과 제목은 유지한다.
대한수학회 수학용어와 ETRI 전문 문헌을 대조했다. 한국물리학회 용어집의 개별 표제 전체는 이번 환경에서 직접 확인하지 못했으므로 모든 선택을 학회 공식 표준이라고 표시하지 않는다.
상세 결정표와 변경 기록은 배포 묶음의 KOREAN_TERMINOLOGY.md와 editorial/에 있다.
KMS-RANK · KMS-NORMAL · KMS-CENTRAL · KMS-SVD · ETRI-FT · ETRI-COMM
선행 개념: 파울리 연산자 · 사영 측정 · 세 큐비트 반복 부호
부호 상태를 , 이라 하자. 이 증명에서는 본문의 를 순서대로 1, 2, 3번 큐비트라고 부른다. 오류는 중 하나라고 가정한다. 검사 연산자는 , 이다.
두 부호 기저 상태는 모두 두 검사의 고윳값이 +1이다. 따라서 임의의 논리 중첩도 같은 고윳값을 갖는다. 여기서 측정하는 것은 개별 큐비트의 값이 아니라 두 큐비트의 홀짝성(패리티)이다.
같은 큐비트의 와 는 반가환하고, 서로 다른 큐비트의 연산자는 가환한다. 따라서 이며, 오류별 결과는 다음과 같다.
| 오류 | ||
|---|---|---|
| +1 | +1 | |
| −1 | +1 | |
| −1 | −1 | |
| +1 | −1 |
예를 들어 의 두 항은 모두 신드롬 (−1,−1)을 갖는다. 측정 결과에서 와 를 알아낼 수 없으므로 이 측정은 두 논리 성분을 구별하지 않는다.
신드롬 에 대한 사영 연산자는
이다. 주어진 오류 에 대해 이고 다른 결과의 확률은 0이다. 신드롬에 해당하는 를 다시 적용하면 에 의해 원래 상태를 복구한다.
이 계산은 위 네 오류에 대한 증명이다. 두 비트 반전은 한 비트 반전과 신드롬이 겹칠 수 있고, 위상 반전은 이 검사로 구별하지 못한다. 따라서 일반적인 단일 큐비트 오류까지 정정한다는 결론은 나오지 않는다.
선행 개념: 해밍 거리 · 최소 거리
서로 다른 부호어가 적어도 두 개 있는 이진 부호의 최소 해밍 거리를 라 하자. 오류 검출은 수신 문자열이 부호 집합에 속하는지 검사하는 방식으로 한다.
부호어 에 1개 이상 개 이하의 비트 반전이 일어나 가 되었다면 이다. 가 다른 부호어라면 최소 거리의 정의에 모순이므로 오류를 검출한다. 반면 거리 인 두 부호어 사이를 옮기는 오류는 이 검사로 검출하지 못한다.
최대 개의 반전을 항상 정정하려면 각 부호어를 중심으로 한 반지름 의 해밍 구가 서로 겹치지 않아야 한다. 와 의 구가 에서 겹치면 삼각 부등식으로
이다. 따라서 이면 최근접 부호어가 유일하며 정확히 복구한다.
반대로 이면 거리 인 두 부호어를 골라, 서로 다른 개 위치 중 일부는 첫 부호어에서 나머지는 둘째 부호어에서 취한다. 그러면 두 부호어와의 거리가 각각 , 인 문자열을 만들 수 있다. 둘 다 이하이므로 유일한 복구가 불가능하다. 최대 보장치는 이다.
선행 개념: 등거리 사상 · 정규직교 기저 · 기저 완성
유한차원 공간 , 사이의 등거리 사상 가 를 만족한다고 하자. 입력 공간을 안에 넣는 등거리 사상 도 하나 고른다. 보여야 할 것은 인 위의 유니타리 가 존재한다는 사실이다.
의 정규직교 기저 에 대해 와 는 각각 정규직교 집합이다. 이는 에서 바로 따른다.
두 정규직교 집합을 각각 의 정규직교 기저 , 으로 완성한다. 처음 개는 , 로 둔다. 정규직교 집합을 기저로 완성할 수 있다는 유한차원 선형대수 결과를 사용한다.
각 입력 기저에 대해 이므로 선형성에 의해 이다. 같은 계에 환경을 붙이는 채널 모형에서는 로 잡는다. 입력·출력 차원이 다르면 두 공간을 담을 만큼 공간을 확장한 뒤 같은 논증을 적용한다. 이는 존재 증명이며 효율적인 회로 구성을 보장하지 않는다.
15절 QE02에서 쓰는 등거리 부호화 ()는 에 대해 첫 큐비트를 제어로 하는 CNOT 두 개로 구현된다.
곧 를 만족하는 유니타리 확장의 하나는 이다. 보조 큐비트가 이 아닌 입력에서 가 하는 일은 가 정하지 않으며, 위의 기저 완성은 그 자유를 뜻한다.
선행 개념: 정화 · 스펙트럼 분해 · 등거리 사상
, 이라 하자. 의 정화 에 대해 로 둔다. 축약 상태가 라는 조건에서
를 얻는다. 고윳값이 0인 방향의 성분은 노름이 0이므로 없고, 이다. 다른 정화도 같은 의 고유기저에서 로 쓸 수 있다.
는 들이 생성하는 공간에서 내적을 보존한다. 따라서
같은 고윳값이 여러 번 나타나도 에서 하나의 정규직교 고유기저를 고정했으므로 논증은 그대로 성립한다. 이 보조계 전체에서 등거리 사상일 필요는 없다. 더 큰 보조계 쪽으로 기저를 완성하면 전체 등거리 사상으로 확장할 수 있고, 차원이 같으면 유니타리로 확장할 수 있다. 필요하면 보조 공간을 먼저 추가한다.
따라서 정화의 자유도는 정화 계의 변환에 있다. 의 축약 상태를 바꾸는 자유도라는 뜻은 아니다.
선행 개념: 밀도 행렬의 고윳값 · 폰 노이만 엔트로피 ·
차원 밀도 행렬의 양의 고윳값을 이라 하자. , 이며, 밑 2의 엔트로피는 이다. 고윳값이 0인 항은 으로 처리한다.
은 에서 등호가 성립한다. 이는 를 미분하면 이므로 에서 최솟값 0을 갖는다는 사실로 확인할 수 있다.
각 양의 고윳값에 대해 을 대입하고 를 곱하여 더하면
왼쪽은 이므로 이다. 등호가 성립하려면 이고 모든 에 대해 이어야 한다. 따라서 최대 엔트로피 상태는 이다.
이 증명은 단일 상태의 차원 상한을 보인다. 결합 상태의 준가법성 는 별도의 정리이며 여기서 증명한 것이 아니다.
선행 개념: 최대 얽힘 모형 · 부분 대각합 · 벨 사영
HP07의 차원 규약 와 지정한 계산 기저를 사용한다. 는 , 는 , 는 , 은 의 기저 지표이며, 프라임이 붙은 지표도 같은 범위를 갖는다. 행렬 성분은 이고, 차원 와 지표 는 문맥으로 구별한다. 은 Bob의 지표다. 세 벨 상태의 정규화 계수는 이다. 따라서 복호 회로 직후 전체 순수 상태의 진폭은
이 단계에서는 을 측정하지 않았다. 와 를 서로 독립인 상태로 바꾸지 않는다.
를 적용하면 가 되고, 남은 를 합한다.
반면 원래 상태에서 와 에 대해 부분 대각합을 취하면
따라서 계의 순열을 제외하면 이며, 노름 제곱은 이다.
이라 하자. 의 부분 대각합을 먼저 펼치면
괄호 안은 HP17c의 다. 한편 Bob의 지표를 , 로 쓰면 두 사영의 성분은
이다. 여기서 와 은 각각 와 의 지표(), 는 의 지표(), 는 의 지표()다. 는 에르미트이므로 오른쪽 인자는 이다. 두 의 벨 계수 과 의 벨 계수 이 곱해진다. 에서 , 로 놓고 , 에 대해 더하면 가운데에 가 남으므로
두 식은 합이 같고 계수만 다르다. 따라서 다. 이는 정해진 에 대한 항등식이며 하르 평균을 취하지 않았다.
이 단계의 는 반복 횟수이며 앞 단계의 지표와 다르다. 복호 회로 직후의 전체 상태 를 Bob 쪽 슈미트 분해로 쓰면 이다. 와 는 각각 정규직교이고, 셋째 단계의 에 의해 는 의 고유벡터(고윳값 )이며 다. 이므로 이고, 이면
이다. 따라서 블록 들은 서로 직교하고, 반복 는 각 블록 안에서 따로 회전한다(HP17a–HP17b).
블록 에서 라 하면 이고, HP17b의 회전에서
이다. 인 1차원 블록은 , 로 두면 같은 식이 성립한다. 가 정규직교이므로 회 뒤의 성공 확률은
이다. 이면 으로 HP17d의 성공 확률과 같다.
완전 소거에서는 모든 가 이므로(HP17d) 모든 블록의 배율이 같다.
곧 증폭 뒤의 성공 성분은 사후 선택한 성공 성분과 방향이 같고 크기만 다르다. 정규화하면 같은 상태이므로 성공한 출력과 조건부 충실도는 HP16–HP17의 사후 선택과 같고, 성공 확률만 에서 로 바뀐다. 각도가 블록마다 다르면 배율도 달라 성공 성분의 방향이 바뀌므로 이 결론을 그대로 쓸 수 없다.
선행 개념: 크라우스 표현과 대각합 보존 · 부호 공간과 직교 사영 · 양의 연산자 · 스펙트럼 정리
부호 공간의 정규직교 기저 에서 정정 조건 는 와 같다. 인 성분이 0이므로 서로 다른 논리 기저 상태는 오류 뒤에도 직교한다. 인 성분이 모든 에서 같으므로, 두 성질을 합치면 모든 정규화된 부호 상태에서 이다. 그래서 오류를 가려내는 측정의 확률은 논리 상태에 의존하지 않고, 측정은 논리 상태의 계수를 알아내지 않는다.
인 식만으로는 부족하다. 유니타리 오류들에서는 인 식이 늘 로 성립하여 각 오류를 혼자서는 되돌릴 수 있다. 하나의 복구로 여러 오류를 정정하게 하는 것은 인 교차항 조건이다. 예를 들어 비트 반전 부호에서 와 은 각각 인 식을 만족하지만, 는 논리 여서 의 배수가 아니다. 두 오류는 신드롬이 같지만 논리 작용이 다르다(O24b).
유한차원에서 부호 공간의 직교 사영을 , 잡음 채널을 , 라 하자. 부호 상태는 를 만족한다.
모든 부호 상태에 대해 인 하나의 CPTP 복구 채널이 존재할 필요충분조건은
이다. 먼저 복구가 존재하면 이 조건이 필요함을 보이고, 이어 조건으로부터 복구를 구성한다. 는 입력 상태에 의존하지 않는 복소수다. 이 증명은 유한차원 CPTP 사상의 크라우스 표현을 사용한다.
복구의 크라우스 연산자를 라 하자. 이며 합성 채널의 크라우스 연산자는 다. 정규화된 부호 벡터 에 대해 정확한 복구는
를 뜻한다. 와 직교하는 임의의 벡터 로 양쪽 기댓값을 취하면
각 항이 음이 아니므로 모두 0이다. 따라서 각각의 는 와 평행하거나 영벡터다. 서로 다른 방향의 성분이 상쇄되어 순수 상태가 되는 것은 아니다.
하나의 를 고정하고 라 쓰자. 부호의 정규직교 기저에서 다. 서로 다른 두 기저 벡터의 중첩에도 앞의 결론을 적용하면
는 와 평행해야 한다. 두 기저 성분을 비교하면 다. 따라서 논리 입력과 무관한 수 가 존재하여
이다. 부호 공간이 1차원이면 이 결론은 바로 성립한다. 기저 상태뿐 아니라 그 중첩까지 복구해야 한다는 요구가 같은 배수를 강제한다.
복구 채널이 대각합을 보존하므로 오류곱 사이에 를 넣을 수 있다.
따라서 로 두면 정정 조건을 얻는다. 필요성의 증명에서 정정 조건을 미리 가정하지 않았다.
이제 정정 조건을 가정한다. 임의의 복소 벡터 와 정규화된 부호 상태에 대해
이므로 는 양의 준정부호다. 로 대각화하고 로 두면
첫 식은 , 둘째 식은 를 전개하여 얻는다. 에 대해 라 두면
서로 다른 오류 공간은 직교한다. 이면 이므로 그 항은 부호 입력에 기여하지 않는다.
양의 고윳값에 대해 로 두면
채널의 완비성에서 이다. 여기서 는 정규화된 부호 벡터이고, 는 조건의 대각 성분이다. 따라서 모든 부호 상태에 대해
아직 이므로 여공간의 작용을 보충한다. 그 공간의 정규직교 기저를 , 고정된 정규화 부호 벡터를 이라 하고 을 추가하면
부호 입력의 잡음 출력은 오류 공간들의 합 안에 있으므로 추가 항은 그 출력에 작용하지 않는다. 이로써 하나의 CPTP 복구 채널을 구성했고, 필요성과 충분성의 증명이 모두 끝났다. 본문의 D15–D16은 이 구성의 오류 공간과 측정 해석을 다시 보여 준다.
A12 정리 상자의 마지막 문장을 증명한다. 을 잡음 을 정정하는 임의의 복구 채널이라 하고, 그 크라우스 연산자를 라 하자. 필요성 2에서 보았듯이 모든 에 대해 이다. 이제 계수 가 논리 상태와 무관한 를 크라우스 연산자로 갖는 다른 잡음 채널 을 생각하자. 이 채널이려면 도 성립해야 한다. 선형성으로
따라서 모든 부호 상태 에 대해
이다. 과 이 모두 대각합을 보존하므로 양변의 대각합을 비교하면 괄호 안은 1이고, 이다. 곧 을 정정하는 복구는 계수가 무엇이든 도 정정하므로, 계수마다 복구를 새로 고를 필요가 없다. 예를 들어 을 정정하는 비트 반전 부호의 복구는 작은 회전 오류도 그대로 정정한다(뒤의 A13에서 계산한다).
선행 개념: 복소 내적 · 정규직교 기저 · 유한차원 단위 구면의 콤팩트성
에르미트 행렬 에 대해 는 실수다. 수 하나의 수반은 복소켤레이므로 에서 이기 때문이다. 유한차원 단위 구면은 콤팩트하므로 연속함수 가 최댓값 를 갖는 단위벡터 가 존재한다. 여기서는 연속함수가 콤팩트 집합에서 최댓값을 갖는다는 기초 해석학 결과를 사용한다.
에 직교하는 단위벡터 를 잡고 를 대입한다. 에서 미분값이 0이므로 이다. 대신 를 넣으면 허수부도 0이다. 따라서 의 에 직교하는 성분은 없고 다.
이면 이다. 따라서 의 직교 여공간은 에 대해 불변이며, 그곳으로 제한한 도 에르미트다. 같은 논증을 차원이 1이 될 때까지 반복하면 정규직교 고유기저를 얻는다.
모든 에서 인 에르미트 행렬을 양의 준정부호라 한다. 이런 행렬이면 각 고윳값은 이다. 거꾸로 모든 고윳값이 0 이상이면 이므로, 이 정의는 모든 고윳값이 0 이상이라는 B13의 정의와 같다.
임의의 복소 행렬 에 대해 는 인 에르미트 행렬이고, 이므로 양의 준정부호다. 양의 고윳값을 , 대응하는 정규직교 고유벡터를 라 두고 로 정의한다.
영 고윳값 방향에서는 이므로 이다. 따라서 다. 두 정규직교 집합을 각각 기저로 완성하면 를 얻는다. 는 비음수 를 대각에 두고 나머지를 0으로 채운 행렬이다. 이것이 슈미트 분해에서 사용하는 SVD의 존재 증명이다.
이므로 모든 는 들의 선형 결합이고, 거꾸로 각 는 의 상에 있다. 따라서 의 상, 곧 모든 의 집합은 들이 생성하는 공간이다. 정규직교 벡터는 선형 독립이므로(에 를 곱하면 ) 이 공간의 차원은 의 개수, 곧 0이 아닌 특잇값의 개수다.
행렬의 계수, 곧 선형 독립인 열의 최대 개수는 열들이 생성하는 공간인 상의 차원이다. 그러므로 계수는 0이 아닌 특잇값의 개수와 같다. O04a에서 이 사실로 곱상태를 판정한다.
선행 개념: 유한 확률분포 · 조건부 엔트로피 ·
유한 확률분포 에 대해 라 두자. 인데 이면 로 정한다. 그 밖에는 에 를 대입하여
을 얻는다. 첫 부등식의 등호는 모든 양의 에서 일 때만 성립하고, 둘째 등호는 나머지 위치의 가 모두 0일 때 성립한다. 그러므로 이며 과 는 동치다.
상호정보량의 엔트로피 표현을 전개하면
인 곳에서는 두 주변 확률도 양수다. 앞의 결과를 결합분포 와 곱분포 에 적용하면 이고, 등호는 모든 에서 일 때만 성립한다. 이것이 독립성이다.
유한 고전 조건부 엔트로피는 확률분포 엔트로피의 평균이므로 음이 아니다. 따라서 이며 를 바꾸면 도 얻는다. 개별 관측에서가 아니라 평균에서 성립하는 주장이다.
값이 개인 확률분포 와 균등분포 에 첫 단계의 결과를 적용하면
이다. 따라서 이고, 등호는 가 균등분포일 때만 성립한다. 이면 이진 엔트로피가 이고 등호는 일 때다. C03과 C04의 용량 계산에서 이 이 결과다. 조건부 엔트로피 도 각각 이하이므로 그 평균 도 이하다.
선행 개념: 완전 양성 · 부분 대각합 · 양의 행렬의 스펙트럼 분해
유한차원 선형 사상 와 입력 기저를 고정한다. 는 정규화하지 않는다. 다음 블록 행렬을 정의한다.
완전 양성의 정의를 이 양의 입력에 적용하면 이다. 역방향은 의 각 벡터를 연산자로 다시 배열하여 증명한다.
이면 스펙트럼 분해로 라 쓸 수 있다. 고윳값의 제곱근을 벡터에 포함했다. 로 전개하고 로 정의한다.
이는 의 블록을 비교한 식이다. 행렬 단위가 연산자 공간의 기저이므로 모든 에 대해 가 성립한다.
임의의 보조계 와 에 대해
각 항이 양의 연산자이므로 크라우스 표현은 완전 양성을 보장한다. 따라서 , 완전 양성, 크라우스 표현의 존재가 서로 동치다. 영벡터를 제외한 크라우스 연산자는 최대 개면 충분하다.
대각합의 순환성을 쓰면 다. 모든 행렬 단위에 대해 이 값이 와 같을 조건은 이다. 한편
따라서 대각합 보존과 도 동치다. 정규화된 벨 입력을 사용하면 우변이 이 된다는 점에 주의한다. 두 조건을 결합하면 채널의 Choi 판정과 크라우스 표현 정리가 모두 성립한다.
선행 개념: 스펙트럼 분해 · 로그 함수의 오목성 · 부분 대각합
먼저 이 증명에서 사용할 양자 상대 엔트로피(quantum relative entropy)를 정의한다. 유한차원 정규화 상태에 대해 이면 여기서 지지 공간은 양의 고윳값에 대응하는 고유벡터들이 생성하는 공간이다. 자연로그를 사용하고 영고윳값의 기여는 극한으로 정한다. 지지 포함 조건이 성립하지 않으면 값은 다. 밑 2의 정의는 이 값을 로 나눈 것이다.
유한차원 정규화 상태를 , 라 하자. 먼저 의 지지에서 계산하고, 의 지지가 그 밖으로 나가면 상대 엔트로피를 로 정한다. , 로 두면
이것은 스칼라 로그의 오목성이다. 따라서
마지막 부등식은 을 에 대입하고 더하여 얻는다. 도 사용했다. 로그 오목성은 미분 에서 따른다.
이면 마지막 로그 부등식에서 모든 에 대해 이고 나머지 는 0이다. 엄격한 로그 오목성의 등호 조건은, 고정된 에서 인 모든 가 와 같다는 것이다. 따라서 다. 나머지 기저 방향에서는 양성과 에 의해 가 0으로 작용한다.
결국 다. 반대로 두 상태가 같으면 정의식이 0이다. 비가환 상태에서도 이 등호 조건이 성립하며, 대각 성분만 같다는 주장보다 강하다.
결합 상태 의 지지는 두 축약 상태의 지지의 텐서곱에 포함된다. 예를 들어 의 영고윳값에 대응하는 고유벡터 방향의 확률은 0이고, 양성 때문에 결합 상태에도 그 방향의 성분이 없다. 지지 공간에서
곱 고유기저에서 고윳값의 로그를 전개한 식이다. 부분 대각합의 정의를 적용하면
왼쪽의 비음성은 엔트로피 준가법성을, 등호 조건은 를 준다. 부분계 엔트로피 각각이 0이어야 한다는 조건은 아니다.
선행 개념: 2×2 유니타리 행렬 · 행렬식 · 회전 게이트
이 되도록 실수 를 택하고 라 두면 이다. 의 첫 열을 라 하면, 직교하는 단위 둘째 열은 위상을 제외하고 뿐이다. 행렬식이 1이라는 조건이 그 위상을 고정한다.
회전의 관례를 다음과 같이 정한다.
의 첫 열은
에서 , 를 만족하는 를 택한다. 가 모두 0이 아니면 , 를 풀면 된다. 하나가 0이면 남은 위상 조건만 맞추고 자유로운 각은 임의로 정한다.
첫 열과 행렬식이 같으므로 두 행렬은 같다. 따라서 다. 특별한 각에서 분해가 유일하지 않은 것도 이 구성에서 드러난다.
선행 개념: SLD 정의 · 힐베르트–슈미트 내적 · 코시–슈바르츠 부등식 · 고전 크라메르–라오 하한
매끄럽고 계수가 일정한 한 모수 상태족을 고정하고 의 표기를 생략한다. 에 직접 의존하지 않는 POVM 에 대해 , 이다. , 라 두고 행렬 내적에 코시–슈바르츠 부등식을 적용하면
이면 이다. 확률이 0이 되는 점에서 극한값으로 정한 항도 같은 부등식을 만족한다. 그 점에 다가가는 동안 인 곳에서는 위 부등식이 성립하고, 계수가 일정하면 양변이 연속이기 때문이다. 모든 에 대해 더하면 다.
고정한 에서 의 스펙트럼 사영 를 측정하면 이므로 다. 따라서 이 점에서 로 상한을 달성한다. 측정은 에서 정한 뒤 미분 동안 고정한다.
독립 준비 의 SLD는 각 복사본 의 합이다. 이므로 서로 다른 복사본의 교차항이 사라져 QFI는 다. 고전 크라메르–라오 하한과 결합하면 공동 측정을 허용해도 이다. 최적 측정의 점별 존재가 미지의 전체에 대한 하나의 최적 추정법을 보장하지는 않는다.
이고 이라 하자. 로 두면 다. 정규화의 미분에서 이므로
가 SLD 방정식을 만족한다. 그러므로
전체 위상만 변하면 이다. 위상 관례에 의존하는 접선 성분이 제거되므로 밀도 행렬의 실제 변화만 측정한다.
선행 개념: 정화의 동치 · 특잇값분해 · 부분 대각합과 POVM
대각합 노름은 특잇값의 합 이다. 에르미트 행렬이면 다. 음의 고윳값도 절댓값으로 더한다.
에르미트 행렬의 양·음 고윳값 부분으로 이라 쓰자. 대각합이 0이므로 다. 측정 사건의 효과 가 를 만족하면 이고, 양의 고유공간으로의 사영을 택하면 위쪽 등호가 성립한다.
따라서 거리가 작으면 어떤 측정 사건의 확률도 크게 다르지 않다.
이 식에서 셋째·넷째 단계가 쓰는 두 성질이 바로 나온다. 첫째, 전체 상태 의 부분계 상태를 라 하자. 의 효과 에 대해 도 효과이고 이므로, 부분 대각합은 를 늘리지 않는다. 둘째, POVM 의 결과 분포 , 에서 인 결과의 집합을 라 하자. 이므로
이다. 여기서 는 를 만족한다. 곧 측정 결과의 분포도 보다 멀어지지 않는다. 일반 채널의 수축성은 C06d에서 보인다.
여기서는 , 으로 쓰고 라 둔다. 로 두면 와 는 각각 와 의 정화다. 정화의 동치(HP01)에 따라 같은 보조계를 쓰는 의 정화는 모두 보조계의 유니타리 로 라 쓸 수 있다. 는 에르미트이므로 두 정화의 겹침은 이고, 성분으로 계산하면
이다. 가 모든 유니타리를 돌면 도 모든 유니타리를 돈다.
의 특잇값분해를 라 하자. , 는 유니타리이고 의 대각 원소는 특잇값 이다. 대각합의 순환성으로 이다. 유니타리 행렬 의 대각 원소는 절댓값이 1 이하이므로 이고, 이면 가 되어 등호가 성립한다. 따라서 최대 겹침의 제곱은 다. 보조계가 더 크면 보조계에서 두 정화의 성분이 놓인 부분공간에서 이 변환을 정한 뒤 나머지 기저로 넓혀 유니타리를 만든다.
두 정규화 순수 상태 가 생성하는 2차원 공간에서 의 고윳값은 이다. 대각합이 0이고 제곱의 대각합이 임을 계산하면 확인된다.
앞 단계의 최대 겹침을 갖는 정화를 고르고 보조계를 버린다. 부분 대각합은 대각합 거리를 늘리지 않으므로(첫 단계) 다.
먼저 가 양의 정부호라고 하자. , 으로 두면 다. 의 정규직교 고유기저에서 측정한 확률을 , 고윳값을 라 하자. 은 의 양쪽에 을 곱한 것이므로 , 곧 이다. 또 이므로
이산분포에서는 이므로 다. 첫 단계의 둘째 성질을 적용하면 를 얻는다.
영 고윳값이 있으면 각 상태를 처럼 정칙화한 뒤 의 극한을 취한다. 유한차원에서 행렬 제곱근과 노름의 연속성을 사용한다. 이로써 의 양쪽을 모두 보였다.
선행 개념: 텐서곱 기저 · 유니타리 불변성 · 직교 사영 · 표현과 불가약성(HP10a)
이고 모든 유니타리 에 대해 가 와 가환한다고 하자. 독립적인 위상의 대각행렬을 택하면, 일 때 두 지표의 중복을 포함한 집합 와 이 같아야 한다. 이면 이 과 같아야 하고, 성분이 0이 아니면 이 위상이 모든 선택에서 1이어야 하기 때문이다.
다음으로 기저 순열을 적용한다. 서로 다른 지표 쌍은 모두 서로 바꿀 수 있고 두 지표의 순서도 바꿀 수 있다. 따라서 어떤 수 에 대해
부분공간에서 인 유니타리를 택한다. 와 의 성분을 비교하면 다. 따라서
HP10의 가 각각 다. 반대로 는 모든 와 가환한다. 이로써 불변 연산자 공간이 정확히 임을 보였다. 에서는 이므로 두 계수가 독립적이지 않다.
유니타리 표현의 불변 부분공간은 직교 여공간도 불변이므로, 그 공간으로의 직교 사영은 표현과 가환한다. 대칭 공간 내부의 불변 부분공간 사영을 전체 공간에 0으로 확장하면 앞의 결과에 따라 대칭 공간에서 스칼라다. 사영의 스칼라는 0 또는 1뿐이므로 대칭 표현은 불가약이다. 반대칭 공간도 같다.
두 표현 사이의 비영인 가환 사상이 있다면 이를 전체 공간의 비대각 블록으로 넣어 가환 연산자를 만들 수 있지만, 에는 그런 블록이 없다. 따라서 두 표현은 동치가 아니다. 일반 Schur 보조정리도 간단하다. 복소 유한차원 행렬에는 고윳값이 존재한다. 불가약 표현과 가환하는 의 고윳값 를 하나 잡으면 가 비영 불변 공간이므로 전체 공간이고 다.
하르 분포의 좌우 불변성에 의해 는 모든 와 가환한다. 따라서 꼴이다. 본문의 두 대각합 계산으로 를 정하면 평균식의 증명이 완성된다.
선행 개념: 부분 대각합 · 교환 연산자의 대각합 항등식 · 순수 상태의 이차 모멘트(HP04c) · 코시–슈바르츠 부등식
의 차원을 , 사영을 라 쓰자. 에서 하르 분포로 뽑은 단위벡터를 정규직교 기저 로 라 쓰자. HP04c에서 여는 증명의 셋째 단계와 같은 계산으로
이다. 두 항은 각각
를 주므로
여기서 는 두 복사본을 바꾸는 교환 연산자다. 같은 식은 32절의 두 복사본 불변 연산자 정리(HP10)로도 얻을 수 있다. 에서도 직접 같은 식이 성립한다. 전체 교환은 다. 는 기저 성분을 전개하여 확인할 수 있다.
이고 그 축약 상태를 라 하자. 앞의 식에 를 곱하고 대각합을 취하면
첫 항에서는 을 각각 부분 대각합하고, 둘째 항에서는 를 사용하여 을 제거했다. 또한 이므로
차원 에르미트 의 고윳값에 코시–슈바르츠 부등식을 적용하면 이다. 다시 확률 평균에 코시–슈바르츠 부등식을 적용하여
이 평균 상한에는 고차원 측도 집중 정리가 필요하지 않다. 평균에서 실패 확률로 가는 마르코프 부등식은 본문에서 이어서 적용한다. 가 깁스 상태에 가깝다는 별도의 열저장고 근사는 이 증명에 포함되지 않는다.
선행 개념: 독립 동일분포 · 큰수의 법칙 · 엔트로피 · 합집합 확률의 상한
유한 알파벳의 독립 동일분포 정보원 을 생각하자. 양의 확률 문자에 대해 의 평균은 다. 큰수의 법칙에 의해 가 확률수렴한다. 따라서 고정된 에 대해
에 들어갈 확률이 1로 간다. 이를 이 증명에서 전형 집합(typical set)이라 부른다. 큰수의 법칙 자체는 확률론의 기초 정리로 사용한다.
전형 문자열 하나의 확률이 적어도 이므로 이다. 이면 로 잡는다. 그러면 전형 문자열의 번호가 비트에 들어가므로, 이 문자열들을 번호로 부호화하고 나머지는 실패로 처리한 고정 길이 블록 압축에서 복원 오류가 0으로 간다.
반대로 비트 부호는 최대 개의 문자열을 정확히 복원할 수 있다. 전형 집합에서 각 문자열의 확률은 최대 이므로 성공 확률은
이고 이면 이 값은 0으로 간다. 이는 독립 동일분포·고정 길이·오류 허용 압축의 점근적 결과다. 모든 문자열의 무오류 압축이나 유한 길이의 정확한 비트 표현을 뜻하지 않는다.
무오류 압축에서는 예외 문자열도 모두 복원해야 한다. 각 문자열 에 길이 인 구간을 서로 겹치지 않게 배정하고, 그 중점의 이진 전개를 자리까지 보낸다. 이 접두부의 이진 구간 길이는 이하이므로 원래 구간 안에 들어간다. 서로 다른 구간은 겹치지 않아 부호어들이 접두 관계를 갖지 않는다. 따라서 평균 길이는 다.
반대로 임의의 접두 부호(C02c)를 생각하자. 문자열에 번호 를 붙여 확률을 , 번째 문자열에 배정한 부호어의 길이를 라 하자. 어느 부호어도 다른 부호어의 처음 부분이 아니므로 부호어들이 정하는 이진 구간은 겹치지 않고 이다. 을 확률분포로 두고 상대 엔트로피 라 하자. 에 를 넣고 를 곱해 인 에 대해 더하면
이다. 곧 이다(C02b에서 여는 증명의 첫 단계). 문자들이 독립이므로 문자열의 엔트로피는 의 평균인 이고
이다. 블록당 으로 나누어 극한을 취하면 접두 부호 압축의 평균률도 로 수렴한다. 고정 길이의 작은 오류 허용과 가변 길이의 무오류 평균률을 구별한다.
이제 반전 확률 인 BSC를 번 독립적으로 사용한다. 개의 부호어를 각각 균등한 비트열로 독립 추출한다. 메시지 의 부호어가 이면 이고 의 각 비트는 다. 잡음의 전형 집합 를 위 방식으로 정의하면 , 이다.
복호기는 이 에 속하는 메시지가 정확히 하나일 때 그것을 고르고, 아니면 오류를 선언한다. 잘못된 부호어 는 와 독립인 균등 문자열이므로 이다.
실제 잡음이 전형적이지 않은 사건과 잘못된 메시지가 경쟁하는 사건에 합집합 상한을 적용하면, 무작위 부호의 평균 블록 오류는
에서 충분히 작은 를 고르면 우변이 0으로 간다. 평균보다 오류가 크지 않은 결정된 부호가 적어도 하나 있으므로 부호의 존재가 증명된다. 최대 메시지 오류까지 요구하면 평균의 두 배보다 오류가 큰 절반 이하의 메시지를 버린다. 남은 메시지 수는 적어도 이고 전송률 손실은 최대 이다. 이 존재 증명은 효율적인 복호 알고리즘을 보장하지 않는다.
메시지 집합 에서 균등하게 고른 메시지 의 추정 오류가 이라 하고, 오류 지시변수를 이라 하자. 을 알 때 이면 메시지가 정해지고 이면 후보는 최대 개다(복호기가 실패를 선언한 경우도 포함). 연쇄 법칙과 조건부 엔트로피의 비음성, 조건을 걸어도 엔트로피가 늘지 않는다는 사실(, 곧 C02b에서 여는 증명의 ), 엔트로피는 값의 개수의 로그를 넘지 않는다는 사실(같은 증명의 셋째 단계)로
또한 결정적 부호화와 독립 BSC 잡음에서 다. 의 값은 개이므로 이다. 따라서 이다. 인 부호열의 전송률은 를 넘지 못한다. 이 단계는 약한 역정리이며, 용량을 넘으면 오류가 1로 간다는 더 강한 주장은 여기서 증명하지 않았다.
선행 개념: 유일 정답 오라클 · 균등분포 · 무작위 알고리즘
개의 후보 가운데 정답이 하나이고, 한 질의는 지정한 후보가 정답인지에 대한 비트만 돌려준다고 하자. 먼저 최대 번 질의하는 결정적 알고리즘을 고정한다. 모든 응답이 0인 경로에서 검사하는 서로 다른 후보는 최대 개다.
정답이 그 후보들 중 하나이면 발견할 수 있다. 그 밖에서는 응답 경로가 모두 같으므로 마지막에 질의하지 않은 후보를 추측해도 추가로 맞힐 수 있는 입력은 하나뿐이다. 따라서 균등한 정답에 대한 성공 확률은
알고리즘의 내부 난수를 고정할 때마다 앞의 상한이 성립한다. 난수에 대해 평균해도 상한은 같다. 모든 정답 위치에서 성공 확률이 적어도 인 알고리즘은 균등 입력 평균에서도 적어도 로 성공해야 하므로 이다.
이것은 최악 실행의 질의 수에 대한 하한이다. 질의 한 번이 구조 있는 정보를 주거나 여러 후보를 한꺼번에 판정하는 다른 오라클에는 그대로 적용할 수 없다.
선행 개념: 유한 연분수 · 정수 점화식 · 분수의 대소 비교
실수 의 연분수를 로 쓰고 은 정수, 이후 는 양의 정수라 하자. 유한 접두부의 분자·분모를 라 쓰면
초깃값은 이다. 점화식은 다음 식에서 나온다. 이고 이면
이다. 이면 점화식에서 , 이므로 양변이 모두 이다. 에서 성립하면 을 넣어 좌변은 , 우변은 이 되므로 에서도 성립한다. 를 넣으면 접두부 의 값이 다. 점화식에 대입하여 마지막 항등식을 귀납적으로 확인한다. 따라서 수렴분수는 기약분수다.
기약분수 의 마지막 항이 2 이상인 유한 연분수를 고르자. 직전 수렴분수를 이라 하면(1단계의 ) 이다. 뒤에 실수 꼬리 을 붙인 값은 1단계의 식에서
이고, 1단계의 항등식에서 이므로
가 1에서 로 움직이면 의 한쪽에서 길이 인 열린 구간을 모두 지난다. 의 다른 표현은 마지막 를 로 바꾼 것이며, 그 직전 분모는 이다. 이 표현의 꼬리는 반대쪽에서 길이 인 구간을 준다. 가 정수이면 와 을 사용하여 같은 결론을 얻는다.
두 구간의 길이는 모두 이상이다. 따라서 이면 이거나, 는 위 두 꼬리 구간 중 하나에 속한다. 각 경우 의 연분수에는 를 주는 유한 접두부가 있다. 즉 는 의 수렴분수다.
본문에서는 를 대입한다. 서로소 조건이 없으면 먼저 약분해야 하고, 부등식은 엄격한 <이다. 이 정리는 가까운 분수가 후보로 나타남을 보일 뿐, 그 분모가 모듈러 연산의 실제 주기인지까지 보장하지 않는다.
선행 개념: 행렬의 QR 소거 · 제어 게이트 · 한 큐비트 회전 분해
임의의 유니타리 행렬에서 두 행만 섞는 2×2 유니타리를 왼쪽에서 곱하여 대각 아래 성분을 하나씩 없앤다. 이는 QR 소거의 구성이다. 마지막에 남은 상삼각 유니타리는 대각 위상 행렬이다. 따라서 원래 연산자는 두 계산 기저 상태 사이에만 작용하는 연산자들과 대각 위상의 곱이다.
각 가 어떤 두 기저 상태를 섞는지가 중요하다. 이것을 바로 한 큐비트 게이트라고 부를 수는 없다.
두 비트열 사이에서 한 번에 한 비트씩 바꾸는 경로를 잡는다. 나머지 비트의 값에 조건을 건 연산으로 중간 상태를 순열 이동시키면 두 상태를 한 비트만 다른 위치로 옮길 수 있다. 그 비트에 다중 제어 한 큐비트 연산을 적용한 뒤 순열을 되돌린다.
남은 회로 합성 입력은 다중 제어 한 큐비트 연산을 CNOT과 임의의 한 큐비트 회전으로 분해할 수 있다는 구성 정리다. 이 패널은 그 재귀 회로를 전부 전개하지 않는다. 한 제어의 경우에는 , 인 한 큐비트 를 회전 분해에서 구해 두 CNOT 사이에 넣는 것이 기본 단계다. 전체 위상은 제어선의 위상 게이트로 따로 처리한다.
연속 각도 회전의 분해와 유한 게이트 집합의 조밀성은 다른 정리다. 유한 목록으로 원하는 정확도까지 근사하려면, 생성되는 곱으로 모든 유니타리 연산에 원하는 만큼 가깝게 갈 수 있다는(조밀성) 추가 증명이 필요하다. Toffoli와 의 실수 진폭·보조 큐비트 모형도 별도의 보편성 정리를 사용한다. 이 모형은 복소 진폭의 실수부와 허수부를 보조 큐비트 하나의 두 성분에 나누어 담아, 측정 확률을 원하는 정밀도로 재현한다.
따라서 여기까지는 일반 행렬 분해를 회로 합성으로 환원하는 증명 개요다. 모든 유한 게이트 집합의 보편성이나 효율적인 근사 길이를 증명한 것으로 읽지 않는다. 이므로 위 일반 구성 자체도 에 대해 지수적으로 길 수 있다.
선행 개념: 주기 찾기 회로 · 연분수와 수렴분수(D11) · 연분수 근사 정리(D12) · 중국인의 나머지 정리 · 효율적인 정수 산술 · 위상 추정의 분포와 확률 하한(D09, D10) · 곱셈 연산자의 고유 상태(B07에서 여는 증명) ·
짝수와 완전 거듭제곱을 고전적으로 처리하고, 서로 다른 홀수 소인수가 적어도 두 개인 을 남긴다. 균등하게 고른 와 의 최대공약수가 비자명하면 이미 인수를 얻었다. 아니면 는 을 법으로 하는 가역 원소이며 유한 주기 을 갖는다.
양자 단계의 역할은 의 후보를 만드는 것이다. 그 뒤 인지 계산하여 검증한다. 검증되지 않은 분모를 곧바로 주기라고 쓰지 않는다.
인 완전 거듭제곱 에서는 이다. 각 마다 인 가장 큰 정수 을 이분 탐색으로 구해 인지 보면 되므로, 이 검사는 의 다항식 번의 곱셈과 비교로 끝난다. 소수인지도 다항식 시간에 판정되므로(O19a) 먼저 걸러 낸다. 소수 거듭제곱을 따로 처리하는 이유는 주기 찾기가 그 인수를 주지 못하기 때문이다. 이면 이고, 두 인수의 차는 2이므로 홀수 소수 는 둘을 함께 나누지 못한다. 그래서 과 가운데 하나가 의 배수이고, 이다. 곧 이 짝수여도 은 1이 아닌 1의 제곱근, 즉 이어서 이 자명하다.
를 이상인 2의 거듭제곱으로 잡으면 각 고유 위상 에 가장 가까운 는 오차가 최대 이다. 위상 추정의 등비수열 합(D09)에서 이 가까운 결과의 확률은 적어도 이다(D10). B07에서 여는 증명대로 입력 레지스터의 분포는 개 고유 위상 의 위상 추정 분포를 같은 비율 로 섞은 것이다.
에서 은 위수의 최소성에서 서로 다른 0 아닌 나머지이므로 이다. 그래서 와 이 서로소이면 이고, D12에서 다루는 연분수 근사 정리에 의해 정확한 이 수렴분수의 분모로 나타난다. 가운데 과 서로소인 의 비율을 이라 하자. 다음 단계에서 이 비율의 하한과 한 시행의 성공 확률을 센다.
의 서로 다른 소인수를 라 하자. 가운데 의 배수는 개다. 여러 소인수로 동시에 나누어떨어지는 수는 그 곱의 배수이므로, 번호 집합 에 속한 소인수 모두로 나누어떨어지는 는 개다. 포함–배제로 세면 어느 로도 나누어떨어지지 않는 의 비율은
이다. 소인수 개로 나누어떨어지는 는 이 합에서 번, 어느 소인수로도 나누어떨어지지 않는 는 한 번 세어지기 때문이다. 번째로 작은 소인수는 이상이므로
이다. 마지막 부등식은 에서 나온다.
서로 다른 의 위상은 이상 떨어져 있고 이다. 가장 가까운 격자점이 같다면 두 위상의 거리가 이하가 되므로, 격자점 들은 서로 다르다. 각 의 확률은 적어도 이므로, 한 번의 시행에서 서로소인 의 를 얻어 정확한 이 후보에 나올 확률은
이다. 후보 은 으로 검증하고, 검증된 후보 가운데 가장 작은 것을 택한다. 최소성에서 보다 작은 분모는 검증을 통과하지 못하므로, 이 한 번이라도 나오면 그것이 택해진다.
서로 다른 홀수 소수 거듭제곱 성분에 대한 중국인의 나머지 정리를 적용한다. 각 성분에서 의 위수에 포함된 2의 지수는 독립적으로 정해진다. 그 지수들이 모두 같을 때만 이 홀수이거나 인 실패가 가능하다. 지수가 서로 다르면 은 짝수이고, 가장 큰 지수를 갖는 성분에서 은 1이 아닌 1의 제곱근이어서 1단계에 따라 이며, 더 작은 지수를 갖는 성분에서는 1이기 때문이다.
홀수 소수 거듭제곱 을 법으로 하는 가역 원소는 개이고, 이들이 인 꼴로 한 번씩 나타나는 원소 가 있다(원시근의 존재, 외부 결과). 은 와 같으므로 의 위수는 이다. 은 짝수이므로 이 위수의 2의 지수는 가 홀수일 때, 그리고 그때만 가장 크다. 균등한 가 홀수일 확률은 1/2이므로 각 지수값의 확률은 최대 1/2이다. 따라서 서로 다른 성분이 둘 이상일 때 모든 지수가 같은 확률은 최대 1/2이다. 나머지 경우 은 1과 −1 이외의 1의 제곱근이어서 으로 비자명한 인수를 얻는다(B08).
반복 제곱, 최대공약수, 연분수 계산과 가역 모듈러 산술은 의 다항식 비용으로 구현할 수 있다. 입력 레지스터도 개 큐비트다. 셋째 단계의 확률 로 독립 시행을 번 하면 을 한 번도 얻지 못할 확률은 이다(). 따라서 번이면 이 확률이 작은 상수 이하가 된다. 넷째 단계의 인수 추출 확률(적어도 1/2)과 결합해 새 로 다항식 횟수만큼 반복하면 실패 확률을 1/3 이하로 줄인다. 얻은 인수들에도 같은 절차를 적용한다.
이것은 계산·확률·정수론·산술 구현이 어떻게 결합되는지 보이는 증명 개요다. 인용한 원시근의 존재, 소수 판정, 산술 회로 합성과 연분수 근사 정리(D12)까지 전부 증명한 것은 아니다. 작은 수 하나의 계산 예와 일반 성능 보장을 구별하기 위한 경로다.
선행 개념: 유한 셀 분할 · 연결합으로 표현한 가향 곡면
라 하자. 변 하나를 둘로 나누면 꼭짓점과 변이 하나씩 늘고, 면 안에 대각선을 넣어 둘로 나누면 변과 면이 하나씩 늘어난다. 어느 경우에도 는 변하지 않는다. 구면의 정사면체 분할에서는 다.
이 계산을 임의의 적절한 셀 분할로 옮길 때는 두 분할이 공통 세분을 갖는다는 곡면 위상수학 결과를 사용한다. 단순한 계수 계산만으로 그 존재까지 증명한 것은 아니다.
토러스의 기본 다각형에서는 꼭짓점 하나, 변 둘, 면 하나이므로 이다. 두 곡면에서 원판 하나씩을 제거하면 각각 가 1씩 줄어든다. 경계 원을 붙일 때 경계의 꼭짓점 수와 변 수가 같으므로 의 추가 변화는 없다. 따라서 연결합은
를 만족한다. 구면에 토러스 손잡이를 번 붙이면 다. 모든 연결·닫힌·가향 곡면이 이런 형태라는 곡면 분류 정리는 여기서 외부 입력이다. 본문의 계산은 이 위상수학 입력과 안정자 관계의 계수를 함께 사용한다.
선행 개념: 확률로 고른 부호 상태와 POVM · 양자 상대 엔트로피 · 측정에 대한 상대 엔트로피의 데이터 처리 부등식
측정 에 대해 상대 엔트로피는 증가하지 않는다.
여기서 는 SM03의 자연로그 상대 엔트로피를 밑 2로 바꾼 값이다. 레니 상대 엔트로피와는 구별한다. 이 데이터 처리 부등식(data processing inequality)은 보조정리로 받아들인다. 일반 증명은 연산자 볼록성 등의 별도 이론을 요구하므로, 아래는 이 보조정리에 의존하는 홀레보 상한의 증명이다.
라 하자. 인 각 상태의 지지는 평균 상태의 지지에 포함된다. 정의를 전개하면
에 곱해지는 로그 항에서는 합과 대각합을 교환했다. 비직교한 부호 상태도 포함하는 항등식이다.
모든 에 같은 POVM을 적용하여 라 쓰자. 측정 출력 상태들은 같은 기저에서 대각이므로
첫 단계의 데이터 처리 부등식을 마다 적용하여 더하면 다. 마지막으로 각 상태의 엔트로피는 음이 아니고 차원 상태의 엔트로피가 이하이므로 다. 사전 자원 없이 차원 수신계만 측정한다는 가정이 이 마지막 차원 상한에 들어간다.
선행 개념: 불 연산 AND·OR·NOT
두 비트 에는 네 입력만 있다. 각 식의 값을 직접 계산한다.
| 0,0 | 1 | 1 | 1 | 1 |
| 0,1 | 1 | 1 | 0 | 0 |
| 1,0 | 1 | 1 | 0 | 0 |
| 1,1 | 0 | 0 | 0 | 0 |
각 쌍의 열이 모든 입력에서 같으므로 두 불 함수가 같다. 몇 가지 예만 확인한 것이 아니라 정의역 전체를 조사한 증명이다.
선행 개념: 슈미트 분해와 계수의 수 · 엔트로피의 차원 상한 · 두 자리 게이트의 행렬 전개
절단 양쪽의 한 자리씩에 작용하는 게이트 를 쪽 행렬 단위로 전개한다.
입력 상태의 슈미트 계수 개수가 이면 입력은 개의 곱벡터 합이다. 위 식을 적용한 출력은 많아야 개의 곱벡터 합이므로 출력의 슈미트 계수 개수는 이하이다. 한쪽에만 작용하는 유니타리는 계수의 개수를 바꾸지 않는다.
곱상태는 이다. 서로 겹치지 않는 최근접 게이트의 한 층에서 절단을 가로지를 수 있는 게이트 수는 이하이다. 층 뒤에는 이다. 개의 양의 고윳값을 갖는 축약 상태의 엔트로피는 이하이므로
이는 정확한 유한 깊이 회로의 상한이다. 임의의 갭 있는 바닥 상태가 이런 고정 깊이 회로로 정확히 표현된다는 가정은 쓰지 않았다. 상태를 근사하는 경우에는 별도의 오차·엔트로피 연속성 제어가 필요하다.
선행 개념: 독립 가환 파울리 안정자와 그 사영(B17) · 부분 대각합 · 사영의 고윳값과 엔트로피
개의 독립 생성원 가 생성하는 군 는 를 포함하지 않는다. B17에서 으로 두면 공통 +1 공간으로의 사영 는 이어서 와 같고, B17의 전개에 따라
에서 적어도 한 자리의 파울리가 비항등이면 그 항의 부분 대각합은 0이다. 에서 항등인 항만 의 인자를 남긴다. 따라서
의 독립 생성원이 개이면 역시 공통 +1 사영이다. 따라서 이다.
사영의 고윳값은 0 또는 1이다. 항등 항의 대각합으로 이므로 양의 고윳값 의 중복도는 이다. 정규화도 곧 확인된다.
따라서 얽힘 에너지는 지지 위에서 모두 이다. 군 생성원의 지지 상쇄를 빠뜨리지 않고 전체를 구해야 한다.
선행 개념: 토릭 부호의 면·꼭짓점 검사 · 홀짝성이 0인 닫힌 고리는 검사의 곱(D20에서 여는 증명) · 파울리 연산자 기저
원판 의 임의 연산자 를 파울리 문자열 의 선형 결합으로 전개한다. 각 에 대해 가 스칼라배 임을 보이면 선형성으로 충분하다. 는 토릭 부호의 모든 검사가 +1인 공간으로의 사영이다.
어떤 검사 와 가 반가환하면 이다. 따라서
이 문자열은 바닥 공간 밖으로 보낸다. 바닥 공간 안에서의 행렬 원소는 모두 0이다.
는 모든 검사와 가환하므로 부분은 원래 격자의 닫힌 고리이고 부분은 쌍대 격자의 닫힌 고리다. 원판은 토러스보다 충분히 작아 두 고리의 두 방향 홀짝성이 모두 0이므로, D20에서 여는 증명에 따라 부분은 면 검사의 곱이고 부분은 꼭짓점 검사의 곱이다. 따라서 는 전체 위상을 제외하면 면·꼭짓점 검사의 곱이다. 그 곱은 부호 공간에서 항등이므로 이다.
두 경우를 선형 결합하면 를 얻는다. 임의의 바닥 상태 에서 국소 기댓값은 이고, 모든 국소 연산자에서 같으므로 축약 상태도 같다. 원판 제한이 빠지면 비수축 논리 고리가 가능하므로 결론이 성립하지 않는다. 작은 섭동에 대한 위상 상의 안정성은 이 정확한 고리 논증과 별개다.
선행 개념: 하르 무작위 순수 상태 · 순수 상태의 이차 모멘트(HP04c) · 부분 대각합과 순도 · 슈미트 분해 · 로그의 오목성
유한차원 이분계의 전체 순수 상태를 하르 분포로 뽑는다. 작은 쪽과 큰 쪽의 차원을 각각 , 이라 쓰고 이라 하자. 이 증명에서 의 아래첨자 2는 로그의 밑이다. 2차 Rényi 엔트로피와 혼동하지 않는다.
보일 것은
큰 쪽도 순수 이분계의 슈미트 고윳값을 공유하므로 같은 엔트로피를 갖는다. 이 결과는 하르 모형에 관한 것으로, 중력의 증발 방정식을 가정하거나 풀지 않는다.
라 쓰자. 하르 분포에서는 모든 유니타리 에 대해 와 가 같은 분포를 따른다. 따라서 이면 이 불변성만 쓰는 HP04c에서 여는 증명의 셋째 단계와 같은 계산으로
이다. 이면 상태가 하나뿐이므로 결론을 직접 확인할 수 있다.
이제 로 나누자. 이고 이다. 작은 쪽의 두 지표는 , 큰 쪽의 두 지표는 로 쓴다. 이므로
앞의 두 짝짓기를 대입하면 각각 와 가 남는다. 첫 합은 개, 둘째 합은 개이므로
이고 인 항은 두 합에 모두 들어간다. 앞 단계의 식에서 이면 두 항이 모두 남는 것과 일치한다.
의 양의 고윳값을 라 하자. 합이 1인 를 가중치로 삼아 로그의 오목성을 쓰면
0인 고윳값은 으로 처리한다. 따라서 각 상태에서 이다. 이번에는 양의 확률변수인 순도에 의 볼록성을 적용한다.
순도 평균식을 대입하면 하한이 나온다. 상한은 차원 에서 이라는 엔트로피 경계다. 평균과 로그를 등식으로 교환하지 않았다는 점에 주의한다.
총 큐비트에서 개를 복사로 두면 , 이다. 엔트로피 부족량 은
을 만족한다. 이므로 이고, 로그 안의 값은 2보다 작다. 그러므로 평균 곡선은 에서 아래로 1비트 미만만 벗어난다. 이면 이므로 엔트로피는 정확히 0이다.
고정된 을 잡자. 이므로 는 인 경우 이상이고, 그 밖의 경우 이상이다. 기댓값을 취하면 이다(마르코프 부등식, SM06). 따라서
이는 고정된 방출 비율에서 정규화된 선도항이 전형적임을 보인다. 모든 시각의 곡선이 동시에 가깝다는 주장도, 개별 동역학이 하르 분포를 생성한다는 증명도 아니다.
더 강한 외부 결과인 Page 평균식은
이다. 에서는 에 가까우므로 중앙의 유한 크기 보정도 알 수 있다. 위에서 완전히 유도한 것은 순도에 근거한 상·하한과 정규화된 선도항이다. 정확한 조화합 공식의 증명은 여기서 다루지 않고 Sen의 결과를 인용한다. Page의 원래 추측과 Sen의 증명을 구별한다.
출처: Page (1993), Sen (1996). 실제 증발 시간에 적용하려면 유효 차원과 시간의 관계, 에너지 제약, 상태 앙상블을 추가로 정해야 한다.
선행 개념: 위의 행렬과 선형 사상 · 계수와 핵 · 기저와 좌표
이진 행렬 와 을 고정하고 사상 를 생각한다. 모든 계산은 에서 한다. 두 입력이 같은 값을 준다고 하자.
양변에 를 더하면 에서는 이므로 이다. 곧 은 에 속하고 이다. 거꾸로 이면 이다. 따라서 을 포함하는 역상은 정확히 잉여류 이다.
는 에서 로 가는 일대일 대응이다. 서로 다른 는 서로 다른 를 주기 때문이다. 따라서 공집합이 아닌 모든 역상은 원소가 개다.
위의 차원 벡터 공간에서 기저를 하나 고르면, 모든 벡터는 기저 좌표 개로 유일하게 쓰이고 각 좌표는 0 또는 1이다. 따라서 원소는 개다. 상 은 차원이 이므로 원소가 개다. 실제로 나타나는 값의 집합 은 이를 만큼 옮긴 것이므로 역시 개다. 같은 이유로 이다.
입력 개는 각자 주는 값에 따라 서로 겹치지 않는 역상들로 나뉜다. 공집합이 아닌 역상은 개이고 각각 원소가 개이므로
따라서 이다. 앞 단계의 과 비교하면 이다. 이로써 O39c 상자의 세 주장, 곧 차원 정리, 역상의 크기 , 값의 개수 을 모두 얻는다. 이 증명은 실수 행렬이 아니라 위의 행렬에 대한 것이다.
의 행 가운데 서로 독립인 행을 가장 많이 고른 것을 개라 하고, 이 행들로 행렬 을 만든다. 다른 행을 하나 더하면 독립이 아니게 되므로 의 모든 행은 의 행 몇 개의 합이고, 의 행들은 의 행들이 생성하는 공간의 기저다. 또 의 행은 의 행이므로 과 은 동치다. 곧 이다. 차원 정리를 두 행렬에 쓰면
이다. 마지막 부등식은 의 상이 안에 있어 셋째 단계처럼 세면 이기 때문이다. 같은 논증을 전치 행렬 에 쓰자. 의 행은 의 열이므로 그 독립인 행의 최대 개수는 열들이 생성하는 공간, 곧 상의 차원 이다. 또 의 상은 의 행들이 생성하는 공간이므로 이다. 따라서 이고, 두 부등식에서 다. O39c 상자의 “계수는 독립인 행의 최대 개수와 같다”가 이 결과다.
선행 개념: 얽힘 충실도(HP02) · 크라우스 표현(C06a) · 유니타리 불변 측도
차원 의 양자 채널을 , 로 쓴다. HP04c의 정리는 두 식을 입력으로 쓴다. 하나는 이고, 다른 하나는 순수 상태의 이차 모멘트다.
여기서 균일한 측도 는 모든 유니타리 에 대해 와 가 같은 분포를 따르는 정규화된 측도다. 이 불변성이 아래 셋째 단계의 근거다.
HP02의 정의에서 이고 이다. 크라우스 표현을 넣으면
또 이므로 이다.
에서 로 쓰자. 대각 유니타리 를 적용하면 에 가 곱해지는데, 측도가 불변이므로 값은 그대로여야 한다. 따라서 중복을 포함한 두 지표 쌍 와 이 같을 때만 0이 아닐 수 있다. 기저의 순열도 유니타리이므로 , 두 값만 정하면 된다.
로 바꾸는 유니타리에서도 분포가 같으므로 이다. 네제곱을 전개하고 앞의 위상 논증으로 짝이 맞지 않는 항을 없애면 , 곧 이다. 정규화에서
따라서
이면 두 항이 모두 남아 이 된다.
와 을 곱해 평균하자. 앞 단계의 식에서 항은 를, 항은 를 준다. 따라서
이면 는 수이고 양변이 모두 이므로 같은 식이 성립한다. 확인: 이면 양변이 모두 1이다. 두 입력을 HP04c 본문의 계산에 넣으면 을 얻는다. 32절 HP00e의 페이지 곡선 증명도 같은 네 계수 평균을 쓴다.
선행 개념: 스펙트럼 정리(A05p) · 부분 대각합의 규칙(A05a) · 곱상태와 얽힘(O02) · 분리 가능 상태(B13d) · 연산자의 텐서곱(O22)
두 계의 순수 상태 와 그 축약 상태 를 생각하자. 스펙트럼 정리(A05p)로 의 정규직교 고유기저 를 잡고 의 기저 로 라 쓴다. 마다 로 모으면
이다. 는 정규화되어 있지 않을 수 있다.
이다. A05a의 규칙 를 의 성분 에 선형으로 적용하면 가 남는다. 따라서
이다. 곧 의 행렬은 끼리의 내적을 늘어놓은 행렬이다.
가 순수하다고 하자. 고유기저는 (고윳값 1)와 그에 직교하는 벡터들(고윳값 0)로 택할 수 있다. 에 대응하는 성분을 라 하면, 나머지 성분은 이므로 모두 0이다. 따라서
이고 전체는 곱 상태다.
B13d의 분리 가능성이 순수 상태에서는 O02의 곱 상태와 같은 뜻임을 확인하자. 곱 상태는 항이 하나인 분리 가능 상태다. 거꾸로 순수 상태가 분리 가능하다고 하자. 인 항만 남기면 이다. 마다 두 인자를 스펙트럼 분해 , ()로 쓰면, O22의 규칙으로 이고 곱벡터 들은 정규직교 기저다. 따라서 에 직교하는 에서
이고 모든 항이 0 이상이므로, 인 곱벡터 는 에 직교하는 모든 벡터와 직교한다. 도 에 직교하므로 이고, 에서 이다. 곧 는 의 위상 배수다. 정규직교인 두 곱벡터가 모두 에 비례할 수는 없으므로 각 에서 인 항은 하나뿐이고, 는 곱 상태다. 따라서 순수 상태에서는 B13d의 얽힌 상태와 O02의 얽힌 상태가 같다.
B13d의 앞 방향(곱 상태의 축약 상태는 순수하다)과 합치면, 전체가 순수할 때 축약 상태가 순수한 것과 곱 상태인 것은 동치다. 따라서 축약 상태가 혼합인 것과 두 계가 얽혀 있는 것도 동치다. 일반적인 에서는 둘째 단계의 식이 가 된다. 곧 들은 서로 직교하고 길이의 제곱이 이다. 이들을 정규화하여 쓴 것이 9절의 슈미트 분해(O04a)다.
선행 개념: 스펙트럼 정리(A05p) · 외적과 대각합(A05p) · 수반(A00a)
스펙트럼 분해 에 대각합의 선형성과 (A05p)을 쓰면 이다. 따라서 은 고윳값의 합이 1이라는 조건이고, 과 함께 고윳값은 확률분포를 이룬다.
정규화된 와 , 로 라 하자. 외적 의 성분은 이므로 수반은 이고, 각 항 와 그 합은 에르미트다. 대각합은 이다. 임의의 벡터 에서
이므로, 를 정규화된 고유벡터로 잡으면 그 고윳값 도 0 이상이다.
이면 모든 에 대해 이다. 이므로 는 고윳값 1의 고유벡터이고, 에 직교하는 벡터는 모두 고윳값 0의 고유벡터다. 또 이다.
앞 단계에서 순수 상태는 양의 고윳값이 정확히 하나(값 1)다. 거꾸로 양의 고윳값이 하나뿐이면 고윳값의 합이 1이므로 그 값이 1이고, 스펙트럼 분해가 가 되어 순수 상태다. 따라서 양의 고윳값이 둘 이상인 밀도 행렬은 어떤 정규화된 벡터의 사영으로도 쓸 수 없는 혼합 상태다. 또 이므로 는 모든 고윳값이 0 또는 1이라는 뜻이고, 합이 1이므로 1은 하나뿐이다. 따라서 는 순수 상태의 판정 기준이 된다.
선행 개념: 파울리 행렬의 곱 관계(O15a) · 행렬 함수(O16c) · 블로흐 좌표(O16a) · 벡터곱과 삼중곱 항등식
실수 벡터 에 대해 로 쓴다. O15a의 관계 , , , 로 두 합의 곱을 전개하자. 같은 행렬끼리의 곱은 를 주고, 서로 다른 행렬끼리의 곱은 벡터곱 의 성분을 준다.
예를 들어 의 계수는 다음 두 항에서만 나온다.
단위벡터 이면 이다. 또 순서를 바꾼 식을 빼면 교환자가 나온다.
는 에르미트이고 제곱이 이므로 고윳값이 이다. O16c의 규칙을 대신 에 그대로 쓰면
이다. 이 좌표축이면 O16a의 이고, 이면 이다.
, 라 하고 블로흐 벡터 의 를 변환하자. 이므로
첫 단계의 두 식으로 둘째 항과 셋째 항을 계산한다. 셋째 항은 에 을 한 번 더 곱하고, 벡터 항등식 , 을 쓴 것이다.
, , 를 쓰면 는 로 간다.
이것이 축 둘레로 만큼 돌리는 로드리게스(Rodrigues) 회전 공식이다. 방향 성분은 그대로이고, 수직 성분은 에 대해 오른손 방향으로 만큼 돈다. 이면 D01에서 직접 계산하는 행렬과 같다.
이면 이다. 이면 이고 도 같은 방식이다. 이면 이므로
이다. 이므로 표의 와 는 회전과 전체 위상 만 다르고, 전체 위상은 블로흐 벡터를 바꾸지 않는다.
이면 이다. , , 이므로 세 행 , , 를 얻는다. 항등 행렬은 이다. 이로써 O16b의 표를 모두 유도했다.
선행 개념: 원격 효과 사상(C09a) · 행렬 함수와 양의 제곱근(O16c) · 전치(C09a) · 슈미트 분해(O04a)
원하는 분해에서 각 이고 이므로 이다. 의 지지 공간에 직교하는 에서는
이다. 양의 준정부호 행렬에서 이면 이다. 지지 공간으로의 사영을 라 하면 이고, 수반을 취하면 이므로 이다.
이라 하자. 로 두면 모든 에서 이다. 전치도 양성을 보존한다. 를 성분의 켤레라 하면
이기 때문이다. 따라서 C09p의 효과 는 양의 준정부호다.
첫 등식은 고윳값마다 이고 영 고윳값 공간에서는 0이기 때문이다. 는 에르미트이고 이므로 사영이며, 따라서 이다. 이를 첫 효과에 더하면 합이 인 POVM이 된다.
C09p의 식 에 를 넣으면 이므로
이다. 마지막 등식은 첫 단계의 결과다. 첫 효과에 더한 는 을 주므로 복원을 바꾸지 않는다. 이로써 의 모든 분해가 의 측정 결과로 준비된다는 HJW 구성이 완성된다.
선행 개념: 유니타리 시간 진화 · 행렬 함수(O16c)
유한차원 해밀토니안을 서로 다른 에너지 의 사영으로 라 쓰면, O16c의 행렬 함수로 이다. 따라서
인 항은 시간에 무관하다. 이면
이고 에서 0으로 간다. 에너지 값은 유한 개이므로 합과 극한의 순서를 바꿀 수 있고, SM07의 식 를 얻는다. 평균하는 시간 가 가장 작은 에너지 간격 에 대해 보다 훨씬 길 때 유한 시간 평균이 이 값에 가깝다.
선행 개념: 모듈러 위수(B06) · 위상 추정의 회로(B04) · 등비수열의 합과 측정 분포(B05, D09) · 정규직교 기저와 유니타리 연산
이고 의 위수가 이라 하자. 둘째 레지스터에 작용하는 를 에서 , 나머지 기저 상태에서 로 정한다. 이므로 이면 이다. 곧 은 일대일이고, 는 기저 상태의 순열이어서 유니타리다. 또 값 은 위수의 최소성에서 서로 다르고 이므로, 는 이 개 상태를 차례로 돌린다.
에 대해
로 두자. 는 을 으로 보내고 이므로, 합의 번호를 하나 옮겨 쓰면
이다. 곧 는 고유 위상이 인 고유 상태다.
고유 상태들을 같은 계수로 더하면
이다. 괄호 안은 공비가 인 등비수열의 합이다. 이면 모든 항이 1이어서 합이 1이고, 이면 공비가 1이 아니고 그 제곱이 1이므로 B05에서처럼 0이다. 따라서 이 중첩은 이다. 같은 등비수열의 합에서 이므로 들은 정규직교한다.
B06의 회로는 을 로 보낸다. 의 이진 자리마다 제어된 을 거는 것과 같으므로(B04), 위상 추정의 회로에 고유 상태 대신 을 넣은 것이다. 둘째 단계의 식과 선형성에서 역 푸리에 변환 뒤의 상태는
이다. 여기서 는 위상이 일 때 D09의 진폭이다. 들이 정규직교하므로 입력 레지스터에서 를 얻을 확률은
이다. 곧 고유 위상 를 균등하게 무작위로 고른 위상 추정과 같은 분포다. 둘째 레지스터를 보지 않아도 이 분포가 나오므로, 고유 상태를 준비하지 않고도 무작위 의 표본을 얻는다.
, , 이면 이고 고유 위상은 이다. 가 정수이므로 B05에서처럼 는 에서 1이고 그 밖에서 0이다. 따라서
이고 나머지 의 확률은 0이다. 이는 B07에서 둘째 레지스터의 측정값별로 계산한 결과와 같다. 와 이 공약수를 가지면 가 약분되어 분모가 보다 작게 보인다. 예를 들어 는 , 곧 을 준다(B06).
선행 개념: 독립 사건과 확률의 곱(N01) · 세 번 반복 부호의 다수결(O11) · BPP·BQP의 정의(O19b) · 회로의 균일성(O19b--2)
결정 문제의 한 입력에서 정답을 낼 확률이 인 알고리즘을 독립적으로 번 실행하고, 더 많이 나온 답을 택하자. 여기서 이고 는 홀수로 잡는다. 다수결이 틀리는 것은 정답이 나온 횟수 이 보다 작을 때다. 그런 결과 열 하나의 확률은
이다. 이고 이기 때문이다. 결과 열은 모두 개이므로
이다. 마지막 등식은 에서 나온다. 이면 괄호 안이 1보다 작으므로 실패 확률은 가 커질수록 지수적으로 줄어든다.
, 이면 정답이 0번 또는 1번 나올 때 틀린다.
이는 O11의 세 번 반복 부호에서 반전 확률을 로 둔 다수결 오류 확률 과 같다. 두 경우 모두 독립인 세 결과의 다수결이기 때문이다. 첫 단계의 상한 는 느슨하지만, 가 커질 때 지수적으로 줄어든다는 점이 중요하다.
모든 입력에서 정답 확률이 적어도 인 다항식 시간 확률적 알고리즘이 있다고 하자. 여기서 는 입력과 무관한 상수다. 인 홀수 도 입력과 무관한 상수이므로, 번 실행하고 다수결하는 알고리즘은 여전히 다항식 시간이고 모든 입력에서 정답 확률이 적어도 이다. 거꾸로 정답 확률이 이상이면 같은 방법으로 1보다 작은 어떤 상수 이상으로도 올릴 수 있다. 따라서 BPP의 정의에서 대신 보다 크고 1보다 작은 다른 상수를 써도 같은 클래스를 얻는다.
양자 알고리즘도 새 큐비트로 번 따로 실행하면 측정 결과들이 독립이고, 다수결은 고전적으로 계산하면 된다. 반복한 회로도 균일하게 생성되므로 BQP에도 같은 논증이 적용된다. 정답 확률이 정확히 이면() 반복해도 오류가 줄지 않으므로 기준은 보다 커야 한다. 또 한 번의 정답 확률이 1보다 작으면 번 모두 틀릴 확률이 0보다 크므로, 반복으로는 기준 1에 이르지 못한다.
선행 개념: 튜링 기계와 결정 문제(O06) · 기계와 입력의 부호화(O06--2)
튜링 기계 의 전이표는 유한하므로, 보편 튜링 기계에서처럼 하나의 유한한 문자열 으로 부호화할 수 있다. 기계의 부호와 입력 문자열의 쌍도 하나의 문자열로 부호화한다. 정지 문제는 쌍 를 받아, 을 에서 실행하면 언젠가 정지하는지 묻는 결정 문제다.
이 문제를 푸는 튜링 기계 가 있다고 가정하자. 는 모든 입력에서 정지하고, 이 에서 정지하면 에, 정지하지 않으면 에 도달한다.
를 부분 절차로 쓰는 새 기계 를 만든다. 는 입력 을 받아 쌍 의 부호로 바꾼 뒤 를 실행한다. 가 에 도달하면 는 헤드를 오른쪽으로 끝없이 옮기며 정지하지 않고, 에 도달하면 정지한다. 부호를 복사하는 단계, 의 전이표, 마지막 분기는 모두 유한한 전이 규칙이므로 도 튜링 기계다.
를 자기 자신의 부호 에서 실행하자. 가 에서 정지한다면 는 를 수락하므로, 구성에 따라 는 정지하지 않는다. 정지하지 않는다면 가 거부하므로 는 정지한다. 어느 쪽도 모순이므로 는 존재하지 않는다.
기계를 행, 입력 부호를 열로 늘어놓은 표를 생각하면 는 대각선 의 답을 뒤집도록 만든 기계다. 그래서 이 논증을 대각선 논법이라 부른다. 처치–튜링 논제를 받아들이면, 어떤 기계적 절차로도 모든 입력에서 정지 문제를 풀 수 없다.
선행 개념: 쇼어 9큐비트 부호와 여덟 검사(O26a, O27) · 연산자의 파울리 전개(O16d) · 보조계를 이용한 사영 측정(O23a) · 오류 신드롬(B09)
O27의 여덟 검사가 모두 인 공간을 라 하자. 계산 기저 상태 는 의 고유 상태이고, 고윳값은 이면 , 다르면 이다. 여섯 검사를 모두 로 만드는 기저 상태는 세 묶음이 각각 또는 인 여덟 개뿐이므로, 의 벡터는 이 여덟 상태의 중첩이다.
각 묶음의 기저를 로 바꾸자. 은 과 을 맞바꾸므로 이다. 따라서 의 값은 첫째와 둘째 묶음의 부호의 곱이고, 의 값은 둘째와 셋째 묶음의 부호의 곱이다. 두 값이 모두 이려면 세 부호가 같아야 하므로
이다. 곧 검사로 정한 공간은 O26a의 부호 공간과 같고 2차원이다.
잡음이 물리 큐비트 하나에만 작용한다고 하자. 잡음 채널의 각 크라우스 연산자 는 큐비트 의 행렬이므로, O16d의 전개로
이다. 계수는 에만 의존하고 논리 상태와는 무관하다. 따라서 네 파울리 가 부호 상태를 어떻게 바꾸는지, 그리고 신드롬 측정이 그 결과들을 어떻게 가르는지 알면 된다.
파울리 오류 가 검사 와 반가환하면 이고, 가환하면 이다. 따라서 은 여덟 검사의 공통 고유 상태이고, 그 고윳값 목록이 신드롬이다. 신드롬은 만으로 정해지고 논리 상태에 의존하지 않는다.
| 오류 | 값이 바뀌는 검사 | 값이 바뀌는 검사 | 신드롬의 수 |
|---|---|---|---|
| 의 묶음에서 를 포함한 것 | 없음 | 9 | |
| 없음 | 의 묶음을 포함한 것 | 3 | |
| 와 같음 | 와 같음 | 9 |
묶음의 첫째·가운데·셋째 자리의 오류는 그 묶음의 두 검사를 각각 , , 로 바꾸므로 아홉 의 신드롬은 모두 다르다. 첫째·둘째·셋째 묶음의 오류는 두 검사를 각각 , , 로 바꾸므로, 의 신드롬은 묶음만 알려 준다. 는 두 부분을 함께 바꾼다. 항등 오류까지 더하면 서로 다른 신드롬은 가지다.
신드롬이 다른 두 벡터는 서로 직교한다. 어떤 검사 에 대해 , 이면, 가 에르미트이므로 , 곧 이기 때문이다.
오류 가 작용한 상태의 네 항 , , , 은 신드롬이 서로 다르다. 따라서 신드롬을 측정하면 한 항만 남는다. 예를 들어 의 신드롬이 나오면 남는 상태는 이고, 그 확률 은 논리 상태와 무관하다.
복구는 신드롬의 검사 부분이 가리키는 자리에 를, 검사 부분이 가리키는 묶음의 한 자리 에 를 적용한다. 같은 묶음의 는 그 묶음 검사들의 곱이므로(예: ) 부호 공간에서 항등으로 작용한다. 따라서
이다. 마지막 식은 에서 나오며, 는 이면 , 아니면 다. 남는 것은 논리 상태와 무관한 전체 위상뿐이므로 어느 결과에서나 원래 부호 상태가 복구된다. 같은 절의 D14에 나오는 은 , 인 경우다.
측정 결과마다 복구까지 거친 상태는 꼴이다. 여기서 는 그 신드롬을 주는 중 하나다. 네 결과를 합하면 크라우스 연산자 하나의 기여는
이다. 등식은 네 벡터 이 정규직교이기 때문이다. 채널의 모든 크라우스 연산자에 대해 더하면 에서 계수가 1이 되어, 복구 뒤의 상태는 정확히 이다. 혼합된 부호 상태도 선형성으로 같다.
오류가 어느 큐비트에 생길지 모르고 여러 자리의 한 큐비트 오류가 확률적으로 섞여 있어도 결론은 같다. 복구 규칙은 신드롬만 보고 정해지며, 어느 자리의 오류든 위의 계산이 그대로 성립하기 때문이다. 같은 묶음의 은 신드롬이 같지만 부호 공간에서 같은 작용을 한다(같은 절 D14의 축퇴). 이로써 O27의 정리를 증명했다. 두 큐비트에 동시에 생긴 오류는 이 논증에 포함되지 않는다. 실제로 는 의 신드롬을 주어 잘못 복구되고 논리 오류 을 남긴다.
선행 개념: 양자 오류 정정 조건과 그 필요성(A12) · 안정자 사영과 대각합(B17) · 논리 파울리 연산자(O33b) · 파울리 연산자의 가환·반가환(O31)
큐비트 안정자군 가 독립 생성원 으로 생성되고 라 하자. B17에서 부호 공간의 사영은
이다. 오류 집합 는 파울리 연산자들이다. 곱 도 전체 위상을 제외하면 파울리 문자열이고, 파울리 연산자끼리는 가환하거나 반가환하므로(O31) 는 어떤 검사와 반가환하거나 모든 검사와 가환하여 에 속한다(O33b). 각 경우에 를 계산한다.
검사 가 와 반가환하면, 이므로
곧 이다. , 곧 (, )이면 이므로 이다.
O40a의 조건은 모든 에서 라는 것이다. 그러면 각 곱은 어떤 검사와 반가환하거나 에 속하므로, 앞 단계에서
이다. 이것이 A12의 정정 조건이다. 오류에 양의 확률 를 붙인 채널 의 크라우스 연산자 도 계수만 배가 되어 같은 조건을 만족하므로, 이 채널을 정확히 되돌리는 하나의 CPTP 복구 이 있다. 순수한 부호 상태 에서 이고, 순수 상태는 다른 상태들의 확률 혼합으로 쓸 수 없으므로(A12에서 여는 증명의 필요성 1과 같은 논증) 각 이다. 곧 하나의 복구가 어느 오류가 생겼든 되돌리므로 는 정정 가능한 오류 집합이다. 같은 절의 O40b에서 신드롬으로 구성한 복구가 이런 복구의 한 예다.
라 하자. 는 모든 검사와 가환하므로 와 가환하고, 부호 공간을 부호 공간으로 보낸다. 의 원소는 서로 가환하고 제곱이 인 생성원의 곱이므로 이다. 따라서 라면 가 되어 가정에 어긋나고, 각 는 항등이 아닌 파울리 문자열에 전체 위상을 곱한 것이다. 그 대각합은 0이므로(B17)
만약 부호 공간에서 가 스칼라 로 작용하면 이고, 대각합에서 , 곧 이다. 그러나 는 유니타리이고 이므로 이다. 따라서 는 부호 공간에서 어떤 스칼라로도 작용하지 않는다. 부호 공간의 모든 벡터가 의 고유벡터라면 고윳값이 다른 두 고유벡터의 합은 고유벡터가 아니므로 고윳값이 모두 같아 가 스칼라가 된다. 그러므로 가 방향을 바꾸는 부호 상태가 있다. 같은 절 O41a의 “일부 논리 상태를 바꾼다”가 이 뜻이다.
이제 오류 집합에 인 두 오류가 있다고 하자. 두 오류를 모두 정정하는 CPTP 복구 이 있다면, 선형성으로 그 복구는 채널 도 정정한다. A12의 정정 조건은 모든 복구에 대한 필요조건이므로(A12에서 여는 증명의 필요성 부분) , 곧 여야 한다. 이므로 이는 앞 단계의 보조정리와 모순이다. 따라서 신드롬을 읽고 파울리를 적용하는 복구뿐 아니라 어떤 CPTP 복구도 두 오류를 함께 정정하지 못한다. 앞의 충분성과 합치면, 파울리 오류 집합에 대해 O40a의 판정은 필요충분조건이다.
같은 절의 O41c에서는 무게가 이하인 두 오류의 곱의 무게가 이하, 곧 미만이어서 에 속할 수 없으므로 충분성 쪽이 적용된다.
선행 개념: 군의 공리: 좌항등원, 좌역원, 결합 법칙(O28)
O28의 공리는 좌항등원 (모든 에 대해 ), 좌역원(각 마다 인 ), 결합 법칙이다. 곱셈 기호는 생략한다. 이 세 공리만으로 O28 오른쪽의 다섯 성질을 증명한다. 순서가 중요하다. 우항등원을 보이려면 우역원이 필요하므로, 좌역원이 우역원이라는 것부터 보인다.
의 좌역원 에도 좌역원 가 있어 이다. 좌항등원과 결합 법칙을 차례로 쓰면
따라서 은 의 우역원이기도 하다.
앞 단계의 를 쓰면 모든 에 대해
곧 는 우항등원이기도 하다.
도 좌항등원이면 이고, 앞 단계에서 이므로 이다. 이 우항등원이어도 과 에서 같다. 또 이면
이고, 이면 이다. 곧 어느 쪽에서 곱해 가 되는 원소도 하나뿐이다.
이면 왼쪽에 을 곱하고 결합 법칙을 쓰면
거꾸로 이면 는 당연하다. 오른쪽에서 곱한 도 우역원 을 오른쪽에 곱해 같은 방법으로 를 준다. 대우를 취하면 일 때 이다. 그래서 연산표의 각 행과 각 열에는 같은 원소가 두 번 나타나지 않는다.
선행 개념: 토릭 검사와 닫힌 경로(O42, O45) · 두 전역 관계와 연결성(O44--2) · 홀짝성을 재는 고리 연산자(O48, O49) · 차원 정리(O39c)
변의 집합 의 모든 변에 를 곱한 연산자를 라 하자. 가 모든 꼭짓점 검사와 가환하는 것은 각 꼭짓점에서 의 변이 짝수 개인 것과 같다. 이런 를 닫힌 고리라 부른다. 고리 여러 개의 합이어도 된다. 가로 변 가운데 좌표가 와 사이인 개를 열이라 하자. O48 그림의 세로 점선이 가로지르는 변들이다.
에 있는 꼭짓점 개에서 의 변 수를 모두 더하면 짝수다. 이 합에는 열과 열의 가로 변이 한 번씩, 두 열 사이의 세로 변이 두 번씩 들어간다. 따라서 가 두 열에서 갖는 변 수의 홀짝이 같다. 모든 열에서 같은 이 값을 라 쓴다. 세로 변 가운데 좌표가 과 사이인 개를 행이라 하고, 같은 방식으로 를 정한다.
이면 개의 열마다 의 변이 적어도 하나 있고 열들은 서로 겹치지 않으므로 이다. 마찬가지로 이면 이다.
모든 계산은 에서 한다. 변 집합을 의 벡터로 보고, 각 꼭짓점에 닿는 변의 수를 로 세는 선형 사상 을 생각하자. 한 변의 상은 두 끝점이므로 상은 원소가 짝수 개인 꼭짓점 집합에 들어 있다. 격자가 연결되어 있으므로 두 꼭짓점을 잇는 경로의 상은 그 두 점이고, 이런 쌍을 더해 원소가 짝수 개인 집합을 모두 얻는다. 따라서 상의 차원은 이고, O39c의 차원 정리로 닫힌 고리들의 공간 의 차원은
이다. 한편 면 집합 에 속한 면마다 네 변을 로 모두 더한 것을 의 경계라 하자. 면 하나의 경계는 꼭짓점마다 변을 0개 또는 2개 가지므로 면 경계는 모두 닫힌 고리다. 경계가 0이면 변을 공유한 두 면이 에 함께 들거나 함께 빠지므로, 쌍대 격자가 연결되어 있어 는 공집합이나 전체다(O44--2). 이 사상에도 차원 정리를 쓰면 면 경계들의 공간은 차원이 이다.
면 하나의 경계는 각 열의 가로 변과 각 행의 세로 변을 0개 또는 2개 가지므로 두 홀짝성이 0이다. 선형성으로 모든 면 경계에서 두 홀짝성이 0이다. 한편 한 가로줄의 가로 변 개로 된 직선 고리는 이고, 한 세로줄의 세로 변으로 된 직선 고리는 이다. 따라서 닫힌 고리 공간에서 으로 가는 선형 사상 는 전사이고, 차원 정리로 그 핵의 차원은
이다. 면 경계들의 공간은 이 핵에 들어 있고 차원이 같으므로 원소 수 이 같다. 따라서 두 공간은 같다.
곧 두 홀짝성이 모두 0인 닫힌 고리 는 어떤 면 집합 의 경계이다. 공유된 변의 는 두 번 곱해져 지워지므로 이다. 가로 직선 고리 두 개의 합처럼 고리 하나하나는 토러스를 감아도 홀짝성이 0이면 여기에 들어간다. 두 고리 사이 띠의 면 검사를 모두 곱한 것이기 때문이다.
가 모든 검사와 가환하면 는 닫힌 고리다. 두 홀짝성이 0이면 앞 단계에 따라 는 면 검사의 곱이어서 부호 공간에서 항등으로 작용한다. 이면 는 한 열의 가로 변에 를 곱한 O49의 와 공유하는 변이 홀수 개이므로 반가환한다. 그 는 모든 검사와 가환하므로 는 검사의 곱에 위상을 곱한 것일 수 없고, 비자명한 논리 연산자다. 일 때도 같다. 첫 단계에 따라 이런 의 무게는 이상이거나 이상이다.
쌍대 격자도 토러스이고 면 검사와 꼭짓점 검사의 역할만 바뀌므로, 쌍대 격자의 닫힌 고리인 형 연산자에도 같은 결론이 성립한다. 두 종류가 섞인 파울리 가 모든 검사와 가환하면 는 꼭짓점 검사와, 는 면 검사와 가환한다. 두 부분이 모두 검사의 곱이면 도 위상을 빼면 검사의 곱이다. 따라서 가 비자명하면 적어도 한 부분이 비자명하고, 의 무게는 그 부분의 무게 이상이다. 직선 고리가 와 를 달성하므로 이다.
변 집합 가 토러스보다 충분히 작은 직사각형 패치 안에 있어서, 의 변을 하나도 쓰지 않는 열과 행, 그리고 와 겹치지 않는 가로·세로 직선 고리가 있다고 하자. 안의 닫힌 고리 는 그 열과 행에서 변이 0개이므로 두 홀짝성이 0이고, 셋째 단계에 따라 어떤 면 집합 의 경계다.
이제 에 온전히 들어 있지 않은 면들, 곧 밖의 변을 하나라도 가진 면들이 밖의 변을 가로질러 서로 이어져 있다고 하자. 직사각형 면 패치의 모든 변을 로 잡으면 그렇다. 밖의 변은 에 없으므로 그 변을 공유한 두 면은 에 함께 들거나 함께 빠진다. 따라서 이런 면들은 모두 에 들거나 모두 빠진다. 필요하면 를 여집합으로 바꾸어(경계는 같다) 모두 빠지게 할 수 있으므로, 는 에 온전히 들어 있는 면 검사들의 곱이다.
쌍대 격자에 같은 논리를 쓰면, 밖의 변을 가진 꼭짓점들이 밖의 변을 따라 이어져 있을 때 안의 형 쌍대 고리는 에 온전히 들어 있는 꼭짓점 검사들의 곱이다. 따라서 에 지지되고 모든 검사와 가환하는 파울리는 위상을 빼면 안의 검사들의 곱이다. 두 홀짝성 가운데 하나가 0이 아닌 논리 연산자는 에 지지될 수 없다. 뒤의 TO03은 이 결과로 원판에 지지되는 독립 안정자를 센다.
선행 개념: 직사각형 패치의 데이터와 검사 위치(O52, O56) · 파울리 연산자의 가환과 반가환 · 안정자와 논리 연산자(O33b)
O56의 기준 격자를 쓰자. 데이터는 격자점 (, )와 칸 중심 에 있다. 세로 변 –의 중점에 있는 검사를 라 하자. 이 검사는 두 끝점과 좌우의 칸 중심에 작용하고, 좌우 경계에서는 칸 중심이 하나뿐이라 인자가 셋이다. 가로 변 –의 중점에 있는 검사를 라 하자. 이 검사는 두 끝점과 위아래의 칸 중심에 작용하고, 상하 경계에서 인자가 셋이다. 서로 다른 종류의 두 검사는 데이터를 0개 또는 2개 공유하므로 가환한다.
세로줄 의 격자점 개에 를 곱한 것을 , 가로줄 의 격자점 개에 를 곱한 것을 라 하자. 뒤의 A15에서 쓰는 과 이 이런 줄이다. 는 검사와 데이터를 0개 또는 2개 공유하고 는 검사와 0개 또는 2개 공유하므로, 둘 다 모든 검사와 가환한다. 또 와 는 격자점 하나만 공유하므로 반가환한다.
세로줄 와 사이의 검사 개를 모두 곱하자. 그 사이의 칸 중심은 위아래 두 검사에 한 번씩 들어가 지워지고, 두 세로줄의 격자점은 한 번씩 남는다. 가로줄 사이의 검사도 같으므로
이다. 따라서 모든 는 검사를 곱해 서로 바뀌고, 모든 는 검사를 곱해 서로 바뀐다. 특히 가로줄의 대표 는 서로 겹치지 않는 개의, 부호 공간에서 같은 논리 연산자다.
데이터 큐비트의 집합 에 를 곱한 연산자 가 모든 검사와 가환한다고 하자. 칸 중심을 칸 열마다 아래에서부터 지운다. 칸 열 의 맨 아래 칸 중심에 가 있으면 그 칸 위의 가로 변 검사 을 곱한다. 이 검사가 작용하는 칸 중심은 그 칸과 바로 위 칸뿐이므로, 아래 칸이 지워지고 위 칸만 바뀐다. 이를 위로 반복하고 맨 위 칸은 상하 경계의 무게 3 검사 로 지운다. 모든 칸 열에서 이렇게 하면 검사를 곱해 칸 중심에 가 없는 을 얻고, 이것도 모든 검사와 가환한다.
이제 검사 는 칸 중심 말고는 두 격자점 , 에만 작용하므로, 가환하려면 이 두 점을 함께 갖거나 함께 갖지 않아야 한다. 따라서 은 세로줄 몇 개의 합이고 이다. 둘째 단계로 줄을 하나씩 옮기면 이 곱은 검사를 곱해 또는 이 된다. 곧 모든 검사와 가환하는 형 연산자는 검사의 곱이거나, 그것에 을 곱한 것이다.
형 연산자 가 모든 검사와 가환하고 검사의 곱이 아니면, 앞 단계에 따라 는 에 검사 몇 개를 곱한 것이다. 검사는 모든 와 가환하고 은 모든 와 반가환하므로, 는 서로 겹치지 않는 와 모두 반가환한다. 반가환하려면 공유하는 큐비트가 있어야 하므로 는 가로줄마다 적어도 한 큐비트를 갖고 이다.
형은 가로와 세로, 검사와 검사를 바꾸어 같은 논리가 성립한다. 칸 중심을 칸 행마다 검사로 지우고, 남은 격자점이 가로줄의 합임을 쓴다. 그래서 비자명한 형 연산자의 무게는 이상이다. 두 종류가 섞인 파울리 가 모든 검사와 가환하면 는 검사와, 는 검사와 가환한다. 따라서 각 부분은 검사의 곱에 또는 논리 연산자를 곱한 것이다. 가 비자명하면 적어도 한 부분이 비자명하므로 의 무게는 이상이고, 대표 경로가 이 값을 달성한다.
또 모든 검사와 가환하는 파울리는 위상을 빼면 검사의 곱에 , , , 가운데 하나를 곱한 것이다. 논리 파울리 쌍이 하나뿐이므로 O56의 과 맞는다.
선행 개념: 안정자 상태의 엔트로피 (EN05) · 원판의 독립 안정자 세기(TO03) · 영역 안 고리를 검사로 채우기(D20에서 여는 증명) · Kitaev–Preskill 조합(TO04)
TO03처럼 서로 가환하는 두 논리 파울리의 고윳값을 고정한 순수 안정자 바닥 상태를 쓰자. 변 집합 에 대해 EN05에서 이다. 는 의 변 수이고, 는 에 지지되는 안정자들의 독립 생성원 수다.
가 토러스보다 충분히 작은 패치 안에 있고, 밖의 변을 가진 면들이 밖의 변을 가로질러 이어져 있으며, 밖의 변을 가진 꼭짓점들도 밖의 변을 따라 이어져 있다고 하자. D20에서 여는 증명의 마지막 단계에 따라 에 지지되는 안정자는 에 온전히 들어 있는 면·꼭짓점 검사들의 곱이다. 이 검사들은 모든 면이나 모든 꼭짓점을 담지 않으므로 서로 독립이다(O44--2). 따라서 는 에 온전히 들어 있는 검사의 수다.
가 서로 겹치지 않는 변 집합이면 처럼 변의 수는 더해지므로
이다. 일곱 영역이 모두 첫 단계의 조건을 만족하면 TO04의 조합은
가 된다.
에 온전히 들어 있는 검사 하나를 잡고, 그 변들이 속한 영역의 모임을 이라 하자. 이 검사는 의 영역을 모두 포함하는 합집합에만 온전히 들어 있다. 이면 에 하나씩 들어가 부호를 붙인 합이 이다. 이면 에만 들어가 이다. 다른 영역도 같다. 일 때만 하나에 들어가 이 남는다. 에 온전히 들어 있지 않은 검사는 어느 항에도 들지 않는다. 따라서 은 세 영역의 변을 모두 가진 검사의 수다.
TO04 그림의 배치를 격자에서 이렇게 잡자. 는 큰 직사각형 면 패치의 모든 변이고, 가운데 꼭짓점 을 지나는 가로선보다 위에 있는 변들이 다. 그 가로선에 놓인 변은 의 왼쪽이 , 오른쪽이 다. 가로선 아래에서는 에서 내려가는 세로선의 변과 그 왼쪽의 변이 , 오른쪽의 변이 다. 세 영역이 모두 의 바깥 경계에 닿으므로, 한 영역에 온전히 들어 있지 않은 면이나 꼭짓점에서 그 영역 밖의 변만 따라 바깥까지 갈 수 있다. 그래서 일곱 영역이 모두 첫 단계의 조건을 만족한다.
세 영역의 변을 모두 가진 검사는 의 꼭짓점 검사 하나뿐이다. 그 네 변은 위가 , 왼쪽과 아래가 , 오른쪽이 다. 두 영역의 경계선에 놓인 다른 꼭짓점과 면, 그리고 에 닿는 네 면은 많아야 두 영역에 걸치고(왼쪽 아래 면은 에만 들어 있다), 나머지 검사는 한 영역에만 걸친다. 따라서 이고 비트다. 이 값은 패치의 크기와 무관하며, TO02a의 에서 얻는 과 같다. 위상 이론의 일반식은 쓰지 않았다.
Equation output: MathJax 4.1.3; official @mathjax/mathjax-stix2-font package.
Apache License
Version 2.0, January 2004
http://www.apache.org/licenses/
TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
1. Definitions.
"License" shall mean the terms and conditions for use, reproduction,
and distribution as defined by Sections 1 through 9 of this document.
"Licensor" shall mean the copyright owner or entity authorized by
the copyright owner that is granting the License.
"Legal Entity" shall mean the union of the acting entity and all
other entities that control, are controlled by, or are under common
control with that entity. For the purposes of this definition,
"control" means (i) the power, direct or indirect, to cause the
direction or management of such entity, whether by contract or
otherwise, or (ii) ownership of fifty percent (50%) or more of the
outstanding shares, or (iii) beneficial ownership of such entity.
"You" (or "Your") shall mean an individual or Legal Entity
exercising permissions granted by this License.
"Source" form shall mean the preferred form for making modifications,
including but not limited to software source code, documentation
source, and configuration files.
"Object" form shall mean any form resulting from mechanical
transformation or translation of a Source form, including but
not limited to compiled object code, generated documentation,
and conversions to other media types.
"Work" shall mean the work of authorship, whether in Source or
Object form, made available under the License, as indicated by a
copyright notice that is included in or attached to the work
(an example is provided in the Appendix below).
"Derivative Works" shall mean any work, whether in Source or Object
form, that is based on (or derived from) the Work and for which the
editorial revisions, annotations, elaborations, or other modifications
represent, as a whole, an original work of authorship. For the purposes
of this License, Derivative Works shall not include works that remain
separable from, or merely link (or bind by name) to the interfaces of,
the Work and Derivative Works thereof.
"Contribution" shall mean any work of authorship, including
the original version of the Work and any modifications or additions
to that Work or Derivative Works thereof, that is intentionally
submitted to Licensor for inclusion in the Work by the copyright owner
or by an individual or Legal Entity authorized to submit on behalf of
the copyright owner. For the purposes of this definition, "submitted"
means any form of electronic, verbal, or written communication sent
to the Licensor or its representatives, including but not limited to
communication on electronic mailing lists, source code control systems,
and issue tracking systems that are managed by, or on behalf of, the
Licensor for the purpose of discussing and improving the Work, but
excluding communication that is conspicuously marked or otherwise
designated in writing by the copyright owner as "Not a Contribution."
"Contributor" shall mean Licensor and any individual or Legal Entity
on behalf of whom a Contribution has been received by Licensor and
subsequently incorporated within the Work.
2. Grant of Copyright License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
copyright license to reproduce, prepare Derivative Works of,
publicly display, publicly perform, sublicense, and distribute the
Work and such Derivative Works in Source or Object form.
3. Grant of Patent License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
(except as stated in this section) patent license to make, have made,
use, offer to sell, sell, import, and otherwise transfer the Work,
where such license applies only to those patent claims licensable
by such Contributor that are necessarily infringed by their
Contribution(s) alone or by combination of their Contribution(s)
with the Work to which such Contribution(s) was submitted. If You
institute patent litigation against any entity (including a
cross-claim or counterclaim in a lawsuit) alleging that the Work
or a Contribution incorporated within the Work constitutes direct
or contributory patent infringement, then any patent licenses
granted to You under this License for that Work shall terminate
as of the date such litigation is filed.
4. Redistribution. You may reproduce and distribute copies of the
Work or Derivative Works thereof in any medium, with or without
modifications, and in Source or Object form, provided that You
meet the following conditions:
(a) You must give any other recipients of the Work or
Derivative Works a copy of this License; and
(b) You must cause any modified files to carry prominent notices
stating that You changed the files; and
(c) You must retain, in the Source form of any Derivative Works
that You distribute, all copyright, patent, trademark, and
attribution notices from the Source form of the Work,
excluding those notices that do not pertain to any part of
the Derivative Works; and
(d) If the Work includes a "NOTICE" text file as part of its
distribution, then any Derivative Works that You distribute must
include a readable copy of the attribution notices contained
within such NOTICE file, excluding those notices that do not
pertain to any part of the Derivative Works, in at least one
of the following places: within a NOTICE text file distributed
as part of the Derivative Works; within the Source form or
documentation, if provided along with the Derivative Works; or,
within a display generated by the Derivative Works, if and
wherever such third-party notices normally appear. The contents
of the NOTICE file are for informational purposes only and
do not modify the License. You may add Your own attribution
notices within Derivative Works that You distribute, alongside
or as an addendum to the NOTICE text from the Work, provided
that such additional attribution notices cannot be construed
as modifying the License.
You may add Your own copyright statement to Your modifications and
may provide additional or different license terms and conditions
for use, reproduction, or distribution of Your modifications, or
for any such Derivative Works as a whole, provided Your use,
reproduction, and distribution of the Work otherwise complies with
the conditions stated in this License.
5. Submission of Contributions. Unless You explicitly state otherwise,
any Contribution intentionally submitted for inclusion in the Work
by You to the Licensor shall be under the terms and conditions of
this License, without any additional terms or conditions.
Notwithstanding the above, nothing herein shall supersede or modify
the terms of any separate license agreement you may have executed
with Licensor regarding such Contributions.
6. Trademarks. This License does not grant permission to use the trade
names, trademarks, service marks, or product names of the Licensor,
except as required for reasonable and customary use in describing the
origin of the Work and reproducing the content of the NOTICE file.
7. Disclaimer of Warranty. Unless required by applicable law or
agreed to in writing, Licensor provides the Work (and each
Contributor provides its Contributions) on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied, including, without limitation, any warranties or conditions
of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
PARTICULAR PURPOSE. You are solely responsible for determining the
appropriateness of using or redistributing the Work and assume any
risks associated with Your exercise of permissions under this License.
8. Limitation of Liability. In no event and under no legal theory,
whether in tort (including negligence), contract, or otherwise,
unless required by applicable law (such as deliberate and grossly
negligent acts) or agreed to in writing, shall any Contributor be
liable to You for damages, including any direct, indirect, special,
incidental, or consequential damages of any character arising as a
result of this License or out of the use or inability to use the
Work (including but not limited to damages for loss of goodwill,
work stoppage, computer failure or malfunction, or any and all
other commercial damages or losses), even if such Contributor
has been advised of the possibility of such damages.
9. Accepting Warranty or Additional Liability. While redistributing
the Work or Derivative Works thereof, You may choose to offer,
and charge a fee for, acceptance of support, warranty, indemnity,
or other liability obligations and/or rights consistent with this
License. However, in accepting such obligations, You may act only
on Your own behalf and on Your sole responsibility, not on behalf
of any other Contributor, and only if You agree to indemnify,
defend, and hold each Contributor harmless for any liability
incurred by, or claims asserted against, such Contributor by reason
of your accepting any such warranty or additional liability.
END OF TERMS AND CONDITIONS
APPENDIX: How to apply the Apache License to your work.
To apply the Apache License to your work, attach the following
boilerplate notice, with the fields enclosed by brackets "[]"
replaced with your own identifying information. (Don't include
the brackets!) The text should be enclosed in the appropriate
comment syntax for the file format. We also recommend that a
file or class name and description of purpose be included on the
same "printed page" as the copyright notice for easier
identification within third-party archives.
Copyright [yyyy] [name of copyright owner]
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.