2026-07-25T14:29:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18313 2024-03-06T11:01:38Z ddc:004 open_access

Optimal Algorithms for Learning Quantum Phase States Arunachalam, Srinivasan Bravyi, Sergey Dutt, Arkopal Yoder, Theodore J. Tomography binary phase states generalized phase states IQP circuits 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Srinivasan Arunachalam and Sergey Bravyi and Arkopal Dutt and Theodore J. Yoder 2023 Is Part Of LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2023.3 urn:nbn:de:0030-drops-183139 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.3 eng https://creativecommons.org/licenses/by/4.0/legalcode