論文の概要: Analysis of the shortest vector problems with the quantum annealing to
search the excited states
- arxiv url: http://arxiv.org/abs/2209.03721v1
- Date: Thu, 8 Sep 2022 11:27:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 08:02:28.337152
- Title: Analysis of the shortest vector problems with the quantum annealing to
search the excited states
- Title(参考訳): 励起状態探索のための量子アニールによる最短ベクトル問題の解析
- Authors: Katsuki Ura, Takashi Imoto, Tetsuro Nikuni, Shiro Kawabata, and
Yuichiro Matsuzaki
- Abstract要約: 最短ベクトル問題(SVP)は格子問題の一つであり、格子ベースの暗号の数学的基礎である。
我々は,励起状態探索が基底状態探索よりも高い確率で解を提供することを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The shortest vector problem (SVP) is one of the lattice problems and is
mathematical basis for the lattice-based cryptography, which is expected to be
post-quantum cryptography. The SVP can be mapped onto the Ising problem, which
in principle can be solved by quantum annealing (QA). However, one issue in
solving the SVP using QA is that the solution of the SVP corresponds to the
first excited state of the problem Hamiltonian. Therefore, QA, which searches
for ground states, cannot provide a solution with high probability. In this
paper, we propose to adopt an excited-state search of the QA to solve the
shortest vector problem. We numerically show that the excited-state search
provides a solution with a higher probability than the ground-state search.
- Abstract(参考訳): 最短ベクトル問題(SVP)は格子問題の1つであり、量子後暗号として期待される格子ベースの暗号の数学的基礎である。
SVP はイジング問題に写像することができ、原理的には量子アニール (QA) によって解ける。
しかし、QAを用いてSVPを解く際の一つの問題は、SVPの解がハミルトニアン問題の第一励起状態に対応することである。
したがって、基底状態を探すqaは、高い確率で解を提供することができない。
本稿では,最短ベクトル問題を解くために,QAの励起状態探索を採用することを提案する。
我々は,励起状態探索が基底状態探索よりも高い確率で解を提供することを示す。
関連論文リスト
- Quantum algorithmic solutions to the shortest vector problem on
simulated coherent Ising machines [17.796840950659018]
量子コンピューティングは現代の暗号システムに脅威をもたらし、今後数十年にわたって予測される問題を引き起こすような状態へと進化する。
量子セキュアであるように設計された暗号システムの多くは、最短ベクトル問題と関連する問題に基づいている。
本稿では,擬似コヒーレントイジングマシン上での量子イジングモデルとして実装された最短ベクトル問題の2次非拘束二項最適化定式化を用いる。
論文 参考訳(メタデータ) (2023-04-08T17:34:10Z) - 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) - BILP-Q: Quantum Coalition Structure Generation [0.0]
我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。
実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
論文 参考訳(メタデータ) (2022-04-28T22:19:50Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Variational quantum solutions to the Shortest Vector Problem [6.126929553818864]
最短ベクトル問題(SVP)は、最短ベクトル問題(SVP)として知られる問題である。
この問題は量子コンピュータでも難しいと考えられており、量子後暗号において重要な役割を担っている。
本研究では,(効率のよい)ノイズ中間量子(NISQ)デバイスを用いてSVPを解く方法について検討する。
論文 参考訳(メタデータ) (2022-02-14T14:27:38Z) - A prescreening method for variational quantum state eigensolver [0.0]
本稿では,変分量子状態固有解法(VQSE)とサブスペース探索VQE(SSVQE)を用いて,全ての状態を高精度に導出する方法を提案する。
我々は,VQSEとSSVQEプレスクリーニング法を用いて,水素分子の状態をすべて正しく抽出できることを実証した。
論文 参考訳(メタデータ) (2021-11-03T18:13:33Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳(メタデータ) (2021-07-11T10:56:24Z) - 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) - A Query-based Quantum Eigensolver [8.136660631939154]
固定点量子探索を用いてII型固有値問題の解法を提案する。
さらに,QPE法と比較して,クエリベースの手法は,タイプIIの問題を解く際の2次高速化を実現する。
論文 参考訳(メタデータ) (2020-08-03T00:29:19Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。