論文の概要: Counting with the quantum alternating operator ansatz

• arxiv url: http://arxiv.org/abs/2503.07720v1
• Date: Mon, 10 Mar 2025 18:00:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:38:53.395211
• Title: Counting with the quantum alternating operator ansatz
• Title（参考訳）: 量子交互作用素 ansatz の数え方
• Authors: Julien Drapeau, Shreya Banerjee, Stefanos Kourtis,
• Abstract要約: 本稿では,量子交互演算子 Ansatz (QAOA) に基づく変分アルゴリズムを導入する。 我々のアルゴリズムはVQCountと呼ばれ、ランダムサンプリングと近似カウントの等価性に基づいており、QAOAを解サンプリングとして利用する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We introduce a variational algorithm based on the quantum alternating operator ansatz (QAOA) for the approximate solution of computationally hard counting problems. Our algorithm, dubbed VQCount, is based on the equivalence between random sampling and approximate counting and employs QAOA as a solution sampler. We first prove that VQCount improves upon previous work by reducing exponentially the number of samples needed to obtain an approximation within a multiplicative factor of the exact count. Using tensor network simulations, we then study the typical performance of VQCount with shallow circuits on synthetic instances of two #P-hard problems, positive #NAE3SAT and positive #1-in-3SAT. We employ the original quantum approximate optimization algorithm version of QAOA, as well as the Grover-mixer variant which guarantees a uniform solution probability distribution. We observe a tradeoff between QAOA success probability and sampling uniformity, which we exploit to achieve an exponential gain in efficiency over naive rejection sampling. Our results highlight the potential and limitations of variational algorithms for approximate counting.
• Abstract（参考訳）: 本稿では,量子交互演算子 Ansatz (QAOA) に基づく変分アルゴリズムを導入する。 我々のアルゴリズムはVQCountと呼ばれ、ランダムサンプリングと近似カウントの等価性に基づいており、QAOAを解サンプリングとして利用する。 まず、VQCountは、正確な数の乗算係数内で近似を得るために必要となるサンプル数を指数関数的に減らし、従来の作業を改善することを証明した。 次に、テンソルネットワークシミュレーションを用いて、2つの#Pハード問題、正の#NAE3SAT、正の#1-in-3SATの合成インスタンスに対して、浅い回路を持つVQCountの典型的な性能について検討する。 我々はQAOAの元の量子近似最適化アルゴリズムバージョンと、一様解の確率分布を保証するGrover-mixer変種を用いる。 我々は,QAOA成功確率とサンプリング均一性のトレードオフを観察し,本手法を有効性向上に活用する。 本結果は,近似カウントのための変分アルゴリズムの可能性と限界を浮き彫りにした。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
  QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための量子アルゴリズムの一分野である。 特定の変種であるGrover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA)は、等価な目的値を共有する状態間で均一な振幅を保証する。 GM-QAOAはサンプリング確率を2次的に向上させ,一貫した性能を維持するために,問題サイズと指数関数的にスケールする回路深度を必要とすることを示す。
  論文  参考訳（メタデータ） (2024-05-06T05:47:27Z)
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models [0.0]
  パリティマッピングは、量子近似最適化アルゴリズム(QAOA)の幾何学的に局所的な符号化を提供する パリティ符号化されたQAOA層が一定個ある場合、その性能や出力エネルギーはゼロになる。 その結果,パリティエンコードされたQAOAは,QAOAの標準バージョンと比較して,有望なスケーリングを行なわないことが示唆された。
  論文  参考訳（メタデータ） (2023-11-03T18:00:00Z)
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
  マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。 我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
  論文  参考訳（メタデータ） (2023-10-01T03:57:13Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。 サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。 格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
  論文  参考訳（メタデータ） (2022-12-12T15:06:32Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime [0.0]
  量子サンプリング回帰(QSR)は、代替の量子古典的アルゴリズムである。 低量子ビット数構造における時間的複雑さに基づいて,その利用事例を分析した。 ベンチマーク問題に対するアルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2020-12-04T00:01:15Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。 QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
  論文  参考訳（メタデータ） (2020-06-08T18:00:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。