Learning Quantum States and Unitaries of Bounded Gate Complexity
While quantum state tomography is notoriously hard, most states hold little interest to practically minded tomographers. Given that states and unitaries appearing in nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to lea...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2024-10-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.5.040306 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850034416953327616 |
|---|---|
| author | Haimeng Zhao Laura Lewis Ishaan Kannan Yihui Quek Hsin-Yuan Huang Matthias C. Caro |
| author_facet | Haimeng Zhao Laura Lewis Ishaan Kannan Yihui Quek Hsin-Yuan Huang Matthias C. Caro |
| author_sort | Haimeng Zhao |
| collection | DOAJ |
| description | While quantum state tomography is notoriously hard, most states hold little interest to practically minded tomographers. Given that states and unitaries appearing in nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to learn a state generated by a quantum circuit with G two-qubit gates to a small trace distance, a sample complexity scaling linearly in G is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by G gates to a small average-case error scales linearly in G. While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity G must scale exponentially in G. We illustrate how these results establish fundamental limitations on the expressivity of quantum machine-learning models and provide new perspectives on no-free-lunch theorems in unitary learning. Together, our results answer how the complexity of learning quantum states and unitaries relate to the complexity of creating these states and unitaries. |
| format | Article |
| id | doaj-art-730c469988fd4b67b5bce8209329f52e |
| institution | DOAJ |
| issn | 2691-3399 |
| language | English |
| publishDate | 2024-10-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | PRX Quantum |
| spelling | doaj-art-730c469988fd4b67b5bce8209329f52e2025-08-20T02:57:51ZengAmerican Physical SocietyPRX Quantum2691-33992024-10-015404030610.1103/PRXQuantum.5.040306Learning Quantum States and Unitaries of Bounded Gate ComplexityHaimeng ZhaoLaura LewisIshaan KannanYihui QuekHsin-Yuan HuangMatthias C. CaroWhile quantum state tomography is notoriously hard, most states hold little interest to practically minded tomographers. Given that states and unitaries appearing in nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to learn a state generated by a quantum circuit with G two-qubit gates to a small trace distance, a sample complexity scaling linearly in G is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by G gates to a small average-case error scales linearly in G. While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity G must scale exponentially in G. We illustrate how these results establish fundamental limitations on the expressivity of quantum machine-learning models and provide new perspectives on no-free-lunch theorems in unitary learning. Together, our results answer how the complexity of learning quantum states and unitaries relate to the complexity of creating these states and unitaries.http://doi.org/10.1103/PRXQuantum.5.040306 |
| spellingShingle | Haimeng Zhao Laura Lewis Ishaan Kannan Yihui Quek Hsin-Yuan Huang Matthias C. Caro Learning Quantum States and Unitaries of Bounded Gate Complexity PRX Quantum |
| title | Learning Quantum States and Unitaries of Bounded Gate Complexity |
| title_full | Learning Quantum States and Unitaries of Bounded Gate Complexity |
| title_fullStr | Learning Quantum States and Unitaries of Bounded Gate Complexity |
| title_full_unstemmed | Learning Quantum States and Unitaries of Bounded Gate Complexity |
| title_short | Learning Quantum States and Unitaries of Bounded Gate Complexity |
| title_sort | learning quantum states and unitaries of bounded gate complexity |
| url | http://doi.org/10.1103/PRXQuantum.5.040306 |
| work_keys_str_mv | AT haimengzhao learningquantumstatesandunitariesofboundedgatecomplexity AT lauralewis learningquantumstatesandunitariesofboundedgatecomplexity AT ishaankannan learningquantumstatesandunitariesofboundedgatecomplexity AT yihuiquek learningquantumstatesandunitariesofboundedgatecomplexity AT hsinyuanhuang learningquantumstatesandunitariesofboundedgatecomplexity AT matthiasccaro learningquantumstatesandunitariesofboundedgatecomplexity |