License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2023.3
URN: urn:nbn:de:0030-drops-183139
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18313/
Arunachalam, Srinivasan ;
Bravyi, Sergey ;
Dutt, Arkopal ;
Yoder, Theodore J.
Optimal Algorithms for Learning Quantum Phase States
Abstract
We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2ⁿ basis vectors x with amplitudes proportional to (-1)^{f(x)}, where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Θ(n^d) if we allow separable measurements and Θ(n^{d-1}) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its ?₂ representation (with sample complexity O(2^d sn)), f has Fourier-degree-t (with sample complexity O(2^{2t})), and learning quadratic phase states with ε-global depolarizing noise (with sample complexity O(n^{1+ε})). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.
BibTeX - Entry
@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3,
author = {Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.},
title = {{Optimal Algorithms for Learning Quantum Phase States}},
booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
pages = {3:1--3:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-283-9},
ISSN = {1868-8969},
year = {2023},
volume = {266},
editor = {Fawzi, Omar and Walter, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18313},
URN = {urn:nbn:de:0030-drops-183139},
doi = {10.4230/LIPIcs.TQC.2023.3},
annote = {Keywords: Tomography, binary phase states, generalized phase states, IQP circuits}
}
|
Keywords: |
|
Tomography, binary phase states, generalized phase states, IQP circuits |
|
Collection: |
|
18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
18.07.2023 |
