[2207.05898] Testing and Learning Quantum Juntas Nearly Optimally
source link: https://arxiv.org/abs/2207.05898
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 13 Jul 2022 (v1), last revised 17 Sep 2022 (this version, v2)]
Testing and Learning Quantum Juntas Nearly Optimally
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.
| Subjects: | Quantum Physics (quant-ph); Computational Complexity (cs.CC) |
| Cite as: | arXiv:2207.05898 [quant-ph] |
| (or arXiv:2207.05898v2 [quant-ph] for this version) | |
| https://doi.org/10.48550/arXiv.2207.05898 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK