論文の概要: Testing and Learning Quantum Juntas Nearly Optimally
- arxiv url: http://arxiv.org/abs/2207.05898v3
- Date: Fri, 27 Oct 2023 06:36:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-30 18:54:15.655432
- Title: Testing and Learning Quantum Juntas Nearly Optimally
- Title（参考訳）: 量子ジュータをほぼ最適にテストし学習する
- Authors: Thomas Chen, Shivam Nadimpalli, Henry Yuen
- Abstract要約: 量子量$k$-juntasの検証と学習の問題を考察する。
a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。
我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
- 参考スコア（独自算出の注目度）: 3.030969076856776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of testing and learning quantum $k$-juntas: $n$-qubit
unitary matrices which act non-trivially on just $k$ of the $n$ qubits and as
the identity on the rest. As our main algorithmic results, we give (a) a
$\widetilde{O}(\sqrt{k})$-query quantum algorithm that can distinguish quantum
$k$-juntas from unitary matrices that are "far" from every quantum $k$-junta;
and (b) a $O(4^k)$-query algorithm to learn quantum $k$-juntas. We complement
our upper bounds for testing quantum $k$-juntas and learning quantum $k$-juntas
with near-matching lower bounds of $\Omega(\sqrt{k})$ and
$\Omega(\frac{4^k}{k})$, respectively. Our techniques are Fourier-analytic and
make use of a notion of influence of qubits on unitaries.
- Abstract（参考訳）: 量子$k$-juntas:$n$-qubitユニタリ行列は、$n$ qubitsのわずか$k$で非自明に作用し、残りはアイデンティティとして機能する。
アルゴリズムの主な結果として、私たちは
a)$\widetilde{O}(\sqrt{k})$-query量子アルゴリズムで、量子$k$-juntasと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。
(b)量子$k$-juntasを学ぶための$O(4^k)$-queryアルゴリズム。
我々は、量子$k$-juntasのテストと量子$k$-juntasを、それぞれ$\Omega(\sqrt{k})$と$\Omega(\frac{4^k}{k})$のほぼ一致する下界で学習するための上限を補完する。
我々の手法はフーリエ解析であり、ユニタリに対するキュービットの影響の概念を利用する。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳（メタデータ） (2024-01-29T23:23:27Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
本稿では, 加算誤差$varepsilon$内のトレース距離を, ランク$r$の混合量子状態間で推定する効率的な量子アルゴリズムを提案する。
低ランクトレース距離推定の判定版が$mathsfBQP$-completeであることを示す。
論文 参考訳（メタデータ） (2023-01-17T10:16:14Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
論文 参考訳（メタデータ） (2022-06-01T03:40:56Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
論文 参考訳（メタデータ） (2021-11-10T19:03:49Z) - Sample Complexity of Learning Quantum Circuits [4.329298109272386]
物理量子回路は、経験的リスク最小化により、量子コンピュータ上でPACを学習可能であることを示す。
我々の結果は、理論と実験の両方において量子機械学習のための貴重なガイドを提供する。
論文 参考訳（メタデータ） (2021-07-19T18:00:04Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。
我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-16T13:57:01Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。