論文の概要: Efficient Quantum State Identity Testing
- arxiv url: http://arxiv.org/abs/2610.04597v1
- Date: Sat, 03 Oct 2026 15:33:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-11 18:34:26.954433
- Title: Efficient Quantum State Identity Testing
- Title（参考訳）: 効率的な量子状態同一性テスト
- Abstract要約: 回路深度とサンプル複雑度を相補的に保証する2つの量子アルゴリズムを提案する。
1つは、並列スワップテストを使用して一定の深さで実行し、各入力状態のコピーを$O(log(n/)log(2/))で、少なくとも1-$の確率で成功する。
第二に、サンプルの複雑さを$O(log(n/))$に減らし、Jucys--Murphy 要素と Schur サンプリングに関する分析を行う。
- 参考スコア（独自算出の注目度）: 0.7639235704257864
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\in(0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log(n/δ)\log(2/δ))$ copies of each input state to succeed with probability at least $1-δ$. The second uses the Schur transform to reduce the sample complexity to $O(\log(n/δ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $Ω(\log(n/δ))$ for any quantum algorithm with failure probability at most $δ\le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $δ$ for fixed $\varepsilon$.
- Abstract（参考訳）: 我々は以下の量子状態のアイデンティティ問題を研究する:$n$未知の純量子状態のコピーへのアクセスが与えられた場合、各ペアが少なくとも1-\varepsilon$を持つか、あるペアが少なくとも1-\varepsilon$を持つかを決定することが目的である。
この問題は、以前の研究で考慮された同一または直交の約束を緩和する。
任意の固定重なりパラメータ $\varepsilon\in(0,1/4)$ に対して、回路深さとサンプリング複雑性を相補的に保証する2つの量子アルゴリズムを提案する。
1つは並列スワップテストを用いて一定深さで実行し、各入力状態のコピーを$O(\log(n/δ)\log(2/δ))$とすることで、少なくとも1-δ$の確率で成功する。
2つ目は、シュール変換を用いてサンプルの複雑さを$O(\log(n/δ))$に減らし、ジューシー-マーフィー要素とシュールサンプリングに関する分析を行う。
また、任意の定数$c>0$に対して、失敗確率が最大$δ\le 1/2-c$の任意の量子アルゴリズムに対して$Ω(\log(n/δ))$の一致するサンプル複雑性の低い境界を証明し、固定された$\varepsilon$に対して$n$と$δ$の両方の最適な依存を達成することを証明した。
関連論文リスト
- Learning Sparse Quantum States [0.8122270502556375]
我々は、$n$-qubit $k$-sparse純量子状態を学ぶための最初の近似アルゴリズムを与える。
我々は、$tildeO(k/varepsilon)$状態のコピーと$tildeO(kn/varepsilon)$時間を使って、高い確率で少なくとも1-varepsilon$を得る。
例えば、ほぼ最適な$tildeO(kr/varepsilon)$サンプル複雑性を持つアルゴリズムも得られ、$k$-sparse rank-$rを学習する。
論文 参考訳（メタデータ） (2026-09-10T21:28:21Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Replicability in Reinforcement Learning [46.89386344741442]
生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。
ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
論文 参考訳（メタデータ） (2023-05-31T05:16:23Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - 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) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。
また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文 参考訳（メタデータ） (2020-11-22T01:22:37Z) - Multi-reference alignment in high dimensions: sample complexity and
phase transition [31.841289319809814]
マルチ参照アライメントは、円形にシフトしたノイズの多いコピーから$mathbbRL$のシグナルを推定する。
単一粒子の低温電子顕微鏡により、高次元状態における問題のサンプルの複雑さを解析した。
我々の分析では、パラメータ $alpha = L/(sigma2log L)$ で制御される相転移現象を発見し、$sigma2$ はノイズの分散である。
論文 参考訳（メタデータ） (2020-07-22T15:04:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。