論文の概要: Unbounded Quantum Advantage in Communication with Minimal Input Scaling

• arxiv url: http://arxiv.org/abs/2305.10372v4
• Date: Mon, 31 Mar 2025 12:38:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-02 16:16:39.686286
• Title: Unbounded Quantum Advantage in Communication with Minimal Input Scaling
• Title（参考訳）: 最小入力スケーリングを用いた通信における非有界量子アドバンテージ
• Authors: Sumit Rout, Nitica Sakharwade, Some Sankar Bhattacharya, Ravishankar Ramanathan, Paweł Horodecki,
• Abstract要約: 一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。 また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアル・アンバイアスド・ベースの検出への応用についても強調する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set $\Theta(2^{n})$ bits with respect to classical communication $\Theta(n)$ bits. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: 1) distributed computation of relation and 2) {\it relation reconstruction}, we study the one-way zero-error communication complexity of a relation induced by a distributed clique labelling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an {\it unbounded quantum advantage} in relation reconstruction without public coins. Specifically, for a class of graphs with order $m$, the quantum complexity is $\Theta(1)$ while the classical complexity is $\Theta(\log_2 m)$. Remarkably, the input size is $\Theta(\log_2 m)$ bits and the order of its scaling with respect to classical communication is {\it minimal}. This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of restricted communication and connect this to the existence of Orthogonal Arrays. Finally, we highlight some applications of this task to semi-device-independent dimension witnessing and the detection of Mutually Unbiased Bases.
• Abstract（参考訳）: 通信複雑性のような問題において、以前の研究では、古典的な通信に対して、指数的に大きい入力セット$\Theta(2^{n})$ bitsで指数的量子優位または非有界量子優位を示す。 (n)$ bits. 前者では、量子と古典の分離は指数関数的に増加し、後者の量子通信資源は定数である。 注目すべきは、入力が指数関数的にスケールしない間に、非有界な量子優位性が存在するかどうかである。 ここでは、最適順序の入力サイズを用いて肯定的にこの質問に答える。 タスクとして2つの変種を考慮する。 1)関係の分散計算及び分散計算 直交グラフに対する分散斜めラベリング問題により誘導される関係の一方向ゼロエラー通信複雑性について検討する。 最初のタスクでは量子上の優位性は証明されていないが、公開硬貨を使わずに関係の再構築において量子上の優位性を示す。 具体的には、次数$m$のグラフのクラスに対して、量子複雑性は$\Theta(1)$であり、古典複雑性は$\Theta(\log_2)である。 m)$ 注目すべきは、入力サイズが$\Theta(\log_2)であることだ。 m)$bits で、古典的な通信に対するスケーリングの順序は、最小限である。 これは以前の作品より指数関数的に優れている。 さらに、制限された通信のシナリオにおける分離を克服するために必要な古典的公鋳貨幣の量に対する下限(最大斜め数の直線)を証明し、直交配列の存在と結び付ける。 最後に、このタスクの半デバイス非依存なディメンションの目撃とミューチュアルアンバイアスベースの検出への応用を強調した。

関連論文リスト

• KPZ scaling from the Krylov space [83.88591755871734]
  近年,Cardar-Parisi-Zhangスケーリングをリアルタイムの相関器や自動相関器に示す超拡散が報告されている。 これらの結果から着想を得て,Krylov演算子に基づく相関関数のKPZスケーリングについて検討する。
  論文  参考訳（メタデータ） (2024-06-04T20:57:59Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• 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)
• The Complexity of Being Entangled [0.0]
  ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。 バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
  論文  参考訳（メタデータ） (2023-11-07T19:00:02Z)
• One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
  1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。 我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
  論文  参考訳（メタデータ） (2023-10-03T19:58:08Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Bounds on oblivious multiparty quantum communication complexity [0.0]
  幅広い種類の関数に対して、その難解な量子$k$-party通信複雑性に対して強い下界を証明する方法を示す。 特に、最適$Omega(ksqrtn)$low bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function。
  論文  参考訳（メタデータ） (2022-10-27T13:09:51Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
  最小ウェイト完全マッチングを用いて表面コードを復号するパイプライン手法について述べる。 独立な非通信可能な並列化処理段階は、潜在的な相関に従ってグラフを再重み付けする。 後続の一般的なステージがマッチングを終了します。 完全にフォールトトレラントなトーリック, 回転しない, 回転する曲面符号に対して, 新たなアルゴリズムの有効性を検証した。
  論文  参考訳（メタデータ） (2022-05-19T19:58:02Z)
• Exponential separations between learning with and without quantum memory [17.763817187554096]
  量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。 多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。 このトレードオフは、幅広い学習問題に固有のものであることを示す。
  論文  参考訳（メタデータ） (2021-11-10T19:03:49Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  古典ベクトル $mathbfb$ は量子状態の振幅で符号化される。 任意の状態の$Q$ qubitsは通常、約2Q$のエンタングゲートを必要とする。 状態準備に必要な量子資源を柔軟に削減できる決定論的(非変分法)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-26T07:37:54Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
  論文  参考訳（メタデータ） (2021-10-07T09:38:15Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。 本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
  論文  参考訳（メタデータ） (2021-09-06T14:35:15Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• Quantum advantage for computations with limited space [6.327095331866255]
  我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。 我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
  論文  参考訳（メタデータ） (2020-08-14T17:31:12Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Solution to the Quantum Symmetric Simple Exclusion Process : the Continuous Case [0.0]
  無限大極限における一次元 Q-SSEP の不変確率測度に対する解を提案する。 本稿では,Q-SSEP相関関数の解釈を,驚くべきコネラトニクスとアソシアヘドロン多面体を通して,偶然に指摘する。
  論文  参考訳（メタデータ） (2020-06-22T13:20:40Z)
• 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)
• Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
  ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。 最大勝利確率が量子値を超える任意の物理理論において、通信複雑性が崩壊することを示す。 我々は、0.91の結果が証明戦略の大規模なクラスで可能な限り最良のものであることを示す。
  論文  参考訳（メタデータ） (2018-09-25T22:39:03Z)

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

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