論文の概要: Space-Bounded Communication Complexity of Unitaries

• arxiv url: http://arxiv.org/abs/2511.04250v1
• Date: Thu, 06 Nov 2025 10:35:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-07 20:17:53.39233
• Title: Space-Bounded Communication Complexity of Unitaries
• Title（参考訳）: ユニタリの空間境界通信複雑性
• Authors: Longcheng Li, Xiaoming Sun, Jialin Zhang, Jiadong Zhu,
• Abstract要約: 分散量子プロセッサにおけるユニタリ実装のための空間境界通信複雑性について検討する。 一般的な$n$-qubitユニタリに対しては、自明な$O(4n)$通信境界を改善する。 特殊ユニタリに対しては、量子フーリエ変換(QFT)とクリフォード回路の両方が通信複雑性の線形上界を認めていることを示す。
• 参考スコア（独自算出の注目度）: 7.120902966697645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization. Our contributions are twofold. First, for general $n$-qubit unitaries, we improve upon the trivial $O(4^n)$ communication bound. Considering $k$ pairwise-connected processors (each with $n/k$ data qubits and $m$ ancillas), we prove the communication complexity satisfies $O\left(\max\{4^{(1-1/k)n - m}, n\}\right)$--for example, $O(2^n)$ when $m=0$ and $k=2$--and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale distributed quantum computing (DQC) systems.
• Abstract（参考訳）: 分散量子プロセッサにおけるユニタリ実装のための空間境界通信の複雑さについて検討し、実用的な妥当性と技術的非自明性を確保するために、プロセッサ当たりのキュービット数を制限した。 我々は分散量子回路を用いて分散量子プロセッサをモデル化し、その実現に必要な非局所ゲートの最小数としてユニタリの通信複雑性を定義する。 私たちの貢献は2倍です。 まず、一般的な$n$-qubitユニタリに対して、自明な$O(4^n)$通信境界を改善する。 k$ペアワイズ接続プロセッサ(それぞれ$n/k$データキュービットと$m$アンシラを持つ)を考えると、通信の複雑さは$O\left(\max\{4^{(1-1/k)n - m}, n\right)$--例えば$O(2^n)$は$m=0$と$k=2$である。 さらに、近似モデルと一般的なネットワークトポロジに解析を拡張します。 第2に、特殊ユニタリに対しては、量子フーリエ変換(QFT)とクリフォード回路の両方が、正確なモデルにおける通信複雑性の線形上界を認め、これらの場合に適用可能な自明な二次境界よりも優れていることを示す。 近似モデルでは、QFTの通信複雑性は線形から対数へと劇的に減少し、クリフォード回路は線形の下界を保持する。 これらの結果は、分散量子ユニタリ実装における通信を最適化するための基本的な洞察を与え、大規模分散量子コンピューティング(DQC)システムの実現可能性を向上させる。

関連論文リスト

• Quantum Communication Complexity of L2-Regularized Linear Regression Protocols [0.0]
  本稿では,量子コーディネータモデルにおける分散線形回帰について検討する。 通常の(非正規化)およびL2正規化(ティコノフ)最小二乗問題を解くための改良された拡張量子プロトコルを提案する。
  論文  参考訳（メタデータ） (2025-08-22T07:07:14Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Communication-efficient Quantum Algorithm for Distributed Machine Learning [14.546892420890943]
  我々の量子アルゴリズムは、通信複雑性が$O(fraclog_2(N)epsilon)$で、$N$はデータポイントの数、$epsilon$はパラメータエラーのバウンドである。 分散内積とハミング距離を量子加速度で推定するアルゴリズムの構築ブロックは、分散機械学習の様々なタスクにさらに適用でき、通信を高速化できる。
  論文  参考訳（メタデータ） (2022-09-11T15:03:58Z)
• Halving the cost of quantum multiplexed rotations [0.0]
  我々は、$c$制御を持つ多重量子ゲートの$b$-bit近似に必要な$T$ゲートの数を改善する。 以上の結果から,2要素あるいはテンソルハイパーコントラクション表現の量子化に基づく最先端電子構造シミュレーションのコストを約半分に抑えることができた。
  論文  参考訳（メタデータ） (2021-10-26T06:49:44Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions [0.9634136878988853]
  距離において1/ラルファ$の強度が減衰するパワーロー相互作用は、情報処理のための実験的に実現可能な資源を提供する。 我々はこれらの相互作用のパワーを活用して、任意の数のターゲットを持つ高速量子ファンアウトゲートを実装する。 我々は、ファリングが古典的に難解であるという標準的な仮定の下で、$alpha le D$ のパワーロー系は、短時間でも古典的にシミュレートすることは困難であることを示す。
  論文  参考訳（メタデータ） (2020-07-01T18:00:00Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

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

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