論文の概要: Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria

• arxiv url: http://arxiv.org/abs/2206.06594v1
• Date: Tue, 14 Jun 2022 05:06:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-15 15:02:32.526259
• Title: Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria
• Title（参考訳）: 平衡の連続体を持つ大人口プロトコルで実数を計算する
• Authors: Xiang Huang and Rachel N. Huls
• Abstract要約: Bournez氏、Fraigniaud氏、Koegler氏は[0,1]の数値を、Large-Population Protocol(LPP)モデルで計算可能であると定義した。 この概念は LPP に付随する通常の微分方程式(ODE)を有限個の平衡しか持たないものに制限する。 一般汎用アナログコンピュータ(GPAC)や化学反応ネットワーク(CRN)で計算可能な[0,1]の全ての数値もLPPで計算可能であることを示す。
• 参考スコア（独自算出の注目度）: 1.2851416353405603
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bournez, Fraigniaud, and Koegler defined a number in [0,1] as computable by their Large-Population Protocol (LPP) model, if the proportion of agents in a set of marked states converges to said number over time as the population grows to infinity. The notion, however, restricts the ordinary differential equations (ODEs) associated with an LPP to have only finitely many equilibria. This restriction places an intrinsic limitation on the model. As a result, a number is computable by an LPP if and only if it is algebraic, namely, not a single transcendental number can be computed under this notion. In this paper, we lift the finitary requirement on equilibria. That is, we consider systems with a continuum of equilibria. We show that essentially all numbers in [0,1] that are computable by bounded general-purpose analog computers (GPACs) or chemical reaction networks (CRNs) can also be computed by LPPs under this new definition. This implies a rich series of numbers (e.g., the reciprocal of Euler's constant, $\pi/4$, Euler's $\gamma$, Catalan's constant, and Dottie number) are all computable by LPPs. Our proof is constructive: We develop an algorithm that transfers bounded GPACs/CRNs into LPPs. Our algorithm also fixes a gap in Bournez et al.'s construction of LPPs designed to compute any arbitrary algebraic number in [0,1].
• Abstract（参考訳）: Bournez, Fraigniaud, Koegler は、[0,1] の数値を、[0,1] の大規模最適化プロトコル(LPP)モデルで計算可能であると定義した。 しかし、この概念は LPP に付随する通常の微分方程式(ODE)を有限個の平衡しか持たないものに制限する。 この制限はモデルに固有の制限を与える。 結果として、ある数が LPP によって計算可能であることと、それが代数的であること、すなわち1つの超越数がこの概念の下で計算できないことのみである。 本稿では,平衡条件の引き上げについて述べる。 すなわち、平衡の連続体を持つ系を考える。 有界汎用アナログコンピュータ (gpacs) や化学反応ネットワーク (crns) によって計算可能な [0,1] の全ての数値は、この新しい定義の下で lpps によって計算できることを示した。 これは、豊富な数列(例えば、オイラー定数の逆数、$\pi/4$、オイラーの$\gamma$、カタルーニャ定数、ドッティ数)が全てLPPによって計算可能であることを意味する。 我々は有界gpacs/crnsをlppに転送するアルゴリズムを開発した。 我々のアルゴリズムは、[0,1] における任意の代数的数を計算するために設計された LPP の構成においてギャップを埋める。

関連論文リスト

• Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms [0.0]
  2023年、レジチェフはショアのアルゴリズムの多次元バージョンを提案し、より少ない量子ゲートを必要とした。 解析的数論の道具を用いて、この予想のバージョンを証明する。 その結果、この改良された量子アルゴリズムの正確性の無条件証明が得られる。
  論文  参考訳（メタデータ） (2024-04-25T09:30:19Z)
• 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)
• An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis [1.2246649738388387]
  単純複素数のベッチ数を計算するための新しい量子アルゴリズムを提案する。 我々のアルゴリズムは、複素数が最大数の単純数に近い場合に最もよく機能する。
  論文  参考訳（メタデータ） (2023-07-13T21:46:45Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform [0.0]
  量子シュア変換を実装するための透過的アルゴリズムを提案する。 クレーブシュ=ゴルダン係数を介して結合された量子ビットからなるシュル状態について検討する。 Wigner 6-j 記号と SU(N) Clebsch-Gordan 係数が我々の枠組みに自然に適合していることが示されている。
  論文  参考訳（メタデータ） (2023-05-06T15:19:52Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  ディジタル量子コンピュータ上で状態の密度を推定する量子アルゴリズムを実装した。 我々は,量子H1-1トラップイオンチップ上での非可積分ハミルトニアン状態の密度を18ビットの制御レジスタに対して推定する。
  論文  参考訳（メタデータ） (2023-03-23T17:46:28Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
  論文  参考訳（メタデータ） (2023-03-03T16:53:30Z)
• Quantum computing with anyons: an $F$-matrix and braid calculator [0.0]
  我々は,SageMathの一部として利用可能なペンタゴン方程式解法を導入し,それを用いて任意のシステムに関連付けられたブレイド群表現を構築する。 我々は,複数の公理を満たすデータの集合とともに,ラベルの集合として抽象的に提示する。 RFCの言語では、マルチプライシティフリーな融合環に対応する任意のシステムに対して$F$-matriceを生成できる。
  論文  参考訳（メタデータ） (2022-12-01T19:31:17Z)
• The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for Two-Dimensional Systems [62.997667081978825]
  開量子系は、FGKLS(Franke-Gorini-Kossakowski-Lindblad-Sudarshan)方程式に従うことができる。 我々はヒルベルト空間次元が 2$ である場合を徹底的に研究する。
  論文  参考訳（メタデータ） (2022-04-16T07:03:54Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)
• PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations [77.34726150561087]
  本稿では,量子演算のコヒーレント制御を含む量子計算を表現・推論するためにPBS計算を導入する。 我々はこの言語に方程式理論を加え、それが健全で完備であることが証明された。 我々は、制御された置換の実装やループのアンロールのようなアプリケーションを考える。
  論文  参考訳（メタデータ） (2020-02-21T16:15:58Z)

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

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