Fugu-MT 論文翻訳(概要): Clifford testing: algorithms and lower bounds

論文の概要: Clifford testing: algorithms and lower bounds

arxiv url: http://arxiv.org/abs/2510.07164v1
Date: Wed, 08 Oct 2025 16:02:07 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-09 16:41:20.608526
Title: Clifford testing: algorithms and lower bounds
Title（参考訳）: クリフォード検定:アルゴリズムと下限
Authors: Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Briët, Jonas Helsen,
Abstract要約: 我々はクリフォード検定の問題を考察し、ブラックボックス$n$-qubitユニタリがクリフォードユニタリであるのか、あるいはクリフォードユニタリから少なくとも$varepsilon$-farであるのかを問う。耐久安定度テストのテクニックを我々の設定に適応させることにより、テスターは寛容であることを示す。
参考スコア（独自算出の注目度）: 2.678461526933908
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: We consider the problem of Clifford testing, which asks whether a black-box $n$-qubit unitary is a Clifford unitary or at least $\varepsilon$-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability $\mathrm{poly}(\varepsilon)$. This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an $O(n)$-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least $\Omega(n^{1/4})$ queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest.
Abstract（参考訳）: クリフォード検定の問題は、ブラックボックス$n$-qubitユニタリがクリフォードユニタリであるのか、少なくともクリフォードユニタリから$\varepsilon$-farであるのかを問うものである。これは確率 $\mathrm{poly}(\varepsilon)$ でこの問題を決定する。これは、スタビライザーテストの密接な関連タスクに必要な最低6つのコピーとは対照的である。耐久安定度テストのテクニックを私たちの設定に適応させることにより、テスターが寛容であることを示します。そうすることで、非可換ガワーズ3一様ノルムに対する多項式逆定理を証明して、Bu, Gu, Jaffe の正の予想に着目する。また、単一コピーアクセスの制限された設定についても検討し、補助的なメモリキュービットや適応性を必要としない$O(n)$-query Cliffordテスタを与えます。我々はこれを低境界で補い、そのような、潜在的に適応的なシングルコピーアルゴリズムには少なくとも$\Omega(n^{1/4})$クエリが必要であることを証明した。この結果を得るために、クリフォード群の可換体の構造を活用し、独立な興味を持つかもしれないいくつかの技術的ステートメントを得る。

関連論文リスト

The non-Clifford cost of random unitaries [0.2796197251957244]
我々は$t$ドープクリフォード回路のアンサンブルを$n$ qubitsで探索する。厳密な収束境界をユニタリな$k$-設計に向けて確立する。ランダムドープされたクリフォード回路のアンサンブル上で回転する演算子の解析式を導出する。
論文参考訳（メタデータ） (2025-05-15T09:28:10Z)
Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文参考訳（メタデータ） (2025-02-09T22:14:45Z)
Low-depth Clifford circuits approximately solve MaxCut [44.99833362998488]
低深さクリフォード回路に基づくMaxCutの量子インスピレーション近似アルゴリズムを提案する。我々のアルゴリズムは、深さ$O(N)$ Clifford回路を構築することにより、$N$頂点グラフ上のMaxCutの近似解を求める。
論文参考訳（メタデータ） (2023-10-23T15:20:03Z)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
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)
Unitary Subgroup Testing [8.282602586225831]
我々は、自明な部分群として $mathcalG$ あるいは Pauli あるいは Clifford 群や $q$-ary 拡張として問題を研究する。私たちの主な成果は、Pauliテスト、Cliffordテスト、Identityテストの等価性です。
論文参考訳（メタデータ） (2021-04-08T08:12:25Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)
Efficient unitary designs with a system-size independent number of non-Clifford gates [2.387952453171487]
指数的資源を用いて、フル$n$-qubit 群から引き出されたハールランダムなユニタリを生成する。 Unitary $t-designsはHaar-$-thの瞬間を模倣する。ランダムなクリフォード回路の収束時間から、クリフォード群上の一様分布の$t$-番目のモーメントを導出する。
論文参考訳（メタデータ） (2020-02-21T19:41:07Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。