論文の概要: Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

• arxiv url: http://arxiv.org/abs/2502.05284v1
• Date: Fri, 07 Feb 2025 19:42:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:31:22.085264
• Title: Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Title（参考訳）: NISQ最短ベクトルプロブレム解のヒューリスティック時間複雑性
• Authors: Miloš Prokop, Petros Wallden,
• Abstract要約: 最短ベクトル問題は古典コンピュータや量子コンピュータでは難しいと考えられている。 我々は、ハミルトン多様体の基底状態において、SVPを効率的に符号化することは可能であることを示す。 より論理的な量子ビットを導入することなく、SVPに対するゼロベクトル解を避ける新しい方法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Shortest Vector Problem is believed to be hard both for classical and quantum computers. Two of the three NIST post-quantum cryptosystems standardised by NIST rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve SVP is crucial to establish confidence in them. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on NISQ devices have in solving SVP has been an active research area. The qubit-requirement for doing so has been analysed and it was demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian efficiently. Due to the heuristic nature of VQAs no analysis of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. Motivated by Boulebnane and Montanaro work on the k-SAT problem, we propose to use angle pretraining of the QAOA for SVP and we demonstrate that it performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and observe the probability of success scaling as $2^{-0.695n}$ with n being dimensionality of the search space for a depth $p=3$ pre-trained QAOA. We observe time complexity $O(2^{0.695n})$, a bit worse than the fault-tolerant Grover approach of $O(2^{0.5n})$. However, both the number of qubits, and the depth of each quantum computation, are considerably better-Grover requires exponential depth, while each run of constant p fixed-angles QAOA requires polynomial depth. We also propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.
• Abstract（参考訳）: 最短ベクトル問題は古典コンピュータでも量子コンピュータでも難しいと考えられている。 NISTによって標準化された3つのNISTポスト量子暗号システムのうちの2つは、その硬さに依存している。 SVPを解くための量子アルゴリズムの理論的および実践的な性能に関する研究は、それらの信頼性を確立するために不可欠である。 NISQデバイス上で動作可能な変分量子アルゴリズム(VQA)のSVP解決能力の探索は,現在,活発な研究領域となっている。 そのためのqubit-requirementは解析され、ハミルトンの基底状態においてSVPを効率的に符号化することが証明された。 VQAsのヒューリスティックな性質のため、興味のない古典的にシミュラブルなサイズを超えるスケールに対するこれらのアプローチの時間的複雑さの分析は行われていない。 ブールブネとモンタナロがk-SAT問題に取り組むことを動機として、我々はQAOAの角度事前学習をSVPに導入することを提案し、トレーニングで使用するものよりもはるかに大きなインスタンスでうまく動作することを示した。 オプティマイザの使用によって生じる制限を避けるため、観測された性能を外挿し、n が深度$p=3$の事前学習 QAOA に対して探索空間の次元性であるような 2^{-0.695n$ のスケーリングの確率を観測することができる。 我々は時間複雑性$O(2^{0.695n})$、O(2^{0.5n})$のフォールトトレラントグローバーアプローチより少し悪い。 しかし、量子ビットの個数と各量子計算の深さはともにかなり良く、グルーバーは指数的な深さを必要とするが、定数pの固定角 QAOA の各ランは多項式深さを必要とする。 また、より論理的な量子ビットを導入することなく、SVPに対するゼロベクトル解を避ける新しい方法を提案する。 これにより、ゼロベクトル問題を無視せずに NISQ アーキテクチャ上で SVP のより空間効率の良い符号化を行うことができる。

関連論文リスト

• 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)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• High-precision and low-depth eigenstate property estimation: theory and resource estimation [2.6811507121199325]
  量子多体系の固有状態特性を推定することは、古典的および量子コンピューティングの双方にとって、長年にわたる、挑戦的な問題である。 本稿では,固有状態に対する固有値と観測可能な期待値を推定するランダムサンプリングアルゴリズムのフルスタック設計を提案する。
  論文  参考訳（メタデータ） (2024-06-06T17:54:26Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  古典ベクトル $mathbfb$ は量子状態の振幅で符号化される。 任意の状態の$Q$ qubitsは通常、約2Q$のエンタングゲートを必要とする。 状態準備に必要な量子資源を柔軟に削減できる決定論的(非変分法)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-26T07:37:54Z)
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup [9.820545418277305]
  我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。 理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
  論文  参考訳（メタデータ） (2021-08-05T18:56:17Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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