论文标题
Clifford电路可以在且仅当$ \ textsf {rp} = \ textsf {np} $时才能正确学习PAC
Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$
论文作者
论文摘要
给定输入状态，测量和概率的数据集，是否有可能有效预测与量子电路相关的测量概率？ Caro和Datta（2020）的最新工作研究了PAC学习量子电路的问题，从信息理论意义上讲，留下了开放的计算效率问题。特别是，一个有效学习者可能有可能的候选电路类是克利福德电路，因为已知该电路（称为稳定剂状态）生成的相应状态有效地可学习（Rocchetto 2018）。在这里，我们提供了一个负面的结果，表明对CNOT电路的正确学习对于经典学习者来说很难，除非$ \ textsf {rp} = \ textsf {np} $。作为Clifford电路的经典类似物和子集，这自然会导致Clifford Circuits的硬度结果。此外，我们表明，如果$ \ textsf {rp} = \ textsf {np} $，那么对于CNOT和Clifford Circuits来说，将存在有效的正确学习算法。通过类似的参数，我们还发现，当且仅当$ \ textsf {np} \ subseteq \ textsf {rqp} $时，就存在此类电路的有效量子学习器。
Given a dataset of input states, measurements, and probabilities, is it possible to efficiently predict the measurement probabilities associated with a quantum circuit? Recent work of Caro and Datta (2020) studied the problem of PAC learning quantum circuits in an information theoretic sense, leaving open questions of computational efficiency. In particular, one candidate class of circuits for which an efficient learner might have been possible was that of Clifford circuits, since the corresponding set of states generated by such circuits, called stabilizer states, are known to be efficiently PAC learnable (Rocchetto 2018). Here we provide a negative result, showing that proper learning of CNOT circuits is hard for classical learners unless $\textsf{RP} = \textsf{NP}$. As the classical analogue and subset of Clifford circuits, this naturally leads to a hardness result for Clifford circuits as well. Additionally, we show that if $\textsf{RP} = \textsf{NP}$ then there would exist efficient proper learning algorithms for CNOT and Clifford circuits. By similar arguments, we also find that an efficient proper quantum learner for such circuits exists if and only if $\textsf{NP} \subseteq \textsf{RQP}$.
