The zero-error capacity of a channel (or “Shannon capacity of a graph”) quantifies how much information can be transmitted with no risk of error. In contrast to the Shannon capacity of achannel, the zero-error capacity has not even been shown to be computable: we have no convergent upper bounds. In this work, we present a new quantity, the zero-errorunitarycapacity, and show that it can be succinctly represented as the tensor product value of a quantum game. By studying the structure of finite automata, we show that the unitary capacity is within a controllable factor of the zero-error capacity. This allows new upper bounds through the sum-of-squares hierarchy, which converges to the commuting operator value of the game. Under the conjecture that the commuting operator and tensor product value of this game are equal, this would yield an algorithm for computing the zero-error capacity.

Abstract Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum state tomography, we show that PSD permanents are NP-hard to approximate within a constant factor, and so admit no polynomial-time approximation scheme (unless P = NP). We also establish that several natural tasks in quantum state tomography, even approximately, are NP-hard in the dimension of the Hilbert space. These state tomography tasks therefore remain hard even with only logarithmically few qubits.

Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum state tomography, we show that PSD permanents are NP-hard to approximate within a constant factor, and so admit no polynomial-time approximation scheme (unless P=NP). We also establish that several natural tasks in quantum state tomography, even approximately, are NP-hard in the dimension of the Hilbert space. These state tomography tasks therefore remain hard even with only logarithmically few qubits.