REVIEW 6 cited by
Optimal algorithms for learning quantum phase states
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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^n$ 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 $\Theta(n^d)$ if we allow separable measurements and $\Theta(n^{d-1})$ if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime $\textsf{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 $\mathbb{F}_2$ 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 $\varepsilon$-global depolarizing noise (with sample complexity $O(n^{1+\varepsilon})$). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP~circuits.
Forward citations
Cited by 6 Pith papers
-
The Keyl-Werner algorithm is not optimal for spectrum estimation
Spectrum estimation of a d-dimensional quantum state is possible with o(d²) copies—specifically O(d² (log log d / log d)²)—beating Keyl–Werner and full tomography.
-
Single-copy stabilizer learning: average case and worst case
Log-depth circuits suffice for average-case single-copy stabilizer learning with t=O(log n), but worst-case adaptive single-copy learning requires exp(t) samples.
-
Energy-independent tomography of Gaussian states
A tomography protocol estimates Gaussian states in trace distance with sample complexity independent of energy (up to doubly logarithmic factors), a doubly exponential improvement over prior methods.
-
Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic
Phase stripping reduces target-state magic to enable O(poly(n)) or O(1) sample fidelity estimation for phase-dominated states using a single fan-out gate plus nonlinear Pauli post-processing.
-
Can scrambling protect quantum state distinguishability under noise?
Noisy 2-design ensembles show a conditional-entropy-governed threshold for distinguishability preservation while post-measured versions collapse exponentially with no protected regime.
-
Efficient Noisy Quantum State and Process Tomography
The paper proposes tomography by estimating only low-weight Pauli coefficients of noisy random-circuit states and processes, with claimed complexity independent of depth and noise strength — but the supporting path-co...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.