論文の概要: Transducer-based linear combination of unitaries: theory and applications

• arxiv url: http://arxiv.org/abs/2609.40073v1
• Date: Wed, 30 Sep 2026 16:25:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.039209
• Title: Transducer-based linear combination of unitaries: theory and applications
• Title（参考訳）: トランスデューサに基づくユニタリの線形結合の理論と応用
• Abstract要約: 線形ユニタリ結合(英: Linear combination of Unitary、LCU)は、量子アルゴリズムにおける基本的なプリミティブであり、そのコストは最も高価なユニタリによって管理される。 我々はトランスデューサベースのLCUフレームワークを開発し、この最悪のケース依存を重み付き平均クエリの複雑さに還元する。 応用として、スパース行列のブロックエンコーディングの改善が得られ、スパースハミルトンシミュレーションと量子線形系のための量子アルゴリズムが導かれる。
• 参考スコア（独自算出の注目度）: 12.58662650841309
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles. Consider $A=\sum_j c_j U_j$, where $c_j>0$ and each unitary $U_j$ can be implemented using $C_j$ primitive queries. Given an upper bound $a\geq \|A\|$, our algorithm implements a block-encoding of $A/α$ with rescaling factor $α=\mathcal{O}(a)$, using $\widetilde{\mathcal{O}} (C_{\max}+\overline{C} λ/{a} )$ primitive queries, where $λ=\sum_j c_j$, $C_{\max}=\max_j C_j$, and $\overline{C}= {\sum_j c_j C_j}/λ$. By comparison, the standard LCU construction requires $\widetilde{\mathcal{O}} (C_{\max} λ/{a} )$ primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and $λ/a$ is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters. Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm $K$ as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an $ε$-approximate block-encoding using only $\mathcal{O}\left(K \log(1/ε)\right)$ queries to the transducer, improving the precision dependence from polynomial to logarithmic.
• Abstract（参考訳）: 線形ユニタリ結合(英: Linear combination of Unitary、LCU)は、量子アルゴリズムにおいて基本的なプリミティブであり、そのコストは通常、組み合わせに現れる最も高価なユニタリによって支配される。 本稿では,トランスデューサをベースとしたLCUフレームワークを開発し,この最悪のケース依存を重み付けされた平均クエリの複雑性に還元する。 たとえば$A=\sum_j c_j U_j$, where $c_j>0$, and each unitary $U_j$を$C_j$プリミティブクエリを使って実装できる。 上界の$a\geq \|A\|$が与えられた場合、我々のアルゴリズムは$A/α$のブロックエンコーディングを実装し、再スケーリング係数$α=\mathcal{O}(a)$, using $\widetilde{\mathcal{O}} (C_{\max}+\overline{C} λ/{a} )$プリミティブクエリ、$λ=\sum_j c_j$, $C_{\max}=\max_j C_j$, $\overline{C}= {\sum_j c_j}/λ$を使用する。 対照的に、標準的なLCUの構成には$\widetilde{\mathcal{O}} (C_{\max} λ/{a} )$プリミティブクエリが必要である。 したがって、コストのかかるユニタリが小さな重みを持ち、λ/a$が大きければ、改善は実質的である。 応用として、スパース行列のブロックエンコーディングを改善し、スパースハミルトニアンシミュレーションと量子線形系の量子アルゴリズムに導かれる。 私たちの技術はBelovs,Jeffery,Yolcu[Quantum, 8:1444 (2024)]が開発したTransducerフレームワークです。 ここではブロックエンコーディングに適した相補的作用素レベル理論を開発する。 我々は、既存の触媒の複雑さに加えて、トランスデューサの実装の鍵となる複雑さ尺度として、分解能ノルム$K$を同定する。 本稿では,Transducer アクションを $\mathcal{O}\left(K \log(1/ε)\right)$クエリだけで$ε$-approximate ブロックエンコーディングに変換できることを示し,多項式から対数への精度依存性を改善した。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Simultaneously Query-Optimal Quantum Linear-System Algorithm [2.8802622551493773]
  Oleft(logfrac1varepsilonright)$ query to $U_A$ and $Oleft(/sright)$ query to $U_b$。 すべての量子線型系アルゴリズムと全ての解ノルムスケールに対して、そのアルゴリズムは$(/s)$行列クエリと$(/s)$状態準備クエリの両方を必要とする単一のエルミートインスタンスが存在する。
  論文  参考訳（メタデータ） (2026-09-27T15:49:21Z)
• Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians [4.914113120082008]
  構成されたフェルミオンおよびスピンハミルトニアンのブロック符号化を単位クリフォード$+T$モデルで構築するコストについて検討する。 我々の主要な技術ツールは、アンシラ圧縮の定理である:$n$-qubit演算子を$a$クリーンアンシラで、少なくとも$s$T$ゲートで圧縮して、少なくとも$mina,n+2s$アンシラで使用することができる。
  論文  参考訳（メタデータ） (2026-09-10T07:01:08Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。 本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。 微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
  論文  参考訳（メタデータ） (2024-10-23T18:00:01Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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