論文の概要: Variational quantum algorithms for Poisson equations based on the
decomposition of sparse Hamiltonians
- arxiv url: http://arxiv.org/abs/2309.12826v1
- Date: Fri, 22 Sep 2023 12:26:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-25 14:39:51.522366
- Title: Variational quantum algorithms for Poisson equations based on the
decomposition of sparse Hamiltonians
- Title（参考訳）: スパースハミルトンの分解に基づくポアソン方程式の変分量子アルゴリズム
- Authors: Hui-Min Li, Zhi-Xi Wang, Shao-Ming Fei
- Abstract要約: 我々は$sigma_xotimes A$を7と$(4d+1)$ Hermitian, one-sparse, and self-inverse operatorの和に分解する。
我々は、損失関数を効率的に評価するために、量子回路を明示的に設計する。
- 参考スコア（独自算出の注目度）: 0.9865722130817715
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving a Poisson equation is generally reduced to solving a linear system
with a coefficient matrix $A$ of entries $a_{ij}$, $i,j=1,2,...,n$, from the
discretized Poisson equation. Although the variational quantum algorithms are
promising algorithms to solve the discretized Poisson equation, they generally
require that $A$ be decomposed into a sum of $O[\text{poly}(\text{log}_2n)]$
simple operators in order to evaluate efficiently the loss function. A tensor
product decomposition of $A$ with $2\text{log}_2n+1$ terms has been explored in
previous works. In this paper, based on the decomposition of sparse
Hamiltonians we greatly reduce the number of terms. We first write the loss
function in terms of the operator $\sigma_x\otimes A$ with $\sigma_x$ denoting
the standard Pauli operator. Then for the one-dimensional Poisson equations
with different boundary conditions and for the $d$-dimensional Poisson
equations with Dirichlet boundary conditions, we decompose $\sigma_x\otimes A$
into a sum of at most 7 and $(4d+1)$ Hermitian, one-sparse, and self-inverse
operators, respectively. We design explicitly the quantum circuits to evaluate
efficiently the loss function. The decomposition method and the design of
quantum circuits can also be easily extended to linear systems with Hermitian
and sparse coefficient matrices satisfying $a_{i,i+c}=a_{c}$ for
$c=0,1,\cdots,n-1$ and $i=0,\cdots,n-1-c$.
- Abstract（参考訳）: ポアソン方程式の解法は、一般に、離散化されたポアソン方程式から a_{ij}$, $i,j=1,2, ...,n$ の成分の係数行列を持つ線型系を解くことに還元される。
変分量子アルゴリズムは離散化されたポアソン方程式を解くために有望なアルゴリズムであるが、損失関数を効率的に評価するためには、一般に$A$を$O[\text{poly}(\text{log}_2n)]$単純作用素の和に分解する必要がある。
A$ と $2\text{log}_2n+1$ のテンソル積分解は、以前の研究で検討されている。
本稿では、スパースハミルトニアンの分解に基づいて、項数を大幅に削減する。
まず、損失関数を演算子 $\sigma_x\otimes A$ with $\sigma_x$ で記述し、標準パウリ演算子を示す。
次に、異なる境界条件を持つ1次元ポアソン方程式とディリクレ境界条件を持つd$-次元ポアソン方程式に対して、それぞれ 7 と $(4d+1)$ hermitian, one-sparse, and self-inverse operator の和に $\sigma_x\otimes a$ を分解する。
損失関数を効率的に評価するために量子回路を明示的に設計する。
分解法と量子回路の設計は、$a_{i,i+c}=a_{c}$ for $c=0,1,\cdots,n-1$および$i=0,\cdots,n-1-c$を満たすエルミート行列とスパース係数行列を持つ線形系にも容易に拡張できる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Variational Quantum algorithm for Poisson equation [4.045204834863644]
ポアソン方程式を解くための変分量子アルゴリズム(VQA)を提案する。
VQAはノイズ中間スケール量子(NISQ)デバイス上で実行される。
数値実験により,本アルゴリズムはポアソン方程式を効果的に解くことができることを示した。
論文 参考訳（メタデータ） (2020-12-13T09:28:04Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。