量子アグノスティックブーストによる深さ3回路の効率的学習
なぜ重要か: 企業や社会への影響が見込まれ、一般メディアにも波及する可能性があります。
arXiv:2509.14461v2において、関数クラス$\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$に関する位相状態の量子アグノスティック学習の研究を開始する。未知のn量子ビット状態$|\psi\rangle$のコピーが与えられ、この状態は、ある$c\in \mathsf{C}$に対して位相状態$|\phi_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$とのフィデリティー$\textsf{opt}$を持つとする。このとき、$|\langle \phi | \psi \rangle|^2 \geq \textsf{opt}-\varepsilon$を満たす$|\phi\rangle$を出力する。この目的のために、以下のクラスに対するアグノスティック学習プロトコルを示す。(i)サイズ$t$の決定木：計算時間は$\textsf{poly}(n,t,1/\varepsilon)$。(これは、$k$-juntaを時間$\textsf{poly}(n,2^k,1/\varepsilon)$でアグノスティック学習できることを意味する。)(ii) $s$-項DNF論理式：計算時間は$\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})$。主な技術的貢献は、弱アグノスティック学習器（$|\langle \phi|\psi\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$を満たすパリティ状態$|\phi\rangle$を出力する）を、強学習器（$|\langle \phi’|\psi\rangle|^2\geq \textsf{opt} – \varepsilon$を満たすパリティ状態の重ね合わせ$|\phi’\rangle$を出力する）に変換する量子アグノスティックブーストプロトコルである。量子アグノスティックブーストを用いて、量子サンプルが与えられた一様PACモデルにおいて、$\textsf{poly}(n)$サイズの深さ3回路（$\textsf{AND}$、$\textsf{OR}$、$\textsf{NOT}$ゲートからなる）を$n^{O(\log \log n \cdot \log(1/\varepsilon))}$時間で学習するアルゴリズムを得る。これは、定数$\varepsilon$に対して準多項式時間である。古典的には、同様の計算量を持つアルゴリズムを得ることがPACモデルにおいて未解決問題であり、本研究は量子サンプルを与えた場合にこれを解決する。
原文（英語）を表示
Title (EN): Efficiently learning depth-3 circuits via quantum agnostic boosting
arXiv:2509.14461v2 Announce Type: replace-cross
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 time $\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\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 a $n^{O(\log \log n \cdot \log(1/\varepsilon))}$-time algorithm for learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform $\textsf{PAC}$ model given quantum examples, which is near-polynomial time for constant $\varepsilon$. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\textsf{PAC}$ model and our work answers this given quantum examples.
Published: 2025-09-24 19:00 UTC