A Caltech Library Service

Quantum Resources Required to Block-Encode a Matrix of Classical Data

Clader, B. David and Dalzell, Alexander M. and Stamatopoulos, Nikitas and Salton, Grant and Berta, Mario and Zeng, William J. (2022) Quantum Resources Required to Block-Encode a Matrix of Classical Data. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We provide modular circuit-level implementations and resource estimates for several methods of block-encoding a dense N×N matrix of classical data to precision ϵ; the minimal-depth method achieves a T-depth of O(log(N/ϵ)), while the minimal-count method achieves a T-count of O(Nlog(1/ϵ)). We examine resource tradeoffs between the different approaches, and we explore implementations of two separate models of quantum random access memory (QRAM). As part of this analysis, we provide a novel state preparation routine with T-depth O(log(N/ϵ)), improving on previous constructions with scaling O(log²(N/ϵ)). Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Dalzell, Alexander M.0000-0002-3756-8500
Salton, Grant0000-0003-3191-0325
Berta, Mario0000-0002-0428-3429
Additional Information:We thank David Bader, Thom Bohdanowicz, Paul Burchard, Connor Hann, Helmut Katzgraber, Rajiv Krishnakumar, Cedric Lin, Shantu Roy, Martin Schuetz, and James Tarantino for helpful discussions. We are especially grateful to Earl Campbell for early collaboration during an initial phase of this project.
Group:AWS Center for Quantum Computing
Record Number:CaltechAUTHORS:20220804-201333134
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116138
Deposited By: George Porter
Deposited On:11 Aug 2022 23:38
Last Modified:11 Aug 2022 23:38

Repository Staff Only: item control page