論文の概要: Approximating Output Probabilities of Shallow Quantum Circuits which are
Geometrically-local in any Fixed Dimension
- arxiv url: http://arxiv.org/abs/2202.08349v1
- Date: Wed, 16 Feb 2022 21:37:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 16:18:28.225446
- Title: Approximating Output Probabilities of Shallow Quantum Circuits which are
Geometrically-local in any Fixed Dimension
- Title（参考訳）: 固定次元の幾何学的局所性を有する浅量子回路の出力確率の近似
- Authors: Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi,
Matthew Coudron
- Abstract要約: 準多項式時間における任意の逆多項式加法誤差に対して,$|x|C|0otimes n>|2$を計算できるアルゴリズムを提案する。
これは [CC21] の結果の拡張であり、元々は$D = 3$でこの結果が証明された。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a classical algorithm that, for any $D$-dimensional
geometrically-local, quantum circuit $C$ of polylogarithmic-depth, and any bit
string $x \in {0,1}^n$, can compute the quantity $|<x|C|0^{\otimes n}>|^2$ to
within any inverse-polynomial additive error in quasi-polynomial time, for any
fixed dimension $D$. This is an extension of the result [CC21], which
originally proved this result for $D = 3$. To see why this is interesting, note
that, while the $D = 1$ case of this result follows from standard use of Matrix
Product States, known for decades, the $D = 2$ case required novel and
interesting techniques introduced in [BGM19]. Extending to the case $D = 3$ was
even more laborious and required further new techniques introduced in [CC21].
Our work here shows that, while handling each new dimension has historically
required a new insight, and fixed algorithmic primitive, based on known
techniques for $D \leq 3$, we can now handle any fixed dimension $D > 3$.
Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate
the desired quantity via several instantiations of the same problem type, each
involving $D$-dimensional circuits on about half the number of qubits as the
original. This division step is then applied recursively, until the width of
the recursively decomposed circuits in the $D^{th}$ dimension is so small that
they can effectively be regarded as $(D-1)$-dimensional problems by absorbing
the small width in the $D^{th}$ dimension into the qudit structure at the cost
of a moderate increase in runtime. The main technical challenge lies in
ensuring that the more involved portions of the recursive circuit decomposition
and error analysis from [CC21] still hold in higher dimensions, which requires
small modifications to the analysis in some places.
- Abstract（参考訳）: 古典的アルゴリズムでは、任意のD$次元幾何学的に局所的な量子回路$C$のポリ対数深度に対して、任意のビット列$x \in {0,1}^n$は、任意の固定次元$D$の逆多項式時間における任意の逆多項式加法誤差$|<x|C|0^{\otimes n}>|^2$を計算できる。
これは [CC21] の結果の拡張であり、元々は$D = 3$でこの結果を証明した。
この結果の$D = 1$のケースは、何十年にもわたって知られているMatrix Product Statesの標準的な使用に由来するが、$D = 2$のケースは、[BGM19]で導入された斬新で興味深いテクニックである。
D = 3$に拡張するとさらに手間がかかり、[CC21]で導入された新しいテクニックが必要になった。
ここでの我々の研究は、各新しい次元を扱うには歴史的に新しい洞察が必要であり、固定されたアルゴリズムプリミティブが$D \leq 3$の既知のテクニックに基づいていることを示している。
我々のアルゴリズムは[CC21]のDivide-and-Conquerフレームワークを用いて、同じ問題型のいくつかのインスタンス化によって所望の量を近似する。
この分割ステップは再帰的に適用され、d^{th}$次元における再帰的に分解された回路の幅があまりに小さく、d^{th}$次元の小さな幅をランタイムの増加を犠牲にしてqudit構造に吸収することにより、実質的に$(d-1)$次元問題と見なすことができる。
主な技術的課題は、[cc21]からの再帰的回路分解とエラー解析のより関与的な部分が依然として高次元に保持されていることを保証することである。
関連論文リスト
- On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
本稿では,量子ゲート生成の符号化問題について述べる。
emphReference Input Generation Algorithm (RIGA) はこの研究で一般化されている。
論文 参考訳（メタデータ） (2024-09-02T10:41:15Z) - A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies [34.7582575446942]
多次元スケーリング(MDS)は、低次元ユークリッド空間に$n$ポイントの計量を埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - 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) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits [0.0]
本稿では,任意の3次元局所多元数量子回路に対する古典的アルゴリズムを提案する。
準多項式時間における任意の逆多項式加法誤差に$| x |C|0otimes n>|2$を演算する。
論文 参考訳（メタデータ） (2020-12-10T05:19:29Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - How to trap a gradient flow [3.198144010381572]
我々は、$mathbbRd$ のコンパクト領域上の滑らかな関数の $varepsilon$-approximate 定常点を求める問題を考える。
我々の主な貢献は、勾配流トラップ法(GFT)と呼ばれるアルゴリズムと、そのオラクルの複雑さの分析である。
論文 参考訳（メタデータ） (2020-01-09T13:30:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。