論文の概要: Fast simulation of planar Clifford circuits
- arxiv url: http://arxiv.org/abs/2009.03218v3
- Date: Wed, 31 Jan 2024 04:50:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-01 18:26:04.059676
- Title: Fast simulation of planar Clifford circuits
- Title（参考訳）: 平面クリフォード回路の高速シミュレーション
- Authors: David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer
- Abstract要約: 一般的な量子回路は指数時間で古典的にシミュレートすることができる。
ツリー幅と平面性はクリフォード回路シミュレーションの改善に有効であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A general quantum circuit can be simulated classically in exponential time.
If it has a planar layout, then a tensor-network contraction algorithm due to
Markov and Shi has a runtime exponential in the square root of its size, or
more generally exponential in the treewidth of the underlying graph.
Separately, Gottesman and Knill showed that if all gates are restricted to be
Clifford, then there is a polynomial time simulation. We combine these two
ideas and show that treewidth and planarity can be exploited to improve
Clifford circuit simulation. Our main result is a classical algorithm with
runtime scaling asymptotically as $n^{\omega/2}<n^{1.19}$ which samples from
the output distribution obtained by measuring all $n$ qubits of a planar graph
state in given Pauli bases. Here $\omega$ is the matrix multiplication
exponent. We also provide a classical algorithm with the same asymptotic
runtime which samples from the output distribution of any constant-depth
Clifford circuit in a planar geometry. Our work improves known classical
algorithms with cubic runtime. A key ingredient is a mapping which, given a
tree decomposition of some graph $G$, produces a Clifford circuit with a
structure that mirrors the tree decomposition and which emulates measurement of
the corresponding graph state. We provide a classical simulation of this
circuit with the runtime stated above for planar graphs and otherwise
$nt^{\omega-1}$ where $t$ is the width of the tree decomposition. Our algorithm
incorporates two subroutines which may be of independent interest. The first is
a matrix-multiplication-time version of the Gottesman-Knill simulation of
multi-qubit measurement on stabilizer states. The second is a new classical
algorithm for solving symmetric linear systems over $\mathbb{F}_2$ in a planar
geometry, extending previous works which only applied to non-singular linear
systems in the analogous setting.
- Abstract（参考訳）: 一般的な量子回路は指数時間で古典的にシミュレートすることができる。
平面レイアウトを持つ場合、マルコフとシによるテンソル-ネットワーク縮小アルゴリズムは、その大きさの平方根に指数関数的、またはより一般に基礎となるグラフのツリー幅に指数的である。
これとは別に、ゴッテスマンとクニルは、すべてのゲートがクリフォードに制限されている場合、多項式時間シミュレーションが存在することを示した。
これら2つのアイデアを組み合わせることで、ツリー幅と平面性を利用してクリフォード回路シミュレーションを改善することができることを示す。
我々の主な結果は、与えられたパウリ基底の平面グラフ状態のすべての$n$ qubitsを測定することで得られる出力分布から得られるサンプルである$n^{\omega/2}<n^{1.19}$と漸近的にスケールする古典的アルゴリズムである。
ここで$\omega$は行列乗算指数である。
また,平面幾何における定深さクリフォード回路の出力分布からサンプルする,同じ漸近的ランタイムを持つ古典的アルゴリズムを提供する。
我々の研究は、既知の古典的アルゴリズムを立方体ランタイムで改善する。
重要な要素は、あるグラフ$G$のツリー分解が与えられたとき、ツリー分解を反映し、対応するグラフ状態の測定をエミュレートする構造を持つクリフォード回路を生成するマッピングである。
この回路の古典的なシミュレーションを平面グラフのランタイムと、それ以外は$t$が木分解の幅である$nt^{\omega-1}$で提供する。
アルゴリズムには2つのサブルーチンが組み込まれている。
1つ目は、安定化状態におけるマルチキュービット測定のゴッテマン・クニルシミュレーションの行列乗算時間バージョンである。
2つ目は、平面幾何学において$\mathbb{f}_2$ 上の対称線型系を解くための新しい古典的アルゴリズムであり、同様の設定で非特異線型系にのみ適用される以前の作品を拡張している。
関連論文リスト
- Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Laplacian Eigenmaps with variational circuits: a quantum embedding of
graph data [0.0]
量子変分回路を用いたラプラシアン固有写像の計算法を提案する。
量子シミュレータを用いた32ノードグラフ上でのテストでは,古典的なラプラシアン固有写像アルゴリズムと同様の性能が得られた。
論文 参考訳（メタデータ） (2020-11-10T14:51:25Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - Quantum Speedup for Graph Sparsification, Cut Approximation and
Laplacian Solving [1.0660480034605238]
スペクトルスペーシフィケーション」は、ノード数でエッジの数をほぼ直線に減らす。
スペクトルスカラー化のための量子スピードアップとその多くの応用について述べる。
我々のアルゴリズムはラプラシア系を解くための量子スピードアップを意味する。
論文 参考訳（メタデータ） (2019-11-17T17:29:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。