Institute for Quantum Information (IQI) Weekly Seminar

Quantum entanglement is considered, by an large, to be a very delicate and nonrobust

phenomenon, that is very hard to maintain in the presence of noise, or non-zero

temperatures. In recent years however, and motivated, in part, by a quest for a quantum

analog of the PCP theorem [1, 2], researches have tried to establish whether or not we

can preserve quantum entanglement at "constant" temperatures that are independent of

system size. This would imply that any quantum state with energy at most, say 0.05 of

the total available energy of the Hamiltonian, would be highly-entangled. However to

date, no such systems were found, and moreover, it became evident that even embedding

local Hamiltonians on robust, albeit "non-physical" topologies, namely expanders, does

not guarantee entanglement robustness [9, 4].

In this talk, we will try to indicate that such robustness may be possible after all, by slightly

relaxing the approximation condition, in a way that is reminiscent of classical approximation

problems. Instead of asking that any quantum state with fractional energy at

most 0.05 be highly-entangled, we just ask that any quantum state violating a fraction at

most 0.05 of constraints is highly-entangled.

I will then construct an infinite family of (logarithmically)-local Hamiltonians, with the

following property of such combinatorial inapproximability: any quantum state that violates

a fraction at most 0.05 of all local terms cannot be even approximately simulated

by classical circuits whose depth is logarithmic. Alternatively, this will show that in a system

of n qubits, it is possible to enforce a robust form of entanglement on the order of W(pn)

qubits, using quantum constraints whose support is polylog(n). Several open questions

follow from this construction that are related both to previous approximability results

[9, 4], the definition of entanglement-robust systems called NLTS [12], quantum locally

testable codes [5], linear distance LDPC codes, and quantum circuit lower bounds.