complexity-classes Archives - Page 11 of 12

계산 모델 MPostBQP를 PostBQP와 동일하게 정의합니다. 단, 포스트 선택 및 최종 측정 전에 다 항적으로 많은 큐 비트 측정이 가능합니다.

MPostBQP가 PostBQP보다 강력하다는 증거를 제시 할 수 있습니까?

MPostBQP [k]를 정의하여 최종 측정을하기 전에 여러 라운드의 측정 및 사후 선택이 가능합니다. MPostBQP [1] = PostBQP 및 MPostBQP [2] = MPostBQP 등의 인덱싱을 선택하십시오. (업데이트 : 공식적인 정의는 다음과 같습니다.)

Arthur-Merlin 게임을 고려하십시오. 아마도 우리는이 계산 모델에서 그것들을 시뮬레이션 할 수있을 것입니다 : Postselection은 설득력있는 메시지를 생성하는 Merlin의 역할을 수행 할 수 있으며 중간 측정은 Arthur의 공개 동전 던지기의 역할을 수행 할 수 있습니다. 이 가능성은 다음과 같이 묻습니다.

AM [k] MPostBQP [k]가 있습니까? $\subset$
⊂

이것은 실제로 MA PP 라고하는 알려져 있습니다. 경우 AM PP 인 경우에만 MPostBQP = PP 를 나타냅니다 . PP에 AM이 포함되어 있지 않은 오라클이 있기 때문에 첫 번째 질문에 긍정적 인 대답을 줄 수 있습니다. $k = 1$

k=1

$\subset$

⊂

$k = 2$

k=2

$\subset$

⊂

마지막으로 다 항적으로 많은 라운드의 경우

PSPACE MPostBQP [poly]가 있습니까? 그렇다면 평등입니까? $\subset$
⊂

이것은 철학적으로 흥미로울 것입니다. (적어도 나에게는) “포스트 셀렉 팅 소서러”에 대한 “참을 수있는”종류의 문제 는 모든 PSPACE를 포함하거나 (또는 ) 있습니다.

편집 : MPostBQP의 공식적인 정의를 요청 받았습니다. (다음 내용을 업데이트했습니다.)

MPostBQP [k]는 언어 클래스로 , 모든 다항식 크기의 양자 회로 이 균일하게 존재 합니다. 입력 이면, 아래 절차는 인 경우 최소 확률로 , 경우 최대 확률로 true를 생성합니다 . ( 아님) 에 따라 달라질 수있는 일부 선택을 허용하는 절차 는 다음과 같이 정의됩니다. $L \subset {0, 1}^{*}$

L⊂{0,1}∗

${C_{n}}_{n \geq 1}$

{Cn}n≥1

$x$

$2 / 3$

2/3

$x \in L$

x∈L

$1 / 3$

1/3

$x \notin L$

x∉L

$L$

$x$

절차 : 단계 1. 에 해당하는 단일 연산자를 입력 상태 . 첫 번째 레지스터의 길이는 길이에서 최대 다항식입니다 . 2 단계 : : 가 짝수이면 첫 번째 레지스터 (레지스터의 크기에 따라 최대 폴리 노 미적으로 많은)에서 원하는 수의 큐 비트를 측정합니다. 가 홀수 인 경우 첫 번째 레지스터에서 선택한 단일 큐 비트가 $C_{n}$
Cn
$| 0 \dots 0 ⟩ \otimes | x ⟩$
|0⋯0⟩⊗|x⟩
$| 0 \dots 0 ⟩$
|0⋯0⟩
$x$
x
$i = 1 \dots k$
i=1⋯k
$i$
i
$i$
i
$| 0 ⟩$
|0⟩
(그리고 확률이 0이 아니라는 것을 보장하므로 사후 선택은 물론 유효합니다). 단계 3. 마지막으로, 첫 번째 레지스터에서 마지막 큐 비트를 측정하고 측정하면 true를, 그렇지 않으면 false를 반환합니다. $| 1 ⟩$
|1⟩

