Polynomial-time tolerant testing stabilizer states

2024/08/12 by Arunachalam, Srinivasan, Dutt, Arkopal · 6 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2408.06289

Abstract

We consider the following task: suppose an algorithm is given copies of an unknown n-qubit quantum state |ψ⟩ promised (i) |ψ⟩ is ε₁-close to a stabilizer state in fidelity or (ii) |ψ⟩ is ε₂-far from all stabilizer states, decide which is the case. We show that for every ε₁>0 and ε₂≤ ε₁^C, there is a \textsfpoly(1/ε₁)-sample and n⋅ \textsfpoly(1/ε₁)-time algorithm that decides which is the case (where C>1 is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-3 norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.

Cited by

• Clifford testing: algorithms and lower bounds
• Learning stabilizer structure of quantum states
• On Estimating the Quantum Tsallis Relative Entropy
• Quantum Higher Order Fourier Analysis and the Clifford Hierarchy
• Adversarially robust quantum state learning and testing
• Operational interpretation of the Stabilizer Entropy

Related

• A note on polynomial-time tolerant testing stabilizer states
• Improved bounds for testing low stabilizer complexity states
• Learning stabilizer structure of quantum states
• Improved Stabilizer Estimation via Bell Difference Sampling
• Single-copy stabilizer testing