論文の概要: Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla
- arxiv url: http://arxiv.org/abs/2504.02385v2
- Date: Wed, 03 Sep 2025 09:27:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 17:24:09.12661
- 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要約: 量子特異値変換(Quantum Singular Value Transformation, QSVT)は,最もよく知られた量子アルゴリズムをカプセル化する統一フレームワークである。
その結果,量子アルゴリズムの新しいフレームワークが確立され,ハードウェアのオーバヘッドが大幅に低減され,ほぼ最適性能が維持された。
- 参考スコア（独自算出の注目度）: 18.660349597156266
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic $O(\log L)$ ancilla overhead and circuit depth $\widetilde{O}(L d\lambda )$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L H_k$, where $d$ is the polynomial degree and $\lambda=\sum_{k}\|H_k\|$. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of $\widetilde{O}(L(d\lambda_{\mathrm{comm}})^{1+o(1)})$, without requiring any complicated multi-qubit controlled gates. Moreover, $\lambda_{\mathrm{comm}}$ depends on the nested commutators of the terms of $H$ and can be substantially smaller than $\lambda$ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. As applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly 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}(L d\lambda )$ for polynomial transformations of a Hamiltonian $H=\sum_{k=1}^L H_k$, where $d$ is the polynomial degree and $\lambda=\sum_{k}\|H_k\|$である。
我々は、基本的なハミルトニアンシミュレーション技術、すなわち、トロッター法のみを利用する、単純だが強力なアプローチを導入する。
(i)ブロックエンコーディングの必要性を排除する。
(ii) ancilla オーバーヘッドを 1 キュービットに減らし
(iii) 相変わらずほぼ最適の複雑さを維持している。
本手法は,複雑なマルチキュービット制御ゲートを必要とせず,回路深さを$\widetilde{O}(L(d\lambda_{\mathrm{comm}})^{1+o(1)})$とする。
さらに、$\lambda_{\mathrm{comm}}$は、$H$のネストされた交換子に依存しており、標準的なQSVTにはない多くの物理的に関連するハミルトン多様体に対して$\lambda$よりもかなり小さい。
これらの結果を達成するために、Richardson外挿法を新しい方法で利用し、任意のユニタリとハミルトン進化作用素のインターリーブ列の誤りを体系的に排除し、QSVTを含むがより広く適用可能な一般的なフレームワークを確立する。
応用として、線形系を解くためのエンドツーエンドの量子アルゴリズムを開発し、ハミルトニアンの基底状態特性を推定する。
本研究は, 量子アルゴリズムの新しいフレームワークを構築し, ハードウェアのオーバーヘッドを大幅に低減し, ほぼ最適性能を維持しつつ, 短期的およびフォールトトレラントな量子コンピューティングの両立を図っている。
関連論文リスト
- 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) - Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。
我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-04T17:58:01Z) - 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) - Replicability in Reinforcement Learning [46.89386344741442]
生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。
ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
論文 参考訳（メタデータ） (2023-05-31T05:16:23Z) - Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
そこで我々は, 断熱量子計算に基づく線形線形解法アルゴリズムを開発した。
このアルゴリズムは最適スケーリング$O(kappa/log$)$に改善され、$epsilon$が指数関数的に改善される。
ハミルトンシミュレーションの代わりに、より安価なランダム化されたウォーク演算子法を導入する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - 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 Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。