論文の概要: Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions

• arxiv url: http://arxiv.org/abs/2608.04627v1
• Date: Wed, 05 Aug 2026 09:42:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-06 14:48:43.804245
• Title: Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
• Title（参考訳）: ハンミング重み計算と対称性ブール関数のための効率的な深さ-アンシラトレードオフ
• Authors: Wei Zi, Pei Yuan, Junhong Nie, Shengyu Zhang,
• Abstract要約: ハミングウェイトは、その量に$n$-bitの入力をマッピングする。 対称ブール関数は量子コンピューティングにおいて最も一般的なプリミティブの一つである。 両問題の効率的な回路は多くの量子アルゴリズムの効率にとって重要である。
• 参考スコア（独自算出の注目度）: 8.46046792536661
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hamming weight computation maps an $n$-bit input to the number of ones it contains. It is a basic subroutine in quantum computing, and the core building block for symmetric Boolean functions, whose value depends only on the Hamming weight of the input. Moreover, symmetric Boolean functions are among the most common primitives in quantum computing. Efficient circuits for both problems are therefore important for the efficiency of many quantum algorithms. We study the depth-ancilla tradeoffs of Hamming weight computation under two qubit connectivity models, all-to-all and two-dimensional nearest-neighbor square grid (2D), in both the standard and dynamic circuit models. In the standard all-to-all model, we obtain depth $O(\log n)$ with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth $O(\sqrt n)$ with $O(\log^2 n)$ ancillas, and a matching lower bound showing that $Θ(\sqrt n)$ is optimal. In both dynamic models, we obtain constant-depth circuits with $O(n^{1+\varepsilon}\operatorname{polylog}\,n)$ ancillary qubits for every fixed $\varepsilon>0$. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.
• Abstract（参考訳）: ハミングウェイト計算は、その量に$n$-bitの入力をマッピングする。 量子コンピューティングの基本的なサブルーチンであり、入力のハミング重みにのみ依存する対称ブール関数のコアビルディングブロックである。 さらに、対称ブール関数は量子コンピューティングにおいて最も一般的なプリミティブの一つである。 したがって、両方の問題に対する効率的な回路は、多くの量子アルゴリズムの効率にとって重要である。 標準回路モデルと動的回路モデルの両方において、ハミング重み計算の2つのクビット接続モデル(全2次元および近接2次元2次元正方格子(英語版))の下での深度・アンシラトレードオフについて検討した。 標準的なオール・ツー・オールモデルでは、アンシラの亜線型数を持つ深さ$O(\log n)$を得る。 標準的な2Dモデルでは、深さ$O(\sqrt n)$と、深さ$O(\log^2 n)$のアンシラの回路を与え、一致する下界は、$(\sqrt n)$が最適であることを示す。 どちらのモデルも、固定された$\varepsilon>0$に対して$O(n^{1+\varepsilon}\operatorname{polylog}\,n)$ ancillary qubits を持つ定数深さ回路を得る。 すべての構成は滑らかな深度アンシラトレードオフを与え、また任意の対称ブール函数にも拡張する。

関連論文リスト

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。 我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
  論文  参考訳（メタデータ） (2026-07-14T18:42:40Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  ディック状態は量子コンピューティングに広く応用された、絡み合った量子状態の重要なクラスを表す。 一般に見られる2つの量子ビット接続制約の下でDicke状態生成のための決定論的量子回路を提案する。
  論文  参考訳（メタデータ） (2025-05-21T11:55:17Z)
• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• Logarithmic-Depth Quantum Circuits for Hamming Weight Projections [3.481985817302898]
  入力純状態上でのコヒーレントハミング重みの射影測定を実現する量子アルゴリズムを提案する。 我々は、対応する量子回路の深さ幅のトレードオフを分析し、より多くの制御量子ビットのコストで回路の深さの低減を可能にする。
  論文  参考訳（メタデータ） (2024-04-10T16:35:36Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test [10.386115383285288]
  我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。 我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。 本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-28T12:59:27Z)

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

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