Hot answers tagged

8

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 ...


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