論文の概要: Rank lower bounds on non-local quantum computation

• arxiv url: http://arxiv.org/abs/2402.18647v3
• Date: Mon, 09 Dec 2024 20:43:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:33:38.383653
• Title: Rank lower bounds on non-local quantum computation
• Title（参考訳）: 非局所量子計算におけるランク下界
• Authors: Vahid R. Asadi, Eric Culf, Alex May,
• Abstract要約: 非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。 NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function $f(x,y)$ in terms of the rank of a matrix $g(x,y)$ whose entries are zero when $f(x,y)=0$, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of $f(x,y)$. Because of a relationship between $f$-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.
• Abstract（参考訳）: 非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1つの同時通信と共有絡み合いに置き換える。 NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。 両設定の絡み合いに対する最初の非自明な下界を与えるが、完全正当性を持つ下界プロトコルに制限される。 この設定の中で、与えられた函数 $f(x,y)$ に対してこれらのタスクを完備化する任意の絡み合った状態のシュミット階に対する下界を、$f(x,y)=0$ のときの成分が 0 である行列 $g(x,y)$ のランクの観点で与え、それ以外は厳密に正である。 これはまた、非決定論的量子通信の複雑さが$f(x,y)$であるという点でシュミット階数に低い境界をもたらす。 情報理論暗号において研究されている秘密の条件開示と$f$-routingの関係から,CDSのランダム性複雑性を下げるための新しい手法が得られた。

関連論文リスト

• Linear gate bounds against natural functions for position-verification [0.0]
  量子位置検証スキームは、証明者の空間的位置を検証しようとする。 我々は、$f$-routing(英語版)と$f$-BB84(英語版)として知られる2つのよく研究された位置検証スキームを考える。
  論文  参考訳（メタデータ） (2024-02-28T19:00:10Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Relating non-local quantum computation to information theoretic cryptography [0.0]
  非局所量子計算(NLQC)は位置検証スキームの不正な方法であり、AdS/CFT対応の文脈に現れている。 我々は、NLQCの特別な場合として、$f$-routing(英語版)と呼ばれ、シークレットプリミティブの条件開示の量子アナログと等価であることを示す。 これらの暗号プリミティブに位置検証を関連付けることで、暗号文学における多くの結果がNLQCに新しい意味を与える。
  論文  参考訳（メタデータ） (2023-06-28T18:00:05Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。 最初の設定について、Omegabig(frac-1+ppp)$。 第二設定については、おめがの()$。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。
  論文  参考訳（メタデータ） (2022-12-07T19:02:36Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。 我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。 我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
  論文  参考訳（メタデータ） (2020-10-16T08:10:02Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。 量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
  論文  参考訳（メタデータ） (2020-05-18T16:55:08Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。