論文の概要: Nearly Optimal Algorithms for Testing and Learning Quantum Junta
Channels
- arxiv url: http://arxiv.org/abs/2305.12097v2
- Date: Thu, 8 Jun 2023 18:34:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 16:33:59.777307
- Title: Nearly Optimal Algorithms for Testing and Learning Quantum Junta
Channels
- Title（参考訳）: 量子ジュンタチャネルのテストと学習のための近似最適アルゴリズム
- Authors: Zongbo Bao and Penghui Yao
- Abstract要約: 我々は、$n$-qubitから$n$-qubitの量子チャネルが$n$-qubitの少なくとも$k$で非自明に作用する、量子$k$-juntaチャネルのテストと学習の問題を考察する。
- 参考スコア（独自算出の注目度）: 5.076419064097734
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problems of testing and learning quantum $k$-junta channels,
which are $n$-qubit to $n$-qubit quantum channels acting non-trivially on at
most $k$ out of $n$ qubits and leaving the rest of qubits unchanged. We show
the following.
1. An $\widetilde{O}\left(\sqrt{k}\right)$-query algorithm to distinguish
whether the given channel is $k$-junta channel or is far from any $k$-junta
channels, and a lower bound $\Omega\left(\sqrt{k}\right)$ on the number of
queries;
2. An $\widetilde{O}\left(4^k\right)$-query algorithm to learn a $k$-junta
channel, and a lower bound $\Omega\left(4^k/k\right)$ on the number of queries.
This answers an open problem raised by Chen et al. (2023). In order to settle
these problems, we develop a Fourier analysis framework over the space of
superoperators and prove several fundamental properties, which extends the
Fourier analysis over the space of operators introduced in Montanaro and
Osborne (2010).
- Abstract（参考訳）: 我々は、$n$-qubitから$n$-qubitの量子チャネルである$n$-juntaチャネルのテストと学習の問題を、$n$-qubitsの少なくとも$k$で非自明に作用し、残りの量子ビットは変わらないと考える。
以下に示す。
1. $\widetilde{o}\left(\sqrt{k}\right)$-queryアルゴリズムは、与えられたチャンネルが$k$-juntaチャンネルであるか、あるいは$k$-juntaチャネルから遠く、下限の$\omega\left(\sqrt{k}\right)$がクエリ数で、$\widetilde{o}\left(4^k\right)$-queryアルゴリズムが$k$-juntaチャンネルを学習し、下限の$\omega\left(4^k/k\right)$がクエリ数で区別する。
これは Chen らによって提起された開問題 (2023) に答える。
これらの問題を解決するため、超作用素空間上のフーリエ解析フレームワークを開発し、モンタナロとオズボーンで導入された作用素の空間上でフーリエ解析を拡張するいくつかの基本的な性質を証明した(2010年)。
関連論文リスト
- Tolerant Quantum Junta Testing [0.0]
耐久ジャンタテストは標準バージョンよりも一般的で難しい。
我々は、ユニタリが$epsilon$-juntaか、または任意の量子$k$-juntaから$epsilon$-farかを決定する最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2024-11-04T16:34:50Z) - Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
本稿では,量子ジャンタ分布の学習問題,量子カウンター部,量子ジャンタ状態,QAC$0$回路について考察する。
誤差$varepsilon$を全変動距離で学習できることが示される。
また、$Omega(4k+log (n)/varepsilon2)$コピーの低い境界も証明します。
論文 参考訳（メタデータ） (2024-10-21T09:39:20Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳（メタデータ） (2023-02-20T19:11:44Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳（メタデータ） (2022-12-19T09:36:33Z) - Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
量子量$k$-juntasの検証と学習の問題を考察する。
a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。
我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
論文 参考訳（メタデータ） (2022-07-13T00:11:14Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。