Sample-Query Interconversion of Block Encoding of Unknown Quantum States

Abstract

Block encoding embeds a matrix as a sub-block of a unitary matrix and serves as a fundamental input model for quantum algorithms based on quantum singular value transformation, enabling polynomial transformations of matrices encoded in unitary operators. Block encoding of unknown quantum states can be useful for quantum learning; however, the fundamental limits on converting between unknown quantum states and their block-encoding unitary channels remain poorly understood. In this paper, we investigate this convertibility in both directions. First, we prove that implementing an $\varepsilon$-approximate block-encoding unitary channel of an unknown quantum state requires $\Omega(1/\varepsilon)$ copies of the state, matching known upper bounds up to logarithmic factors. Second, we show that recovering a rank-$r$, $d$-dimensional quantum state $\rho$ given query access to its block-encoding unitary channel generally requires $\Omega((1/\lambda_{\max}(\rho))\sqrt{d/r})$ queries, where $\lambda_{\max}(\rho)$ is the maximum eigenvalue of $\rho$, revealing an unavoidable dependence on the dimension of the state. Our results identify inherent limitations of block encoding as a representation of unknown quantum states and reveal a separation between learning properties of a quantum state and generating the state itself. Using our techniques, we further establish lower bounds for specific state-generation tasks, including ground-state preparation and Gibbs-state preparation.