hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
양자 논리 게이트 목록 비 클리포드 큐비트 게이트
모든 단일 큐비트 게이트와 마찬가지로 위상 이동 게이트의 제어 버전을 구축할 수 있다. 계산 기저에 대해 2-큐비트 제어 위상 이동 게이트는 다음과 같다. 상태 에 작용하는 경우에만 위상을 만큼 이동시킨다.
제어-Z(또는 CZ) 게이트는 인 특수 경우이다.
제어-S 게이트는 일 때 제어-의 경우이며 일반적으로 사용되는 게이트이다.
회전 연산자 게이트  및 는 SO(3)의 세 데카르트 축에 대한 회전 행렬의 아날로그이며, 블로흐 구면 투영의 x, y 또는 z축을 따라 회전한다.
파울리 행렬은 회전의 생성자와 관련되어 있으므로, 이러한 회전 연산자는 인수에 파울리 행렬이 있는 행렬 지수 함수로 작성될 수 있다. SU(2)의 모든  유니터리 행렬은 세 개 이하의 회전 게이트의 곱(즉, 직렬 회로)으로 작성될 수 있다. 큐비트 및 스피너와 같은 2준위 시스템의 경우 이러한 회전은 4π의 주기를 갖는다. 2π (360도) 회전은 다른 위상을 가진 동일한 상태 벡터를 반환한다.
양자 논리 게이트 목록 비 클리포드 큐비트 게이트
또한 모든 에 대해  및 가 성립한다.
회전 행렬은 다음 방식으로 파울리 행렬과 관련된다.
파울리 벡터에 대한 회전의 수반 작용을 계산할 수 있으며, 이는 로드리게스 회전 공식을 적용하기 위해 a 각도의 두 배만큼 효과적으로 회전하는 것이다.
위 공식에 임의의 단위 벡터를 내적하면 수반 회전 게이트 사이에 끼워 넣을 때 모든 단일 큐비트 게이트의 표현이 생성된다. 예를 들어, 임을 보일 수 있다. 또한, 반교환 관계를 사용하면 이다.
회전 연산자는 흥미로운 항등식을 가지고 있다. 예를 들어,  및 이다. 또한, 반교환 관계를 사용하면  및 이다.
전역 위상과 위상 이동은 Z-회전 연산자로 서로 변환될 수 있다. .
게이트는 블로흐 구면에서 x축에 대한 π/2 회전을 나타낸다. .
겔만 행렬을 사용하여 SU(3)에도 유사한 회전 연산자 게이트가 존재한다. 이들은 큐트리트와 함께 사용되는 회전 연산자이다.
큐비트-큐비트 이징 결합 또는 하이젠베르크 상호작용 게이트 Rxx, Ryy 및 Rzz는 2-큐비트 게이트로, 예를 들어 멜머-소렌센 게이트 절차를 사용하여 일부 이온 트랩 양자 컴퓨터에 기본적으로 구현된다.
양자 논리 게이트 목록 비 클리포드 큐비트 게이트
이러한 게이트는 사인파 형태로도 표현될 수 있으며, 예를 들어 와 같다.
CNOT 게이트는 회전 연산자 게이트와 정확히 하나의 2-큐비트 상호작용 게이트의 곱으로 더 분해될 수 있다. 예를 들어,
SWAP 게이트는 다른 게이트, 예를 들어 2큐비트 상호작용 게이트를 사용하여 구성될 수 있다. .
초전도 회로에서는 하이젠베르크 상호작용에서 비롯된 게이트 패밀리를 때때로 fSim 게이트 세트라고 부른다. 이들은 플럭스 조절 가능한 결합을 가진 플럭스 조절 가능한 큐비트를 사용하여 또는 고정 주파수 큐비트에서 마이크로파 구동을 사용하여 고정 결합으로 구현될 수 있다.
√SWAP 게이트는 2큐비트 스왑(클리포드 게이트 참조)의 절반을 수행한다. 이 게이트는 모든 다중 큐비트 게이트가 √SWAP 및 단일 큐비트 게이트만으로 구성될 수 있도록 범용적이다. 벨 상태를 곱셈 상태에서 생성하려면 √SWAP를 여러 번 적용해야 한다. √SWAP 게이트는 교환 상호작용을 활용하는 시스템에서 자연스럽게 발생한다.
양자 논리 게이트 목록 비 클리포드 큐비트 게이트
이징형 상호작용을 가진 시스템의 경우, 허수 스왑 또는 iSWAP을 도입하는 것이 때로는 더 자연스럽다. 이고 이며, 더 일반적으로는 0을 제외한 모든 실수 n에 대해 임을 유의하라.
SWAPα는 스핀트로닉스 양자 컴퓨터에서 자연스럽게 발생한다.
프레드킨 게이트 (CSWAP 또는 CS 게이트라고도 함)는 에드워드 프레드킨의 이름을 따서 명명된 3비트 게이트로, 제어 스왑을 수행한다. 이 게이트는 고전적인 계산에 대해 범용적이다. 이 게이트는 0과 1의 개수가 항상 보존된다는 유용한 속성을 가지고 있으며, 이는 당구공 컴퓨터 모델에서 입력된 공의 수와 동일한 수의 공이 출력된다는 것을 의미한다.
성희엽
성희엽(成熙曄, 1963년 ~ )은 대한민국의 행정공무원이다.
양자 레지스터
양자 컴퓨팅에서 양자 레지스터(영어: Quantum register)는 여러 큐비트로 구성된 시스템이다. 이는 고전적인 프로세서 레지스터의 양자적 아날로그이다. 양자 컴퓨터는 양자 레지스터 내의 큐비트를 조작하여 계산을 수행한다.
양자 레지스터 정의
레지스터는 일반적으로 큐비트로 구성된다고 가정된다. 또한 레지스터는 밀도 행렬이 아니라 순수하다고 일반적으로 가정되지만, '레지스터'의 정의는 밀도 행렬로 확장될 수 있다.
크기 양자 레지스터는 개의 순수 큐비트로 구성된 양자 시스템이다.
양자 레지스터에 데이터가 저장되는 힐베르트 공간, 는 로 주어지며, 여기서 는 텐서곱이다.
힐베르트 공간의 차원 수는 레지스터가 어떤 종류의 양자 시스템으로 구성되어 있는지에 따라 달라진다. 큐비트는 2차원 복소수 공간()인 반면, 큐트리트는 3차원 복소수 공간() 등이다. N개의 d-차원(또는 d-준위) 양자 시스템으로 구성된 레지스터의 경우 힐베르트 공간은 이다.
레지스터의 양자 상태는 브라-켓 표기법으로 로 쓸 수 있다. 값 는 확률 진폭이다. 보른 규칙과 확률론의 2차 공리에 따라 이므로 레지스터의 가능한 상태 공간은 에서 단위구의 표면이다.
예시:
양자 레지스터 양자 레지스터와 고전 레지스터의 비교
첫째, 양자 레지스터와 고전 레지스터 사이에는 개념적인 차이가 있다.
 크기 고전 레지스터는 개의 플립플롭 배열을 의미한다.  크기 양자 레지스터는 단순히 개의 큐비트 모음이다.
