論文の概要: Harrow-Hassidim-Lloyd algorithm without ancilla postselection
- arxiv url: http://arxiv.org/abs/2208.02200v2
- Date: Thu, 9 Nov 2023 12:13:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-10 19:14:13.556166
- Title: Harrow-Hassidim-Lloyd algorithm without ancilla postselection
- Title(参考訳): harrow-hassidim-lloydアルゴリズム
- Authors: D. V. Babukhin
- Abstract要約: HHL (Harrow-Hassidim-Lloyd algorithm) は線形方程式系の指数関数的に高速な解を可能にするアルゴリズムである。
HHLは、この溶液を得るために、アンシラクビットのポストセレクションを必要とする。
ここでは,HHLアルゴリズムがアシラ量子ビットのポストセレクションなしで動作可能な条件を示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Harrow-Hassidim-Lloyd algorithm (HHL) allows for the exponentially faster
solution of a system of linear equations. However, this algorithm requires the
postselection of an ancilla qubit to obtain the solution. This postselection
makes the algorithm result probabilistic. Here we show conditions when the HHL
algorithm can work without postselection of ancilla qubit. We derive
expectation values for an observable $M$ on the HHL outcome state when ancilla
qubit is measured in $\ket{0}$ and $\ket{1}$ and show condition for
postselection-free HHL running. We provide an explicit example of a
practically-interesting input matrix and an observable, which satisfy
postselection-free HHL condition. Our work can improve the performance of the
HHL-based algorithms.
- Abstract(参考訳): harrow-hassidim-lloyd algorithm (hhl) は線形方程式系の指数関数的に高速な解法である。
しかし、このアルゴリズムでは解を得るにはアンシラキュービットのポストセレクションが必要となる。
このポストセレクションはアルゴリズム結果を確率的にする。
ここでは、hhlアルゴリズムがancilla qubitの事後選択なしで機能する条件を示す。
ancilla qubit が $\ket{0}$ と $\ket{1}$ で測定された場合の hhl の結果状態の観測可能な $m$ に対する期待値を導出し、ポストセレクションフリー hhl の実行条件を示す。
我々は,ポスト選択フリーなhhl条件を満たす,事実上興味のある入力行列とオブザーバブルの明示的な例を示す。
我々の研究は、HHLベースのアルゴリズムの性能を向上させることができる。
関連論文リスト
- Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳(メタデータ) (2023-11-06T16:00:07Z) - Light Schrödinger Bridge [72.88707358656869]
我々は,軽量でシミュレーション不要で理論的に正当化されたSchr"odinger Bridgesソルバを開発した。
我々の光解法は密度推定に広く用いられているガウス混合モデルに類似している。
この類似性に着想を得て、光解法がSBの普遍近似であることを示す重要な理論的結果も証明した。
論文 参考訳(メタデータ) (2023-10-02T13:06:45Z) - 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) - Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-28T16:53:41Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳(メタデータ) (2021-09-14T11:12:32Z) - An Iterative Improvement Method for HHL algorithm for Solving Linear
System of Equations [0.0]
本稿では,Harrow-Hassidim-Lloyd (HHL) アルゴリズムの線形方程式系を解くための反復的改善法を提案する。
HHLアルゴリズムの精度は、行列の固有値を表現するために使用される量子ビットの数によって制限される。
改良された反復法は測定回数を減らすことができる。
論文 参考訳(メタデータ) (2021-08-17T16:25:01Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳(メタデータ) (2021-02-25T15:50:19Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳(メタデータ) (2020-12-06T18:39:20Z) - Robust quantum minimum finding with an application to hypothesis
selection [0.0]
雑音コンパレータを用いて長さ$N$の最小要素を求める問題を考える。
雑音のないケースの二次的なスピードアップを保った雑音量子最小化のための量子アルゴリズムを実証する。
我々は、コンパレータが分解能に制限されたり、不確実性がある場合に、ロバストな量子最小化がアルゴリズムの有用な構築ブロックになることを期待する。
論文 参考訳(メタデータ) (2020-03-26T07:42:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。