論文の概要: Quantum Legendre-Fenchel Transform
- arxiv url: http://arxiv.org/abs/2006.04823v3
- Date: Wed, 17 Mar 2021 07:07:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 07:00:04.588732
- Title: Quantum Legendre-Fenchel Transform
- Title(参考訳): 量子レジェンドル・フェンシェル変換
- Authors: David Sutter, Giacomo Nannicini, Tobias Sutter, Stefan Woerner
- Abstract要約: 離散ルジャンドル・フェンシェル変換を計算する量子アルゴリズムを提案する。
量子アルゴリズムは多対数因子に最適であることを示す。
- 参考スコア(独自算出の注目度): 6.643082745560234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum algorithm to compute the discrete Legendre-Fenchel
transform. Given access to a convex function evaluated at $N$ points, the
algorithm outputs a quantum-mechanical representation of its corresponding
discrete Legendre-Fenchel transform evaluated at $K$ points in the transformed
space. For a fixed regular discretization of the dual space the expected
running time scales as $O(\sqrt{\kappa}\,\mathrm{polylog}(N,K))$, where
$\kappa$ is the condition number of the function. If the discretization of the
dual space is chosen adaptively with $K$ equal to $N$, the running time reduces
to $O(\mathrm{polylog}(N))$. We explain how to extend the presented algorithm
to the multivariate setting and prove lower bounds for the query complexity,
showing that our quantum algorithm is optimal up to polylogarithmic factors.
For multivariate functions with $\kappa=1$, the quantum algorithm computes a
quantum-mechanical representation of the Legendre-Fenchel transform at $K$
points exponentially faster than any classical algorithm can compute it at a
single point.
- Abstract(参考訳): 離散レジェンドル・フェンシェル変換を計算するために量子アルゴリズムを提案する。
n$ポイントで評価された凸関数にアクセスすると、アルゴリズムは変換空間内の$k$ポイントで評価される対応する離散レジェンドル・フェンシェル変換の量子力学的表現を出力する。
双対空間の固定された正則離散化に対して、期待されるランニング時間は$O(\sqrt{\kappa}\,\mathrm{polylog}(N,K))$で、$\kappa$は函数の条件数である。
双対空間の離散化が適応的に $k$ と $n$ で選択されると、実行時間は $o(\mathrm{polylog}(n))$ となる。
提案したアルゴリズムを多変量設定に拡張し、クエリの複雑さの低い境界を証明し、我々の量子アルゴリズムが多変数因子に最適であることを示す。
量子アルゴリズムは、$\kappa=1$の多変量関数に対して、ルジャンドル・フェンシェル変換の量子力学的表現を、どの古典的アルゴリズムよりも指数関数的に速いk$で計算する。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Quantum mutual information redistribution by Number Partitioning
algorithm [9.818805141128935]
両部ユニタリ変換 $U_AB$ は、三部形式純状態 $|psirangle_ABC$ において量子相互情報を、d_Atimes d_Btimes d_C$ 次元ヒルベルト空間において、三部形式純状態 $|psirangle_ABC$ で再分配することを示す。
我々の近似アルゴリズムは、高次元の三部分量子状態に対して量子相互情報の再分配を実装するための実用的なプロトコルを提供する。
論文 参考訳(メタデータ) (2023-06-17T09:00:11Z) - Simulating Quantum Mean Values in Noisy Variational Quantum Algorithms:
A Polynomial-Scale Approach [0.1290382979353427]
大規模変動量子アルゴリズムは量子優位性を達成するための潜在的な経路として広く認識されている。
パウリパス上のオブザーバブルのバックプロパゲーションの積分パスに基づく新しい$lambda$メソッドを提案する。
論文 参考訳(メタデータ) (2023-06-09T10:42:07Z) - A Unified Quantum Algorithm Framework for Estimating Properties of
Discrete Probability Distributions [23.359007839448193]
離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。
我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
論文 参考訳(メタデータ) (2022-12-03T08:01:55Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳(メタデータ) (2022-10-12T19:10:43Z) - Extracting a function encoded in amplitudes of a quantum state by tensor
network and orthogonal function expansion [0.0]
量子回路とその最適化手法により、$d$に対して自由度が多数ある$f$の近似関数を得る。
また,金融動機関数を近似した数値実験を行い,本手法が有効であることを実証した。
論文 参考訳(メタデータ) (2022-08-31T04:10:24Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - On quantum algorithms for the Schr\"odinger equation in the
semi-classical regime [27.175719898694073]
半古典的状態におけるシュル・オーディンガーの方程式を考える。
このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
論文 参考訳(メタデータ) (2021-12-25T20:01:54Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳(メタデータ) (2021-08-13T09:47:11Z) - Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文 参考訳(メタデータ) (2020-07-20T16:42:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。