Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$
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 \cite{2020Caro} studied the problem of PAC learning quantum circuits in an information theoretic sen...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2023-06-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2023-06-07-1036/pdf/ |
| _version_ | 1797809363790856192 |
|---|---|
| author | Daniel Liang |
| author_facet | Daniel Liang |
| author_sort | Daniel Liang |
| collection | DOAJ |
| description | 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 \cite{2020Caro} 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 \cite{rocchetto2018stabiliser}. Here we provide a negative result, showing that proper learning of CNOT circuits with 1/ poly($n$) error is hard for classical learners unless $\textsf{RP = NP}$, ruling out the possibility of strong learners under standard complexity theoretic assumptions. 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 = 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 ⊆ RQP}$. We leave open the problem of hardness for improper learning or $\mathcal{O(1)}$ error to future work. |
| first_indexed | 2024-03-13T06:51:31Z |
| format | Article |
| id | doaj.art-5e6add3866ed486d83b89d7915645c9c |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-03-13T06:51:31Z |
| publishDate | 2023-06-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-5e6add3866ed486d83b89d7915645c9c2023-06-07T13:49:43ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2023-06-017103610.22331/q-2023-06-07-103610.22331/q-2023-06-07-1036Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$Daniel LiangGiven 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 \cite{2020Caro} 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 \cite{rocchetto2018stabiliser}. Here we provide a negative result, showing that proper learning of CNOT circuits with 1/ poly($n$) error is hard for classical learners unless $\textsf{RP = NP}$, ruling out the possibility of strong learners under standard complexity theoretic assumptions. 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 = 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 ⊆ RQP}$. We leave open the problem of hardness for improper learning or $\mathcal{O(1)}$ error to future work.https://quantum-journal.org/papers/q-2023-06-07-1036/pdf/ |
| spellingShingle | Daniel Liang Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ Quantum |
| title | Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ |
| title_full | Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ |
| title_fullStr | Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ |
| title_full_unstemmed | Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ |
| title_short | Clifford Circuits can be Properly PAC Learned if and only if $\textsf{RP}=\textsf{NP}$ |
| title_sort | clifford circuits can be properly pac learned if and only if textsf rp textsf np |
| url | https://quantum-journal.org/papers/q-2023-06-07-1036/pdf/ |
| work_keys_str_mv | AT danielliang cliffordcircuitscanbeproperlypaclearnedifandonlyiftextsfrptextsfnp |