論文の概要: Finding dense sub-lattices as low-energy states of a Hamiltonian
- arxiv url: http://arxiv.org/abs/2309.16256v2
- Date: Thu, 07 Nov 2024 16:39:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-08 19:36:24.741458
- Title: Finding dense sub-lattices as low-energy states of a Hamiltonian
- Title（参考訳）: ハミルトニアンの低エネルギー状態としての高密度部分格子の発見
- Authors: Júlia Barberà-Rodríguez, Nicolas Gama, Anand Kumar Narayanan, David Joseph,
- Abstract要約: 格子ベースの暗号は、量子後暗号の最も顕著な候補の1つである。
最短ベクトル問題(SVP)は、与えられた格子の中で最短の非ゼロベクトルを見つけることである。
我々は、与えられた格子の最も密度の高い$K$-Densest Sub-lattice(K$-DSP)を求めるために、$K$-Densest Sub-lattice Problem(K$-DSP)として知られるSVPの自然な一般化を研究する。
- 参考スコア（独自算出の注目度）: 1.2183430883527995
- License:
- Abstract: Lattice-based cryptography has emerged as one of the most prominent candidates for post-quantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest non-zero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the $K$-Densest Sub-lattice Problem ($K$-DSP): to find the densest $K$-dimensional sub-lattice of a given lattice. We formulate $K$-DSP as finding the first excited state of a Z-basis Hamiltonian, making $K$-DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and Variational Quantum Algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that $O(KN^2)$ qubits suffice for solving $K$-DSP for $N$ dimensional input lattices. We empirically demonstrate the performance of a Quantum Approximate Optimization Algorithm $K$-DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of $K$-DSP in relation to the SVP, to see if there is reason to build post-quantum cryptography on $K$-DSP. We devise a quantum algorithm that solves $K$-DSP with run-time exponent $(5KN\log{N})/2$. Therefore, for fixed $K$, $K$-DSP is no more than polynomially harder than the SVP.
- Abstract（参考訳）: 格子ベースの暗号は、大規模なフォールトトレラント量子コンピュータの差し迫った脅威に対して安全であると予測された、量子後暗号の最も顕著な候補の1つとして登場した。
最短ベクトル問題(SVP)は、与えられた格子の中で最短の非ゼロベクトルを見つけることである。
格子ベースの暗号の基本であり、量子コンピュータでも難しいと信じられている。
我々は、与えられた格子の最も密度の高い$K$-Densest Sub-lattice(K$-DSP)を求めるために、$K$-Densest Sub-lattice Problem(K$-DSP)として知られるSVPの自然な一般化を研究する。
我々は、Z基底ハミルトニアンの最初の励起状態を見つけるために$K$-DSPを定式化し、グロバー探索、量子ギブスサンプリング、断熱、変分量子アルゴリズムを含む一連の量子アルゴリズムによる探索を可能にする。
アルゴリズムの複雑さは、入力格子が提示される基礎に依存する。
本稿では、任意の入力ベースを基本とし、量子アルゴリズムに適した入力にプリプロセッシングする古典多項式時間アルゴリズムを提案する。
前処理では、$O(KN^2)$ qubitsが$N$の入力格子に対して$K$-DSPを解くのに十分であることを示す。
我々は、低次元の量子近似最適化アルゴリズムの$K$-DSPソルバの性能を実証的に実証し、優れた前処理された入力ベースの影響を強調した。
次に、SVPに関する$K$-DSPの難しさについて議論し、$K$-DSP上にポスト量子暗号を構築する理由があるかどうかを確認する。
我々は、実行時指数$(5KN\log{N})/2$で$K$-DSPを解く量子アルゴリズムを考案した。
したがって、固定$K$の場合、$K$-DSP は SVP よりも多項式的に難しい。
関連論文リスト
- 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) - Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the
Dominating Set Problem [0.0]
グロバーのアルゴリズムは、量子コンピュータ上で実行されるよく知られた非構造量子探索アルゴリズムである。
本稿では、Groverのアルゴリズムのオラクルを構成するために、3つの優れた性質を持つ新しい量子カウンタを利用する。
論文 参考訳（メタデータ） (2023-12-14T23:00:35Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。
ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。
バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文 参考訳（メタデータ） (2023-05-25T08:43:11Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Lattice sieving via quantum random walks [0.0]
格子ベースの暗号は、量子後暗号の主要な提案の一つである。
最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。
我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-12T11:59:30Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-16T13:57:01Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。