論文の概要: Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla

• arxiv url: http://arxiv.org/abs/2504.02385v1
• Date: Thu, 03 Apr 2025 08:24:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-04 12:55:05.420263
• Title: Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla
• Title（参考訳）: ブロックエンコーディングを伴わない量子特異値変換:最小アンシラを用いた近似的複雑性
• Authors: Shantanav Chakraborty, Soumyabrata Hazra, Tongyang Li, Changpeng Shao, Xinzhao Wang, Yuxin Zhang,
• Abstract要約: 我々は量子特異値変換(QSVT)のための新しいアルゴリズムを開発した。 この結果は量子アルゴリズムの新しいフレームワークを提供し、ほぼ最適性能を維持しながらハードウェアのオーバーヘッドを低減させる。 応用として,量子線形系と基底状態特性推定のためのエンドツーエンド量子アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 10.23939777076027
• License:
• Abstract: We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework underlying a wide range of quantum algorithms. Existing implementations of QSVT rely on block encoding, incurring $O(\log L)$ ancilla overhead and circuit depth $\widetilde{O}(d\lambda L)$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L \lambda_k H_k$, where $d$ is polynomial degree, and $\lambda=\sum_k |\lambda_k|$. We introduce a new approach that eliminates block encoding, needs only a single ancilla qubit, and maintains near-optimal complexity, using only basic Hamiltonian simulation methods such as Trotterization. Our method achieves a circuit depth of $\widetilde{O}(L(d\lambda_{\mathrm{comm}})^{1+o(1)})$, without any multi-qubit controlled gates. Here, $\lambda_{\mathrm{comm}}$ depends on the nested commutators of the $H_k$'s and can be much smaller than $\lambda$. Central to our technique is a novel use of Richardson extrapolation, enabling systematic error cancellation in interleaved sequences of arbitrary unitaries and Hamiltonian evolution operators, establishing a broadly applicable framework beyond QSVT. Additionally, we propose two randomized QSVT algorithms for cases with only sampling access to Hamiltonian terms. The first uses qDRIFT, while the second replaces block encodings in QSVT with randomly sampled unitaries. Both achieve quadratic complexity in $d$, which we establish as a lower bound for any randomized method implementing polynomial transformations in this model. Finally, as applications, we develop end-to-end quantum algorithms for quantum linear systems and ground state property estimation, achieving near-optimal complexity without oracular access. Our results provide a new framework for quantum algorithms, reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.
• Abstract（参考訳）: 量子特異値変換(quantum Singular Value Transformation, QSVT)のための新しいアルゴリズムを開発した。 既存のQSVTの実装はブロックエンコーディングに依存しており、$O(\log L)$ ancilla overhead and circuit depth$\widetilde{O}(d\lambda L)$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L \lambda_k H_k$, where $d$ is polynomial degree, $\lambda=\sum_k |\lambda_k|$である。 本稿では,ブロック符号化を排除し,単一アンシラ量子ビットのみを必要とする新しい手法を提案する。 本手法は,マルチキュービット制御ゲートを使わずに,回路深さを$\widetilde{O}(L(d\lambda_{\mathrm{comm}})^{1+o(1)})$とする。 ここでは、$\lambda_{\mathrm{comm}}$は、$H_k$のネストされた通勤者に依存し、$\lambda$よりもずっと小さい。 我々の技術の中心は、任意のユニタリーとハミルトン進化作用素のインターリーブ列における体系的なエラーキャンセルを可能にする、リチャードソン外挿法(Richardson extrapolation)の斬新な使用であり、QSVTを超えて広く適用可能なフレームワークを確立する。 さらに,ハミルトン項にのみアクセスするケースに対して,ランダム化された2つのQSVTアルゴリズムを提案する。 1つはqDRIFT、もう1つはQSVTのブロックエンコーディングをランダムにサンプリングされたユニタリに置き換える。 どちらも$d$の二次複雑性を達成し、このモデルで多項式変換を実装する任意のランダム化メソッドの下位境界として確立する。 最後に, 量子線形系と基底状態特性推定のためのエンドツーエンドの量子アルゴリズムを開発し, 眼球運動を伴わない近似的複雑性を実現する。 本研究は,量子アルゴリズムのための新しいフレームワークを提供することにより,ハードウェアのオーバーヘッドを低減し,ほぼ最適性能を維持しつつ,短期的およびフォールトトレラントな量子コンピューティングに影響を及ぼす。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• 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)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Generalized Quantum Signal Processing [0.6768558752130311]
  本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。 我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。 P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
  論文  参考訳（メタデータ） (2023-08-03T01:51:52Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
  我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。 また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
  論文  参考訳（メタデータ） (2023-06-19T23:20:30Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。 我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
  論文  参考訳（メタデータ） (2021-12-15T21:44:05Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。 このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-09-09T18:00:09Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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