論文の概要: Halving the Cost of Quantum Algorithms with Randomization
- arxiv url: http://arxiv.org/abs/2409.03744v2
- Date: Tue, 17 Sep 2024 19:03:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-19 22:22:45.928721
- Title: Halving the Cost of Quantum Algorithms with Randomization
- Title（参考訳）: ランダム化による量子アルゴリズムのコスト削減
- Authors: John M. Martyn, Patrick Rall,
- Abstract要約: 量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
- 参考スコア（独自算出の注目度）: 0.138120109831448
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., $\epsilon \rightarrow O(\epsilon^2)$) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing. Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as $O(\log(1/\epsilon))$ -- stemming from a result in functional analysis -- this error suppression reduces their query complexity by a factor that asymptotically approaches $1/2$. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.
- Abstract（参考訳）: 量子信号処理(QSP)は、線形作用素の多項式変換を実装するための体系的なフレームワークを提供し、ほとんどすべての既知の量子アルゴリズムを統一する。
並行して、最近の研究はランダム化されたコンパイルを開発した。これはユニタリゲートを量子チャネルにプロモートし、誤りの二次的な抑制を可能にする技術である($\epsilon \rightarrow O(\epsilon^2)$)。
ここでは、確率量子信号処理によるランダム化コンパイルをQSPに統合する。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択された多項式の確率的混合を実装し, 誤差は等価な個々の多項式よりも2次的に小さい。
ほとんど全てのQSPベースのアルゴリズムは、$O(\log(1/\epsilon))$ -- 関数解析の結果から生じる -- のクエリ複雑さを示すので、このエラーは、漸近的に1/2$に近づいた要因によって、クエリの複雑さを減少させる。
QSPの統一能力により、この削減は量子アルゴリズムにまで拡張され、実時間と想像の時間進化、位相推定、基底状態の準備、行列逆転のアルゴリズムで示される。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Accelerated Quantum Amplitude Estimation without QFT [0.0]
我々は、現在利用可能なアプローチと比較して優れた性能(より低い量子計算複雑性と高速な古典計算部分)を実現する量子振幅推定アルゴリズムを提唱した。
このアルゴリズムの正しさと量子計算複雑性に縛られる$O(frac1varepsilon)$は、正確な証明によって支持される。
論文 参考訳（メタデータ） (2024-07-23T18:49:11Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Generalized Quantum Signal Processing [0.6768558752130311]
本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。
我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。
P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
論文 参考訳（メタデータ） (2023-08-03T01:51:52Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - Efficient phase-factor evaluation in quantum signal processing [1.3614427997190908]
量子信号処理(QSP)は、量子コンピュータに行列を正確に実装する強力な量子アルゴリズムである。
現在、QSP回路構築に必要な位相係数を計算できる古典的安定なアルゴリズムは存在しない。
本稿では、標準的な倍精度演算を用いて位相係数を正確に計算できる最適化に基づく手法を提案する。
論文 参考訳（メタデータ） (2020-02-26T17:23:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。