論文の概要: 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$のノイズ量子ビットで対処できることを見出した。
関連論文リスト
- Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method [0.0]
本稿では,最短ベクトル問題を解くために,代替符号化と代替量子アルゴリズムを提案する。
本研究では,量子コンピューティングフレームワークにおけるSVPの適用可能性について検討した。
論文 参考訳（メタデータ） (2024-08-28T18:01:22Z) - A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。
我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。
我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
論文 参考訳（メタデータ） (2024-08-15T05:11:35Z) - DanceQ: High-performance library for number conserving bases [0.0]
粒子数保存の問題に現れる$U(1)$対称性に対するエレガントで強力な多次元的アプローチを提案する。
分割並列アルゴリズムは複数のサブシステムを用いており、従って従来の手法を一般化してスケーラブルにする。
提案アルゴリズムの理論的プレゼンテーションに加えて, 与えられた粒子数セクタの任意の基底状態を操作, 列挙, マップ化するための, フレキシブルでモダンなヘッダのみのC++20実装であるDanceQを提供する。
論文 参考訳（メタデータ） (2024-07-19T18:00:01Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳（メタデータ） (2023-10-11T18:00:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。