Fugu-MT 論文翻訳(概要): How to compute the volume in low dimension?

論文の概要: How to compute the volume in low dimension?

arxiv url: http://arxiv.org/abs/2503.02207v1
Date: Tue, 04 Mar 2025 02:38:51 GMT
ステータス: 翻訳完了
システム内更新日: 2025-03-05 19:14:42.514042
Title: How to compute the volume in low dimension?
Title（参考訳）: 低次元の体積を計算するには?
Authors: Arjan Cornelissen, Simon Apers, Sander Gribling,
Abstract要約: 凸体の体積を推定することは理論計算機科学における標準的な問題である。我々は、この問題の決定論的、ランダム化、および量子的クエリの複雑さを、高精度な極限で厳しく特徴づける。
参考スコア（独自算出の注目度）: 1.9686770963118383
License:
Abstract: Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.
Abstract（参考訳）: 凸体の体積を推定することは理論計算機科学における標準的な問題である。その研究はランダム化アルゴリズム、マルコフ連鎖理論、計算幾何学に大きな進歩をもたらした。特に、ボリューム推定のクエリの複雑さをメンバーシップオラクルに決定することは、長い間公然とされてきた問題である。以前の研究のほとんどは高次元の極限に焦点を当てていた。本研究では,この問題における決定論的,ランダム化,および量子クエリの複雑性を,次元が一定である場合の高精度な限界において強く特徴づける。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文参考訳（メタデータ） (2023-12-18T18:29:01Z)
Dense outputs from quantum simulations [5.295277584890625]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。この問題は量子制御や分光計算などの応用で頻繁に発生する。我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文参考訳（メタデータ） (2023-07-26T18:16:51Z)
Geometrical causality: casting Feynman integrals into quantum algorithms [0.0]
本稿では,ループ・トレー・デュナリティに基づく効率的な戦略,その明確な因果表現,および基礎となる幾何学的解釈について論じる。具体的には、幾何学的因果選択規則を利用して、基底状態が因果表現に寄与する項に直接関連しているハミルトニアンを定義する。このようにして、問題は最小化に変換され、量子コンピュータに実装され、潜在的なスピードアップを探すことができる。
論文参考訳（メタデータ） (2023-05-15T11:22:51Z)
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)
An entanglement perspective on the quantum approximate optimization algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文参考訳（メタデータ） (2022-06-14T17:37:44Z)
QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文参考訳（メタデータ） (2022-05-24T03:49:10Z)
Variational quantum solutions to the Shortest Vector Problem [6.126929553818864]
最短ベクトル問題(SVP)は、最短ベクトル問題(SVP)として知られる問題である。この問題は量子コンピュータでも難しいと考えられており、量子後暗号において重要な役割を担っている。本研究では,(効率のよい)ノイズ中間量子(NISQ)デバイスを用いてSVPを解く方法について検討する。
論文参考訳（メタデータ） (2022-02-14T14:27:38Z)
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)
HighDist Framework: Algorithms and Applications [0.5584060970507505]
量子回路の出力分布のモードが与えられた閾値よりも大きいかどうかを判定する問題を導入する。空間複雑性が分布領域の大きさの対数的であるこれらの問題の有望バージョンに対する量子アルゴリズムを設計する。
論文参考訳（メタデータ） (2021-03-16T13:06:36Z)

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