論文の概要: Parallel Quantum Signal Processing Via Polynomial Factorization
- arxiv url: http://arxiv.org/abs/2409.19043v1
- Date: Fri, 27 Sep 2024 17:54:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-06 04:40:55.514296
- Title: Parallel Quantum Signal Processing Via Polynomial Factorization
- Title（参考訳）: ポリノミアル因子による並列量子信号処理
- Authors: John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, Isaac L. Chuang,
- Abstract要約: 量子並列信号処理アルゴリズムを開発した。
我々のアルゴリズムは、$texttr (P(rho)$ over $k$の計算を並列化し、クエリの深さを$d/k$に減らし、QSPの時間空間トレードオフのファミリを可能にする。
これにより、量子コンピュータに適した特性推定が可能となり、$O(textpoly(d) 2(k) )$ で測定数を増やすことで実現される。
- 参考スコア（独自算出の注目度）: 3.1981483719988235
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum signal processing (QSP) is a methodology for constructing polynomial transformations of a linear operator encoded in a unitary. Applied to an encoding of a state $\rho$, QSP enables the evaluation of nonlinear functions of the form $\text{tr}(P(\rho))$ for a polynomial $P(x)$, which encompasses relevant properties like entropies and fidelity. However, QSP is a sequential algorithm: implementing a degree-$d$ polynomial necessitates $d$ queries to the encoding, equating to a query depth $d$. Here, we reduce the depth of these property estimation algorithms by developing Parallel Quantum Signal Processing. Our algorithm parallelizes the computation of $\text{tr} (P(\rho))$ over $k$ systems and reduces the query depth to $d/k$, thus enabling a family of time-space tradeoffs for QSP. This furnishes a property estimation algorithm suitable for distributed quantum computers, and is realized at the expense of increasing the number of measurements by a factor $O( \text{poly}(d) 2^{O(k)} )$. We achieve this result by factorizing $P(x)$ into a product of $k$ smaller polynomials of degree $O(d/k)$, which are each implemented in parallel with QSP, and subsequently multiplied together with a swap test to reconstruct $P(x)$. We characterize the achievable class of polynomials by appealing to the fundamental theorem of algebra, and demonstrate application to canonical problems including entropy estimation and partition function evaluation.
- Abstract（参考訳）: 量子信号処理(QSP)は、ユニタリで符号化された線形作用素の多項式変換を構成する手法である。
状態 $\rho$ の符号化に適用すると、QSP は多項式 $P(x)$ に対して $\text{tr}(P(\rho))$ という形の非線形関数の評価を可能にする。
しかし、QSPはシーケンシャルアルゴリズムである:次数-$d$多項式を実装するには、エンコーディングに$d$クエリを必要とする。
ここでは、並列量子信号処理を開発することにより、これらの特性推定アルゴリズムの深さを小さくする。
我々のアルゴリズムは$\text{tr} (P(\rho))$ over $k$の計算を並列化し、クエリの深さを$d/k$に減らし、QSPの時間空間トレードオフのファミリを可能にする。
これにより、分散量子コンピュータに適した特性推定アルゴリズムが実現され、係数$O( \text{poly}(d) 2^{O(k)} )$で測定数を増やすことで実現される。
この結果は、$P(x)$を$k$の次数$O(d/k)$の小さな多項式の積に分解し、それぞれQSPと並列に実装し、その後、$P(x)$を再構成するためにスワップテストで乗算することで達成される。
代数の基本定理に訴えることで達成可能な多項式のクラスを特徴づけ、エントロピー推定や分割関数評価を含む正準問題への応用を実証する。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Computational Supremacy of Quantum Eigensolver by Extension of Optimized Binary Configurations [0.0]
我々は、D-Wave Quantum Annealer(D-Wave QA)に基づく量子固有解法を開発する。
このアプローチは、古典的コンピュータの導出を伴わない固有状態$vert psi rangle$を最適化するために反復的なQA測定を実行する。
提案したQEアルゴリズムは誤差の5倍の10～3$の正確な解を提供することを確認した。
論文 参考訳（メタデータ） (2024-06-05T15:19:53Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Generalized Quantum Signal Processing [0.6768558752130311]
本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。
我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。
P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
論文 参考訳（メタデータ） (2023-08-03T01:51:52Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。
ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。
バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文 参考訳（メタデータ） (2023-05-25T08:43:11Z) - Infinite quantum signal processing [1.3614427997190908]
量子信号処理(QSP)は、次数$d$の真のスカラーを表す。
QSPは多種多様なポリノミカル関数を表現できることを示す。
解析の結果,対象関数の正則性と因子の減衰特性との間には,驚くべき関連性があることが判明した。
論文 参考訳（メタデータ） (2022-09-21T07:50:26Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Variational Quantum Linear Solver [0.3774866290142281]
本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。
リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
論文 参考訳（メタデータ） (2019-09-12T17:28:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。