We prove a \\emph{query complexity} lower bound for approximating the top $r$\ndimensional eigenspace of a matrix. We consider an oracle model where, given a\nsymmetric matrix $\\mathbf{M} \\in \\mathbb{R}^{d \\times d}$, an algorithm\n$\\mathsf{Alg}$ is allowed to make $\\mathsf{T}$ exact queries of the form\n$\\mathsf{w}^{(i)} = \\mathbf{M} \\mathsf{v}^{(i)}$ for $i$ in\n$\\{1,...,\\mathsf{T}\\}$, where $\\mathsf{v}^{(i)}$ is drawn from a distribution\nwhich depends arbitrarily on the past queries and measurements\n$\\{\\mathsf{v}^{(j)},\\mathsf{w}^{(i)}\\}_{1 \\le j \\le i-1}$. We show that for\nevery $\\mathtt{gap} \\in (0,1/2]$, there exists a distribution over matrices\n$\\mathbf{M}$ for which 1) $\\mathrm{gap}_r(\\mathbf{M}) = \\Omega(\\mathtt{gap})$\n(where $\\mathrm{gap}_r(\\mathbf{M})$ is the normalized gap between the $r$ and\n$r+1$-st largest-magnitude eigenvector of $\\mathbf{M}$), and 2) any algorithm\n$\\mathsf{Alg}$ which takes fewer than $\\mathrm{const} \\times \\frac{r \\log\nd}{\\sqrt{\\mathtt{gap}}}$ queries fails (with overwhelming probability) to\nidentity a matrix $\\widehat{\\mathsf{V}} \\in \\mathbb{R}^{d \\times r}$ with\northonormal columns for which $\\langle \\widehat{\\mathsf{V}}, \\mathbf{M}\n\\widehat{\\mathsf{V}}\\rangle \\ge (1 - \\mathrm{const} \\times\n\\mathtt{gap})\\sum_{i=1}^r \\lambda_i(\\mathbf{M})$. Our bound requires only that\n$d$ is a small polynomial in $1/\\mathtt{gap}$ and $r$, and matches the upper\nbounds of Musco and Musco '15. Moreover, it establishes a strict separation\nbetween convex optimization and \\emph{randomized}, "strict-saddle" non-convex\noptimization of which PCA is a canonical example: in the former, first-order\nmethods can have dimension-free iteration complexity, whereas in PCA, the\niteration complexity of gradient-based methods must necessarily grow with the\ndimension.\n