論文の概要: Unitary Subgroup Testing
- arxiv url: http://arxiv.org/abs/2104.03591v3
- Date: Tue, 22 Nov 2022 07:27:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-04 12:13:20.105084
- Title: Unitary Subgroup Testing
- Title(参考訳): 単体サブグループテスト
- Authors: Zvika Brakerski, Devika Sharma, Guy Weissenberg
- Abstract要約: 我々は、自明な部分群として $mathcalG$ あるいは Pauli あるいは Clifford 群や $q$-ary 拡張として問題を研究する。
私たちの主な成果は、Pauliテスト、Cliffordテスト、Identityテストの等価性です。
- 参考スコア(独自算出の注目度): 8.282602586225831
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of $\textit{subgroup testing}$ for a quantum circuit
$C$: given access to $C$, determine whether it implements a unitary that is
$a$-close or $b$-far from a subgroup $\mathcal{G}$ of the unitary group. It
encompasses the problem of exact testing, property testing and tolerant
testing. In this work, we study these problems with the group $\mathcal{G}$ as
the trivial subgroup (i.e. identity testing) or the Pauli or Clifford group and
their $q$-ary extension, and a $\textit{promise}$ version of these problems
where $C$ is promised to be in some subgroup of the unitaries that contains
$\mathcal{G}$ (e.g. identity testing for Clifford circuits).
Our main result is an equivalence between Pauli testing, Clifford testing and
Identity testing. We derive the equivalence between Clifford and Identity
testing by showing a structural property of the Clifford unitaries. Namely,
that their (normalized) trace lies in the discrete set $\{2^{-k/2}: k \in
\mathbb{N}\} \cup \{0\}$, regardless of the dimension. We also state and prove
the analogous property for the $q$-ary Cliffords. This result allows us to
analyze a very simple single-query identity test under the Clifford/Pauli
promise. To prove the equivalence between Pauli and Identity testing, we
analyze the conjugation action of a non-Pauli unitary on the Pauli group and
show that its distance from the Pauli group affects the number of fixed points.
We believe that these results are of interest, independent of their application
to establish the equivalences.
We use the equivalences to compare (and thus establish) computational
hardness for the problems of Pauli and Clifford testing.
- Abstract(参考訳): 量子回路に対する$\textit{subgroup testing}$の問題は、$C$:$C$へのアクセスを与えられた場合、単位群のサブグループ$\mathcal{G}$から$a$-closeあるいは$b$-farのユニタリを実装しているかどうかを決定する。
正確なテスト、プロパティテスト、耐性テストの問題を包含する。
本研究では、これらの問題を自明な部分群として $\mathcal{G}$ あるいは Pauli あるいは Clifford 群とその $q$-ary 拡張として、および $C$ が $\mathcal{G}$ を含むユニタリ群の一部部分群に属することを約束する $\textit{promise}$ として研究する。
私たちの主な成果は、Pauliテスト、Cliffordテスト、Identityテストの等価性です。
クリフォードユニタリの構造特性を示すことにより、クリフォード検定とアイデンティティ検定の等価性を導出する。
すなわち、それらの(正規化された)トレースは、次元に関係なく、離散集合 $\{2^{-k/2}: k \in \mathbb{N}\} \cup \{0\}$ にある。
また、$q$-ary Cliffords の類似性についても述べ、証明する。
この結果、Clifford/Pauli の約束の下で、非常に単純な単一クエリIDテストを分析することができる。
パウリと同一性テストの同値性を証明するために、パウリ群上の非パウリユニタリの共役作用を分析し、パウリ群からの距離が不動点の数に影響することを示す。
これらの結果は、同値性を確立するための応用とは独立して、興味のあるものであると我々は信じている。
等価性を用いて、パウリとクリフォードテストの問題に対して計算硬度を比較する(そして確立する)。
関連論文リスト
- Polynomial-time tolerant testing stabilizer states [4.65004369765875]
アルゴリズムは未知の$n$-qubit量子状態 $|psirangle promise $(i)$ $|psirangle$のコピーを与える。
すべての$varepsilon_1>0$と$varepsilonleq varepsilon_C$に対して、どちらが正しいかを決定する$textsfpolyが存在することを示す。
我々の証明には、量子状態に対するガウワーズノルムの新しい定義、量子状態のガウワーズ-3$のノルムに対する逆定理、および安定化器被覆に対する新しい境界が含まれる。
論文 参考訳(メタデータ) (2024-08-12T16:56:33Z) - Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。
このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。
信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
論文 参考訳(メタデータ) (2024-06-21T20:56:35Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳(メタデータ) (2022-08-12T15:05:07Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳(メタデータ) (2022-06-21T20:43:53Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳(メタデータ) (2022-02-23T16:10:23Z) - Testing matrix product states [5.225550006603552]
未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。
MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
論文 参考訳(メタデータ) (2022-01-05T21:10:50Z) - A Kernel Test for Causal Association via Noise Contrastive Backdoor Adjustment [18.791409397894835]
我々は、textitdo-null仮説である$H_0:; p(y|textit do(X=x))=p(y)$をテストする非パラメトリックな方法を開発した。
我々は,バックドアHSIC (bd-HSIC) が校正され,多数の共同設立者の下でバイナリと継続的治療を行う能力を持っていることを実証した。
論文 参考訳(メタデータ) (2021-11-25T19:12:37Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z) - Sample optimal Quantum identity testing via Pauli Measurements [11.98034899127065]
我々は、$Theta(mathrmpoly(n)cdotfrac4nepsilon2)$が、2つの$n$-qubit量子状態$rho$と$sigma$が同一であるか、または2つのアウトカムパウリ測定を用いて、トレース距離において$epsilon$-farであるかどうかをテストするサンプル複雑性であることを示した。
論文 参考訳(メタデータ) (2020-09-24T06:54:09Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-09-14T16:09:17Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。