Hot answers tagged

6

I don't know of any function with communication much higher than the $\gamma_2$ bound. However, my intuition of why it is not tight is because the $\gamma_2$-norm is also a lower bound for QCMA communication. See this paper by Klauck for the definition of QCMA communication. To prove the lower bound on QCMA communication using the $\gamma_2$-norm you can ...


3

The norms are the usual norms of a ket vector, i.e. $|||a\rangle||^2 = \langle a|a\rangle$. What did we do on the bottom of page 3? It is really running the argument from the An Analog Analogue paper backwards. Imagine we start from the state $|g_x\rangle$ (a particular ground state of the final Hamiltonian $H_{P}$, related to $|x\rangle$), and evolve ...


Only top voted, non community-wiki answers of a minimum length are eligible