論文の概要: Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation

• arxiv url: http://arxiv.org/abs/2610.03800v1
• Date: Thu, 01 Oct 2026 06:46:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 05:11:36.483701
• Title: Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation
• Title（参考訳）: ポリノミアル状態調製のための指数圧縮・無洗浄エイリアスサンプリング
• Abstract要約: コヒーレントエイリアスサンプリングは、量子ルックアップテーブルを用いたブロックエンコーディングと量子シミュレーションのための重要なサブルーチンを実装している。 関連する構造は、量子特異値変換に使用するブロック符号化を実装するために、データルックアップと行列構造を利用する。 我々は,コヒーレントエイリアスサンプリングにより生成した補助レジスタを非計算する新しい手法を開発した。
• 参考スコア（独自算出の注目度）: 11.698279857205463
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Coherent alias sampling implement an important subroutine for block encoding and qubitization based quantum simulation using quantum lookup table. Related constructions exploit data lookup and matrix structure to implement block encodings for use in quantum singular value transformation. For a state on $n$ qubits, constructing and storing the alias table requires both classical and quantum resources exponential in $n$. We show that when the amplitudes are samples of a polynomial of degree at most $d$, the table can be represented and evaluated coherently with cost polynomial in $n$, $d$, exponentially reduced from $Θ(2^n)$ classical and quantum cost. We construct a quantum circuit for coherently computing the alias table for polynomial states using reversible integer arithmetic. By employing fast arithmetic, we construct a deterministic circuit for preparing polynomial states over Clifford+$T$ with a complete gate count of $\tilde{O}(ndB+B^2)$, where arithmetic width $B=\tilde{O}(dn+d\log(d+1))$. In the high precision limit for state fidelity $ε$ with fixed $n$ and $d$, it is sufficient have $B=Θ(\log(1/ε))$ and the complete gate count becomes $O(\log^3(1/ε)\log\log(1/ε))$. Additionally, the effective representation of the alias table can also be used for classical sampling algorithms. Furthermore, we develop a novel technique for uncomputing the auxilary register generated by coherent alias sampling. This technique opens a research direction in sampling based initial state preparation.
• Abstract（参考訳）: コヒーレントエイリアスサンプリングは、量子ルックアップテーブルを用いたブロックエンコーディングと量子化に基づく量子シミュレーションのための重要なサブルーチンを実装している。 関連する構造は、量子特異値変換に使用するブロック符号化を実装するために、データルックアップと行列構造を利用する。 n$ qubitsの状態の場合、エイリアステーブルの構築と保存には古典的リソースと量子的リソースの両方を$n$で指数関数化する必要がある。 振幅が少なくとも$d$の次数多項式のサンプルであるとき、テーブルは$n$, $d$のコスト多項式とコヒーレントに表され、古典的および量子的コストから指数関数的に減少することを示す。 可逆整数算術を用いて多項式状態のエイリアステーブルをコヒーレントに計算する量子回路を構築する。 高速算術を用いることで、算術幅$B=\tilde{O}(dn+d\log(d+1))$の完全ゲート数$\tilde{O}(ndB+B^2)$のクリフォード+$T$上で多項式状態を作成するための決定論的回路を構築する。 固定された$n$と$d$を持つ状態忠実度$ε$に対する高い精度の極限では、$B=(\log(1/ε))$で十分であり、完全ゲートカウントは$O(\log^3(1/ε)\log(1/ε))$となる。 さらに、エイリアステーブルの効率的な表現は古典的なサンプリングアルゴリズムにも利用できる。 さらに,コヒーレントエイリアスサンプリングによって生成された補助レジスタを解法する手法を開発した。 この技術はサンプリングに基づく初期状態準備における研究の方向性を開放する。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。 我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
  論文  参考訳（メタデータ） (2026-07-14T18:42:40Z)
• Quantum Krylov Algorithm for Szegö Quadrature [0.8158532237212478]
  ユニタリ作用素の関数の行列要素を評価する量子アルゴリズムを提案する。 この方法は、量子プロセッサから収集されたデータを用いて、二次ノードと重みを計算することに基づいている。
  論文  参考訳（メタデータ） (2025-09-23T16:13:08Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  スパースランク入力演算子の逆を効率的に決定することができる。 このアルゴリズムは、完全に誤り訂正された量子コンピュータのために想定されている。 このアルゴリズムがカーネルベースの量子機械学習にどのように使えるかについて議論する。
  論文  参考訳（メタデータ） (2025-01-16T09:39:31Z)
• Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography [3.040305634723913]
  計算量と記憶量の両方を削減できるquditシャドウトモグラフィーに基づく量子的アプローチを提案する。 (operatornametr(rho O)) は (textpoly(log d)) 計算で効率的に推定できる。
  論文  参考訳（メタデータ） (2024-08-29T03:56:16Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)

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

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