論文の概要: Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits
- arxiv url: http://arxiv.org/abs/2012.05460v2
- Date: Sun, 6 Jun 2021 00:11:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-21 06:02:54.361560
- Title: Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits
- Title（参考訳）: 幾何学的局所的浅層量子回路の出力確率の準多項時間近似
- Authors: Nolan J. Coble and Matthew Coudron
- Abstract要約: 本稿では,任意の3次元局所多元数量子回路に対する古典的アルゴリズムを提案する。
準多項式時間における任意の逆多項式加法誤差に$| x |C|0otimes n>|2$を演算する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a classical algorithm that, for any 3D geometrically-local,
polylogarithmic-depth quantum circuit $C$ acting on $n$ qubits, 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. It is
known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$
additive error [Mov20, KMM21]. The previous best known algorithm for this
problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute
probabilities to within additive error $\epsilon$ [BGM20]. Notably, the [BGM20]
paper included an elegant polynomial time algorithm for this estimation task
restricted to 2D circuits, which makes a novel use of 1D Matrix Product States
(MPS) carefully tailored to the 2D geometry of the circuit in question.
Surprisingly, it is not clear that it is possible to extend this use of MPS to
address the case of 3D circuits in polynomial time. This raises a natural
question as to whether the computational complexity of the 3D problem might be
drastically higher than that of the 2D problem. In this work we address this
question by exhibiting a quasi-polynomial time algorithm for the 3D case. In
order to surpass the technical barriers encountered by previously known
techniques we are forced to pursue a novel approach.
Our algorithm has a Divide-and-Conquer structure, demonstrating how to
approximate the desired quantity via several instantiations of the same problem
type, each involving 3D-local circuits on about half the number of qubits as
the original. This division step is then applied recursively, expressing the
original quantity as a weighted combination of smaller and smaller 3D-local
quantum circuits. A central technical challenge is to control correlations
arising from entanglement that may exist between the different circuit
``pieces" produced this way.
- Abstract（参考訳）: n$ qubits に作用する任意の3次元幾何学的局所的多対数深さ量子回路 $c$ と任意のビット文字列 $x\in\{0,1\}^n$ に対して、|<x |c|0^{\otimes n}>|^2$ を準多項時間で任意の逆多項加法誤差内で計算できる古典的なアルゴリズムを提案する。
2-n^2}$加法誤差[Mov20, KMM21]の範囲内で同じ量を計算するのが$\#P$-hardであることが知られている。
この問題の最もよく知られたアルゴリズムは$o(2^{n^{1/3}}\text{poly}(1/\epsilon))$であり、加算誤差$\epsilon$ [bgm20]内で確率を計算するのに時間がかかった。
特に、[BGM20]論文は、この推定タスクを2D回路に限定するエレガントな多項式時間アルゴリズムを含んでおり、1D行列生成状態(MPS)を問題となる回路の2D幾何学に注意深く適合させる。
驚くべきことに、多項式時間で3d回路の場合に対処するためにこのmpsの使用を拡張できるかどうかは明らかではない。
このことは、3次元問題の計算複雑性が2次元問題よりも大幅に高いかどうかという自然な疑問を提起する。
本研究では,3次元ケースに対する準多項式時間アルゴリズムを用いてこの問題に対処する。
既知のテクニックが直面する技術的障壁を克服するために、私たちは新しいアプローチを追求せざるを得ません。
このアルゴリズムは分割・分割構造を持ち、同じ問題型の複数のインスタンス化を通じて所望の量を近似する方法を示し、それぞれが元の量子ビットの約半分に3dローカル回路を含む。
この分割ステップは再帰的に適用され、元の量をより小さな3d局所量子回路の重み付け結合として表現する。
中心的な技術的課題は、このような方法で生成された異なる回路 ``pieces' の間に生じる絡み合いから生じる相関を制御することである。
関連論文リスト
- On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
本稿では,量子ゲート生成の符号化問題について述べる。
emphReference Input Generation Algorithm (RIGA) はこの研究で一般化されている。
論文 参考訳（メタデータ） (2024-09-02T10:41:15Z) - 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) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53: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) - Approximating Output Probabilities of Shallow Quantum Circuits which are
Geometrically-local in any Fixed Dimension [0.0]
準多項式時間における任意の逆多項式加法誤差に対して,$|x|C|0otimes n>|2$を計算できるアルゴリズムを提案する。
これは [CC21] の結果の拡張であり、元々は$D = 3$でこの結果が証明された。
論文 参考訳（メタデータ） (2022-02-16T21:37:16Z) - 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) - 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) - A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
この研究は、最先端のフォールトトレラントな量子エラー訂正符号を使用する場合の量子アルゴリズム実装の物理的コストの低減に重点を置いている。
普遍ゲート集合であるクリフォード+Tゲート集合からなる量子回路によって正確に実装できるユニタリ群を考える。
論文 参考訳（メタデータ） (2020-06-22T17:21:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。