Optimal algorithms for learning quantum phase states - Arkopal Dutt | TQC 2023
Channel: Squid: Schools for Quantum Information Development
Date: 23/08/2023

Arkopal Dutt
Optimal algorithms for learning quantum phase states

 https://arxiv.org/pdf/2208.07851.pdf    
We analyze the complexity of learning $latex n$-qubit quantum phase states. A degree-$latex d$ phase state is defined as a superposition of all $latex 2^n$ basis vectors $latex x$ with amplitudes proportional to $latex (-1)^{f(x)}$, where $latex f$ is a degree-$latex d$ Boolean polynomial over $latex n$ variables. We show that the sample complexity of learning an unknown degree-$latex d$ phase state is $latex \Theta(n^d)$ if we allow separable measurements and $latex \Theta(n^{d-1})$ if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime $latex \textsf{poly}(n)$ (for constant $latex d$) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli $latex X$ and $latex 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 $latex f$ has sparsity-$latex s$, degree-$latex d$ in its $latex \mathbb{F}_2$ representation (with sample complexity $latex O(2^d sn)$), $latex f$ has Fourier-degree-$latex t$ (with sample complexity $latex O(2^{2t})$), and learning quadratic phase states with $latex \varepsilon$-global depolarizing noise (with sample complexity $latex O(n^{1+\varepsilon})$). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.

July 26, 2023
--------

TQC 2023 | 24-28 July 2023, University of Aveiro, Portugal
http://tqc-conference.org

18th Conference on the  Theory of Quantum Computation, Communication and Cryptography.

TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.


Organisation:
Squids - Schools for Quantum Information Development  
Universidade de Aveiro: Departamento de Matemática, CIDMA & Fábrica


Sponsors:
Phasecraft, UK
Google Quantum AI, USA
QuSoft, The Netherlands
Quantum for Life Centre, Denmark
Technology Innovation Institute, UAE
ML4Q, Germany
Dulwich Quantum