論文の概要: On additive error approximations to #BQP

• arxiv url: http://arxiv.org/abs/2411.02602v1
• Date: Mon, 04 Nov 2024 20:51:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:59:34.125782
• Title: On additive error approximations to #BQP
• Title（参考訳）: BQPへの加算誤差近似について
• Authors: Mason L. Rhodes, Sam Slezak, Anirban Chowdhury, Yiğit Subaşı,
• Abstract要約: 我々は、#BQPとして知られる数え上げクラスの量子一般化に対する加法近似について研究する。 まず,#BQP問題に対する加算近似を,対応する検証回路における証人量子ビット数の誤差指数に近似する効率的な量子アルゴリズムが存在することを示す。
• 参考スコア（独自算出の注目度）: 0.34089646689382486
• License:
• Abstract: Counting complexity characterizes the difficulty of computing functions related to the number of valid certificates to efficiently verifiable decision problems. Here we study additive approximations to a quantum generalization of counting classes known as #BQP. First, we show that there exist efficient quantum algorithms that achieve additive approximations to #BQP problems to an error exponential in the number of witness qubits in the corresponding verifier circuit, and demonstrate that the level of approximation attained is, in a sense, optimal. We next give evidence that such approximations can not be efficiently achieved classically by showing that the ability to return such approximations is BQP-hard. We next look at the relationship between such additive approximations to #BQP and the complexity class DQC$_1$, showing that a restricted class of #BQP problems are DQC$_1$-complete.
• Abstract（参考訳）: 計算複雑性は、有効な証明書の数に関連する計算機能の難しさを特徴付け、効率的に決定問題の検証を行う。 ここでは、#BQPとして知られる数え上げクラスの量子一般化に対する加法近似について研究する。 まず、対応する検証回路における証人量子ビット数の誤差指数に対して、#BQP問題に対する加算近似を達成できる効率的な量子アルゴリズムがあることを示し、その近似のレベルが最適であることを示す。 次に、そのような近似を返す能力が BQP-hard であることを示すことによって、そのような近似が古典的に効率的に達成できないことを示す。 次に、そのような加法近似を#BQPと複雑性クラスDQC$_1$の関係を考察し、#BQP問題の制限クラスがDQC$_1$-completeであることを示す。

関連論文リスト

• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• Scalable Computation of Causal Bounds [11.193504036335503]
  本研究では、未観測の共創者と離散値の観測変数を持つ因果グラフ上の因果クエリの計算バウンダリの問題を考察する。 このような境界を計算するための既存の研究されていないアプローチは、線形プログラミング(LP)の定式化を使用しており、既存の解法にはすぐに難解になる。 このLPは,既存の手法に比べてはるかに大きな因果推論問題に対する境界を計算することができることを示す。
  論文  参考訳（メタデータ） (2023-08-04T21:00:46Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  一般高次量子計算におけるブール関数の問合せ複雑性について検討する。 最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。 因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
  論文  参考訳（メタデータ） (2023-07-18T13:12:55Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations [0.0]
  本稿では,量子特異値変換の枠組みにおいて,$alpha$-QPEのスケーリングが自然かつ簡潔に導出可能であることを示す。 符号関数の近似が良くなるほど、符号を正確に決定する必要があるサンプルは少なくなる。
  論文  参考訳（メタデータ） (2022-07-29T17:57:03Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Computing CQ lower-bounds over OWL 2 through approximation to RSA [12.737436528656131]
  RSA合成手法を用いて,より近い(PAGOd OWLによる)下界近似を求める新しいアルゴリズムを提案する。 本稿では,性能の大幅な向上を示す予備評価を行った。
  論文  参考訳（メタデータ） (2021-07-01T11:13:00Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• 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)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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