論文の概要: FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing
- arxiv url: http://arxiv.org/abs/2205.05004v1
- Date: Tue, 10 May 2022 16:20:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 17:43:43.681180
- Title: FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing
- Title（参考訳）: FastHare: 大規模量子アニーリングのための高速ハミルトン還元
- Authors: Phuc Thai, My T. Thai, Tam Vu, Thang N. Dinh
- Abstract要約: 非分離群の概念を導入し、最適解において同じ値を得るハミルトニアンにおいて、量子ビットの部分集合として定義される。
FastHareは、反復的に、非分離群を単一のキュービットに検出し、マージする。
これは、ユーザ定義パラメータの$alpha$に対して$O(alpha n2)$のみの証明可能な最悪のケースタイムの複雑さ内で行われる。
- 参考スコア（独自算出の注目度）: 17.830687420962512
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum annealing (QA) that encodes optimization problems into Hamiltonians
remains the only near-term quantum computing paradigm that provides sufficient
many qubits for real-world applications. To fit larger optimization instances
on existing quantum annealers, reducing Hamiltonians into smaller equivalent
Hamiltonians provides a promising approach. Unfortunately, existing reduction
techniques are either computationally expensive or ineffective in practice. To
this end, we introduce a novel notion of non-separable~group, defined as a
subset of qubits in a Hamiltonian that obtains the same value in optimal
solutions. We develop a theoretical framework on non-separability accordingly
and propose FastHare, a highly efficient reduction method. FastHare,
iteratively, detects and merges non-separable groups into single qubits. It
does so within a provable worst-case time complexity of only $O(\alpha n^2)$,
for some user-defined parameter $\alpha$. Our extensive benchmarks for the
feasibility of the reduction are done on both synthetic Hamiltonians and 3000+
instances from the MQLIB library. The results show FastHare outperforms the
roof duality, the implemented reduction method in D-Wave's SDK library, with
3.6x higher average reduction ratio. It demonstrates a high level of
effectiveness with an average of 62% qubits saving and 0.3s processing time,
advocating for Hamiltonian reduction as an inexpensive necessity for QA.
- Abstract（参考訳）: ハミルトンに最適化問題を符号化する量子アニール(QA)は、現実世界のアプリケーションに十分な多くの量子ビットを提供する唯一の短期量子コンピューティングパラダイムである。
既存の量子アニーラーにより大きな最適化インスタンスを適合させるために、ハミルトニアンをより小さな等価ハミルトニアンに還元することは有望なアプローチを提供する。
残念ながら、既存の還元技術は計算コストが高いか、実際は効果がない。
この目的のために、最適解において同じ値を得るハミルトンの量子ビットの部分集合として定義される非分離型~群という新しい概念を導入する。
本研究では,非分離性に関する理論的枠組みを開発し,高効率な還元法であるFastHareを提案する。
FastHareは、反復的に、非分離群を単一のキュービットに検出し、マージする。
これは、ユーザ定義パラメータの$\alpha$に対して$O(\alpha n^2)$のみの証明可能な最悪のケース時間内で行われる。
MQLIBライブラリの合成ハミルトニアンおよび3000以上のインスタンスに対して、この削減の実現可能性に関する広範なベンチマークを行った。
その結果,D-Wave の SDK ライブラリに実装された削減手法であるFastHare は,平均還元率を 3.6 倍に向上させた。
平均62%の量子ビットの節約と0.3の処理時間で高い効率性を示し、QAの安価な必要性としてハミルトン還元を提唱している。
関連論文リスト
- Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - SHARC-VQE: Simplified Hamiltonian Approach with Refinement and Correction enabled Variational Quantum Eigensolver for Molecular Simulation [0.0]
SHARC-VQEは分子シミュレーションの計算コストを大幅に削減する。
SHARC-VQEによる測定結果は、量子回路からのノイズによる誤差が少ない。
論文 参考訳（メタデータ） (2024-07-17T04:01:55Z) - Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。
Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。
評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
論文 参考訳（メタデータ） (2024-04-30T23:55:03Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin
Models [8.463477025989542]
我々は、デジタルカウンタダイバティック量子最適化(DCQO)アルゴリズムを利用して、4つの局所相互作用までの$p$-spinモデルの最適解を求める。
変分法を用いてパラメータを最適化することにより,それぞれ100ドル,93%,83%のインスタンスに対して,単位精度2-スピン,3-スピン,4-スピンの問題を解く。
論文 参考訳（メタデータ） (2023-11-11T22:49:16Z) - Continuous Hamiltonian dynamics on digital quantum computers without
discretization error [0.0]
本稿では,デジタル量子コンピュータ上でのハミルトン力学の計算アルゴリズムを提案する。
アルゴリズムは有限深度でゼロ離散化誤差を達成する。
シミュレーションのゲートカウントは、t$が$O(t2mu2)$、mu$が$1$-normである。
論文 参考訳（メタデータ） (2023-08-07T16:12:27Z) - SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
LLMにおける生成推論の主なボトルネックは、単一のバッチ推論のための計算ではなく、メモリ帯域幅である。
学習後量子化フレームワークであるSqueezeLLMを導入し、最大3ビットの超低精度でのロスレス圧縮を実現する。
本フレームワークは,2次情報に基づく最適ビット精度割当を探索する感度ベース非一様量子化法と,2次情報に基づくDense-and-Sparse分解法と,2次情報量割当値と感度重み値を効率的にスパース形式で格納するDense-and-Sparse分解法である。
論文 参考訳（メタデータ） (2023-06-13T08:57:54Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。