MPostBQP [0] = BQP, MPostBQP [1] = PostBQP 및 MPostBQP : = MPostBQP [2]가 있습니다. AM [0] = BPP, AM [1] = MA 및 AM [2] = AM 인 Arthur-Merlin 클래스를 미러링하려고합니다.

편집 (3/27/11 5 PM) :이 맥락에서 사후 선택을 정의하는 방법에 대한 논쟁이있는 것 같습니다. 분명히, 나는 내 질문을 사소하게하지 않는 정의를 의미합니다! 🙂 내가 가정 한 정의는 다음과 같습니다. k 번째 비트에서 사후 선택 은 상태를 k 번째 비트가 하위 공간으로 투영 함을 의미합니다. $0$

그리고 정상화하십시오. 측정하기 전에 사후 선택하는 방식에서는 사후 선택이 측정 값으로 대체되는 방식의 조건부 확률을 확인하여 최종 통계를 얻을 수 있습니다. 그러나 측정 및 사후 선택이 산재 될 때이 특성이 분해된다고 주장합니다. 혼동은 내가 방금 준 “강제 측정”정의보다는이 “조건부 확률 정의”(일반적인 특수 사례에서 작동 함)를 사후 선택의 정의로 사용하는 사람들에서 비롯된 것으로 생각합니다. commutativity 부족으로 질서. 이게 도움이 되길 바란다!

편집 (3/27/11 9 오후) : 나는 순수한 상태 형식주의에서 사후 선택을 이미 정의했다. Niel은 밀도 매트릭스 형식에 대한 분석을 통해 3 큐빗 예제에 대해 내 의견에 동의하지 않았습니다. 원인은 다시 선택 후의 정의입니다. 다음과 같이 밀도 매트릭스 설정에서 사후 선택을 정의하십시오. 밀도 행렬 주어지면 분리 가능한 상태 의 혼합으로 다시 작성하십시오 . 하자 내가 위에서 정의 된 순수한 상태 형식주의를 사용 (일부 큐 비트에) postselection의 결과. 에 postselection 결과 정의 으로 . $M$

$M = \sum p_{i} | a_{i} ⟩ ⟨ a_{i} |$

M=∑pi|ai⟩⟨ai|

$| A_{i} ⟩$

|Ai⟩

$M$

$\sum p_{i} | A_{i} ⟩ ⟨ A_{i} |$

∑pi|Ai⟩⟨Ai|

사후 선택 후 이미 발생한 이벤트 (측정) 통계를 변경한다는 결과를 제공하지 않기 때문에 이는보다 합리적인 정의 입니다. 즉, 는 우리가 "이미 뒤집은"동전의 확률입니다. 우리가 시간을 거슬러 올라가서 이미 발생한 동전 뒤집기를 편향시킬 것이라고 말하는 것은 이해가되지 않습니다. $p_{i}$

편집 (3/28/11 1 PM) : Niel은 내 정의에 따르면 문제가 의미가 있고 사소한 것이 아니라는 것을 인정하지만, postselection 이라고 부를 수 없다는 규정이 있습니다. 혼란의 정도를 감안할 때 나는 그에게 동의해야한다. 이제 "forced measurement"를 수행하는 selection 이라고 정의한 것을 호출 해 봅시다 . 아마도 내가 정의한 복잡성 클래스의 이름도 변경해야합니다 ( "포스트"를 갖지 않기 위해) QMS [k] (quantum-measure-select)라고하겠습니다.

답변

Shaun은 선택 후 일반적으로 이해되는 것과 다른 점을 염두에 둔 것으로 보입니다. 이제는 특정 사후 선택 이전에 수행 한 측정에 대한 통계가 후속 사후 선택에 의해 변경되어서는 안됨을 의미하는 것으로 이해합니다. 이는 정규화가 전체적인 파동 함수보다는 특정 측정 결과에 해당하는 파동 함수의 각 브랜치에 대해 수행되는 프로젝션 오퍼레이터와 유사하다.

