אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

The folklore on quantum entanglement is that it is a fragile phenomenon and physically very hard to maintain. In quantum complexity theory this raises the possibility that there is no analog of the classical hardness-of-approximation in the quantum setting, namely a quantum analog of the PCP theorem. The problem of whether entanglement is robust-enough to even allow a quantum PCP was formalized by Freedman and Hastings ['13] in a conjecture called NLTS (No Low-Energy Trivial States). NLTS asks whether or not there are local Hamiltonians in which any low-energy state (up to, say 1/5 of the total available energy) is "highly-entangled" namely, has a circuit lower-bound which is diverging in the number of qubits. This is analogous to a statement that any "approximate ground state" of a locally-defined system would be highly entangled.

In this talk I will present an affirmative solution to the NLTS conjecture: there are 7-local Hamiltonians in which any quantum state with energy, say 1/4 , can only be generated by quantum circuits whose depth is logarithmic in the number of qubits.

This suggests that our notion that entanglement is fragile is probably an "artifact" of further constraining our local Hamiltonians to be spatially-local, and shows that in principle, quantum hardness of approximation could exist.

Time allowing - I'll present some of the highlights of the proof which connect quantum robustness to local testability, quantum local testability, and the quantum uncertainty principle.

Joint work with Aram Harrow.