論文の概要: On finding dense sub-lattices as low energy states of a quantum
Hamiltonian
- arxiv url: http://arxiv.org/abs/2309.16256v1
- Date: Thu, 28 Sep 2023 08:48:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 15:29:45.429027
- Title: On finding dense sub-lattices as low energy states of a quantum
Hamiltonian
- Title（参考訳）: 量子ハミルトニアンの低エネルギー状態としての密度サブ格子の発見について
- Authors: J\'ulia Barber\`a Rodr\'iguez, 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.3070944530614654
- License: http://creativecommons.org/licenses/by/4.0/
- 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の自然な一般化を研究する。
我々は、k$-dspを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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。