論文の概要: An Uncertainty Principle for the Curvelet Transform, and the
Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors
- arxiv url: http://arxiv.org/abs/2310.03735v2
- Date: Tue, 7 Nov 2023 15:31:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 22:05:19.236149
- Title: An Uncertainty Principle for the Curvelet Transform, and the
Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors
- Title（参考訳）: 曲線レット変換の不確実性原理と短い格子ベクトルを求める量子アルゴリズムの不実現性
- Authors: Yi-Kai Liu
- Abstract要約: 格子問題を解くための量子アルゴリズム構築における一つのアプローチの有効性を示す。
ガウス波動関数の任意の選択に対して、このステップの誤差はBDDと近似SVPを解くのに必要なしきい値を超えていることが示される。
- 参考スコア（独自算出の注目度）: 0.6889425872704066
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The curvelet transform is a special type of wavelet transform, which is
useful for estimating the locations and orientations of waves propagating in
Euclidean space. We prove an uncertainty principle that lower-bounds the
variance of these estimates, for radial wave functions in n dimensions.
As an application of this uncertainty principle, we show the infeasibility of
one approach to constructing quantum algorithms for solving lattice problems,
such as the approximate shortest vector problem (approximate-SVP), and bounded
distance decoding (BDD). This gives insight into the computational
intractability of approximate-SVP, which plays an important role in algorithms
for integer programming, and in post-quantum cryptosystems.
In this approach to solving lattice problems, one prepares quantum
superpositions of Gaussian-like wave functions centered at lattice points. A
key step in this procedure requires finding the center of each Gaussian-like
wave function, using the quantum curvelet transform. We show that, for any
choice of the Gaussian-like wave function, the error in this step will be above
the threshold required to solve BDD and approximate-SVP.
- Abstract（参考訳）: 曲線変換は特別な種類のウェーブレット変換であり、ユークリッド空間で伝播する波の位置と向きを推定するのに有用である。
我々は、n次元のラジアル波動関数に対して、これらの推定の分散を下限とする不確実性原理を証明する。
この不確実性原理の適用例として、近似的最短ベクトル問題(近似-SVP)や境界距離復号法(BDD)といった格子問題の解法として量子アルゴリズムを構築する方法の有効性を示す。
これは、整数プログラミングのアルゴリズムや量子後暗号システムにおいて重要な役割を果たす近似SVPの計算難解性に関する洞察を与える。
格子問題を解くこのアプローチでは、格子点を中心とするガウス型波動関数の量子重ね合わせを準備する。
この手順の重要なステップは、量子曲線変換を用いて各ガウス型波動関数の中心を見つけることである。
ガウス波動関数の任意の選択に対して、このステップの誤差はBDDと近似SVPを解くのに必要なしきい値を超えていることが示される。
関連論文リスト
- Exploiting Structure in Quantum Relative Entropy Programs [6.281229317487581]
量子情報理論の応用から生じる共通構造が、量子相対エントロピープログラムの解法効率を向上させるためにどのように活用できるかを示す。
数値計算の結果,これらの手法は計算時間を最大数桁改善し,それまでの難解な問題を解くことができることがわかった。
論文 参考訳（メタデータ） (2024-06-28T21:37:45Z) - Efficient Computation of the Quantum Rate-Distortion Function [6.281229317487581]
我々は、対称性の低減が、絡み合い支援量子速度歪み問題の一般的な例を著しく単純化することを示す。
提案手法は, 量子速度歪み関数を証明可能なサブ線形収束率で計算するミラー降下アルゴリズムの不正確な変種を提案する。
論文 参考訳（メタデータ） (2023-09-28T00:46:53Z) - GRAPE optimization for open quantum systems with time-dependent
decoherence rates driven by coherent and incoherent controls [77.34726150561087]
グラディエントアセンセントパルス工学(GRAPE)法は量子制御の最適化に広く用いられている。
我々は、コヒーレント制御と非コヒーレント制御の両方によって駆動されるオープン量子系の目的関数を最適化するために、GRAPE法を採用する。
状態-状態遷移問題に対する数値シミュレーションによりアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2023-07-17T13:37:18Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳（メタデータ） (2023-06-10T23:28:13Z) - Efficient Light Propagation Algorithm using Quantum Computers [0.3124884279860061]
現代光学の基盤の1つはビーム伝搬アルゴリズムである。
伝搬は$mathcalO(logN)$ 1 個の位相ゲートで量子計算できることを示す。
我々は、量子的優位性を維持するために適切な観測可能なものを選ぶことの重要性を強調した。
論文 参考訳（メタデータ） (2023-03-13T11:47:09Z) - Quantum Gate Generation in Two-Level Open Quantum Systems by Coherent
and Incoherent Photons Found with Gradient Search [77.34726150561087]
我々は、非コヒーレント光子によって形成される環境を、非コヒーレント制御によるオープン量子系制御の資源とみなす。
我々は、ハミルトニアンにおけるコヒーレント制御と、時間依存デコヒーレンス率を誘導する散逸器における非コヒーレント制御を利用する。
論文 参考訳（メタデータ） (2023-02-28T07:36:02Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Variational waveguide QED simulators [58.720142291102135]
導波管QEDシミュレータは1次元フォトニックバンドギャップ材料と相互作用する量子エミッタによって構成される。
ここでは、これらの相互作用がより効率的な変分量子アルゴリズムを開発するためのリソースとなることを実証する。
論文 参考訳（メタデータ） (2023-02-03T18:55:08Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Bosonic field digitization for quantum computers [62.997667081978825]
我々は、離散化された場振幅ベースで格子ボゾン場の表現に対処する。
本稿では,エラースケーリングを予測し,効率的な量子ビット実装戦略を提案する。
論文 参考訳（メタデータ） (2021-08-24T15:30:04Z) - Calculating the distance from an electronic wave function to the
manifold of Slater determinants through the geometry of Grassmannians [0.0]
重なり関数と相関する波動関数の臨界点であるスレーター行列に収束するアルゴリズムを提案する。
このアルゴリズムは波動関数の絡み合いや相関の定量化に応用できる。
論文 参考訳（メタデータ） (2020-12-09T19:46:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。