2025-06-15
Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation
Publication
Publication
Presented at the
57th Annual ACM Symposium on Theory of Computing, STOC 2025 (June 2025), Prague, Czechia
We prove a conjecture of Arunachalam & Dutt 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.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1145/3717823.3718201 | |
| Zwaartekracht QSC Ada Lovelace | |
| 57th Annual ACM Symposium on Theory of Computing, STOC 2025 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Bao, Z., van Dordrecht, P., & Helsen, J. (2025). Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. In Proceedings of the annual ACM symposium on Theory of Computing (pp. 1254–1262). doi:10.1145/3717823.3718201 |
|
