論文の概要: Finding Short Vectors in Structured Lattices with Reduced Quantum
Resources
- arxiv url: http://arxiv.org/abs/2307.12047v1
- Date: Sat, 22 Jul 2023 10:52:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-25 18:20:12.712342
- Title: Finding Short Vectors in Structured Lattices with Reduced Quantum
Resources
- Title(参考訳): 量子資源削減による構造格子中の短ベクトルの探索
- Authors: Eden Schirman, Cong Ling, Florian Mintert
- Abstract要約: 我々は、環および負環格子の基礎となる対称性を利用するための量子アルゴリズムの枠組みを与える。
このフレームワークは、短いベクトルを見つけようとする量子アルゴリズムを実装するのに必要な量子資源を大幅に節約する。
- 参考スコア(独自算出の注目度): 21.85060137533507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Leading protocols of post-quantum cryptosystems are based on the mathematical
problem of finding short vectors in structured lattices. It is assumed that the
structure of these lattices does not give an advantage for quantum and
classical algorithms attempting to find short vectors. In this work we focus on
cyclic and nega-cyclic lattices and give a quantum algorithmic framework of how
to exploit the symmetries underlying these lattices. This framework leads to a
significant saving in the quantum resources (e.g. qubits count and circuit
depth) required for implementing a quantum algorithm attempting to find short
vectors. We benchmark the proposed framework with the variational quantum
eigensolver, and show that it leads to better results while reducing the qubits
count and the circuit depth. The framework is also applicable to classical
algorithms aimed at finding short vectors in structured lattices, and in this
regard it could be seen as a quantum-inspired approach.
- Abstract(参考訳): 量子暗号系の主要なプロトコルは、構造格子内の短いベクトルを見つける数学的問題に基づいている。
これらの格子の構造は、短いベクトルを見つけようとする量子および古典的アルゴリズムに有利ではないと仮定される。
この研究では、環状および負環格子に焦点を当て、これらの格子の基盤となる対称性を利用するための量子アルゴリズムの枠組みを提供する。
このフレームワークは、短いベクトルを見つけようとする量子アルゴリズムを実装するのに必要な量子リソース(量子ビット数や回路の深さなど)を大幅に節約する。
提案手法を可変量子固有解法を用いてベンチマークし,量子ビット数と回路深度を削減しつつ,よりよい結果をもたらすことを示す。
このフレームワークは、構造化格子の短いベクトルを見つけることを目的とした古典的なアルゴリズムにも適用でき、この点において量子に着想を得たアプローチと見なすことができる。
関連論文リスト
- Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD [0.0]
上述したサブルーチンの量子変種を設計することで、コードシービングのための最初の量子アルゴリズムを導入する。
我々の量子ウォークアルゴリズムは、局所性に敏感なフィルタリング層を追加することにより、基礎となる探索問題の構造を利用する。
我々の分析は、このフレームワークが量子IDDアルゴリズムの最先端性を上回るように適応されるべきであることを強調している。
論文 参考訳(メタデータ) (2024-08-29T11:47:33Z) - Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳(メタデータ) (2024-08-07T19:51:22Z) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳(メタデータ) (2023-10-09T03:10:42Z) - Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms [0.0]
この弱い仮定の下では、ランダム化線形代数の技法がどれだけ多く適用できるかを示す。
また、これらの結果を用いて、多くの量子機械学習アルゴリズムの頑健な復号化を行う。
論文 参考訳(メタデータ) (2023-04-11T02:09:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
本稿では,高レベル言語で記述された量子回路から,アルゴリズム固有のグラフ状態を作成する量子回路コンパイラを提案する。
この計算は、このグラフ状態に関する一連の非パウリ測度を用いて実装することができる。
論文 参考訳(メタデータ) (2022-09-15T14:52:31Z) - Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる
本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。
その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
論文 参考訳(メタデータ) (2022-09-01T17:08:41Z) - Quantum Krylov subspace algorithms for ground and excited state energy
estimation [0.0]
量子クリロフ部分空間対角化(QKSD)アルゴリズムは、従来の量子位相推定アルゴリズムに代わる低コストな代替手段を提供する。
我々は、凝縮物質物理学と量子化学に関連するハミルトンの幅広いクラスが、アダマールテストの使用を避けるために活用できる対称性を含むことを示した。
我々は量子クリロフ部分空間アルゴリズムの統一理論を開発し、基底および励起状態エネルギー推定問題に対する3つの新しい量子古典的アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-14T17:56:53Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。
量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。
提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
論文 参考訳(メタデータ) (2021-06-06T13:15:25Z) - Routed quantum circuits [0.0]
いくつかの最近の研究で研究されている量子論的構造は、量子回路の標準的な枠組みの中で適切に説明できないと論じる。
我々は、テクスチュルト線形写像とテクスチュルト量子回路によって与えられる量子回路の枠組みの拡張を提案する。
論文 参考訳(メタデータ) (2020-11-16T17:31:56Z) - ACSS-q: Algorithmic complexity for short strings via quantum accelerated
approach [1.4873907857806357]
符号化定理法を用いて,アルゴリズムの複雑性を推定する量子回路を提案する。
ユースケースとして,アルゴリズムの複雑さに基づくタンパク質-タンパク質相互作用の応用フレームワークを提案する。
論文 参考訳(メタデータ) (2020-09-18T14:41:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。