論文の概要: Harrow-Hassidim-Lloyd algorithm without ancilla postselection
- arxiv url: http://arxiv.org/abs/2208.02200v1
- Date: Wed, 3 Aug 2022 16:36:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-02 09:55:24.793647
- Title: Harrow-Hassidim-Lloyd algorithm without ancilla postselection
- Title(参考訳): harrow-hassidim-lloydアルゴリズム
- Authors: D. V. Babukhin
- Abstract要約: HHLアルゴリズム(Harrow-Hassidim-Lloyd algorithm)は、線形方程式系の指数関数的に高速な解を可能にするアルゴリズムである。
我々は,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
expressions for expectation values for an observable $M$ on the HHL outcome
state when ancilla qubit is measured in 0 and 1. When a commutator of an input
matrix and an observable matrix is zero, the HHL algorithm can give correct
expectation values for any outcome of ancilla measurement. We demonstrate this
result on a toy 2 by 2 matrix example. We further provide more general examples
of matrices $A$ and observables $M$, which allow the postselection-free running
of the algorithm. Our work can improve the performance of the HHL-based
algorithms.
- Abstract(参考訳): harrow-hassidim-lloyd algorithm (hhl) は線形方程式系の指数関数的に高速な解法である。
しかし、このアルゴリズムでは解を得るにはアンシラキュービットのポストセレクションが必要となる。
このポストセレクションはアルゴリズム結果を確率的にする。
ここでは、hhlアルゴリズムがancilla qubitの事後選択なしで機能する条件を示す。
acilla qubit が 0 と 1 で測定されたとき、hhl の結果状態の観測可能な $m$ に対する期待値の式を導出する。
入力行列と可観測行列の可換行列がゼロのとき、HHLアルゴリズムは任意のアシラ測定の結果に対して正しい期待値を与えることができる。
この結果をトイ2と2のマトリクスの例で示す。
さらに、より一般的な行列の例である$a$とobservables $m$を提供し、このアルゴリズムのポスト選択フリーな実行を可能にします。
我々の研究は、HHLベースのアルゴリズムの性能を向上させることができる。
関連論文リスト
- Quantum speedups for linear programming via interior point methods [2.07180164747172]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳(メタデータ) (2023-11-06T16:00:07Z) - 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) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳(メタデータ) (2021-06-15T02:23:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。