論文の概要: An efficient Pauli decomposition algorithm for structured matrices
- arxiv url: http://arxiv.org/abs/2606.31952v1
- Date: Tue, 30 Jun 2026 16:57:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-03 15:23:48.293461
- Title: An efficient Pauli decomposition algorithm for structured matrices
- Title（参考訳）: 構造行列に対する効率的なパウリ分解アルゴリズム
- Abstract要約: 我々は、行列が$k = Mathsfpoly(n)$ Pauli文字列のみをサポートすることが保証されるパウリ分解問題の公約バージョンを考える。
この空間性を生かし、パウリ分解の精度を少なくとも1-$の確率で再現するランダム化された古典的アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.12744523252873352
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = \mathsf{poly}(n)$ Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in $n$. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least $1 - δ$, for any $δ$. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in $n$, $k$, and $\log(1/δ)$. These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.
- Abstract（参考訳）: 古典行列をパウリ弦の線形結合に分解することは、短期量子アルゴリズムのエンドツーエンド実装において大きなボトルネックとなる。
本研究では,行列が$k = \mathsf{poly}(n)$ Pauli文字列のみをサポートすることが保証され,古典的なスパースクエリアクセスを通じて与えられる,このパウリ分解問題の公約バージョンを考える。
既存のパウリ分解アルゴリズムは、一般の高密度な問題のために設計されており、本質的にこの約束された空間性を利用するわけではないため、これらのアプローチは指数関数的に$n$の時間を要する。
この空間性を生かし、任意の$δ$に対して少なくとも1-δ$の確率で正確なパウリ分解を復元するランダム化された古典的アルゴリズムを提案する。
前述のアクセスモデルの下で、アルゴリズムは、$n$、$k$、$\log(1/δ)$の多項式であるクエリとランタイムの複雑さで実行される。
これらの結果は、パウリ分解は一般の行列に対して指数関数的に困難であるにもかかわらず、パウリ基底においてスパースであることが知られている行列に対して効率的に解けることを示している。
関連論文リスト
- PHASE: Pauli Hierarchical Assembly on Subdivided Elements for Quantum-Compatible Operator Synthesis [0.0]
素数のパウリ展開には、N rceil による $(8lceil log)$ 演算が必要で、N$ は自由度数を表す。
既存のアプローチは代数的スパーシリティや作用素構造を利用するが、有限要素の離散化に固有の組織を組み入れない。
論文 参考訳（メタデータ） (2026-06-09T22:13:50Z) - Counting anticommuting Pauli pairs in linear time [5.706918315850497]
我々は、有界局所性体系に対する$O(m)$アルゴリズムを提供する。
我々のアルゴリズムは、有界な局所性体系の中でパウリ弦の大規模な集合を処理するのに特に有用である。
論文 参考訳（メタデータ） (2026-05-10T14:41:11Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Pauli Decomposition via the Fast Walsh-Hadamard Transform [0.0]
行列要素の置換まで、分解係数は一般化されたアダマール行列の乗算によって元の行列と関係があることが示される。
方程式の数値的な実装は、現在利用可能な解よりも優れている。
論文 参考訳（メタデータ） (2024-08-12T14:56:45Z) - A tree-approach Pauli decomposition algorithm with application to quantum computing [0.0]
本稿では,この分解をツリーアプローチを用いて最適化する並列実装によるアルゴリズムを提案する。
また、特定の行列構造をどのように利用して操作数を削減できるかを説明します。
論文 参考訳（メタデータ） (2024-03-18T10:38:06Z) - Decomposing dense matrices into dense Pauli tensors [0.0]
O(2N) 時間で 2N-by-2N 複素行列と N-term Pauli テンソルの間の内積を計算する固定メモリ分岐式アルゴリズムを導出する。
提案手法は,行列を O(8N) 時間で重み付けしたパウリ弦の和に,恥ずかしく平行な分解を許容する。
論文 参考訳（メタデータ） (2024-01-29T18:18:11Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Coherent randomized benchmarking [68.8204255655161]
独立サンプルではなく,異なるランダム配列の重ね合わせを用いることを示す。
これは、ベンチマーク可能なゲートに対して大きなアドバンテージを持つ、均一でシンプルなプロトコルにつながることを示す。
論文 参考訳（メタデータ） (2020-10-26T18:00:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。