論文の概要: How to simulate quantum measurement without computing marginals
- arxiv url: http://arxiv.org/abs/2112.08499v2
- Date: Thu, 6 Jan 2022 21:34:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-04 11:29:26.687688
- Title: How to simulate quantum measurement without computing marginals
- Title（参考訳）: 限界計算なしで量子計測をシミュレートする方法
- Authors: Sergey Bravyi, David Gosset, Yinchen Liu
- Abstract要約: 量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
- 参考スコア（独自算出の注目度）: 3.222802562733787
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We describe and analyze algorithms for classically simulating measurement of
an $n$-qubit quantum state $\psi$ in the standard basis, that is, sampling a
bit string $x$ from the probability distribution $|\langle x|\psi\rangle|^2$.
Our algorithms reduce the sampling task to computing poly$(n)$ amplitudes of
$n$-qubit states; unlike previously known techniques they do not require
computation of marginal probabilities. First we consider the case where
$|\psi\rangle=U|0^n\rangle$ is the output state of an $m$-gate quantum circuit
$U$. We propose an exact sampling algorithm which involves computing $O(m)$
amplitudes of $n$-qubit states generated by subcircuits of $U$ spanned by the
first $t=1,2,\ldots,m$ gates. We show that our algorithm can significantly
accelerate quantum circuit simulations based on tensor network contraction
methods or low-rank stabilizer decompositions. As another striking consequence
we obtain an efficient classical simulation algorithm for measurement-based
quantum computation with the surface code resource state on any planar graph,
generalizing a previous algorithm which was known to be efficient only under
restrictive topological constraints on the ordering of single-qubit
measurements. Second, we consider the case in which $\psi$ is the unique ground
state of a local Hamiltonian with a spectral gap that is lower bounded by an
inverse polynomial function of $n$. We prove that a simple Metropolis-Hastings
Markov Chain mixes rapidly to the desired probability distribution provided
that $\psi$ obeys a certain technical condition, which we show is satisfied for
all sign-problem free Hamiltonians. This gives a sampling algorithm which
involves computing $\mathrm{poly}(n)$ amplitudes of $\psi$.
- Abstract（参考訳）: 量子状態の標準値である$n$-qubit の量子状態、すなわち確率分布 $|\langle x|\psi\rangle|^2$ からビット文字列 $x$ をサンプリングするアルゴリズムを古典的にシミュレートして解析する。
我々のアルゴリズムは、サンプリングタスクをpoly$の計算に削減する
(n)$振幅は$n$-qubitであり、既知の手法とは異なり、限界確率の計算を必要としない。
まず、$|\psi\rangle=U|0^n\rangle$が$m$ゲート量子回路$U$の出力状態である場合を考える。
我々は$Oの計算を伴う正確なサンプリングアルゴリズムを提案する。
(m)$の振幅は、最初の$t=1,2,\ldots,m$gates で与えられる$u$のサブサーキットによって生成される。
提案アルゴリズムはテンソルネットワーク収縮法や低ランク安定化器分解に基づく量子回路シミュレーションを著しく高速化できることを示す。
もう1つの驚くべき結果として、任意の平面グラフ上の曲面コードリソース状態を持つ計測ベースの量子計算のための効率的な古典的シミュレーションアルゴリズムを求め、単一量子ビット測定の順序付けに関する制限的位相的制約下でのみ効率的であることが知られている以前のアルゴリズムを一般化した。
第二に、$\psi$ が局所ハミルトニアンの一意な基底状態であり、そのスペクトルギャップは、逆多項式関数 $n$ によってより低く有界である場合を考える。
簡単なMetropolis-Hastings Markov Chain が、$\psi$ が特定の技術的条件に従うような所望の確率分布と急速に混ざり合っていることを証明した。
これは$\mathrm{poly}計算を伴うサンプリングアルゴリズムを与える
(n)$の振幅は$\psi$である。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration [0.0]
MCMCの量子アルゴリズムが提案され、古典的なスペクトルギャップに対して$Delta$の2次スピードアップが得られる。
我々は状態生成だけでなく、ベイズ推定における共通課題であるパラメータの信頼区間も見いだすと考えている。
提案した信頼区間計算法では、$Delta$で$ell$スケールを計算するための量子回路へのクエリ数、$epsilon$で必要な精度$epsilon$、および標準偏差$sigma$$$ $ell$ as $tildeO(sigma/epsilonを演算する。
論文 参考訳（メタデータ） (2023-03-10T01:05:16Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。