論文の概要: Quantum Algorithms for Weighted Constrained Sampling and Weighted Model Counting
- arxiv url: http://arxiv.org/abs/2407.12816v1
- Date: Sat, 29 Jun 2024 09:44:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-22 08:47:38.347188
- Title: Quantum Algorithms for Weighted Constrained Sampling and Weighted Model Counting
- Title（参考訳）: 重み付き制約サンプリングおよび重み付きモデルカウントのための量子アルゴリズム
- Authors: Fabrizio Riguzzi,
- Abstract要約: 重み付き制約サンプリングと重み付きモデルカウントを行う量子アルゴリズムであるQWCSとQWMCを提案する。
どちらも重みを考慮に入れた量子探索/量子モデルカウントアルゴリズムに基づいている。
- 参考スコア（独自算出の注目度）: 0.21756081703276
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problems of weighted constrained sampling and weighted model counting, where we are given a propositional formula and a weight for each world. The first problem consists of sampling worlds with a probability proportional to their weight given that the formula is satisfied. The latter is the problem of computing the sum of the weights of the models of the formula. Both have applications in many fields such as probabilistic reasoning, graphical models, statistical physics, statistics and hardware verification. In this article, we propose QWCS and QWMC, quantum algorithms for performing weighted constrained sampling and weighted model counting, respectively. Both are based on the quantum search/quantum model counting algorithms that are modified to take into account the weights. In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWCS requires $O(2^{\frac{n}{2}}+1/\sqrt{\text{WMC}})$ oracle calls, where where $n$ is the number of Boolean variables and $\text{WMC}$ is the normalized between 0 and 1 weighted model count of the formula, while a classical algorithm has a complexity of $\Omega(1/\text{WMC})$. QWMC takes $\Theta(2^{\frac{n}{2}})$ oracle calss, while classically the best complexity is $\Theta(2^n)$, thus achieving a quadratic speedup.
- Abstract（参考訳）: 重み付き制約サンプリングと重み付きモデルカウントの問題を考察し、各世界に命題式と重みを与える。
第1の問題は、式が満たされていると仮定して、その重量に比例する確率でサンプリングされた世界から成り立っている。
後者は公式のモデルの重みの和を計算する問題である。
どちらも確率論的推論、グラフィカルモデル、統計物理学、統計学、ハードウェア検証など多くの分野で応用されている。
本稿では,重み付き制約サンプリングと重み付きモデルカウントを行う量子アルゴリズムであるQWCSとQWMCを提案する。
どちらも重みを考慮に入れた量子探索/量子モデルカウントアルゴリズムに基づいている。
ここで$n$はブール変数の数で$\text{WMC}$は0から1の重み付けされたモデルの数で正規化され、古典的なアルゴリズムは$\Omega(1/\text{WMC})$である。
QWMCは$\Theta(2^{\frac{n}{2}})$ Oracle calssを取るが、古典的には$\Theta(2^n)$である。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。
まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。
近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2024-01-08T14:59:48Z) - End-to-end complexity for simulating the Schwinger model on quantum computers [0.6449786007855248]
シュウィンガーモデルハミルトニアンのブロック符号化の効率的な実装を提案する。
エンド・ツー・エンドのアプリケーションとして、真空永続振幅を計算する。
本研究は,FTQC時代の量子コンピュータの性能予測に関する知見を提供する。
論文 参考訳（メタデータ） (2023-11-29T06:36:11Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Lifted Algorithms for Symmetric Weighted First-Order Model Sampling [7.007419073974192]
数量化器を用いた一階述語論理の2変数フラグメントのサンプリングにおけるドメインリフト性を証明する。
そして、この結果は、基数制約の存在下においても引き続き持続することを示す。
我々のアルゴリズムは、最先端のWMSサンプリングよりもかなりのマージンで優れています。
論文 参考訳（メタデータ） (2023-08-17T07:40:47Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration [0.0]
MCMCの量子アルゴリズムが提案され、古典的なスペクトルギャップに対して$Delta$の2次スピードアップが得られる。
我々は状態生成だけでなく、ベイズ推定における共通課題であるパラメータの信頼区間も見いだすと考えている。
提案した信頼区間計算法では、$Delta$で$ell$スケールを計算するための量子回路へのクエリ数、$epsilon$で必要な精度$epsilon$、および標準偏差$sigma$$$ $ell$ as $tildeO(sigma/epsilonを演算する。
論文 参考訳（メタデータ） (2023-03-10T01:05:16Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - Exact quantum query complexity of computing Hamming weight modulo powers
of two and three [2.1349209400003932]
この問題の正確な量子クエリ複雑性は、$leftlceil n (1 − 1/m) rightil$であることを示す。
上界は、主成分がよく知られた1-クエリ量子アルゴリズムである反復クエリアルゴリズムによって構成される。
論文 参考訳（メタデータ） (2021-12-29T17:57:41Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。