の結果 $MIP^\ast=RE$ 量子アルゴリズムについて
（保留中のピアレビュー）の証明 $MIP^\ast=RE$で、このプレプリントの重要な突破口として歓迎されています。この結果の重要性は、このブログ投稿でHenry Yuen（著者の1人）によって取り上げられています。スコットアーロンソンはまた、このブログ投稿にいくつかの主要な影響をリストしています。
非ローカルゲームの場合（$G$）、非相対論的テンソル積戦略の成功確率の上限を次のように定義します。 $\omega^\ast(G)$、および相対論的通勤演算子（QFT）戦略の成功確率の上限は次のとおりです。 $\omega^{co}(G)$。非相対論的QMはQFTの特殊なケースであるため、最適な通勤オペレーターベースの戦略が少なくとも最適なテンソル積ベースの戦略と同じくらい優れていることは明らかです。$\omega^\ast(G) \le \omega^{co}(G)$。
ユエンの投稿についての私の理解は、 $MIP^\ast=RE$ ローカル以外のゲームが存在するということです $\omega^\ast(G) < \omega^{co}(G)$。具体的には、彼は言います
ゲームが必要です $G$、次に、量子値が通勤演算子値とは異なる。しかし、これはチレルソンの問題が否定的な答えを持っていることを意味し、したがってコンヌの埋め込み予想は誤りです。
これは、QFT（通勤演算子）の手法を使用するアルゴリズムが、非相対論的QM（テンソル積、量子回路形式）の手法を使用するアルゴリズムよりも成功確率が高いクラスの問題があることを意味すると理解しています。
私の質問の最初の部分は、この証明が有効であると仮定することです：
- しますか $MIP^\ast=RE$ 非相対論的QM形式（従来の量子回路）ではなく、QFT（通勤演算子）の数学的形式を採用することで、より効率的に解決できる一連の問題があることを意味しますか？
私が誤解しない限り、これはユエンの発言から直接続いているようです。もしそうなら、ローカル以外のゲームのセットが存在する可能性はありますか？$\omega^\ast(G) < 0.5$ そして $\omega^{co}(G) > 0.5$？具体的には、私の質問の2番目の部分は次のとおりです。
- しますか $MIP^\ast=RE$ 量子回路では解決できない通勤演算子を使用して解決できる一連の問題がある（または存在する可能性がある）ことを意味しますか、それともこの可能性は量子回路モデルの普遍性によって閉じられますか？
EDIT：ヘンリー・ユンが作成したMIP *ウィキをより良い、この複雑性クラスを理解することに興味のある人またはのために$MIP^\ast = RE$ 結果。
回答
MIP * = REの結果かどうか、特に非ローカルゲームが存在するという主張はわかりません $G$ どこ $\omega^*(G) \neq \omega^{co}(G)$は、量子コンピューターにアルゴリズム的な影響を及ぼします。ここで言うことがいくつかあります。
MIP * = REの結果は、非ローカルゲームで解決できるものとは対照的に、非ローカルゲームを使用して検証できる計算上の問題に関するものです（とにかく、それが何を意味するのかわかりません！）。検証と解決の違いは、次の理由によるものです。非ローカルゲームでは、アリスとボブが問題の答えを魔法のように知っていると想定します（したがって、計算上の問題を即座に解決できると想定します）。彼らの挑戦はそれを解決することではなく、証明することです多項式時間の古典的な検証者にとって、彼らは答えを知っています。何かに対する答えを知っているだけでは、他の誰かにその答えを納得させることができるとは限りません。アリスとボブがテンソル積フレームワークまたは通勤演算子フレームワークからの相関関係を使用できるかどうかは、検証者に証明できる内容に影響します。 MIP * = REは、テンソル積の相関関係により、アリスとボブがチューリングマシンが最終的に停止することを知っていることを証明できることを示しています。これは、アリスとボブが通勤オペレーターの相関関係を共有している場合には実行できないことです。したがって、通勤演算子モデルはテンソル積モデルとは異なります。
私が2番目に言及したいのは、それとは別に、通勤演算子と無限次元システムについて話す量子計算のモデルを定義できるかどうかという興味深い質問です。Cleveらは、このためのモデルを考え出そうとしたようです。これは、C *回路モデルと呼ばれています。https://arxiv.org/pdf/1811.12575.pdf。これは面白いと思うかもしれません。