論文の概要: 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-28 17:07:44.373302
• 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: http://creativecommons.org/licenses/by/4.0/
• 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であることを示す。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Towards Quantum Computational Mechanics [1.530480694206666]
  本稿では、量子コンピューティングを用いて、計算ホモジェナイゼーションにおける代表要素体積(RVE)問題を解く方法について述べる。 我々の量子RVE解法は古典解法に対して指数加速度を得る。
  論文  参考訳（メタデータ） (2023-12-06T12:53:02Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• Quantum benefit of the quantum equation of motion for the strongly coupled many-body problem [0.0]
  量子運動方程式 (quantum equation of motion, QEOM) はフェルミオン多体系の励起特性を計算するためのハイブリッド量子古典アルゴリズムである。 我々は、qEOMが要求される量子測定数の独立性により量子的利益を示すことを明らかに示している。
  論文  参考訳（メタデータ） (2023-09-18T22:10:26Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• 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)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。 本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
  論文  参考訳（メタデータ） (2021-11-19T12:35:26Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• 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)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)

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

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