論文の概要: Variational quantum solutions to the Shortest Vector Problem
- arxiv url: http://arxiv.org/abs/2202.06757v5
- Date: Thu, 23 Feb 2023 13:56:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 21:07:38.618806
- Title: Variational quantum solutions to the Shortest Vector Problem
- Title(参考訳): 最短ベクトル問題に対する変分量子解
- Authors: Martin R. Albrecht, Milo\v{s} Prokop, Yixin Shen, Petros Wallden
- Abstract要約: 最短ベクトル問題(SVP)は、最短ベクトル問題(SVP)として知られる問題である。
この問題は量子コンピュータでも難しいと考えられており、量子後暗号において重要な役割を担っている。
本研究では,(効率のよい)ノイズ中間量子(NISQ)デバイスを用いてSVPを解く方法について検討する。
- 参考スコア(独自算出の注目度): 6.126929553818864
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: A fundamental computational problem is to find a shortest non-zero vector in
Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This
problem is believed to be hard even on quantum computers and thus plays a
pivotal role in post-quantum cryptography. In this work we explore how
(efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to
solve SVP. Specifically, we map the problem to that of finding the ground state
of a suitable Hamiltonian. In particular, (i) we establish new bounds for
lattice enumeration, this allows us to obtain new bounds (resp.~estimates) for
the number of qubits required per dimension for any lattices (resp.~random
q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the
optimization space by proposing (a) a different classical optimisation loop or
alternatively (b) a new mapping to the Hamiltonian. These improvements allow us
to solve SVP in dimension up to 28 in a quantum emulation, significantly more
than what was previously achieved, even for special cases. Finally, we
extrapolate the size of NISQ devices that is required to be able to solve
instances of lattices that are hard even for the best classical algorithms and
find that with approximately $10^3$ noisy qubits such instances can be tackled.
- Abstract(参考訳): 基本的な計算問題は、最短ベクトル問題(SVP)として知られるユークリッド格子における最短ゼロベクトルを見つけることである。
この問題は量子コンピュータでも難しいと考えられており、量子後暗号において重要な役割を果たす。
本研究では,(効率のよい)ノイズ中間量子(NISQ)デバイスを用いてSVPを解く方法について検討する。
具体的には、その問題を適切なハミルトニアンの基底状態を見つける問題にマップする。
特に
i) 格子列挙のための新しい境界を確立することにより、SVPを解くために任意の格子(resp.~random q-ary lattice)の次元当たりの量子ビット数に対する新しい境界(resp.~estimates)を得ることができる。
(ii)提案により最適化空間からゼロベクトルを除外する
a) 異なる古典的最適化ループ、または、代わりに
(b)ハミルトニアンへの新しい写像。
これらの改良により、量子エミュレーションにおいて最大28次元のSVPを解くことができる。
最後に、最も優れた古典的アルゴリズムであっても難しい格子のインスタンスを解くために必要なNISQデバイスのサイズを例示し、そのようなインスタンスに約10^3$のノイズ量子ビットで対処できることを見出した。
関連論文リスト
- Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers [0.38366697175402226]
格子内の最短ベクトルを見つけることは、古典コンピュータと量子コンピュータの両方にとって困難であると考えられている問題である。
SVPのための最も優れた古典的、量子的、あるいはハイブリッドな古典量子アルゴリズムを見つけるためには、十分なセキュリティレベルを提供する暗号系パラメータを選択する必要がある。
グロバーの探索量子アルゴリズムは、一般的な二次的なスピードアップを提供する。
我々はGroverの小さなSVPインスタンスの量子探索と最先端の古典的解法を組み合わせる方法について分析する。
論文 参考訳(メタデータ) (2024-02-21T16:05:49Z) - Quantum Computing and Tensor Networks for Laminate Design: A Novel
Approach to Stacking Sequence Retrieval [1.7400502482492273]
この研究は主に量子計算に焦点をあて、テンソルネットワークアルゴリズムの適用により、シークエンス検索のための新しい量子インスパイアされたアプローチが提示される。
量子状態空間内の線形作用素、ハミルトニアンを導出し、積み重ねシーケンス検索問題に固有の損失関数をカプセル化する。
実演では、従来のテンソルネットワークアルゴリズムであるDMRGアルゴリズムを選択し、我々のアプローチを数値的に検証した。
論文 参考訳(メタデータ) (2024-02-09T15:01:56Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳(メタデータ) (2023-10-11T18:00:53Z) - Hamiltonian variational ansatz without barren plateaus [0.0]
変分量子アルゴリズムは、短期量子コンピュータの最も有望な応用の1つである。
その大きな可能性にもかかわらず、数十量子ビットを超える変分量子アルゴリズムの有用性は疑問視されている。
論文 参考訳(メタデータ) (2023-02-16T19:01:26Z) - Towards Neural Variational Monte Carlo That Scales Linearly with System
Size [67.09349921751341]
量子多体問題(Quantum many-body problem)は、例えば高温超伝導体のようなエキゾチックな量子現象をデミストする中心である。
量子状態を表すニューラルネットワーク(NN)と変分モンテカルロ(VMC)アルゴリズムの組み合わせは、そのような問題を解決する上で有望な方法であることが示されている。
ベクトル量子化技術を用いて,VMCアルゴリズムの局所エネルギー計算における冗長性を利用するNNアーキテクチャVector-Quantized Neural Quantum States (VQ-NQS)を提案する。
論文 参考訳(メタデータ) (2022-12-21T19:00:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。