論文の概要: An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems

• arxiv url: http://arxiv.org/abs/2505.08386v1
• Date: Tue, 13 May 2025 09:32:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-14 20:57:54.506496
• Title: An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems
• Title（参考訳）: 最も短いベクトル問題を解くための効率的な変分量子Korkin-Zolotarevアルゴリズム
• Authors: Xiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, Bingjie Xu,
• Abstract要約: 最短ベクトル問題(SVP)を解決するための量子ビット要求を著しく低減する変分量子Korkin-Zolotarev(VQKZ)アルゴリズムを提案する。 提案したVQKZアルゴリズムは、元のSVPを投影された部分格子上の一連のサブプロブレムに変換することにより、格子次元61.39%のSVPインスタンスを、従来の方法で解けるものよりも解決することができる。
• 参考スコア（独自算出の注目度）: 7.839882853089659
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Noisy intermediate-scale quantum cryptanalysis focuses on the capability of near-term quantum devices to solve the mathematical problems underlying cryptography, and serves as a cornerstone for the design of post-quantum cryptographic algorithms. For the shortest vector problem (SVP), which is one of the computationally hard problems in lattice-based cryptography, existing near-term quantum cryptanalysis algorithms map the problem onto a fully-connected quantum Ising Hamiltonian, and obtain the solution by optimizing for the first excited state. However, as the quantum system scales with the problem size, determining the first excited state becomes intractable due to the exponentially increased complexity for large-scale SVP instances. In this paper, we propose a variational quantum Korkin-Zolotarev (VQKZ) algorithm, which significantly reduces the qubit requirement for solving the SVP. Specifically, by transforming the original SVP into a series of subproblems on projected sublattices, the proposed VQKZ algorithm enables near-term quantum devices to solve SVP instances with lattice dimensions 61.39% larger than those solvable by previous methods. Furthermore, numerical simulations demonstrate that the proposed VQKZ algorithm can significantly outperform existing methods in terms of the length of solution vectors.
• Abstract（参考訳）: ノイズの多い中間規模量子暗号解析は、暗号の基礎となる数学的問題を解くために、短期量子デバイスの能力に焦点を当て、量子後暗号アルゴリズムの設計の基礎となる。 格子ベースの暗号において計算的に難しい問題の1つである最短ベクトル問題(SVP)に対して、既存の短期量子暗号解析アルゴリズムは、問題を完全連結量子Ising Hamiltonianにマッピングし、最初の励起状態に最適化することで解を得る。 しかし、量子系が問題の大きさでスケールするにつれて、大規模SVPインスタンスの指数関数的に複雑化するため、最初の励起状態を決定することは困難になる。 本稿では,変分量子Korkin-Zolotarev(VQKZ)アルゴリズムを提案する。 具体的には、元のSVPを投影された部分格子上の一連のサブプロブレムに変換することで、提案されたVQKZアルゴリズムは、格子次元のSVPインスタンスを従来の方法で解けるものよりも61.39%大きい確率で解くことができる。 さらに, 数値シミュレーションにより, 提案手法は解ベクトルの長さで既存手法を著しく上回り得ることを示した。

関連論文リスト

• Quantum Computing for Optimizing Aircraft Loading [1.055551340663609]
  航空機の負荷最適化問題は、最もよく知られた古典的アルゴリズムが対象数と指数関数的にスケールするのに対して、計算的に難しい問題である。 本稿では,QAOAアルゴリズムのマルチ角変種(MAL-VQA)に基づく量子アプローチを提案する。 航空機の負荷問題に対して,IonQ QPUをAriaとForteで実行することで,アルゴリズムの性能を示す。
  論文  参考訳（メタデータ） (2025-04-02T10:10:11Z)
• Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup [4.913177281640608]
  グラムシュミット過程はベクトル集合正規化と行列QR分解を解くために広く用いられている。 既存の方法には、システム次元の$N$で$O(N3)$をスケーリングする、高い複雑性の問題がある。 本稿では,グラマーシュミット過程と量子位相推定のアイデアに基づいて,これらの2つの問題を解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-12-26T07:04:34Z)
• Quantum Algorithm for Shortest Vector Problems with Folded Spectrum Method [0.0]
  本稿では,最短ベクトル問題を解くために,代替符号化と代替量子アルゴリズムを提案する。 本研究では,量子コンピューティングフレームワークにおけるSVPの適用可能性について検討した。
  論文  参考訳（メタデータ） (2024-08-28T18:01:22Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。 シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
  論文  参考訳（メタデータ） (2022-03-04T19:00:45Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。 問題の難易度は解の縮退と局所ミニマの数によって制御される。 最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
  論文  参考訳（メタデータ） (2022-02-18T19:00:01Z)

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

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