Learning stabilizer states by Bell sampling
read the original abstract
We show that measuring pairs of qubits in the Bell basis can be used to obtain a simple quantum algorithm for efficiently identifying an unknown stabilizer state of n qubits. The algorithm uses O(n) copies of the input state and fails with exponentially small probability.
This paper has not been read by Pith yet.
Forward citations
Cited by 11 Pith papers
-
Optimal Stabilizer Testing and Learning with Limited Quantum Memory
Stabilizer testing requires Θ(n-k) copies and non-adaptive learning Θ(n²/k) copies with k-qubit memory, removing the testing-learning separation.
-
Complexity of detecting large coefficients in the Pauli basis
Detecting large Pauli coefficients in circuit-prepared quantum states (even pure) is QCMA-complete and not in BQP unless NP ⊆ BQP, resolving an open question on efficient tomography.
-
Heisenberg-limited Hamiltonian learning without short-time control
Heisenberg-limited Hamiltonian learning is achievable with any constant minimum evolution time T per query, attaining optimal 1/ε total-time scaling for logarithmically sparse Hamiltonians.
-
Cloning is as Hard as Learning for Stabilizer States
For n-qubit stabilizer states the optimal sample complexity of approximate cloning is Θ(n), matching the complexity of learning.
-
Fermionic non-Gaussianity via Bell sampling: monotones and efficient quantum algorithms
Defines bridge degree monotone for fermionic non-Gaussianity from Bell-sampling eigenvalues of Lambda, shows non-increase under Gaussian protocols for stronger no-go theorems, and gives polynomial-sample tests for Gau...
-
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.
-
Sector length distributions of recursively definable graph states through analytic combinatorics
Closed-form sector length distributions for recursively definable graph states (paths, cycles, stars, grids) via generating functions, yielding analytical concentratable entanglement, depolarizing fidelity bounds, and...
-
Adaptive Stabilizer State Fidelity Certification
Adaptive gauge selection protocol for stabilizer state fidelity certification that reports full intervals with monotonic tightening and exact recovery on full coverage.
-
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.
-
Classical Simulations of Low Magic Quantum Dynamics
Classical simulation algorithms for low-magic adaptive quantum circuits with high Pauli measurement rates, demonstrated on all-to-all monitored circuits with sub-extensive T-gates to study measurement-induced phase tr...
-
Optimal detection of dissipation in Lindbladian dynamics
A randomized algorithm detects dissipation of magnitude at least epsilon in unknown Lindbladian dynamics with optimal total evolution time O(epsilon^{-1}) under bounded strength and locality assumptions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.