論文の概要: Quantum Approximate Counting with Additive Error: Hardness and Optimality

• arxiv url: http://arxiv.org/abs/2411.02602v2
• Date: Thu, 13 Mar 2025 21:27:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-17 13:03:45.108568
• Title: Quantum Approximate Counting with Additive Error: Hardness and Optimality
• Title（参考訳）: 加算誤差を伴う量子近似数:硬さと最適性
• Authors: Mason L. Rhodes, Sam Slezak, Anirban Chowdhury, Yiğit Subaşı,
• Abstract要約: 量子カウント(Quantum counting)は、量子検証回路で受け入れられる状態の部分空間の次元を決定するタスクである。 量子数え上げ問題のクラス#BQPを正確にあるいは適切な近似内で解く複雑さは、多体物理量を計算することの難しさに関係している。
• 参考スコア（独自算出の注目度）: 0.34089646689382486
• License:
• Abstract: Quantum counting is the task of determining the dimension of the subspace of states that are accepted by a quantum verifier circuit. It is the quantum analog of counting the number of valid solutions to NP problems -- a problem well-studied in theoretical computer science with far-reaching implications in computational complexity. The complexity of solving the class #BQP of quantum counting problems, either exactly or within suitable approximations, is related to the hardness of computing many-body physics quantities arising in algebraic combinatorics. Here, we address the complexity of quantum approximate counting under additive error. First, we show that computing additive approximations to #BQP problems to within an error exponential in the number of witness qubits in the corresponding verifier circuit is as powerful as polynomial-time quantum computation. Next, we show that returning an estimate within error that is any smaller is #BQP-hard. Finally, we show that additive approximations to a restricted class of #BQP problems are equivalent in computational hardness to the class DQC1. Our work parallels results on additively approximating #P and GapP functions.
• Abstract（参考訳）: 量子カウント(Quantum counting)は、量子検証回路で受け入れられる状態の部分空間の次元を決定するタスクである。 NP問題に対する有効な解の数を数える量子アナログであり、計算複雑性に大きく影響する理論計算機科学においてよく研究されている。 量子数え上げ問題のクラス#BQPを正確にあるいは適切な近似内で解く複雑さは、代数的コンビネータで生じる多体物理量の計算の難しさに関連している。 ここでは、加算誤差の下での量子近似カウントの複雑さに対処する。 まず,#BQP問題に対する加法近似を,対応する検証回路における証人量子ビット数における誤差指数の範囲内で計算することは,多項式時間量子計算と同じくらい強力であることを示す。 次に,より小さい誤差で推定値を返すのが#BQP-hardであることを示す。 最後に、制限された#BQP問題のクラスに対する加法近似が、クラスDQC1の計算硬度に等しいことを示す。 我々の研究は、#P と GapP の関数を加法的に近似した結果と平行である。

関連論文リスト

• Exponential Separation Criteria for Quantum Iterative Power Algorithms [0.0]
  その結果,QIPAとvarQITEの指数的分離は実現不可能であることが判明した。 理論的な結果にもかかわらず、実際に関係のある拡張がまだ可能であることも示している。
  論文  参考訳（メタデータ） (2025-02-08T09:53:10Z)
• 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)
• 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)

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

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