論文の概要: Lowering LCU Circuit Width through Maximum-Weight Birkhoff-von Neumann Decomposition

• arxiv url: http://arxiv.org/abs/2605.27430v1
• Date: Fri, 22 May 2026 04:29:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-28 17:38:55.264693
• Title: Lowering LCU Circuit Width through Maximum-Weight Birkhoff-von Neumann Decomposition
• Title（参考訳）: 最大Birkhoff-von Neumann分解によるLCU回路幅の低下
• Authors: Ammar Daskin,
• Abstract要約: バーホフのアルゴリズムのボトルネック変種が置換数を$O(Nlog(varepsilon))$に減らすことを示す。 項数2次減少は、アンシラレジスタを直接2log N$から$log N$ qubitsに縮める。 この構造は振幅増幅なしで高い成功率を達成するために利用することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Any square matrix can be transformed into a doubly stochastic matrix via Sinkhorn scaling with diagonal matrices or completing to a larger dimensional matrix. Standard Birkhoff-von Neumann and Pauli decompositions represent such matrices as linear combinations of $O(N^2)$ permutation or Pauli terms, leading to a large ancilla overhead in a quantum Linear Combination of Unitaries (LCU) implementation. We prove that a bottleneck variant of Birkhoff's algorithm reduces the number of permutations to $O(N\log(1/\varepsilon))$, where $\varepsilon$ is the $\ell_1$-norm approximation error of the reconstructed matrix, and demonstrate empirically that a largest-weight greedy variant requires only $\approx 2N$ terms for dense matrices (the exact average observed is $\approx 2.4N$). The quadratic reduction in term count directly shrinks the ancilla register from $2\log_2 N$ to $\log_2 N$ qubits, shortens the SELECT circuit, and is especially valuable in fixed-Hadamard LCU architectures whose success probability scales with $1/K$. The approach enables compact quantum implementations of dense operators appearing in optimal transport, non-Hermitian simulation, and other settings amenable to Sinkhorn preconditioning. Furthermore, because the decomposition is a convex combination, the LCU normalization constant is exactly $α= 1$, and the uniform superposition is an eigenvector of the target matrix with eigenvalue~1. This structure can be exploited to achieve high success probability without amplitude amplification in many practical scenarios, including quantum walks and Markov chain simulations.
• Abstract（参考訳）: 任意の正方行列は、対角行列によるシンクホーンスケーリングやより大きな次元行列への完備化によって、二重確率行列に変換することができる。 標準的なバーホフ=ヴォン・ノイマンとパウリ分解は、$O(N^2)$置換あるいはパウリ項の線形結合のような行列を表し、量子線形ユニタリ(LCU)実装において大きなアンシラオーバーヘッドをもたらす。 ここで、Birkhoffのアルゴリズムのボトルネック変種は、置換の数を$O(N\log(1/\varepsilon))$に減らし、$\varepsilon$は、再構成された行列の$\ell_1$-norm近似誤差であり、最も重いグレディ変種は、密度行列の項に対して$\approx 2N$しか必要としないことを実証的に証明している(正確な平均は$\approx 2.4N$である)。 項数における二次的な減少は、アンシラレジスタを$2\log_2 N$から$\log_2 N$ qubitsへ直接縮小し、SELECT回路を短縮し、成功確率が1/K$でスケールする固定アダマールLCUアーキテクチャにおいて特に有用である。 このアプローチは、最適輸送、非エルミートシミュレーション、シンクホーンプレコンディショニングに有効な他の設定に現れる高密度作用素のコンパクトな量子実装を可能にする。 さらに、分解は凸結合であるため、LCU正規化定数は正確には$α=1$であり、一様重ね合わせは固有値~1のターゲット行列の固有ベクトルである。 この構造は、量子ウォークやマルコフ連鎖シミュレーションを含む多くの実践シナリオにおいて振幅増幅なしで高い成功確率を達成するために利用することができる。

関連論文リスト

• Reducing C-NOT Counts for State Preparation and Block Encoding via Diagonal Matrix Migration [10.184239233596562]
  我々は、状態準備とブロック符号化の両方に対して、C-NOTカウントの低いアルゴリズムを与える。 一般的な$n$-qubit状態の場合、Plesch-BruknerアルゴリズムからC-NOT数を改善する。 ブロック符号化では,2n-1times 2n-1$行列に対する単一アンシラプロトコルはスペクトルノルムを部分正規化として利用する。
  論文  参考訳（メタデータ） (2026-03-17T13:20:46Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。 本手法の様々な応用は, 微分問題を解く文脈で論じる。
  論文  参考訳（メタデータ） (2026-02-11T07:24:33Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  検討した$Ntimes N$行列の要素を適切な次元の量子系の状態に符号化した変分量子特異値分解を提案する。 制御された測定は、アンシラ測定の小さな成功を避けるために行われる。
  論文  参考訳（メタデータ） (2025-03-19T07:01:38Z)
• Optimal Quantization for Matrix Multiplication [29.75700570685703]
  アルゴリズムにより,近似誤差を明確に保証したネスト格子に基づく普遍的量子化器を構築する。 我々の量子化器の実用的低複雑さバージョンは、非常に最適に近い性能を達成する。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  我々は,N-1(N-1)時間行列の行列式と逆行列を計算するために,純粋に量子的な量子アルゴリズムを提案する。 基本的な考え方は、行列の各行を量子系の純粋な状態にエンコードすることである。
  論文  参考訳（メタデータ） (2024-01-29T23:23:27Z)
• Improved quantum lower and upper bounds for matrix scaling [0.0]
  古典的2次アルゴリズムにおける量子スピードアップの可能性について検討する。 我々は,高精度システムにおける入力サイズに関して,本質的に量子スピードアップが存在しないことを示す。 我々は低精度方式で改良された量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-09-30T17:29:23Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)

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

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