Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c>0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $\Omega(N)$ and resolves the explicitly stated linear-gap question of...