Self-Testing Quantum Error Correcting Codes: Analyzing Computational Hardness

We present a generalization of the tilted Bell inequality for quantum [[n,k,d]] error-correcting codes and explicitly utilize the simplest perfect code, the [[5,1,3]] code, the Steane [[7,1,3]] code, and Shor's [[9,1,3]] code, to demonstrate the self-testing property of their respective codespaces. Additionally, we establish a framework for the proof of self-testing, as detailed in {baccari2020device}, which can be generalized to the codespace of CSS stabilizers. Our method provides a self-testing scheme for cosθ 0̄ + sinθ 1̄, where θ ∈ [0, π/2], and also discusses its experimental application. We also investigate whether such property can be generalized to qudit and show one no-go theorem. We then define a computational problem called ISSELFTEST and describe how this problem formulation can be interpreted as a statement that maximal violation of a specific Bell-type inequality can self-test a particular entanglement subspace. We also discuss the computational complexity of ISSELFTEST in comparison to other classical complexity challenges and some related open problems.