論文の概要: 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ベースのアルゴリズムの性能を向上させることができる。
関連論文リスト
- Solving the Encoding Bottleneck: Of the HHL Algorithm, By the HHL Algorithm [0.0]
HHL(Harrow-Hassidim-Lloyd)アルゴリズムは、量子線形系問題を解くために指数的スピードアップを提供する。
ここでは,HHLアルゴリズム自体をわずかに修正したバージョンを用いることで,約$O(log N)$のランタイムで状態が作成可能であることを示す。
論文 参考訳(メタデータ) (2025-02-19T08:39:41Z) - Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。
理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
論文 参考訳(メタデータ) (2024-11-29T05:29:47Z) - Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers [0.0]
我々はPsi-HHLが$mathcalkappa$行列を含む状況に対処できることを実証する。
行列は最大で256倍256$で、mathcalkappa$は約466である。
論文 参考訳(メタデータ) (2024-07-31T14:41:30Z) - 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) - Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective [39.58317527488534]
本稿では,HHLアルゴリズムに基づく線形方程式系の解法を,新しい四重項法を用いて提案する。
テンソルネットワーク上で量子インスパイアされたバージョンを実行し、プロジェクションのような非単体演算を行う能力を生かした。
論文 参考訳(メタデータ) (2023-09-11T08:18:41Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。