Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $cN$, for some constant $c>0$, where $N$ is the number of qubits. Our reductions are…