The 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, revealing an unavoidable dependence on the dimension of the state.
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.
Quantum channels can be characterized by their action on an orthogonal operator basis, where these operators are related to observable properties of the quantum system. For qudit and multimode bosonic systems, this is encoded respectively in the Heisenberg--Weyl transfer matrix estimated from the Choi-state, and in the characteristic-function transfer map estimated from a two-mode squeezed vacuum based Choi-state. We derive sample-complexity bounds for estimating entries of the transfer matrix/map to additive accuracy $\epsilon$ with success probability $\ge1-\delta$, under different resources: access to the complex-conjugate channel $\mathcal{E}^*$ and/or parallel access to $c$ copies. In all settings, the learner uses parallel channel calls with adaptively chosen, ancilla-assisted input states and measurements. Absolute values of transfer-matrix entries can be learned efficiently with simultaneous access to $\mathcal{E}$ and $\mathcal{E}^*$, with tight scaling $\epsilon^{-4}$. Without conjugate access, any $c<d$ copies are insufficient for efficient learning, requiring sample complexity exponential in the number of ($d$-level) qudits $n$ (for prime $d$). Efficiency is recovered at $c=d$, with tight scaling $\epsilon^{-2d}$. For bosonic systems, exponential sample complexity holds in terms of an effective dimension induced by an energy constraint for all $c=O(1/\epsilon)$. Although the task is learning a particular state, these bounds carry stronger implications than standard state-learning bounds since the learner controls the inputs and has ancillary assistance. This establishes a hierarchy of channel-learning resources: self-complex-conjugate channels require two-copy ancilla-assisted access for efficient learning, while for every square-free $d$, some channels require $d$-copy access. As a corollary, we derive tighter lower bounds for state learning with limited multi-copy access.
M. Subramanian, Hyukgun Kwon, Liang Jiang· 0 citations
A Clifford+T quantum circuit construction that approximately implements any classically specified unitary to within error $\epsilon$ and achieves a worst-case $T$-count with leading exponential scaling of $2^{5n/4}$ whenever $\log(1/\epsilon)=\operatorname{poly}(n)$.
A closed-form expression for the optimal fidelity is derived and it is proved that a parallel protocol is optimal even among general quantum superchannels, including adaptive and indefinite-causal-order strategies.
This work studies the problem of estimating the state frame potential of order $t$ to within additive error $\varepsilon$ under three progressively weaker access models: (i) query access to a multi-state-preparation oracle, (ii) general sample access, and (iii) single-copy sample access.
Jing Bao, Wang Fang, Y. Nakata et al.· 0 citations
Random quantum objects are powerful resources for quantum information processing, yet exact Haar randomness is costly and typically unnecessary. We introduce an explicit sparse commuting circuit ensemble on $n$ qubits that reproduces low-order Haar moments in the stringent relative-error sense. The circuit consists of a sparse Clifford phase layer followed by independent single-qubit Clifford gates. Acting on a simple product state, the resulting ensemble forms $\epsilon$-approximate projective $2$- and $3$-designs in relative error, with the required logarithmic interaction degree being asymptotically optimal within this circuit family. It admits an ancilla-free implementation of quantum depth $O(\log(n/\epsilon))$ on an all-to-all architecture, as well as an adaptive constant-depth implementation---in fact, depth seven---using $O(n\log(n/\epsilon))$ ancilla qubits. Departing from existing shallow-design paradigms, our analysis exploits the intrinsic moment structure of commuting phase circuits; at third order, this requires a new block decomposition and combinatorial analysis that also suggests a route toward higher-order shallow designs. Our results show that precise Haar-like statistics can emerge from sparse commuting dynamics with remarkably low quantum resources, with applications to randomized characterization, quantum metrology, quantum algorithms, and many-body physics.
Qing-Yue Zhang, Jun-Jie Chen, Zhou You et al.· 0 citations
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping $n$ to $m$ qubits, we give a QPSM protocol with quantum communication $m$, using exponential pre-shared entanglement. In particular, constant-output channels have $O(1)$ quantum communication, and classical-output channels require no quantum communication. (2) With $O(n)$ pre-shared entanglement, every one-qubit-output channel has an $O(n)$-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant $c>0$ for which any protocol with at most $cn$ pre-shared entanglement requires $\Omega(n)$ quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with $O(n)$ pre-shared entangled qubits and only $O(1)$ quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
Tom Gur, Mi-Ying Huang, Eric Tang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
