論文の概要: Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
- arxiv url: http://arxiv.org/abs/2405.18007v6
- Date: Tue, 29 Jul 2025 01:38:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-30 14:59:50.754527
- Title: Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
- Title(参考訳): 低サブ正規化と回路深さを有するスパース行列の辞書ベースブロック符号化
- Authors: Chunlin Yang, Zexian Li, Hongmei Yao, Zhaobing Fan, Guofeng Zhang, Jianshe Liu,
- Abstract要約: 本稿では,新しいデータ構造に基づくスパース行列の効率的なブロック符号化プロトコルを提案する。
同じ値のゼロでない要素は、ブロックエンコーディングプロトコルの辞書で同じ分類に属する。
我々のプロトコルは、ユニタリ(LCU)とスパースアクセス入力モデル(SAIM)の線形結合に接続する。
- 参考スコア(独自算出の注目度): 2.4487770108795393
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Block encoding severs as an important data input model in quantum algorithms, enabling quantum computers to simulate non-unitary operators effectively. In this paper, we propose an efficient block-encoding protocol for sparse matrices based on a novel data structure, called the dictionary data structure, which classifies all non-zero elements according to their values and indices. Non-zero elements with the same values, lacking common column and row indices, belong to the same classification in our block-encoding protocol's dictionary. When compiled into the \{\rm U(2), CNOT\} gate set, the protocol queries a $2^n \times 2^n$ sparse matrix with $s$ non-zero elements at a circuit depth of $\mathcal{O}(\log(ns))$, utilizing $\mathcal{O}(n^2s)$ ancillary qubits. This offers an exponential improvement in circuit depth relative to the number of system qubits, compared to existing methods~\cite{clader2022quantum,zhang2024circuit} with a circuit depth of $\mathcal{O}(n)$. Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to $\sum_{l=0}^{s_0}\vert A_l\vert$, where $s_0$ denotes the number of classifications in the dictionary and $A_l$ represents the value of the $l$-th classification. Furthermore, we show that our protocol connects to linear combinations of unitaries (LCU) and the sparse access input model (SAIM). To demonstrate the practical utility of our approach, we provide several applications, including Laplacian matrices in graph problems and discrete differential operators.
- Abstract(参考訳): 量子アルゴリズムにおける重要なデータ入力モデルとしてのエンコーディングシーバーのブロックにより、量子コンピュータは非ユニタリ演算子を効果的にシミュレートできる。
本稿では,新しいデータ構造である辞書データ構造に基づくスパース行列の効率的なブロック符号化プロトコルを提案する。
共通列と行のインデックスが欠落している同じ値の非ゼロ要素は、ブロックエンコーディングプロトコルの辞書で同じ分類に属する。
プロトコルは \{\rm U(2), CNOT\} ゲートセットにコンパイルされると、$2^n \times 2^n$スパース行列を$s$非ゼロ要素を$\mathcal{O}(\log(ns))$の回路深さで問合せ、$\mathcal{O}(n^2s)$の補助量子ビットを利用する。
これにより、回路深さが$\mathcal{O}(n)$の既存のメソッド~\cite{clader2022quantum,zhang2024circuit}と比較して回路深さが指数関数的に向上する。
さらに、このプロトコルでは、補助量子ビットの測定確率に影響を与えるスケール係数であるサブ正規化を$\sum_{l=0}^{s_0}\vert A_l\vert$に最小化し、$s_0$は辞書の分類数を表し、$A_l$は$l$-th分類の値を表す。
さらに,本プロトコルはユニタリ(LCU)とスパースアクセス入力モデル(SAIM)の線形結合に接続することを示す。
提案手法の実用性を示すために,グラフ問題におけるラプラシア行列や離散微分作用素など,いくつかの応用を提案する。
関連論文リスト
- An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
量子機械学習(QML)は、量子コンピューティングの利点をデータ駆動タスクに移行しようとする分野である。
入力をパウリ弦の有限集合にマッピングすることで、データ符号化に伴うコストを回避できる効率的な手法を提案する。
我々は、古典的および量子モデルに対して、テキストおよび画像分類タスクに対する我々のアプローチを評価する。
論文 参考訳(メタデータ) (2025-04-13T11:49:53Z) - Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
条件測定は、アシラ測定における小さな成功確率を避けるために行われる。
このアルゴリズムの目的関数は、1量子サブシステムの状態を測定することによって確率的に得ることができる。
論文 参考訳(メタデータ) (2025-03-19T07:01:38Z) - Preconditioned Block Encodings for Quantum Linear Systems [0.0]
Matrixプリコンディショニングは、プリコンディショナー$P$で$A$を乗算することで$kappa$を減らすための、確立された古典的テクニックである。
ブロック符号化のためのプリコンディショナと2つの符号化手法を検討する。
計算流体力学(Computational fluid Dynamics)の実用行列を用いて, サブ正規化因子と条件数$kappa$に対する影響を解析した。
論文 参考訳(メタデータ) (2025-02-28T10:08:14Z) - Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
本稿では,量子リード・ミュラー符号(RM)のゲートを,古典的特性を利用して特徴付けることを目的とする。
RM符号のための安定化器生成器のセットは、特定の次元のサブキューブに作用する$X$と$Z$演算子によって記述することができる。
論文 参考訳(メタデータ) (2024-10-10T04:07:24Z) - Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳(メタデータ) (2024-08-07T19:51:22Z) - Quantum sampling algorithms for quantum state preparation and matrix block-encoding [0.0]
まず、量子状態 $|psi_frangle propto sumN_x=1 f(x)|xrangle$ を作成するQRSに基づくアルゴリズムを提案する。
次に、QRSの手法を行列ブロック符号化問題に適用し、与えられた行列をブロック符号化するためのQRSベースのアルゴリズムを、与えられた行列の和 A = sum_ij A_ij |irangle langle j|$ で導入する。
論文 参考訳(メタデータ) (2024-05-19T03:46:11Z) - Block encoding of matrix product operators [0.0]
本稿では,その行列積演算子(MPO)表現に基づいてハミルトニアンをブロックエンコードする手法を提案する。
より具体的には、すべてのMPOテンソルを次元$D+2$でエンコードし、$D = lceillog(chi)rceil$ は、仮想結合次元と対数的にスケールする後に縮約された量子ビットの数である。
論文 参考訳(メタデータ) (2023-12-14T12:34:24Z) - Circuit complexity of quantum access models for encoding classical data [4.727325187683489]
典型的な量子アクセスモデルを構築する際のClifford$+T$複雑さについて検討する。
スパースアクセス入力モデルとブロックエンコーディングの両方が、ほぼ線形回路の複雑さを必要とすることを示す。
我々のプロトコルは、改良された量子状態の準備と、パウリ弦の選択的オラクルの上に構築されている。
論文 参考訳(メタデータ) (2023-11-19T16:23:57Z) - Block-encoding structured matrices for data input in quantum computing [0.0]
本稿では,行列の繰り返し値の間隔とパターンの算術的記述に基づいて,ブロック符号化回路を構築する方法を示す。
得られた回路は、間隔に応じてフラグキュービット数を減少させ、繰り返し値に応じてデータのロードコストを低減させる。
論文 参考訳(メタデータ) (2023-02-21T19:08:49Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
行列のブロック符号化のための近似量子回路を高速に生成するFABLEを提案する。
FABLE回路は単純な構造であり、1ビットと2ビットのゲートで直接定式化されている。
FABLE回路は圧縮・スパシファイド可能であることを示す。
論文 参考訳(メタデータ) (2022-04-29T21:06:07Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。