또한,  크기 고전 레지스터는 개의 고전 순수 비트로 확장되는 가지 가능성 중 하나의 값을 저장할 수 있지만, 양자 레지스터는 양자 순수 큐비트로 확장되는 모든 가지 가능성을 동시에 저장할 수 있다.
예를 들어, 2비트 폭 레지스터를 고려해보자. 고전 레지스터는 2비트로 표현되는 가능한 값 중 하나만 저장할 수 있다.
중첩 상태에 있는 2개의 순수 큐비트 와 를 고려하면, 양자 레지스터 정의 를 사용하면 두 큐비트로 확장되는 가능한 모든 값(모든 결과에 대해 0이 아닌 확률 진폭을 가짐)을 동시에 저장할 수 있음을 알 수 있다.
아다마르 변환
아다마르 변환(영어: Hadamard transform, 월시-아다마르 변환(Walsh–Hadamard transform), 아다마르-라데마허-월시 변환(Hadamard–Rademacher–Walsh transform), 월시 변환(Walsh transform), 또는 월시-푸리에 변환(Walsh–Fourier transform)이라고도 함)은 일반화된 푸리에 변환의 한 예시이다. 이는 2m개의 실수 (또는 복소수 또는 초복소수)에 대해 직교, 대칭, 대합적, 선형 연산을 수행한다 (아다마르 행렬 자체는 순수하게 실수이다).
아다마르 변환은 크기 2의 이산 푸리에 변환(DFT)으로 구성된 것으로 간주될 수 있으며, 실제로는 2 × 2 × ⋯ × 2 × 2 크기의 다차원 DFT와 동일하다. 이는 임의의 입력 벡터를 월시 함수의 중첩으로 분해한다.
이 변환은 프랑스의 수학자인 자크 아다마르(프랑스어: [adamaʁ]), 독일계 미국인 수학자 한스 라데마허, 그리고 미국인 수학자 조세프 월시의 이름을 따서 명명되었다.
아다마르 변환 정의
아다마르 변환 Hm은 2m × 2m 행렬인 아다마르 행렬(정규화 인자로 스케일링됨)로, 2m개의 실수 xn을 2m개의 실수 Xk로 변환한다. 아다마르 변환은 두 가지 방식으로 정의될 수 있다: 재귀적으로 정의하거나, 인덱스 n과 k의 이진 (기수-2) 표현을 사용하여 정의한다.
재귀적으로, 우리는 1 × 1 아다마르 변환 H0를 단위 H0 = 1로 정의하고, m > 0에 대해 Hm을 다음과 같이 정의한다:

여기서 1/√2는 때때로 생략되는 정규화 요소이다.
m > 1의 경우, Hm은 다음과 같이 정의될 수도 있다:

여기서 는 크로네커 곱을 나타낸다. 따라서, 이 정규화 인자를 제외하면, 아다마르 행렬은 완전히 1과 −1로 구성된다.
동등하게, 아다마르 행렬은 (k, n)-번째 항목을 다음과 같이 정의할 수 있다:
아다마르 변환 정의
여기서 kj와 nj는 각각 k와 n의 비트 요소(0 또는 1)이다. 왼쪽 상단 모서리의 요소에 대해 으로 정의한다. 이 경우, 다음이 성립한다:
이는 입력과 출력을 각각 nj와 kj로 인덱싱된 다차원 배열로 간주할 때, 정확히 의 다차원 DFT이며, 유니터리가 되도록 정규화되었다.
아다마르 행렬의 몇 가지 예시는 다음과 같다.

여기서 는 i와 j의 이진 표현의 비트 단위 스칼라곱이다. 예를 들어, 인 경우, 이 되며, 이는 위 결과와 일치한다(전체 상수 무시). 행렬의 첫 번째 행, 첫 번째 열 요소는 으로 표시된다.
H1은 정확히 크기 2의 DFT이다. 이는 또한 Z/(2)의 두 요소 덧셈 그룹에 대한 푸리에 변환으로 간주될 수 있다.
아다마르 행렬의 행은 월시 함수이다.
아다마르 변환 월시-아다마르 변환의 장점
행렬 H의 위 정의에 따르면, 여기서 H = H[m,n]으로 둔다.
월시 변환에서는 행렬에 1과 -1만 나타난다. 1과 -1은 실수이므로 복소수 계산을 수행할 필요가 없다.
DFT는 무리수 곱셈이 필요한 반면, 아다마르 변환은 그렇지 않다. 부호 반전만으로 충분하므로 유리수 곱셈도 필요하지 않다.
월시 변환 행렬에서 각 행과 각 열은 월시 함수이며, 부호 변화의 수가 연속적으로 증가한다. 즉, 첫 번째 행과 첫 번째 열에는 부호 변화가 없다(모든 항목이 1과 같다). 두 번째 행에는 하나의 부호 변화가 있고, 세 번째 행에는 두 개의 부호 변화가 있으며, 이런 식으로 마지막 행까지 이어진다. 이를 이산 푸리에 변환 과 비교하면, 각 행 i에는 개의 영점 교차가 포함된다.
이산 푸리에 변환에서 m이 0과 같을 때(첫 번째 행에 해당), 결과도 1이다. 이후 행에 대해서는 행렬의 특성인 신호 주파수가 첫 번째 원본 행렬에서는 낮게 시작하여 다음 행으로 갈수록 증가하다가 마지막 행에서 최고조에 달하는 것을 관찰할 수 있다.
아다마르 변환 푸리에 변환과의 관계
아다마르 변환은 사실 2 × 2 × ⋯ × 2 × 2 크기의 다차원 DFT와 동일하다.
또 다른 접근 방식은 아다마르 변환을 불 대수군 에 대한 푸리에 변환으로 보는 것이다.
 유한 (아벨) 군에 대한 푸리에 변환을 사용하여, 함수 의 푸리에 변환은 다음과 같이 정의된 함수 이다.

여기서 는 의 지표이다. 각 지표는 어떤 에 대해 의 형태를 가지며, 여기서 곱셈은 비트 문자열에 대한 불 스칼라곱이다. 따라서 의 입력을 (폰트랴긴 쌍대성)와 동일시하고, 를 다음과 같이 정의할 수 있다:
이는 와 의 입력을 불리언 문자열로 간주할 때 의 아다마르 변환이다.
아다마르 변환이 개의 복소수 벡터 에 왼쪽에서 아다마르 행렬 을 곱하는 위의 공식화 측면에서, 이 동등성은 를 의 요소 인덱스에 해당하는 비트 문자열을 입력으로 받고, 가 의 해당 요소를 출력하도록 취함으로써 확인된다.
이는 벡터 에 적용될 때 순환군 의 지표를 사용하는 일반적인 이산 푸리에 변환과 비교된다.
아다마르 변환 계산 복잡도
고전적인 영역에서, 아다마르 변환은 고속 아다마르 변환 알고리즘을 사용하여  연산()으로 계산할 수 있다.
양자 영역에서, 아다마르 변환은 양자 논리 게이트로서 병렬화될 수 있으므로  시간에 계산할 수 있다.
아다마르 변환 양자 컴퓨팅 응용
아다마르 변환은 양자 컴퓨팅에서 광범위하게 사용된다. 2 × 2 아다마르 변환 은 아다마르 게이트로 알려진 양자 논리 게이트이며, -큐비트 레지스터의 각 큐비트에 아다마르 게이트를 병렬로 적용하는 것은 아다마르 변환 과 동일하다.
양자 컴퓨팅에서 아다마르 게이트는 하나의 큐비트 회전으로, 큐비트-기저 상태 와 를 계산 기저 상태 와 의 동일한 가중치를 갖는 두 개의 양자 중첩 상태로 매핑한다. 일반적으로 위상은 다음과 같이 선택된다:
디랙 표기법에서. 이는 변환행렬

