Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which -- due to no-cloning quantum postulate -- loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known PAC framework. Based on that, we propose a quantum analogous of the ERM algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.
翻译:几十年来,传统的资料来源和编码理论的传统信息理论一直用于学习和有效地从数据中提取信息。我们建议进一步一步,为从量数据中学习古典模式提供一个理论基础。然而,为了为这种概括化打下基础,存在若干障碍。首先,古典数据必须由Hilbert空间的密度操作器取代。因此,与州地形学等不同的是,我们的样本是i.d.密度操作器。第二个挑战更为深远,因为我们必须认识到,我们与量数据状态的唯一互动是通过测量(由于不调量子假设),在测量后会丢失信息。铭记这一点,我们提出了众所周知的PAC框架的量子对应。在此基础上,我们提出了类似于机构计算算法的量来学习测算假想课。然后,我们在量抽样复杂量概念类别上设定了量子样本的上限。