PromiseBQPとオペレータの期待値

この質問は、Aaronsonの検索とサンプリングの等価性に関するものです。
4ページで、彼は次の声明を出します。

…難解で未解決のメタ問題は、PromiseBPP = PromiseBQP   SampP =
SampBQPを意味する。 「物理言語」に翻訳されていますが、問題はこれです。
  量子で観測可能なすべての期待値を推定するための効率的な古典的アルゴリズムを持っていた
  力学。これは、量子実験をシミュレートする効率的な古典的アルゴリズムを暗示するでしょうか?
  1つの量子力学に近い確率分布からのサンプリングの意味では?

私はこの声明を理解することができません。 PromiseBQPの定義から、私はPromiseBPP =
PromiseBQPが量子力学の観測値の期待値を推定するための効率的な古典的なアルゴリズムであることは分かりません。どのようにこの接続を作ることができる任意のアイデア?

ベストアンサー

Aaronsonは特定の文脈の中で働いていますが、あなたが絶対的な意味で彼の発言を取るなら、あなたは懐疑的であることが正しいです。

「物理言語」に翻訳されている質問はこれです:量子力学における観測可能性の期待値を推定する効率的な古典的アルゴリズムがあったとしましょう。

これは技術的に不正確です。
PromiseBQPとBQPは、間違いなく理解できるように、多項式サイズの(一様な系列の)回路で構成されたサンプリング状態に関係しています。
「観測可能な値の期待値を見積もる」ということについて話しているのであれば、一般に指数関数的な数の構築が必要な量子状態が含まれているようです。

しかし、複雑さの理論家の懸念は、このような指数関数的に構成可能な量子状態については、あまり心配しない。どのような「量子実験」においても、ある状態が一定の時間t内に特定の純粋な量子状態から進化する場合、その観測値の期待値は、多項式数の回路から構成できる状態に非常に近いゲート。

つまり、「多項式時間構成可能な状態を扱う実験」の複雑さの理論的パラダイムは、私がよく知っているすべての文脈で実験的物理学にとって現実的です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です