The "curse of dimensionality" is a central bottleneck in efficient processing of quantum information. It arises from the existence of highly complicated quantum states on a modest number of qubits, and the freedom of running intricate protocols with such states. Developing ways to overcome this bottleneck is an outstanding problem in several domains of quantum information theory. The leading proposal in two such domains, quantum communication complexity and quantum Hamiltonian complexity, advances the role of entropy in the analysis of underlying quantum objects.
In this talk, we highlight some positives and negatives of the entropic point of view. We consider quantum Hamiltonian complexity, the study of many-body systems through the lens of quantum information, where ground states play a crucial role. We show that the ``entanglement entropy'' of a large family of ground states is significantly smaller than most quantum states, opening up the possibility of efficient ways to analyze their properties. Our proof develops new ways for approximating ground states with low-degree polynomials of the hamiltonian.
In quantum communication complexity, entropic measures help lower bound the cost of distributed computation. We show severe limitations on the possibility of such entropic measures to tightly capture this cost, by exhibiting distributed tasks that require communication exponentially larger than these measures. This suggests that the characterization of communication cost of quantum protocols may require methods beyond the well-established entropic ones.
