論文の概要: Fast estimation of outcome probabilities for quantum circuits
- arxiv url: http://arxiv.org/abs/2101.12223v3
- Date: Fri, 24 Jun 2022 16:36:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 11:20:43.250597
- Title: Fast estimation of outcome probabilities for quantum circuits
- Title（参考訳）: 量子回路における結果確率の高速推定
- Authors: Hakop Pashayan, Oliver Reardon-Smith, Kamil Korzekwa, Stephen D.
Bartlett
- Abstract要約: 我々は、$n$ qubits上の普遍量子回路のシミュレーションのための2つの古典的アルゴリズムを提案する。
我々のアルゴリズムは、パラメータの異なる条件下で最高の処理を行うことで、お互いを補完する。
アルゴリズムのC+Python実装を提供し、ランダム回路を用いてそれらをベンチマークする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present two classical algorithms for the simulation of universal quantum
circuits on $n$ qubits constructed from $c$ instances of Clifford gates and $t$
arbitrary-angle $Z$-rotation gates such as $T$ gates. Our algorithms complement
each other by performing best in different parameter regimes. The
$\tt{Estimate}$ algorithm produces an additive precision estimate of the Born
rule probability of a chosen measurement outcome with the only source of
run-time inefficiency being a linear dependence on the stabilizer extent (which
scales like $\approx 1.17^t$ for $T$ gates). Our algorithm is state-of-the-art
for this task: as an example, in approximately $13$ hours (on a standard
desktop computer), we estimated the Born rule probability to within an additive
error of $0.03$, for a $50$-qubit, $60$ non-Clifford gate quantum circuit with
more than $2000$ Clifford gates. Our second algorithm, $\tt{Compute}$,
calculates the probability of a chosen measurement outcome to machine precision
with run-time $O(2^{t-r} t)$ where $r$ is an efficiently computable,
circuit-specific quantity. With high probability, $r$ is very close to $\min
\{t, n-w\}$ for random circuits with many Clifford gates, where $w$ is the
number of measured qubits. $\tt{Compute}$ can be effective in surprisingly
challenging parameter regimes, e.g., we can randomly sample Clifford+$T$
circuits with $n=55$, $w=5$, $c=10^5$ and $t=80$ $T$ gates, and then compute
the Born rule probability with a run-time consistently less than $10$ minutes
using a single core of a standard desktop computer. We provide a C+Python
implementation of our algorithms and benchmark them using random circuits, the
hidden shift algorithm and the quantum approximate optimization algorithm
(QAOA).
- Abstract（参考訳）: クリフォードゲートの$c$インスタンスと、$T$ゲートのような任意の角度の$Z$回転ゲートから構築した$n$ qubits上での普遍量子回路シミュレーションのための古典的アルゴリズムを2つ提示する。
我々のアルゴリズムは、異なるパラメータレジームで最善を尽くし、互いに補完する。
$\tt{Estimate}$アルゴリズムは、選択された測定結果のボルンの規則確率を、安定度に線形依存する実行時の非効率性の唯一の源で加算精度で推定する($\approx 1.17^t$ for $T$ gates)。
例えば、標準的なデスクトップコンピュータでは、Bornルールの確率は、$0.03$、50$-qubit、$60$、2,000$以上のクリフォードゲートを持つ非クリフォードゲート量子回路に対して、0.03$と見積もった。
第2のアルゴリズムである$\tt{compute}$は、計算可能な回路固有量である実行時間$o(2^{t-r} t)$で、選択された測定結果の確率を計算する。
高い確率では、$r$は、多くのクリフォードゲートを持つランダム回路に対して$\min \{t, n-w\}$に非常に近い。
例えば、clifford+$t$回路をランダムに、$n=55$、$w=5$、$c=10^5$、$t=80$$$t$gateでサンプリングし、標準デスクトップコンピュータの1つのコアを使って10ドル未満で実行時のルール確率を10ドル未満で計算することができる。
アルゴリズムのC+Python実装を提供し、ランダム回路、隠れシフトアルゴリズム、量子近似最適化アルゴリズム(QAOA)を用いてそれらをベンチマークする。
関連論文リスト
- Lower $T$-count with faster algorithms [3.129187821625805]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - 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) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - 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) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Googleの53量子ビット回路のノイズ量子シミュレーションでは、C$は2.24pm0.21)times10-3$の忠実度値を得た。
この結果は,線形XEBテストの不正化が,量子回路の完全なシミュレーションを実現するよりも容易であることを示す証拠とみなすことができる。
論文 参考訳（メタデータ） (2020-05-05T18:01:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。