期刊
QUANTUM MACHINE INTELLIGENCE
卷 2, 期 2, 页码 -出版社
SPRINGERNATURE
DOI: 10.1007/s42484-020-00027-5
关键词
Quantum computing; Computational learning theory; Complexity theory
资金
- TopMath Graduate Center of the TUM Graduate School at the Technische Universitat Munchen, Germany
- TopMath Program at the Elite Network of Bavaria
- German Academic Scholarship Foundation (Studienstiftung des deutschen Volkes)
- National Science Foundation (NSF) Graduate Research Fellowship [DGE 1656518]
- German Academic Exchange Service (DAAD) [57381410]
We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential gate complexity of state preparation, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据