Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation

Zongbo Bao; Philippe van Dordrecht; Jonas Helsen

doi:10.1145/3717823.3718201

STOC2025顶会

Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation

Zongbo Bao, Philippe van Dordrecht, Jonas Helsen

DOI 出版方

2025年份

1被引次数

5顶会引用

摘要

We prove a conjecture of Arunachalam & Dutt [3] on the existence of a tolerant stabilizer testing algorithm, and achieve an exponential improvement in the parameters of the tester. Key to our argument is a generalized uncertainty relation for sets of Pauli operators, based on the Lovász theta function. CCS Concepts • Theory of computation → Quantum complexity theory.