Quantum Resources Required to Block-Encode a Matrix of Classical Data
Abstract
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.
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.Attached Files
Submitted - 2206.03505.pdf
Files
Name | Size | Download all |
---|---|---|
md5:e249d600f25a0abeef2d7f6a7cd888bb
|
1.4 MB | Preview Download |
Additional details
- Eprint ID
- 116138
- Resolver ID
- CaltechAUTHORS:20220804-201333134
- Created
-
2022-08-11Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field
- Caltech groups
- AWS Center for Quantum Computing