Fugu-MT 論文翻訳(概要): Topologically protected Grover's oracle for the partition problem

論文の概要: Topologically protected Grover's oracle for the partition problem

arxiv url: http://arxiv.org/abs/2304.10488v2
Date: Wed, 9 Aug 2023 17:41:01 GMT
ステータス: 処理完了
システム内更新日: 2023-08-10 17:39:15.951055
Title: Topologically protected Grover's oracle for the partition problem
Title（参考訳）: 分割問題に対するグローバーのオラクルの位相的保護
Authors: Nikolai A. Sinitsyn and Bin Yan
Abstract要約: NPP(Number Partitioning Problem)はNP完全計算問題の1つである。ここでは、この問題の高速解への道を、$sqrtN$ quasi-adiabatic quantum annealing stepsで説明する。
参考スコア（独自算出の注目度）: 3.800391908440439
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The Number Partitioning Problem (NPP) is one of the NP-complete computational problems. Its definite exact solution generally requires a check of all $N$ solution candidates, which is exponentially large. Here we describe a path to the fast solution of this problem in $\sqrt{N}$ quasi-adiabatic quantum annealing steps. We argue that the errors due to the finite duration of the quantum annealing can be suppressed if the annealing time scales with $N$ only logarithmically. Moreover, our adiabatic oracle is topologically protected, in the sense that it is robust against small uncertainty and slow time-dependence of the physical parameters or the choice of the annealing protocol.
Abstract（参考訳）: NPP(Number Partitioning Problem)はNP完全計算問題の1つである。その明確な厳密解は一般に指数関数的に大きいn$ソリューション候補のチェックを必要とする。ここでは、この問題の高速解への経路を$\sqrt{n}$ pseudo-adiabatic quantum annealing step で記述する。量子アニーリングの有限持続時間による誤差は、アニーリング時間が対数的に$N$のみでスケールした場合に抑制できると主張する。さらに,我々の断熱オラクルは,物理パラメータの小さな不確実性と遅い時間依存性やアニーリングプロトコルの選択に対して頑健であるという意味で,トポロジカルに保護されている。

関連論文リスト

A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文参考訳（メタデータ） (2024-09-07T06:37:23Z)
Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
論文参考訳（メタデータ） (2024-06-06T11:33:29Z)
Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文参考訳（メタデータ） (2023-06-02T17:49:35Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文参考訳（メタデータ） (2022-05-16T15:47:41Z)
A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文参考訳（メタデータ） (2022-01-31T22:19:49Z)
Quantum Logarithmic Space and Post-selection [0.4588028371034406]
ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
論文参考訳（メタデータ） (2021-05-06T14:02:01Z)
Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
論文参考訳（メタデータ） (2020-09-11T17:31:39Z)
Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文参考訳（メタデータ） (2020-06-18T17:18:02Z)
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文参考訳（メタデータ） (2020-04-25T05:45:59Z)
Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文参考訳（メタデータ） (2020-03-11T23:23:29Z)

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