에 해당한다. 이는  기저, 즉 계산 기저에서도 알려져 있다. 상태 와 는 각각 와 로 알려져 있으며, 함께 양자 컴퓨팅에서 극좌표 기저를 구성한다.
0 또는 1 큐비트에 아다마르 게이트를 한 번 적용하면 (처음 두 연산에서 볼 수 있듯이) 관측될 경우 0 또는 1이 동일한 확률로 나올 양자 상태가 생성된다. 이는 표준 확률적 계산 모델에서 공정한 동전을 던지는 것과 정확히 같다. 그러나 아다마르 게이트를 연속으로 두 번 적용하면 (마지막 두 연산에서 효과적으로 수행되는 것처럼), 최종 상태는 항상 초기 상태와 동일하다.
아다마르 변환 양자 컴퓨팅 응용
양자 아다마르 변환은 아다마르 변환의 텐서곱 구조 때문에 각 큐비트에 아다마르 게이트를 개별적으로 적용하는 것과 같다. 이 간단한 결과는 양자 아다마르 변환이  연산을 필요로 하며, 고전적인 경우  연산과 비교된다는 것을 의미한다.
-큐비트 시스템의 경우, 각  큐비트(각각 으로 초기화됨)에 작용하는 아다마르 게이트는  형태일 때 균일한 양자 중첩 상태를 준비하는 데 사용될 수 있다.
이 경우  큐비트를 사용하면 결합된 아다마르 게이트 은 개의 아다마르 게이트의 텐서곱으로 표현된다:
결과적인 균일 양자 중첩 상태는 다음과 같다:

이는 모든 에 대해 아다마르 게이트를 사용하여 균일 양자 상태를 준비하는 것을 일반화한다.
이 균일 양자 상태의 측정은 과  사이의 무작위 상태를 초래한다.
아다마르 변환 양자 컴퓨팅 응용
많은 양자 알고리즘은 아다마르 변환을 초기 단계로 사용한다. 앞서 설명했듯이, 이는 으로 초기화된 n 큐비트를  기저의 모든 2n 직교 상태의 동일한 가중치를 갖는 중첩으로 매핑하기 때문이다. 예를 들어, 이는 도이치–조사 알고리즘, 사이먼의 알고리즘, 번스타인-바지라니 알고리즘, 그리고 그로버 알고리즘에서 사용된다. 쇼어 알고리즘은 초기 아다마르 변환과 양자 푸리에 변환을 모두 사용하는데, 둘 다 유한군에 대한 푸리에 변환의 일종이다. 첫 번째는 에 대한 것이고 두 번째는 에 대한 것이다.
일반적인 경우  ≠  일 때 균일 양자 중첩 상태를 준비하는 것은 비자명하며 더 많은 작업이 필요하다.
균일 중첩 상태를 준비하기 위한 효율적이고 결정론적인 접근 방식

는 모든 에 대해 게이트 복잡도와 회로 깊이가 에 불과하며 최근에 발표되었다. 이 접근 방식은 오직