이 경우 다른 답변에서 나 자신과 Neil의 주장은 더 이상 유효하지 않습니다. 실제로 쉽게 알 그 MPostBQP [K], 이후 MPostBQP BQP의 수 시스템으로 볼 수있다 보호 프로파일 오라클 쿼리, 따라서 MPostBQP 입니다. $P^{P P [k]} \subseteq$

PPP[k]⊆

$[k]$

[k]

$k$

$P^{# P} \subseteq$

P#P⊆

이제 우리는 사소한 하한을 가지고 있습니다. 상한은 어떻습니까? 분명히 문제는 PSPACE 에 있지만 더 잘할 수 있습니까? 실제로는 할 수 있다고 생각합니다.

MPostBQP의 계산은 양자 계산, 사후 선택, 단일 큐 비트 측정 형식의 레이어 시퀀스로 작성할 수 있습니다 . 실제로, 이것은 mPostBQP [k]를 와 같은 레이어 로 구성된 계산으로 공식화하는 다른 방법 일 수 있습니다 (이것은 사후 선택 수 만 계산하려고하는 Shaun의 정의와 약간 다릅니다). 고전적인 후 처리의 마지막 계층. MPostBQP [k]에 대한 이 정의를 다음에서 사용할 것 입니다. 더 미학적으로 좋은 결과를 가져옵니다. $k$

아래는 교정본의 구멍을 수정하기 위해 원본 버전에서 업데이트되었습니다.

먼저 측정 된 첫 번째 큐 비트 (사후 선택되지 않음)의 측정 결과를 계산하려고합니다. 이를 수행하기 위해 먼저 모든 양자 계산은하다 마드 게이트와 토 게이트 만 사용하여 표현할 수 있으며 , 출력에서 특정 계산 기준 상태 의 진폭 는 최대 의 합으로 쓰여질 수 있습니다. 항 . 여기서 는 Hadamard 게이트의 총 수이며 각 게이트는 고유 한 계산 경로에 해당합니다. 분명히 입니다. 최종 상태를 획득하는 확률은 다음에 의해 주어진다 $α_{w}$

αw

$| w ⟩$

|w⟩

$2^{H}$

$a_{j, w}$

aj,w

$H$

$a_{j, w} = \pm 2^{- H / 2}$

aj,w=±2−H/2

$| w ⟩$

|w⟩

$α_{w}^{2} = (\sum_{j} a_{j, w})^{2} = \sum_{i, j} a_{j, w} a_{i, w}$

αw2=(∑jaj,w)2=∑i,jaj,wai,w

. 1을 측정 할 수있는 총 확률을 계산하려고합니다. 선택 후 기준 (즉, 선택 후 큐 비트가 1)을 충족하는 계산 기준 상태 세트로 설정하고 측정 된 큐 비트에 대해 0을 결과로 설정하고 선택 후 기준을 충족하고 측정 된 qubit에 대해 1이되는 계산 기준 상태 집합이어야합니다. 우리는

및
$S_{0}$

$S_{1}$

π \pm 0 = \sum w \in S 0 \pm \sum s i g n (a j, w a i, w) = \pm a j, w a i, w

π \pm 1 = \pm \sum w \in S 1 \sum s i g n (a j, w a i, w) = \pm a j, w a i, w .

이 경우 사후 선택된 큐 비트에 대해 1에서 조건 1을 측정 할 확률은 . #P 오라클에 대한 4 번의 호출로이를 확인할 수 있습니다. 이를 사용 하여 양자 측정과 같은 확률 1 인 랜덤 비트 을 생성합니다 . 따라서 MPostBQP [1]은 있습니다. $\frac{π_{1}^{+} - π_{1}^{-}}{π_{1}^{+} - π_{1}^{-} - π_{0}^{-} + π_{0}^{+}}$

π1+−π1−π1+−π1−−π0−+π0+

$b_{1}$

$X_{1}$

$B P P^{# P [4]}$

BPP#P[4]

다음으로 두 번째 큐 비트의 측정 결과를 계산합니다. 이를 위해 동일한 실행 #P의 첫번째 층과 같은 쿼리하지만 상기 제 2 층 구성 및 의해 얻어진 회로 여기서 우리는 이후 선택된 큐 비트마다 1 사후 선택할뿐만 아니라,에 위한 이것은 1이 아닌 3 큐 비트의 상태 에서 사후 선택이지만, 이것은 3 큐 비트가 모두 필요한 조건을 충족하는 경우에만 설정되는 ancilla를 추가함으로써 쿼리에 대한 사소한 수정입니다. 이 대신에 사후 선택. 이것은 우리가 라벨 제 큐빗 측정 결과에 대한 올바른 출력 조건부 확률 생성 $b_{1}$

$# P$

$b_{2}$

. 우리는 이제 #P 오라클에 8 번의 호출을 사용했습니다 .

우리는이 프로세스를 반복적으로 반복하여, 레이어 에서 모든 포스트 선택 큐 비트 에 대해 1에서 postselect를 , 모든 이전 측정에 대해 에 postselect 하고 해당 의 결과에 레이블을 붙입니다. 머신 . 전체적으로 이것은 오라클 쿼리 가 필요했습니다 . $j$

$j$

$b_{i < j}$

bi<j

$P^{# P}$

P#P

$b_{j}$

$4 j$

따라서, 우리가 가진 MPostBQP [K] , 이전 결과와 결합되는 것을 MPostBQP , 그 의미 MPostBQP [k] 이므로 MPostBQP 입니다. $\subseteq P^{# P [4 k]}$

⊆P#P[4k]

$P^{P P [k]} \subseteq$

PPP[k]⊆

$[k]$

[k]

$P^{P P [k]} \subseteq$

PPP[k]⊆

$\subseteq B P P^{# P [4 k]}$

⊆BPP#P[4k]

$= P^{# P}$

=P#P

답변

[개정.] 귀하의 질문에 대한 귀하의 수정 사항에 따라 답변을 수정했습니다. 원래 답변의 내용은 유지했지만 더 짧게 만들었습니다. "시뮬레이션"프로세스에 대한보다 자세한 설명이 바뀌었지만이 게시물의 편집 히스토리를 보면 알 수 있다고 생각합니다.

대부분의 사람들은 조건부 확률의 의미에서 "선택 후"를 이해할 것입니다. 실제로, PostBQP 에 관한 Wikipedia 기사 의 현재 버전은이를 설명합니다. 밀도 연산자에 대한 연산으로 본다 (이것은 Φ ² = Φ가 되도록 완전 양성 트레이스-비 증가 맵 Φ를 적용한 후 트레이스를 재 정규화)는이 정의를 회복시킨다.

이러한 사후 선택의 정의가 주어지면 MPostBQP [ k ] 알고리즘의 정의 는 사후 선택을 연기하고 적절한 방식으로 동시에 수행함으로써 PostBQP 알고리즘 으로 시뮬레이션 할 수 있습니다 . 이 아론 손의 종이 3 페이지에 다소간 명시 적으로 언급되어 양자 컴퓨팅, Postselection 및 확률 다항식 타임 클래스 소개 PostBQP을 .

이 비트 시퀀스에 대해, 그 주목하여 명시 적으로 표시 할 수있는 P ₁ , P ₂ postselected으로는, ( 예를 들면 에서 1평소 상태)들이 존재에 조절 사이에는 차이가 없다 1의 중앙은 1이들 비트의 값이 중간에 변경되지 않는 한, 이들 의 계산 및 컨디셔닝은 계산 의 끝에있다. 그런 다음 각각 개별적으로 사후 선택하지 않고 사후 선택 1전에 논리 AND를 계산 한 다음 해당 연결에서 사후 선택을 수행 할 수 있습니다1. 또한, AND의 계산은 비트의 마지막 변환과 그 후 선택 사이의 임의의 시점에서 수행 될 수있다. 이것은 상태 속성의 공동 통계에 영향을 미치지 않습니다.

따라서 조건부 확률과 관련하여 사후 선택의 공통 정의를 사용하면 모든 k > 0에 대해 MPostBQP [ k ] = PostBQP 가 됩니다

. 위의 주석에서 언급했듯이 상태에 대해 설명하는 작업은 생각하지 않습니다. 벡터-구체적으로, 측정 결과에 대한 확률 분포의 각 분기에서 독립적 으로 상태 벡터의 재 정규화와 관련됨

— 현장의 많은 사람들 (종속적으로 실험적인 사람들)이 개념을 설명 하듯이 선택 후와 일치합니다. 밀도 연산자에 대한 매핑으로 확장되는 경우 일부 '비 물리적'속성이 발생할 수도 있습니다. 그러나 노드가 상태 벡터로 레이블이 지정된 의사 결정 트리와 같은 것을 구성하는 가능한 방법이므로 원칙적으로 자체적으로 합리적인 연구 과정입니다. 나는 그 과정을 '선택 후'라고 부르지 않을 것입니다.

[편집] 깔끔함을 위해 계산 된 예를 제거했습니다. 이 게시물의 편집 기록을 보면 볼 수 있다고 생각합니다.

답변

MPostBQP 정의에서 이것은 화려한 드레스를 입은 단순한 PostBQP 입니다. 오히려 아마 당신이 더 입증하기 위해 설득 찾을 것, 측정 순서가 변경 될 수 있음을 설득하는 것보다 MPostBQP = PP를 가 있음을 알 수 있으므로, PostBQP = PP는 (참조 퀀트 - 산도 / 0,412,187을 ). 이를 증명하기 위해 두 가지 작업으로 구분합니다.

증명이 PP MPostBQP $\subseteq$ 및
MPostBQP PP 증명 $\subseteq$

PP = PostBQP = MPostBQP [1] MPostBQP $\subseteq$

⊆

이므로 첫 번째 작업은 간단 합니다. 두 번째 작업은 실제로 주요 질문이지만 quant-ph / 0412187에 제공된 PostBQP = PP 증거에 간단히 적용하여 대답 할 수 있습니다 ( 증거 개요는 PostBQP 의 Wikipedia 페이지 참조 ).

다음은 PostBQP = PP에 대한 Wikipedia 증거 스케치에서 수정 한 것 입니다.

MPostBQP 계산에 해당하는 회로를 일련의 단일 게이트 및 사후 선택으로 작성할 수 있습니다 . 일반성을 잃지 않고 우리는 일단 큐 비트가 일단 선택된 후에는 다시는 행동하지 않는다고 가정 할 수 있습니다. 따라서 계산 종료시 얻은 양자 상태는 로 주어집니다
. 여기서 은 qubit 의 프로젝터를 나타냅니다. 상 서브 스페이스 및 기본 게이트에 대응하는 행렬이다. 일반성을 잃지 않으면 서 모든 항목 이 추가 큐 비트를 희생하여 실제 라고 가정 할 수 있습니다 . $| ψ ⟩ = \prod_{i} (P_{i}^{1} \prod_{j} A^{i j}) | x ⟩$

|ψ⟩=∏i(Pi1∏jAij)|x⟩

$P_{i}^{1}$

Pi1

$i$

$| 1 ⟩$

|1⟩

$A^{i j}$

Aij

$A^{i j}$

Aij

이제, 를 사후 선택된 큐 비트 세트로하고 출력 큐 비트로 하자 . 우리는 정의 및 , ( ) 계산 기저 상태의 설정되어있는 및 ( ). MPostBQP 의 정의는 또는 중 하나를 보장합니다 . 아이디어는 과 을 비교하기 위해 PP 머신 을 구성하는 것 입니다. ${p_{i}}$

{pi}

$q$

$π_{0} = \sum_{w \in S_{0}} ψ_{w}^{2}$

π0=∑w∈S0ψw2

$π_{1} = \sum_{w \in S_{1}} ψ_{w}^{2}$

π1=∑w∈S1ψw2

$S_{0}$

$S_{1}$

$p_{i} = 1 \forall i$

pi=1∀i

$q = 0$

q=0

$q = 1$

q=1

$π (1) \geq 2 π (0)$

π(1)≥2π(0)

$π_{0} \geq 2 π_{1}$

π0≥2π1

$π_{0}$

π0

$π_{1}$

π1

. 표현 최종 wavesfunction 부분 특정 연산 기준 상태에 대응 경로를 통해 합으로서, 상기 인덱스를 교체 및 에 단일 인덱스와 는 1 내지 실행 , 우리는 . $ψ_{w}$

ψw

$ψ$

$w$

$i$

$j$

$A^{i j}$

Aij

$k$

$G$

$ψ_{w} = \sum_{α_{1} . . . α_{G}} A_{w, α_{G}}^{G} A_{α_{G}, α_{G - 1}}^{G - 1} . . . A_{α_{2}, α_{1}}^{1} x_{α_{1}}$

ψw=∑α1...αGAw,αGGAαG,αG−1G−1...Aα2,α11xα1

아이디어는, 그 후, 구성하는 PP의 확률로 수락 기계 일부 , 이후 있음을 암시 및 경우 . $\frac{1}{2} (1 + C (π_{1} - π_{0}))$

12(1+C(π1−π0))

$C > 0$

C>0

$x \in L$

x∈L

$\frac{1}{2} (1 + π_{1} - π_{0}) > \frac{1}{2}$

12(1+π1−π0)>12

$\frac{1}{2} (1 + π_{1} - π_{0}) < \frac{1}{2}$

12(1+π1−π0)<12

$x \notin L$

x∉L

이제 이고 . 그런 다음 . $α = {α_{i}}$

α={αi}

$F (A, w, α, X) = A_{w, α_{G}}^{G} A_{α_{G}, α_{G - 1}}^{G - 1} . . . A_{α_{2}, α_{1}}^{1} x_{α_{1}}$

F(A,w,α,X)=Aw,αGGAαG,αG−1G−1...Aα2,α11xα1

$π_{1} - π_{0} = \sum_{w \in S_{1}} \sum α, α^{'} F (A, w, α, X) F (A, w, α^{'}, X) - \sum_{w \in S_{0}} \sum α, α^{'} F (A, w, α, X) F (A, w, α^{'}, X)$

π1−π0=∑w∈S1∑α,α′F(A,w,α,X)F(A,w,α′,X)−∑w∈S0∑α,α′F(A,w,α,X)F(A,w,α′,X)

그런 다음 PP 기계를 다음과 같이 정의 할 수 있습니다.

연산 기저 상태 픽업 임의로한다. $w$
경우 , 다음 중지 확률로 동의 , 그렇지 않으면 거부합니다. $w \notin S_{0} \cup S_{1}$ $1 / 2$
계산 기본 상태 의 두 시퀀스 및 를 무작위로 균일하게 선택하십시오. $α$ $α^{'}$ $G$
계산 . $X = F (A, w, α, x) F (A, w, α^{'}, x)$
경우 확률로 수락 하고 그렇지 않으면 거부하십시오. 또는 경우 확률로 수락 하고 그렇지 않으면 거부하십시오. $w \in S_{1}$ $\frac{1 + X}{2}$ $w \in S_{0}$ $\frac{1 - X}{2}$

이는두고 MPostBQP [K] PP를 $\subseteq$

⊆

모두를 위해, , 따라서 MPostBQP는 보다 더 강력한입니다 PostBQP . $k$

답변

Exit mobile version

How IT

언제든지 물어보세요.

태그 보관물: complexity-classes

사후 선택을 통한 대화식 증명? : Postselection은 설득력있는 메시지를 생성하는 Merlin의 역할을

답변

답변

답변

답변