Fugu-MT 論文翻訳(概要): Efficiently learning depth-3 circuits via quantum agnostic boosting

論文の概要: Efficiently learning depth-3 circuits via quantum agnostic boosting

arxiv url: http://arxiv.org/abs/2509.14461v1
Date: Wed, 17 Sep 2025 22:28:29 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-19 17:26:52.991858
Title: Efficiently learning depth-3 circuits via quantum agnostic boosting
Title（参考訳）: 量子非依存的ブースティングによる深度3回路の学習
Authors: Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael de Oliveira,
Abstract要約: 位相状態の量子非依存学習について、関数クラス $mathsfC$ について研究する。我々の主な技術的貢献は、弱い学習者を変換する量子非依存的なブースティングプロトコルである。我々は、$textsfpoly(n,(s/varepsilon)log log s/varepsilon)$を学ぶための最初の近似時間$nO(log log n)$アルゴリズムを得る。
参考スコア（独自算出の注目度）: 41.9957758385623
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We initiate the study of quantum agnostic learning of phase states with respect to a function class $\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$: given copies of an unknown $n$-qubit state $|\psi\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathsf{C}$, output $|\phi\rangle$ which has fidelity $|\langle \phi | \psi \rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: (i) Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. (ii) $s$-term DNF formulas in near-polynomial time $\textsf{poly}(n,(s/\varepsilon)^{\log \log s/\varepsilon})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state $|\phi\rangle$ such that $|\langle \phi|\psi\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$, into a strong learner which outputs a superposition of parity states $|\phi'\rangle$ such that $|\langle \phi'|\psi\rangle|^2\geq \textsf{opt} - \varepsilon$. Using quantum agnostic boosting, we obtain the first near-polynomial time $n^{O(\log \log n)}$ algorithm for learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform quantum $\textsf{PAC}$ model using quantum examples. Classically, the analogue of efficient learning depth-$3$ circuits (and even depth-$2$ circuits) in the uniform $\textsf{PAC}$ model has been a longstanding open question in computational learning theory. Our work nearly settles this question, when the learner is given quantum examples.
Abstract（参考訳）: 函数クラス $\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$: 未知の$n$-qubit状態 $|\psi\rangle$のコピーが与えられたときの位相状態 $|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathsf{C}$, $|\phi\rangle$, $|\phi\rangle \langle \|\phi_c\rangle \|\psi-f\rangle$: 位相状態 $|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^{c(x)}|x\rangle$ この目的のために、以下のクラスに対して非依存的な学習プロトコルを提供する。 i) Size-$t$ decision tree which run in time $\textsf{poly}(n,t,1/\varepsilon)$ これはまた、$k$-juntas が時間で不可知的に学習できることを意味している。 (ii)$s$-term DNF formulas in near-polynomial time $\textsf{poly}(n,(s/\varepsilon)^{\log \log s/\varepsilon})$ 我々の主な技術的貢献は、弱非依存的学習者(英語版)を出力する量子非依存的学習者(英語版)プロトコルであり、このプロトコルはパリティ状態 $|\langle \phi|\psi\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$ を出力し、パリティ状態 $|\phi'\rangle$ を出力する強い学習者(英語版)へ変換する。量子非依存的なブースティングを用いて、量子例を用いて量子一様量子$\textsf{PAC}$モデルで、最初の近似時間$n^{O(\log \log n)}$アルゴリズムを学習するために、$\textsf{poly}(n)$- size depth-$3$ circuits (構成は$\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates)を得る。古典的には、均一な$\textsf{PAC}$モデルにおける3$の学習深度(および2$の回路)のアナログは、計算学習理論における長年のオープンな問題である。我々の研究は、学習者が量子的な例を与えられるとき、この問題をほぼ解決する。

論文の概要: Efficiently learning depth-3 circuits via quantum agnostic boosting

関連論文リスト