큐비트만 필요하다. 중요한 점은 이 접근 방식에서 균일 중첩 상태 를 생성하는 데 보조 큐비트나 다중 제어 양자 게이트가 필요하지 않다는 것이다.
아다마르 변환 분자 계통학(진화생물학) 응용
아다마르 변환은 분자 데이터를 사용하여 계통수를 추정하는 데 사용될 수 있다. 계통학은 유기체 간의 관계를 이해하는 데 초점을 맞춘 진화생물학의 하위 분야이다. DNA 다중서열정렬에서 얻은 위치 패턴 빈도의 벡터(또는 행렬)에 적용된 아다마르 변환은 나무 위상에 대한 정보를 담는 또 다른 벡터를 생성하는 데 사용될 수 있다. 계통 발생학적 아다마르 변환의 가역적 특성은 나무 위상 벡터로부터 위치 가능성을 계산할 수 있게 하여, 아다마르 변환을 최대 가능도 추정에 사용할 수 있도록 한다. 그러나 후자의 응용은 위치 가능성을 계산하는 다른 훨씬 더 효율적인 방법이 있기 때문에 위치 패턴 벡터에서 나무 벡터로의 변환보다 덜 유용하다. 그러나 계통 발생학적 아다마르 변환의 가역적 특성은 수학적 계통 발생학을 위한 우아한 도구를 제공한다.
계통 발생학적 아다마르 변환의 메커니즘은 나무 에 대한 위상 및 분지 길이 정보를 제공하는 벡터 를 사이트 패턴 벡터 또는 행렬 를 사용하여 계산하는 것을 포함한다.
여기서 는 적절한 크기의 아다마르 행렬이다. 이 방정식은 해석을 단순화하기 위해 세 개의 방정식 시리즈로 다시 작성될 수 있다:
아다마르 변환 분자 계통학(진화생물학) 응용
이 방정식의 가역적 특성은 다음과 같이 예상되는 사이트 패턴 벡터(또는 행렬)를 계산할 수 있게 한다:
DNA에 대한 Cavender–Farris–Neyman (CFN) 두 상태 치환 모델을 사용하여 뉴클레오타이드를 이진 문자(퓨린 A와 G는 R로, 피리미딘 C와 T는 Y로 인코딩)로 인코딩할 수 있다. 이렇게 하면 다중 서열 정렬을 위 사이트 패턴 벡터 로 인코딩할 수 있으며, 이는 다음 예시에서와 같이 나무 벡터 로 변환될 수 있다:
아다마르 변환 분자 계통학(진화생물학) 응용
이 표에 제시된 예시는 간략화된 세 가지 방정식 체계를 사용하며, Newick 형식으로 ((A,B),(C,D))로 작성될 수 있는 4개 분류군 나무에 대한 것이다. 사이트 패턴은 ABCD 순서로 작성된다. 이 특정 나무는 두 개의 긴 말단 가지(사이트당 0.2개의 트랜스버전 치환), 두 개의 짧은 말단 가지(사이트당 0.025개의 트랜스버전 치환), 그리고 짧은 내부 가지(사이트당 0.025개의 트랜스버전 치환)를 가지고 있다. 따라서 Newick 형식으로는 ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2))로 작성될 것이다. 이 나무는 데이터가 최대 단순성 기준으로 분석될 경우 긴 가지 끌림을 나타낼 것이다(분석된 서열이 관찰된 사이트 패턴 빈도가  열에 표시된 예상 빈도에 근접할 만큼 충분히 길다고 가정). 긴 가지 끌림은 인덱스 6의 사이트 패턴(나무 ((A,C),(B,D))를 지지하는)의 예상 수가 참 나무(인덱스 4)를 지지하는 예상 사이트 패턴의 수를 초과한다는 사실을 반영한다. 분명히, 계통 발생학적 아다마르 변환의 가역적 특성은 나무 벡터 가 정확한 나무에 해당한다는 것을 의미한다. 따라서 변환 후의 단순성 분석은 통계적으로 일치하며, 올바른 모델(이 경우 CFN 모델)을 사용하는 표준 최대 우도 분석과 동일하다.
아다마르 변환 분자 계통학(진화생물학) 응용
0 인덱스의 사이트 패턴은 (뉴클레오타이드를 퓨린 또는 피리미딘으로 인코딩한 후) 변경되지 않은 사이트에 해당한다. 별표가 있는 인덱스(3, 5, 6)는 "parsimony-informative"하며, 나머지 인덱스는 단일 분류군이 다른 세 분류군과 다른 사이트 패턴을 나타낸다(따라서 표준 최대 우도 계통수에서 말단 가지 길이와 동등하다).
RY 데이터 없이 뉴클레오타이드 데이터를 사용하려면(궁극적으로 0과 1로 재코딩), 사이트 패턴을 행렬로 인코딩할 수 있다. 4개 분류군 나무를 고려하면 총 256개의 사이트 패턴(4개의 뉴클레오타이드의 4제곱)이 존재한다. 그러나 기무라 3매개변수(또는 K81) 모델의 대칭성을 통해 DNA에 대한 256개의 가능한 사이트 패턴을 64개 패턴으로 줄일 수 있으며, 이로 인해 4개 분류군 나무에 대한 뉴클레오타이드 데이터를 8 × 8 행렬로 인코딩할 수 있다. 이는 위에서 전이(RY) 사이트 패턴에 사용된 8개 요소 벡터와 유사하다. 이는 클라인 4원군을 사용하여 데이터를 재코딩함으로써 달성된다:
아다마르 변환 분자 계통학(진화생물학) 응용
RY 데이터와 마찬가지로, 사이트 패턴은 임의로 선택된 첫 번째 분류군의 염기를 기준으로 색인화되며, 이후 분류군의 염기는 해당 첫 번째 염기를 기준으로 인코딩된다. 따라서 첫 번째 분류군은 비트 쌍 (0,0)을 받는다. 이 비트 쌍을 사용하여 RY 벡터와 유사한 두 개의 벡터를 생성한 다음 해당 벡터를 사용하여 행렬을 채울 수 있다. 이는 Hendy et al. (1994)의 예시를 사용하여 설명할 수 있으며, 이는 네 가지 영장류 헤모글로빈 유사유전자의 다중 서열 정렬을 기반으로 한다:
0열에 훨씬 더 많은 사이트 패턴이 있는 것은 0열이 전이 차이에 해당하기 때문이며, 이는 거의 모든 유전체 영역 비교에서 트랜스버전 차이보다 더 빠르게 축적된다(그리고 이 예시에 사용된 헤모글로빈 유사유전자에서는 확실히 더 빠르게 축적된다). AAGG 사이트 패턴을 고려하면 클라인 군 비트 쌍의 두 번째 요소에 대해 이진 패턴 0000이 되고, 첫 번째 요소에 대해 0011이 된다. 이 경우 첫 번째 요소를 기반으로 한 이진 패턴은 인덱스 3(테이블에서 단일 별표로 표시)에 해당한다. GGAA, CCTT, TTCC 사이트 패턴도 정확히 같은 방식으로 인코딩된다. AACT 사이트 패턴은 두 번째 요소에 대해 이진 패턴 0011, 첫 번째 요소에 대해 0001로 인코딩된다. 이는 첫 번째 요소에 대해 인덱스 1, 두 번째 요소에 대해 인덱스 3을 생성한다. 두 번째 클라인 군 비트 쌍을 기반으로 한 인덱스는 8을 곱하여 열 인덱스(이 경우 24열)를 산출한다. AACT 사이트 패턴의 개수가 포함될 셀은 두 개의 별표로 표시되어 있다. 그러나 예시에서 숫자가 없는 것은 서열 정렬에 AACT 사이트 패턴이 없음을 나타낸다(마찬가지로 CCAG, GGTC, TTGA 사이트 패턴도 같은 방식으로 인코딩되며, 이들도 없음).
아다마르 변환 기타 응용
아다마르 변환은 데이터 암호화, JPEG XR 및 MPEG-4 AVC와 같은 많은 신호 처리 및 데이터 압축 알고리즘에서도 사용된다. 영상 압축 응용 프로그램에서는 일반적으로 변환된 차이의 절대값 합계 형태로 사용된다. 또한 양자 컴퓨팅에서 상당수의 알고리즘의 중요한 부분이다. 아다마르 변환은 핵자기 공명, 질량 분석법 및 결정학과 같은 실험 기술에도 적용된다. 또한 일부 버전의 지역 민감 해싱에서도 의사 난수 행렬 회전을 얻기 위해 사용된다.
디스카드 프로토콜
디스카드 프로토콜(Discard Protocol)은 인터넷 프로토콜 스위트의 서비스 중 하나로, 1983년 존 포스텔이 RFC 863에서 정의했다. 이 프로토콜은 테스트, 디버깅, 측정 및 호스트 관리 목적으로 설계되었다.
호스트는 전송 제어 프로토콜(TCP) 또는 사용자 데이터그램 프로토콜(UDP)의 포트 번호 9번을 통해 디스카드 프로토콜을 지원하는 호스트로 데이터를 보낼 수 있다. 서버로 전송된 데이터는 단순히 폐기되며, 응답은 반환되지 않는다. 이러한 이유로 UDP가 주로 사용되지만, TCP는 서비스가 세션 지향 연결(예: HTTP 프록시 또는 일부 가상사설망(VPN)을 통한 연결)에서 접근 가능하도록 허용한다.
파일히포
파일히포(FileHippo)는 마이크로소프트 윈도우용 컴퓨터 소프트웨어를 제공하는 소프트웨어 다운로드 웹사이트이다. 이 웹사이트에는 가장 최근에 업데이트된 프로그램과 가장 인기 있는 다운로드 목록이 카테고리별로 정리되어 있으며, 프로그램 정보와 링크가 제공된다. 이 웹사이트에서는 회원 가입이 필요하지 않으며, 파일히포는 게시자의 소프트웨어 제출을 받지 않는다.
파일히포 역사
파일히포는 2004년 맨섬 램지의 기술 회사인 웰 노운 미디어(Well Known Media)에 의해 설립되었다. 이 사이트는 2014년에 뉴스 섹션을 추가했다. 파일히포는 2015년 11월에 1,300만 달러 이상의 가치를 가진 것으로 추정되었다.
소프트오닉이 FileHippo.com 웹사이트를 인수하기 전에는 사용자 기부와 제3자 광고로 자금을 조달했으며, 업데이트 검사기( 이후 앱 관리자로 이름 변경됨)를 보유했는데, 이 무료 프로그램은 컴퓨터에서 오래된 소프트웨어를 검색하고 최신 버전으로 연결되는 링크를 제공했으며, 나중에는 IObit 소프트웨어 업데이터로 리디렉션되었다.
소프트오닉이 파일히포를 인수했다. 2020년 6월 17일 이후 파일히포 홈페이지는 이전에 "© FileHippo s.r.o."라고 명시되어 있었으나, 2020년 7월 3일부터는 "Softonic International, S.A.는 파일히포의 이름과 로고를 사용할 수 있는 라이선스를 보유합니다."라고 명시되어 있다.
P2P 웹 호스팅
P2P 웹 호스팅 또는 피어 투 피어 웹 호스팅(Peer-to-peer web hosting)은 P2P 네트워크를 사용하여 웹 페이지에 대한 접근을 분산하는 것이다. 이것은 전용 웹 서버와 사용자 단말 클라이언트 컴퓨터 간의 웹 데이터 분배를 포함하는 클라이언트 서버 모델과는 차별화된다. P2P 웹 호스팅은 P2P 웹 캐시 및 콘텐츠 전송 네트워크의 형태로도 사용될 수 있다.
P2P 웹 호스팅 비교
P2P 웹 호스팅은 클라이언트와 서버를 구분하지 않으며, 모든 노드가 서비스를 요청하고 응답할 수 있다. 모든 노드는 데이터를 저장할 수 있으며, 자원을 생성하고 소비할 수 있다. 이는 호스팅의 자원 공유 능력이 존재하는 노드의 수와 함께 증가한다는 것을 의미한다. 클라이언트-서버 웹 호스팅보다 비용이 적게 드는 경우가 많다. P2P 공유는 두 컴퓨터 간에 큰 파일을 공유할 때 대역폭을 절약하는 데 도움이 되며, 데이터를 공유하는 데 매우 효율적이다. 이 방법은 보안 부족으로 인해 위험할 수 있다. P2P 사이트에서 발견되고 공유되는 많은 파일은 불법이거나 운영 체제에 위험할 수 있다.
클라이언트 서버 모델 웹 호스팅은 클라이언트와 서버를 구분하며, 중앙 서버는 데이터를 저장하고 클라이언트가 요청하는 서비스에 응답하는 데 사용된다. 클라이언트-서버 네트워크는 더 안정적이지만 클라이언트 수가 증가함에 따라 성능이 저하되기 시작한다. 모든 데이터가 중앙 웹 서버에 저장되고 호스트가 접근할 수 있으므로 데이터를 규제하기가 훨씬 쉽다.
프레드킨 게이트
프레드킨 게이트(영어: Fredkin gate, 제어-SWAP 게이트(controlled-SWAP gate) 또는 보존 논리 게이트(conservative logic gate)라고도 함)는 에드워드 프레드킨이 발명한 가역 컴퓨팅에 적합한 계산 회로이다. 이는 보편적이며, 이는 모든 논리적 또는 산술적 연산이 전적으로 프레드킨 게이트로 구성될 수 있음을 의미한다. 프레드킨 게이트는 3개의 입력과 3개의 출력을 가진 회로 또는 장치로, 첫 번째 비트는 변경하지 않고 전송하며, 첫 번째 비트가 1인 경우에만 마지막 두 비트를 바꾼다.
프레드킨 게이트 배경
MIT 컴퓨터 과학 연구소에서 에드워드 프레드킨과 토마소 토폴리가 개념화한 프레드킨 게이트는 가역 컴퓨팅 및 보존 논리 분야에서 중추적인 발전이었다. 보존 논리 프레임워크 내에서 개발된 이 게이트는 계산 프로세스를 역동적인 법칙의 가역성 및 에너지 보존과 같은 근본적인 물리적 원칙과 일치하도록 설계되었다. 프레드킨 게이트의 기술적 근거는 비가역적 연산이 일반적으로 상당한 에너지 손실을 초래하는 기존 컴퓨팅의 비효율성을 해결하는 데 뿌리를 두고 있다.
정보를 지우고 란다우어의 원리에 따라 열을 방출하는 기존 논리 게이트와 달리, 프레드킨 게이트는 계산 과정에서 정보 손실이 없도록 하는 가역성을 유지한다. 게이트의 각 출력 상태는 입력 상태를 고유하게 결정하여 정보가 보존될 뿐만 아니라 에너지 보존 원칙과도 일치한다. 이러한 특성은 계산 능력에 대한 수요가 증가함에 따라 에너지 효율성이 핵심 고려 사항이 되면서 특히 중요하다.
프레드킨 게이트 배경
프레드킨 게이트의 발명은 계산 연산의 에너지 발자국을 최소화하려는 노력에서 비롯되었다. 이는 처리 속도 및 전력 소비 측면에서 효율적일 뿐만 아니라 환경적으로도 지속 가능한 컴퓨팅 시스템을 구축할 수 있게 한다. 가역 컴퓨팅의 원리를 구현함으로써 프레드킨 게이트는 디지털 계산과 관련된 에너지 비용을 절감하는 실용적인 솔루션을 제공하여 보다 지속 가능한 컴퓨팅 기술로의 중요한 전환점을 마련했다.
프레드킨 게이트 정의
기본 프레드킨 게이트는 세 개의 입력 (C, I1, I2)를 세 개의 출력 (C, O1, O2)로 매핑하는 제어 스와프 게이트(CSWAP 게이트)이다. C 입력은 C 출력으로 직접 매핑된다. C = 0이면 스와프가 수행되지 않는다. I1은 O1로 매핑되고, I2는 O2로 매핑된다. 그렇지 않으면 두 출력이 스와프되어 I1은 O2로, I2는 O1로 매핑된다. 이 회로는 가역적이며, 즉 역방향으로 실행될 때 자체적으로 "되돌려진다"는 것을 쉽게 알 수 있다. 일반화된 n × n 프레드킨 게이트는 첫 n - 2개의 입력을 해당 출력으로 변경 없이 통과시키고, 첫 n - 2개의 입력이 모두 1인 경우에만 마지막 두 출력을 바꾼다.
프레드킨 게이트 AND, OR, XOR, NOT을 사용한 진리 함수
프레드킨 게이트는 AND, OR, XOR, NOT과 같은 진리 함수를 사용하여 다음과 같이 정의할 수 있다.
O1 = I1 XOR S,
O2 = I2 XOR S,
Cout = Cin,
여기서 S = (I1 XOR I2) AND C이다.
또는:
O1 = (NOT C AND I1) OR (C AND I2),
O2 = (C AND I1) OR (NOT C AND I2),
Cout = Cin.
프레드킨 게이트 완전성
프레드킨 게이트가 보편적임을 알 수 있는 한 가지 방법은 AND, NOT, OR을 구현하는 데 사용될 수 있다는 점을 관찰하는 것이다.
I2 = 0이면, O2 = C AND I1이다.
I2 = 1이면, O1 = C OR I1이다.
I1 = 0이고 I2 = 1이면, O2 = NOT C이다.
프레드킨 게이트 하드웨어 설명
베릴로그와 같은 하드웨어 설명 언어로 진리표를 인코딩할 수 있다.
프레드킨 게이트 예시
5개의 프레드킨 게이트를 사용하는 3비트 전가산기(캐리 포함 덧셈). "가비지" 출력 비트 g는 r = 0이면 (p NOR q)이고, r = 1이면 (p NAND q)이다.
두 개의 상수를 포함한 왼쪽 입력은 세 개의 게이트를 통과하여 패리티를 빠르게 결정한다. 설정된 각 입력 비트에 대해 0과 1 비트가 위치를 바꾸어, 네 번째 행에 패리티 비트가, 다섯 번째 행에 패리티의 역이 나타난다.
그 다음, 패리티 비트가 설정되면 캐리 행과 역 패리티 행이 위치를 바꾸고, p 또는 q 입력 비트 중 하나가 설정되면(어떤 것을 사용하든 상관없음) 다시 위치를 바꾸어 결과 캐리 출력이 세 번째 행에 나타난다.
p 및 q 입력은 게이트 제어로만 사용되므로 출력에서 변경되지 않고 나타난다.
프레드킨 게이트 응용 분야
최근 연구에 따르면 프레드킨 게이트가 프로그래밍 가능한 실리콘 광자 칩에서 시연되었다. 이 칩들은 마흐-젠더 간섭계 네트워크를 사용하여 광자를 효율적으로 라우팅하며, 다수의 양자 게이트를 처리할 수 있는 다용도 및 확장 가능한 플랫폼을 생성한다. 이러한 접근 방식은 프레드킨 게이트를 대규모 양자 프로세서에 통합할 수 있게 하여 미래 양자 컴퓨팅 발전을 위한 길을 열어준다.
광자 설정에서 프레드킨 게이트는 효율적인 제어-SWAP 메커니즘으로 작동하여 대상 큐비트의 조건부 스왑을 가능하게 한다. 이는 양자 통신 및 기타 프로토콜에 중요한 고충실도 그린베르거-호른-자일링거 상태를 생성하는 데 특히 유용하다. 따라서 이 게이트는 효율적인 조건부 연산이 필요한 양자 프로토콜에 강력한 도구를 제공한다.
프레드킨 게이트의 제어 연산은 자원 집약적인 양자 상태 단층 촬영 없이 양자 상태 간의 중첩을 추정할 수 있게 한다. 이는 효율성과 정확성이 가장 중요한 양자 통신, 측정 및 암호화에 특히 유용하다.
프레드킨 게이트 양자 프레드킨 게이트
2016년 3월 25일, 그리피스 대학교와 퀸즐랜드 대학교 연구원들은 빛 입자의 양자 얽힘을 이용하여 큐비트를 교환하는 양자 프레드킨 게이트를 구축했다고 발표했다. 양자 프레드킨 게이트의 가용성은 양자 컴퓨터 구축을 용이하게 할 수 있다.
프레드킨 게이트 더 읽어보기
Fredkin, Edward; Toffoli, Tommaso (1982). 《Conservative Logic》 (PDF). 《International Journal of Theoretical Physics》 21. 219–253쪽. Bibcode:1982IJTP...21..219F. doi:10.1007/BF01857727. S2CID 37305161. 2006년 10월 17일에 원본 문서 (PDF)에서 보존된 문서.
RuTracker.org
RuTracker.org (rutracker★org로도 표기되며, 2010년까지는 torrents.ru로 알려짐)는 가장 큰 러시아 비트토렌트 트래커이다. 2024년 12월 현재 1490만 명의 등록된 활성 사용자, 248만 4천 개의 토렌트 (이 중 247만 9천 개가 활성 상태)를 보유하고 있으며, 모든 토렌트의 총 용량은 5.8 페타바이트이다.
일반화된 분배 법칙
일반화된 분배 법칙(영어: Generalized distributive law, GDL)은 분배법칙을 일반화한 것으로, 일반적인 메시지 전달 알고리즘을 발생시킨다. 이는 정보 이론, 디지털 통신, 신호 처리, 통계학, 인공지능 분야의 많은 저자들의 작업을 종합한 것이다. 이 법칙과 알고리즘은 스리니바스 M. 아지(Srinivas M. Aji)와 로버트 매켈리스(Robert J. McEliece)가 같은 제목의 준-튜토리얼에서 소개했다.
일반화된 분배 법칙 서론
"수학에서 분배 법칙은 곱셈과 덧셈 연산을 관련시키는 법칙으로, 기호적으로 로 표현된다. 즉, 단항식 인수 는 이항식 인수 의 각 항에 분배되거나 개별적으로 적용되어 곱 를 생성한다" - 브리태니커.
정의에서 알 수 있듯이, 산술식에 분배 법칙을 적용하면 연산의 수가 줄어든다. 이전 예에서 총 연산 수는 세 개(에서 두 개의 곱셈과 하나의 덧셈)에서 두 개(에서 하나의 곱셈과 하나의 덧셈)로 줄었다. 분배 법칙의 일반화는 많은 고속 알고리즘을 탄생시킨다. 여기에는 FFT와 비터비 알고리즘이 포함된다.
이는 아래 예에서 더 형식적으로 설명된다.
여기서 와 는 실수 값 함수이고, 이며  (가령)
여기서 우리는 독립 변수(, , )를 "주변화(marginalizing out)"하여 결과를 얻는다. 계산 복잡도를 계산할 때, 의 각  쌍에 대해 삼중항 로 인해 개의 항이 존재하며, 각 단계에서 하나의 덧셈과 하나의 곱셈을 포함하여 의 평가에 참여해야 함을 알 수 있다. 따라서 필요한 총 계산 수는 이다. 그러므로 위 함수의 점근적 복잡도는 이다.
일반화된 분배 법칙 서론
방정식의 RHS에 분배 법칙을 적용하면 다음을 얻는다.
이는 가 곱 로 설명될 수 있음을 의미한다. 여기서 이고
이제 계산 복잡도를 계산할 때, 와  각각에 개의 덧셈이 있고, 곱 를 사용하여 를 평가할 때 개의 곱셈이 있음을 알 수 있다. 따라서 필요한 총 계산 수는 이다. 그러므로 를 계산하는 점근적 복잡도는 에서 로 줄어든다. 이는 분배 법칙을 적용하는 것이 계산 복잡도를 줄여 "고속 알고리즘"의 좋은 특징 중 하나임을 예시로 보여준다.
일반화된 분배 법칙 역사
분배 법칙을 사용하여 해결된 문제 중 일부는 다음과 같이 분류할 수 있다.
디코딩 알고리즘: GDL과 유사한 알고리즘이 갤러거(Gallager)에 의해 저밀도 패리티 검사 부호(low density parity-check codes) 디코딩에 사용되었다. 갤러거의 작업을 기반으로 태너(Tanner)는 태너 그래프를 도입하고 갤러거의 작업을 메시지 전달 형식으로 표현했다. 태너 그래프는 비터비 알고리즘을 설명하는 데도 도움이 되었다. 포니(Forney)는 컨볼루션 부호에 대한 비터비의 최대 우도 디코딩(maximum likelihood decoding) 또한 GDL과 유사한 일반성의 알고리즘을 사용했음을 관찰했다.
일반화된 분배 법칙 MPF 문제
MPF 또는 곱 함수 주변화(marginalize a product function)는 이산 아다마르 변환, 무기억 채널을 통한 선형 부호의 최대 우도 디코딩, 행렬 연쇄 곱셈과 같은 많은 고전적인 문제를 특수한 경우로 포함하는 일반적인 계산 문제이다. GDL의 힘은 덧셈과 곱셈이 일반화되는 상황에 적용된다는 사실에 있다.
가환 반환은 이러한 동작을 설명하는 좋은 프레임워크이다. 이는 집합 에서 연산 ""와 ""를 사용하여 정의되며, 여기서 와 는 가환 모노이드이고 분배 법칙이 성립한다.
을 변수라고 하자. 여기서 이고 는 유한 집합이며 이다. 여기서 이다. 만약 이고 이면,
, ,
, , 그리고
라고 하자. 여기서 이다. 함수가 로 정의된다고 가정하자. 여기서 은 가환 반환이다. 또한, 는 지역 도메인(local domains)으로, 는 지역 커널(local kernels)로 명명된다.
일반화된 분배 법칙 MPF 문제
이제 전역 커널(global kernel) 는 다음과 같이 정의된다:
MPF 문제의 정의: 하나 이상의 인덱스 에 대해, 전역 커널 의 -주변화(marginalization) 값 테이블을 계산한다. 이는 로 정의된 함수로 이다.
여기서 는 에 대한 의 여집합이고, 는  목표 함수 또는 에서의 목표 함수라고 불린다.  목표 함수의 계산은 명백한 방법으로  연산이 필요하다는 것을 알 수 있다. 이는  목표 함수의 계산에 개의 덧셈과 개의 곱셈이 필요하기 때문이다. 다음 섹션에서 설명할 GDL 알고리즘은 이러한 계산 복잡도를 줄일 수 있다.
다음은 MPF 문제의 예이다.
및 를 변수라고 하자. 여기서  및 이다. 여기서 이고 이다. 이 변수들을 사용하여 정의된 함수는 와 이며, 우리는 다음과 같이 정의된 와 를 계산해야 한다.
여기서 지역 도메인과 지역 커널은 다음과 같이 정의된다.
일반화된 분배 법칙 MPF 문제
여기서 는  목표 함수이고 는  목표 함수이다.
이고 가 실수 값 함수인 또 다른 예를 생각해보자. 이제, 교환 가능한 반환(commutative semiring)이 일반적인 덧셈과 곱셈을 가진 실수의 집합으로 정의되는 MPF 문제를 고려할 것이며, 지역 도메인과 지역 커널은 다음과 같이 정의된다.
이제 전역 커널은 지역 커널의 곱으로 정의되므로, 다음과 같다.
그리고 지역 도메인 에서의 목표 함수는 다음과 같다.
이것은 함수 의 아다마르 변환이다. 따라서 아다마르 변환의 계산이 MPF 문제의 특수한 경우임을 알 수 있다. 위에서 설명했듯이 MPF 문제가 많은 고전적인 문제의 특수한 경우를 형성한다는 것을 입증하기 위해 더 많은 예를 제시할 수 있으며, 자세한 내용은 다음에서 찾을 수 있다.
일반화된 분배 법칙 GDL: MPF 문제를 해결하기 위한 알고리즘
주어진 집합 의 요소들 사이에 관계를 찾을 수 있다면, "메시지 전달" 기술의 특별한 용법인 신뢰전파의 개념을 기반으로 MPF 문제를 해결할 수 있다. 필요한 관계는 주어진 지역 도메인 집합이 결합 트리로 구성될 수 있다는 것이다. 다시 말해, 의 요소를 트리 의 정점으로 사용하여 그래프 이론적 트리를 생성하는데, 임의의 두 정점 와  (단 이고 이 두 정점 사이에 간선이 존재함)에 대해, 해당 레이블의 교집합, 즉 가 에서 까지의 유일한 경로에 있는 각 정점의 레이블의 부분 집합이 되도록 한다.
예를 들어,
예시 1: 다음 아홉 가지 지역 도메인을 고려해 보자.
위에서 주어진 지역 도메인 집합에 대해 다음과 같이 결합 트리를 구성할 수 있다.
마찬가지로 다음과 같은 또 다른 집합이 주어진다면
예시 2: 다음 네 가지 지역 도메인을 고려해 보자.
일반화된 분배 법칙 GDL: MPF 문제를 해결하기 위한 알고리즘
이러한 지역 도메인만으로 트리를 구성하는 것은 불가능하다. 이 값 집합에는 위 집합의 어떤 두 값 사이에도 배치할 수 있는 공통 도메인이 없기 때문이다. 하지만, 아래와 같이 두 개의 더미 도메인을 추가하면 업데이트된 집합을 결합 트리로 구성하는 것이 가능하고 쉽다.
5.,
6.,
마찬가지로 이러한 도메인 집합에 대한 결합 트리는 아래와 같이 보인다.
입력: 지역 도메인 집합.
출력: 주어진 도메인 집합에 대해, 문제를 해결하는 데 필요한 최소 연산 수를 계산한다.
따라서, 와 가 결합 트리에서 간선으로 연결되어 있다면, 에서 로의 메시지는 함수로 주어지는 값의 집합/테이블이다: :. 시작 시 모든 함수, 즉 주어진 트리의 모든 와 의 조합에 대해 는 항등적으로 로 정의되며, 특정 메시지가 업데이트될 때 아래 주어진 방정식을 따른다.
일반화된 분배 법칙 GDL: MPF 문제를 해결하기 위한 알고리즘
=
여기서 는 가 트리에서 의 인접 정점임을 의미한다.
마찬가지로 각 정점은 함수 에서 값을 포함하는 테이블로 정의된 상태를 가진다. 메시지가 항등적으로 1로 초기화되는 것처럼, 의 상태는 지역 커널 로 정의되지만, 가 업데이트될 때마다 다음 방정식을 따른다.
입력으로 주어진 지역 도메인 집합에 대해, 먼저 집합을 직접 사용하거나 더미 도메인을 추가하여 결합 트리를 생성할 수 있는지 알아낸다. 만약 결합 트리 생성이 불가능하면, 알고리즘은 주어진 방정식 문제를 계산하기 위한 단계 수를 줄일 방법이 없다고 출력한다. 하지만 결합 트리가 있으면, 알고리즘은 메시지를 스케줄링하고 상태를 계산해야 한다. 이를 통해 단계 수를 줄일 수 있는 지점을 알 수 있으므로, 아래에서 논의할 것이다.
일반화된 분배 법칙 메시지 전달 및 상태 계산의 스케줄링
여기서 다룰 두 가지 특수한 경우가 있다. 하나는 목표 함수가 단 하나의 정점 에서 계산되는 단일 정점 문제(Single Vertex Problem)이고, 다른 하나는 모든 정점에서 목표 함수를 계산하는 것이 목표인 모든 정점 문제(All Vertices Problem)이다.
단일 정점 문제부터 시작하자. GDL은 각 간선을 대상 정점  방향으로 지정하는 것으로 시작한다. 여기서는 메시지가 대상 정점 방향으로만 한 번만 전송된다. 메시지는 잎 노드(Degree가 1인 노드)에서 시작하여 대상 정점  방향으로 이동한다. 메시지는 잎에서 부모로, 그리고 거기서부터 다시 부모로 계속 이동하여 대상 정점 에 도달한다. 대상 정점 은 모든 이웃 노드로부터 모든 메시지를 받은 후에만 상태를 계산한다. 상태를 얻으면 답을 얻은 것이므로 알고리즘이 종료된다.
예를 들어, 위에 주어진 지역 도메인 집합, 즉 예시 1의 집합으로 구성된 결합 트리를 고려해 보자.이제 이 도메인에 대한 스케줄링 테이블은 다음과 같다(대상 정점은 ).
일반화된 분배 법칙 메시지 전달 및 상태 계산의 스케줄링
따라서 단일 정점 GDL의 복잡도는 다음과 같이 표현될 수 있다.
산술 연산
여기서 (참고: 위 방정식에 대한 설명은 이 문서 뒷부분에 설명되어 있다.)
는 의 레이블이다.
는 의 차수 (즉, 에 인접한 정점의 수)이다.
모든 정점 문제를 해결하기 위해 GDL을 여러 가지 방법으로 스케줄링할 수 있다. 그중 일부는 병렬 구현으로, 각 라운드에서 모든 상태가 업데이트되고 모든 메시지가 동시에 계산 및 전송된다. 이러한 유형의 구현에서 상태와 메시지는 트리의 지름(diameter)과 같거나 그 이하의 라운드 후에 안정화된다. 이 시점에서 모든 정점의 모든 상태는 원하는 목표 함수와 동일해진다.
이 문제에 대한 GDL을 스케줄링하는 또 다른 방법은 직렬 구현이다. 이는 단일 정점 문제와 유사하지만, 필요한 집합의 모든 정점이 모든 이웃으로부터 모든 메시지를 받고 자신의 상태를 계산할 때까지 알고리즘을 멈추지 않는다는 점이 다르다.
따라서 이 구현에 필요한 산술 연산의 수는 최대 개이다.
일반화된 분배 법칙 결합 트리 구성
결합 트리를 구성하는 핵심은 지역 도메인 그래프 에 있다. 이는 개의 정점 을 가진 가중치 있는 완전 그래프이다. 즉, 각 지역 도메인에 대해 하나의 정점이 있으며, 간선 의 가중치는 다음과 같이 정의된다.
.
만약 이면, 가 에 포함된다고 말한다.  ( 의 최대 가중치 신장 트리의 가중치)는 다음과 같이 정의된다.
여기서 n은 해당 집합의 요소 수이다. 더 명확하고 자세한 내용은 다음을 참조하라.
일반화된 분배 법칙 스케줄링 정리
를 정점 집합 와 간선 집합 를 가진 결합 트리라고 하자. 이 알고리즘에서 메시지는 어떤 간선에서든 양방향으로 전송되므로, 간선 집합 E를 순서쌍 정점의 집합으로 간주할 수 있다. 예를 들어, 그림 1에서 는 다음과 같이 정의될 수 있다.
참고:는 트리를 통해 메시지가 이동할 수 있는 모든 가능한 방향을 나타낸다.
GDL의 스케줄은 의 부분집합으로 이루어진 유한 수열로 정의된다. 이는 일반적으로 다음과 같이 표현된다.
{}, 여기서 은 알고리즘 실행의  라운드 동안 업데이트된 메시지 집합이다.
몇 가지 표기법을 정의/확인했으니, 정리가 무엇을 말하는지 살펴보자. 스케줄 이 주어지면, 해당 메시지 트렐리스는 정점 집합이 인 유한 방향 그래프로, 일반적인 요소는 에 대해 로 표시된다. 메시지 전달 완료 후, 정점 에서의 상태는 다음에 정의된  목표가 된다.
그리고 iff 에서 로의 경로가 존재한다.
일반화된 분배 법칙 계산 복잡도
여기서는 계산에 필요한 수학적 연산의 수로 MPF 문제 해결의 복잡도를 설명하고자 한다. 즉, 일반적인 방법(여기서 일반적인 방법이란 메시지 전달이나 결합 트리를 사용하지 않는 방법, 요컨대 GDL의 개념을 사용하지 않는 방법)과 일반화된 분배 법칙을 사용한 방법 간에 필요한 연산 수를 비교한다.
예시: 와 같은 표현을 계산해야 하는 가장 간단한 경우를 고려해 보자.
이 표현을 순진하게 평가하려면 두 번의 곱셈과 한 번의 덧셈이 필요하다. 분배 법칙을 사용하여 표현하면 로 쓸 수 있으며, 이는 연산 수를 한 번의 덧셈과 한 번의 곱셈으로 줄이는 간단한 최적화이다.
위에 설명된 예시와 유사하게, GDL을 적용하여 가능한 한 적은 연산을 수행하도록 방정식을 다른 형태로 표현할 것이다.
일반화된 분배 법칙 계산 복잡도
이전 섹션에서 설명했듯이, 우리는 결합 트리 개념을 사용하여 문제를 해결한다. 이러한 트리를 사용하여 얻은 최적화는 트리에서 반군 문제를 해결하여 얻은 최적화와 비교할 수 있다. 예를 들어, 일련의 숫자 중 최소값을 찾으려면 트리가 있고 요소가 모두 트리 바닥에 있을 때, 두 항목의 최소값을 병렬로 비교하고 결과 최소값은 부모에게 기록된다. 이 과정이 트리를 따라 위로 전파되면 그룹 요소의 최소값이 루트에서 발견될 것이다.
메시지 전달을 사용하여 결합 트리를 해결하는 복잡도는 다음과 같다.
이전에 사용된 공식을 다음 형태로 다시 작성한다. 이는 정점 v에서 w로 메시지를 보낼 때 사용되는 방정식이다.
----메시지 방정식
마찬가지로, 정점 v의 상태를 계산하는 방정식을 다음과 같이 다시 작성한다.
먼저 단일 정점 문제에 대해 분석하고, 대상 정점을 라고 가정하며, 따라서 에서 로의 간선이 하나 존재한다.
간선 가 있다고 가정하고, 메시지 방정식을 사용하여 메시지를 계산한다. 를 계산하는 데는 다음이 필요하다.
덧셈과
곱셈.
(를 로 나타낸다.)
그러나 에 대해 많은 가능성이 있을 것이므로 
개의 에 대한 가능성.
따라서 전체 메시지에는 다음이 필요하다.
일반화된 분배 법칙 계산 복잡도
덧셈과
곱셈.
트리의 간선을 따라 를 향해 메시지를 보내는 데 필요한 총 산술 연산은 다음과 같다.
덧셈과
곱셈.
모든 메시지가 전송되면, 에서의 상태 계산으로 알고리즘이 종료된다. 상태 계산에는 개의 곱셈이 추가로 필요하다.
따라서 상태를 계산하는 데 필요한 계산 수는 다음과 같다.
덧셈과
곱셈.
따라서 총 계산 수는 다음과 같다.
----
여기서 는 간선이며, 그 크기는 로 정의된다.
위 공식은 상한을 제공한다.
만약 간선 의 복잡도를 다음과 같이 정의한다면,
따라서 은 다음과 같이 쓸 수 있다.
이제 그림 1에서 정의된 문제에 대한 간선 복잡도를 다음과 같이 계산한다.
총 복잡도는 로, 직접적인 방법(여기서 직접적인 방법이란 메시지 전달을 사용하지 않는 방법을 의미한다. 직접적인 방법을 사용한 시간은 각 노드에서 메시지를 계산하고 각 노드의 상태를 계산하는 시간과 동일할 것이다)에 비해 상당히 낮다.
일반화된 분배 법칙 계산 복잡도
이제 모든 정점 문제를 고려한다. 여기서 메시지는 양방향으로 전송되어야 하며, 두 정점에서 모두 상태가 계산되어야 한다. 이는 가 소요되지만, 사전 계산을 통해 곱셈 횟수를 로 줄일 수 있다. 여기서 는 정점의 차수이다. 예: 개의 숫자로 구성된 집합 가 있다면,  중 개의 모든 곱을 명백한  대신 최대 개의 곱셈으로 계산할 수 있다.
이는 와 를 사전 계산하여 수행하며, 이는 개의 곱셈을 필요로 한다. 그런 다음 가 를 제외한 모든 의 곱을 나타낸다면,  등이 또 다른 개의 곱셈을 필요로 하여 총 가 된다.
결합 트리 구성에 있어서는 우리가 할 수 있는 일이 많지 않다. 단지 많은 최대 가중치 신장 트리가 있을 수 있으며, 가장 적은 를 가진 신장 트리를 선택해야 한다는 점만 기억하면 된다. 때로는 이를 위해 결합 트리 복잡도를 낮추기 위해 지역 도메인을 추가해야 할 수도 있다.
GDL은 지역 도메인이 결합 트리로 표현될 때만 정확한 것처럼 보일 수 있다. 하지만 사이클이 존재하고 여러 번 반복되는 경우에도 메시지는 목표 함수와 거의 같아진다. 저밀도 패리티 검사 코드에 대한 Gallager–Tanner–Wiberg 알고리즘 실험은 이러한 주장을 뒷받침했다.
교환 상호작용
화학 및 물리학에서 교환 상호작용(영어: Exchange interaction)은 구별 불가능한 입자의 상태에 대한 양자역학적 제약이다. 때로는 교환력(exchange force) 또는 페르미온의 경우 파울리 반발(Pauli repulsion)이라고도 불리지만 그 결과는 힘에 대한 고전적 개념만으로는 항상 예측할 수 없다. 보손과 페르미온 모두 교환 상호작용을 경험할 수 있다.
구별 불가능한 입자의 파동 함수는 교환 대칭성의 적용을 받는다. 두 입자가 교환될 때 파동 함수는 부호가 바뀌거나(페르미온의 경우) 변하지 않는다(보손의 경우). 교환 대칭성은 두 구별 불가능한 입자의 파동 함수가 겹칠 때 이들 사이의 거리의 기대값을 변경한다. 페르미온의 경우 거리의 기대값은 증가하고, 보손의 경우 감소한다(구별 가능한 입자와 비교하여).