論文の概要: Computationally Efficient Quantum Expectation with Extended Bell
Measurements
- arxiv url: http://arxiv.org/abs/2110.09735v2
- Date: Fri, 8 Apr 2022 08:04:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 02:10:34.623360
- Title: Computationally Efficient Quantum Expectation with Extended Bell
Measurements
- Title(参考訳): 拡張ベル測定による計算効率の高い量子期待
- Authors: Ruho Kondo, Yuki Sato, Satoshi Koide, Seiji Kajita, Hideki Takamatsu
- Abstract要約: 本稿では,任意の観測可能な$Ainmathbb C2ntimes 2n$の期待値を評価する手法を提案する。
この分析法は、4n$行列要素を少なくとも2n+1$グループにまとめて同時測定する。
- 参考スコア(独自算出の注目度): 7.620967781722716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Evaluating an expectation value of an arbitrary observable $A\in{\mathbb
C}^{2^n\times 2^n}$ through na\"ive Pauli measurements requires a large number
of terms to be evaluated. We approach this issue using a method based on Bell
measurement, which we refer to as the extended Bell measurement method. This
analytical method quickly assembles the $4^n$ matrix elements into at most
$2^{n+1}$ groups for simultaneous measurements in $O(nd)$ time, where $d$ is
the number of non-zero elements of $A$. The number of groups is particularly
small when $A$ is a band matrix. When the bandwidth of $A$ is $k=O(n^c)$, the
number of groups for simultaneous measurement reduces to $O(n^{c+1})$. In
addition, when non-zero elements densely fill the band, the variance is
$O((n^{c+1}/2^n)\,{\rm tr}(A^2))$, which is small compared with the variances
of existing methods. The proposed method requires a few additional gates for
each measurement, namely one Hadamard gate, one phase gate and at most $n-1$
CNOT gates. Experimental results on an IBM-Q system show the computational
efficiency and scalability of the proposed scheme, compared with existing
state-of-the-art approaches. Code is available at
https://github.com/ToyotaCRDL/extended-bell-measurements.
- Abstract(参考訳): 任意の観測可能な$A\in{\mathbb C}^{2^n\times 2^n}$ の期待値を評価するには、多くの項を評価する必要がある。
本稿では,ベル計測に基づく手法を用いてこの問題にアプローチし,この手法を拡張ベル計測法と呼ぶ。
この分析方法は、すぐに4^n$マトリックス要素を最大$^{n+1}$グループに組み立て、同時に$o(nd)$時間で測定し、ここで$d$は0でない要素の数が$a$である。
a$ がバンド行列であるとき、グループの数は特に小さい。
A$の帯域幅が$k=O(n^c)$の場合、同時測定のためのグループの数は$O(n^{c+1})$に減少する。
さらに、非零元がバンドを密度的に満たすとき、分散は$O((n^{c+1}/2^n)\,{\rm tr}(A^2))$であり、既存の方法の分散と比較して小さい。
提案手法では,1つのアダマールゲート,1つの位相ゲート,最大で最大$n-1$ cnotゲートなど,測定毎に数個のゲートが必要となる。
IBM-Qシステムにおける実験結果から,提案手法の計算効率と拡張性について,従来の最先端手法と比較した。
コードはhttps://github.com/ToyotaCRDL/extended-bell-measurementsで入手できる。
関連論文リスト
- Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳(メタデータ) (2024-08-10T04:26:19Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳(メタデータ) (2024-06-25T06:07:20Z) - Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
我々は、$k$-means++の量子実装を示し、その時間は$tildeO(zeta2 k2)$で実行される。
これは、量子バージョンが$O(logk)$近似を保証する$k$-means++の堅牢な近似解析によって示される。
これはQI-$k$-means++と呼ばれ、実行時間は$O(Nd) + tildeO(zeta)である。
論文 参考訳(メタデータ) (2024-05-22T05:13:28Z) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳(メタデータ) (2023-09-25T09:50:15Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳(メタデータ) (2023-08-16T06:46:37Z) - 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) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳(メタデータ) (2022-10-05T22:52:00Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳(メタデータ) (2021-12-15T21:44:05Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。