計算量的仮定に基づくノンユニバーサル 量子計算の研究

計算量的仮定に基づくノンユニバーサル
量子計算の研究－ＳＢＱＰと多項式階層
(BQPのちょっと上とちょっと下)
（25分）
森前智行（群馬大）
2015/5/30 ELC第一回領域会議＠田町
BPPとBQP
BPP：古典確率的TMで多項式時間で高い確率で解けるdecision problemの集合
BQP: 量子TM(回路)で多項式時間で高い確率で解けるdecision problemの集合
夢：BPP≠BQPを示したい！
PSPACE
PP
AWPP
しかし、これはPSPACE≠Pを意味するの
で難しい！
BPP=BQPだと変なこと（PHの崩壊等）が
起こる、というのも知られていない。
BQP
BPP
P
何らかの意味で量子計算機＞古典計算機を示したい。
例：
オラクルセパレーション
Communication complexity
Function problem
Sampling problem　←　今回のテーマ
BQPのちょっと下
ユニバーサル量子計算
測定
実際の測定は
ノイジー
任意のユニタリ演算が実現できる。
Pure inputを好きなだけ用意できる。
NMRなんかでは難しい。Pure inputは
１個しか用意できないような弱いモデ
ルを考えよう：DQC1
かなりむずい。特定のユニタリ演算しかできないよ
うな弱いモデルを考えよう：IQP、Boson sampling
このような、弱いモデルを非ユニバーサル量子計算と呼ぶことにする。
非ユニバーサル量子計算でも、「古典計算より速い」ものがあればうれしい。
BQPのちょっと下
X：ある非ユニバーサル量子計算モデル
BQXP:　Xモデルで多項式時間で高い確率で解けるdecision problemの集合　（イメージ）
PSPACE
PP
BPP≠BQXP≠BQPを示したい！
しかし、これはPSPACE≠Pを意味する！
AWPP
BQP
BQXP
BPP
P
（あくまでイメージ）
オラクルセパレーション？
Communication complexity？
Function problem？
Sampling problem？　←　今回のテーマ
IQP
１．インプットは |+.....+>
２．ゲートは
のみ
３．X基底で測定
明らかに、ユニバーサルでない。しかし、
古典サンプルできたらPHが3rdレベルで崩壊 [Bremner, et. al. Proc. Roy. Soc. 2010]
IQPの出力確率分布＝イジング分配関数 [Fujii and TM, arXiv:1311.2128]
Boson sampling
光の粒子（Boson）を使った量子コンピューター
相互作用有り＝ユニバーサル、相互作用無し＝Boson sampling
古典サンプルできたらPHが3rdレベルで崩壊 [Aaronson and Arkhipov STOC 2011]
DQC1モデル（one clean qubitモデル）
U
U
I/2
I/2
I/2
通常の量子計算
DQC1
(Knill and Laflamme, Phys. Rev. Lett. 1998)
NMR(Nuclear Magnetic Resonance)量子計算機モデル
ｋ個の測定を行う：　DQC1_k
一見すると、全然量子パワーがなさそう。。。
ここかも
BPP
明らかにここではない
BQP
PP
実際、 リーズナブルな仮定のもとではユニバーサルでないことは示された [Ambainis,
Schulman, and Vazirani, STOC2000].　（対称性がありすぎて、多項式サイズの情報がレ
ジスターに保持できない。）
しかし、驚くことに、古典計算機よりは「速い」ように見える証拠がいくつも。。。
例：結び目不変量であるJones多項式の計算
古典：効率的に計算する方法が知られていない
DQC1：効率的に計算できる！(Shor and Jordan QIC 2008)
H
H
I/2
I/2
I/2
Open problem: DQC1は古典計算よりも真に速いのか？
「Jones多項式を効率的に計算できる」では不十分。
将来誰かが古典計算機でJones多項式を効率的に計算する方法を見つけるかも。
[TM, Fujii, and Fitzsimons, Physical Review Letters 2013]：
もしDQC1_k (k>=3) の出力分布が古典計算機で効率的にサンプルできたら、polynomial
hierarchyが3rdレベルで崩壊する。
Polynomial hierarchy: P, NPを一般化したもの。
NP, NP^{NP}, NP^{NP^{NP}},...
崩壊しないだろうと非常に強く信じられている。
k=１、
3rd level → 2nd level
に改良された！！
[Fujii, Kobayashi, TM, Nishimura, Tamate, and Tani (alphabetical order), arXiv:1409.6777]
DQC1が古典サンプルできたらPHが2nd levelで崩壊。
[Fujii, Kobayashi, TM, Nishimura, Tamate, and Tani (alphabetical order), arXiv:1409.6777]
NQP (= coC=P)というクラスを使用。
（NPの量子バージョン）
L is in NQP iff there exists a QC s.t.
If x is in L then P(o=1)>0
If x is not in L then P(o=1)=0
Assume L is in NQP
P' = P(1-P)/2^n
測定値o
x
x
x
x
x
Therefore, L is in NP
NQP ⊆　NP　leads to the collapse of PH to 2nd level
注：SBQPでもいえる。NQPやSBQPがDQC1に制限しても不変なことが効いてる！
x
x
x
x
x
今後の課題
１．multiplicative error approximationは厳しい
→　additive でできないか？　Boson samplingではできる（Aaronson）
最近、IQPでもできることが示された[Bremner, et. al.]
DQC1でもできないか？
（Boson samplingはPermanentと、IQPはイジングと対応あるが、DQC1は何か対応あるのか？）
２．DQC1とBPP、BQPのオラクルセパレーションは？
→いくつか結果はあるが、まだまだ分かっていない。
BQPのちょっと上
タイムトラベル（CTC）
PSPACE
PP=postBQP
ポストセレクション、非線形量子力学、
p-norm確率ルール、等
SBQP
AWPP
BQP
BPP
この辺のものは無いの？
→Lee and Barrett 2014, GPT
CTC (Closed timelike curve)
ρ’
U
σ
ρ
Non-linearityをつかって
小さな確率を増幅できる。
→NP解ける。
BQP_CTC=PSPACE
[Watrous and Aaronson]
Open timelike curve
U
NP ⊆　BQP_OTC [Yuan, et. al. 2014]
ポストセレクション
量子測定：　結果は確率的
a|0>+b|1>
0の出る確率は|a|^2
自分で好きな結果を出すことは無理。
もしできたら。。。
タイムトラベルが可能！
光速を超えて情報が伝わる！
＃Pが解ける　（Lloyd and Adams, Phys. Rev. Lett. 1998）
自分の好きな結果が確率１でなぜか出せる、という架空の能力をポストセレクションという。
つまり、 a|0>+b|1> を常に|0> に射影できる！
postBQP=PP [Aaronson]
PostBQP
A language L is in the class postBQP iff there exists 0 < d < ½ and a uniform family of BQP
circuits such that
U
P
O
Post-BQP=PP (Aaronson Proc. Roy. Soc. 2005)
ex. postBPP=BPP_path is in PH. postの世界ではBQP≠BPP！　制限されたPostBQPを考えると。。。
AWPP,APPの量子的解釈！
WPPを含むのでBQPのちょっと上！
[TM and Nishimura, arXiv:1502.00067]
AWPP
A language L is in AWPP iff there exists a GapP function g and FP function f s.t.
If x is in L then 2/3 < g/f <1
If x is not in L then 0<g/f<1/3
A function g is a GapP function iff there exists a NDTM s.t.
g(x) = # of accepting paths - # of rejecting paths
Quantum probability = GapP/2^n (cf. Classical probability=#P/2^n )
BQP　⊆　AWPP　⊆　PP
AWPPは、PPより良い上限であるものの、PPに比べて意味がよく分からん。
→今回、制限されたpostBQP＝AWPPという、AWPPの量子解釈を初めて与えた！
今後の課題
1. AWPP=postBQP_FPにならないの？？
2. AWPPが制限されたポストセレクションで説明できる物理的、計算量的理由は？
3. 何か他のGeneralized quantum theoryで面白い計算量を持つものは？
（特に、GPTで何か例がないか？？）
4. BQP_pathのようなものはないの？
postBQPの古典バージョン、postBPPというのも考えれる。これはBPP_pathと等価。
BPP_path: BPPにおけるNon-determinisitic計算の計算パスの長さが等しくないもの。
QMA (Quantum Merlin-Arthur)
AWPPとは違う方向でのBQPのちょっと上。
Merlin: super power
Arthur: BQP
Witness: polynomial-size quantum state sent from Merlin to Arthur
L is in QMA iff
1. if x is in L then Arthur accepts witness with probability >a
2. if x is not in L then Arthur accepts witness with probability <b
Here a-b > 1/poly(n)
PP
SBQP
AWPP
QMA
BQP
End