論文の概要: Quantum and Classical Communication Complexity of Permutation-Invariant Functions

• arxiv url: http://arxiv.org/abs/2401.00454v1
• Date: Sun, 31 Dec 2023 11:07:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-03 17:21:28.470766
• Title: Quantum and Classical Communication Complexity of Permutation-Invariant Functions
• Title（参考訳）: 置換不変関数の量子・古典的通信複雑性
• Authors: Ziyi Guan, Yunqi Huang, Penghui Yao, Zekun Ye
• Abstract要約: 置換不変ブール関数の量子的およびランダムな通信複雑性は(対数係数まで)2次同値であることを示す。 本研究は,通信複雑性に対するクエリ複雑性に関する最近の研究を拡張したものである。
• 参考スコア（独自算出の注目度）: 4.410515368583671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of the permutation-invariant Boolean functions are quadratically equivalent (up to a logarithmic factor). Our results extend a recent line of research regarding query complexity \cite{AA14, Cha19, BCG+20} to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a logarithmic factor).
• Abstract（参考訳）: 本稿では、置換不変ブール関数の量子通信の複雑性を概密に評価する。 このような特徴付けにより、置換不変ブール関数の量子およびランダム化通信複雑性は(対数係数まで)二次同値であることを示す。 この結果,クエリの複雑性に関する最近の研究の行を通信の複雑さに拡張し,対称性が指数的量子スピードアップを防ぐことを示した。 さらに、任意の非自明な全置換不変ブール関数に対して、Log-rank Conjecture ホールドを示す。 さらに、量子/古典的通信複雑性と置換不変ブール関数の近似ランクの関係を確立する。 これは、乱数と量子の設定(対数係数まで)における置換不変ブール関数に対する対数次予想の正しさを意味する。

関連論文リスト

• A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
  量子暗号プリミティブの最初のメタ複雑性のキャラクタリゼーションを証明した。 片方向パズルが存在することは、カルモゴロフ複雑性を近似することが困難であるような二進弦の量子サンプリング可能な分布が存在する場合に限る。
  論文  参考訳（メタデータ） (2024-10-07T12:29:27Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$ [0.0]
  量子交換相関に近似をエンコードするqc-モジュラーの概念を導入する。 計算可能なqc-モジュラーの存在は、上記の質問の自然な変形に対して負の答えを与えることを示す。
  論文  参考訳（メタデータ） (2022-09-16T15:45:49Z)
• On query complexity measures and their relations for symmetric functions [0.0]
  本稿では, ブール法と逆法を用いて, 量子クエリの複雑性を低く抑える方法について述べる。 また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。 証明の複雑さとブロック感度が対称関数の感度と比較していかに大きいかを示す。
  論文  参考訳（メタデータ） (2021-10-25T02:55:39Z)
• Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
  量子状態の構築やユニタリ変換の実行など、本質的に量子演算の複雑さについて検討する。 量子状態とユニタリの対話的証明のモデルを定義する。 複数の絡み合ったプロバーの設定でも類似した結果が得られる。
  論文  参考訳（メタデータ） (2021-08-16T15:59:33Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandryは、量子クエリアルゴリズムとランダム関数に対応する量子オラクルの間の相互作用を研究した。 オラクルがランダム関数の代わりにランダムな置換に対応する場合にも同様の解釈を導入する。 乱数関数と乱数置換の両方がセキュリティ証明において極めて重要であるため、本フレームワークが量子暗号に応用されることを期待する。
  論文  参考訳（メタデータ） (2021-03-16T11:05:48Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。 演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
  論文  参考訳（メタデータ） (2021-01-21T22:18:49Z)
• Representation matching for delegated quantum computing [64.67104066707309]
  表現マッチングは、量子ネットワークにおける量子計算のコストを削減するための一般的な確率的プロトコルである。 表現マッチングプロトコルは,様々なタスクにおいて,通信コストやメモリコストを最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2020-09-14T18:07:43Z)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  OTOC-RE定理(OTOC-RE theorem)は、作用素の完備な基底にまとめられたOTOCを第二レニイエントロピー(Renyi entropy)に関連付ける定理である。 関係作用素の小さな集合に対する和は、エントロピーの非常によい近似を得るのに十分であることを示す。 逆に、これは複雑性の別の自然な指標、すなわち時間と関連する演算子の数のスケーリングを提供する。
  論文  参考訳（メタデータ） (2020-07-31T19:23:26Z)

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

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