論文の概要: A Dequantized Algorithm for the Guided Local Hamiltonian Problem
- arxiv url: http://arxiv.org/abs/2411.16163v2
- Date: Tue, 26 Nov 2024 02:33:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-27 13:34:35.064638
- Title: A Dequantized Algorithm for the Guided Local Hamiltonian Problem
- Title（参考訳）: ガイド付き局所ハミルトニアン問題の定式化アルゴリズム
- Authors: Yukun Zhang, Yusen Wu, Xiao Yuan,
- Abstract要約: 誘導局所ハミルトニアン問題(GLH)は量子コンピュータ上で効率よく解くことができ、BQP完全であることが証明されている。
これにより、GLH問題は古典計算と量子計算の基本的な分離を探求するための貴重なフレームワークとなる。
ランダム化量子想像時間進化量子アルゴリズムの量子化古典アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.891413712995642
- License:
- Abstract: The local Hamiltonian (LH) problem, the quantum analog of the classical constraint satisfaction problem, is a cornerstone of quantum computation and complexity theory. It is known to be QMA-complete, indicating that it is challenging even for quantum computers. Interestingly, the guided local Hamiltonian (GLH) problem -- an LH problem with a guiding state that has a non-trivial overlap with the ground state -- can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. Remarkably, the quantum algorithm for solving the GLH problem can be `dequantized' (i.e., made classically simulatable) under certain conditions, such as when only constant accuracy is required and when the Hamiltonian satisfies an unrealistic constant operator norm constraint. In this work, we relieve these restrictions by introducing a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm. We demonstrate that it achieves either limited or arbitrary constant accuracy, depending on whether the guiding state's overlap is general or exceeds a certain threshold. Crucially, our approach eliminates the constant operator norm constraint on the Hamiltonian, opening its applicability to realistic problems. Our results advance the classical solution of the GLH problem in practical settings and provide new insights into the boundary between classical and quantum computational power.
- Abstract（参考訳）: 古典的制約満足問題の量子アナログである局所ハミルトン問題(LH)は、量子計算と複雑性理論の基礎となっている。
QMA完全であることが知られており、量子コンピュータでも困難であることを示している。
興味深いことに、ガイド付き局所ハミルトン問題(基底状態と非自明な重複を持つ誘導状態を持つLH問題)は、量子コンピュータ上で効率よく解き、BQP完全であることが証明されている。
これにより、GLH問題は古典計算と量子計算の基本的な分離を探求するための貴重なフレームワークとなる。
注目すべきは、GLH問題を解決する量子アルゴリズムは、一定の精度しか必要とせず、ハミルトニアンが非現実的な定数作用素ノルム制約を満たすような条件下で 'dequantized'(古典的にシミュラブルにする)ことができることである。
本研究では、ランダム化量子想像時間進化量子アルゴリズムの量子化古典アルゴリズムを導入することにより、これらの制約を緩和する。
誘導状態のオーバーラップが一般的なものであるか、一定の閾値を超えているかによって、制限または任意の一定精度を達成することを実証する。
重要なことに、我々のアプローチはハミルトニアンに対する定数作用素ノルムの制約を排除し、現実的な問題への適用性を開放する。
本結果は,GLH問題の古典解を現実的に推し進め,古典的計算パワーと量子的計算パワーの境界に関する新たな洞察を与えるものである。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics [42.29248343585333]
最大133キュービットの量子ハードウェアとエラー軽減手法をベンチマークする。
最大2量子ゲート幅は28で、最大1396個の2量子ゲートを持つ。
結果はハミルトンシミュレーション、変分アルゴリズム、最適化、量子機械学習などのアプリケーションに転送可能である。
論文 参考訳（メタデータ） (2024-04-11T18:00:05Z) - State-Averaged Orbital-Optimized VQE: A quantum algorithm for the
democratic description of ground and excited electronic states [0.0]
SA-OO-VQEパッケージは、典型的な変分量子固有解法に基づくハイブリッド量子古典的概念によって両方の問題を解決することを目的としている。
SA-OO-VQEは、同じ足場上で退化状態(または準退化状態)を処理できるので、回避された交差や円錐交差に関する既知の数値最適化問題を回避することができる。
論文 参考訳（メタデータ） (2024-01-22T12:16:37Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Theory of Quantum Generative Learning Models with Maximum Mean
Discrepancy [67.02951777522547]
量子回路ボルンマシン(QCBM)と量子生成逆ネットワーク(QGAN)の学習可能性について検討する。
まず、QCBMの一般化能力を解析し、量子デバイスがターゲット分布に直接アクセスできる際の優位性を同定する。
次に、QGANの一般化誤差境界が、採用されるAnsatz、クォーディットの数、入力状態に依存することを示す。
論文 参考訳（メタデータ） (2022-05-10T08:05:59Z) - Minimum-Time Quantum Control and the Quantum Brachistochrone Equation [3.0616044531734192]
完全量子ブラキストロン方程式の一般解を示す。
制約の下での進化の速度は、制約のない場合に対して減少することを示す。
量子ブラキストロン方程式の解法はラグランジュ乗算の力学の解法と密接に関連していることがわかった。
論文 参考訳（メタデータ） (2022-04-27T09:26:59Z) - Schr\"odinger-Heisenberg Variational Quantum Algorithms [1.9887498823918806]
最近のブレークスルーにより、数十から数百キュービットの中間スケールの量子コンピューティングが可能になった。
古典的コンピュータを超えるために必要な極めて高い精度は、回路深度に重大な需要をもたらす。
本稿では,この問題を解決するために,シュリンガー・ハイゼンベルク変分量子アルゴリズムのパラダイムを提案する。
論文 参考訳（メタデータ） (2021-12-15T04:53:01Z) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。
量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
論文 参考訳（メタデータ） (2021-03-12T20:58:41Z) - Iterative Quantum Assisted Eigensolver [0.0]
我々は、ハミルトニアン基底状態を近似するハイブリッド量子古典アルゴリズムを提供する。
我々のアルゴリズムは、現在の量子コンピュータに適した方法で、強力なKrylov部分空間法に基づいている。
論文 参考訳（メタデータ） (2020-10-12T12:25:16Z) - Limitations of optimization algorithms on noisy quantum devices [0.0]
我々は、古典的アルゴリズムと、短期的な量子デバイス上で動作している量子アルゴリズムを比較する透過的な方法を提案する。
我々のアプローチは、量子状態がノイズモデルの定点にどれだけ早く収束するかを決定するエントロピック不等式の組み合わせに基づいている。
論文 参考訳（メタデータ） (2020-09-11T17:07:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。