Fully tolerant product state testing and closest product state learning
Abstract
We address the problem of testing whether an unknown n-qudit state ρ is a-close to a product state or b-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an n-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of [n] into q parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor O(1/q) larger. This reduces the problem to tolerant testing of q parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural k-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester. We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in Õ((nd)2) 2Õ(1/ε8) copies of the unknown state and produces an ε-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
Related
- Fast Fault-Tolerant Decoders for Hypergraph Product and Lifted-Product Codes
- Verified Pauli-Product Measurement Compilation for Fault-Tolerant Quantum Computation
- Robust self-testing of nonmaximal entanglement from a reduced inner product game
- Learning unknown stabilizer codes using product measurements
- Efficient Learning of Clifford-Scrambled Product States
BibTeX
@misc{bao2026fully,
title = {{Fully tolerant product state testing and closest product state learning}},
author = {Zongbo Bao and Jonas Helsen and Tuyen Nguyen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01979},
eprint = {2610.01979},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01979},
}
RIS
TY - UNPB
TI - Fully tolerant product state testing and closest product state learning
AU - Zongbo Bao
AU - Jonas Helsen
AU - Tuyen Nguyen
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01979
UR - https://arxiv.org/abs/2610.01979
AB - We address the problem of testing whether an unknown n-qudit state ρ is a-close to a product state or b-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an n-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of [n] into q parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor O(1/q) larger. This reduces the problem to tolerant testing of q parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural k-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester. We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in Õ((nd)^2) 2^Õ(1/ε^8) copies of the unknown state and produces an ε-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
ER -