# Tag Info

The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\... 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 ... 3 The spectral norm$||H||$determines the maximum energy involved in driving the evolution of the quantum system and thus the quantum computation. Any quantum evolution could be sped-up by a factor of$\lambda$by simply driving the system with Hamiltonian$\lambda H\$ as a simple consequence of Schrödinger's equation. The energy involved is simply another ...