PaperlayerView exact revision on arXiv

Source-linked AI summary

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

B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, William J. Zeng

arXiv:2206.03505v1quant-ph

TL;DR

Block-encoding dense classical matrices requires accounting for the cost of each QRAM-backed query, not only query complexity. The paper supplies modular circuit constructions and resource estimates, including two QRAM models and a pre-rotated state-preparation routine. The minimal-depth approach achieves O(log(N/epsilon)) T-depth, while the analysis exposes substantial width and parallelism costs.

  • Problem

    Assessing QRAM-based quantum algorithms requires resource estimates for each block-encoding query, not only asymptotic oracle-query counts.

  • Method

    The paper combines QRAM data loading with state preparation to construct Clifford+T block-encodings and compares select-swap and bucket-brigade QRAM models.

  • Results

    The minimal-depth construction achieves O(log(N/epsilon)) T-depth, while the pre-rotated routine improves state-preparation scaling from O(log^2(N/epsilon)) to O(log(N/epsilon)).

  • Takeaways & Limitations

    The modular estimates make the resource trade-offs and costs of accessing large classical datasets explicit for block-encoding-based quantum algorithms.

  • Takeaways & Limitations

    Achieving polylogarithmic depth requires O(N^2) parallel T gates, whose magic-state-distillation and decoding overheads may challenge large-scale implementation.

Abstract

from arXiv · show

We provide modular circuit-level implementations and resource estimates for several methods of block-encoding a dense $N\times N$ matrix of classical data to precision $\epsilon$; the minimal-depth method achieves a $T$-depth of $\mathcal{O}{(\log (N/\epsilon))},$ while the minimal-count method achieves a $T$-count of $\mathcal{O}{(N\log(1/\epsilon))}$. 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 $\mathcal{O}{(\log (N/\epsilon))}$, improving on previous constructions with scaling $\mathcal{O}{(\log^2 (N/\epsilon))}$. 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.

I. INTRODUCTION

The paper develops circuit-level methods and resource estimates for block-encoding dense classical matrices, emphasizing costs beyond oracle-query complexity. It combines QRAM with state-preparation routines and characterizes trade-offs among qubits, T-count, and T-depth.

  • B. Model: QRAM is modeled with select-swap and bucket-brigade circuits, respectively favoring T-gate efficiency and reduced susceptibility to faulty hardware.A select-swap variant also loads a more general single-qubit state controlled by a flag qubit.
  • C. Overview of results: The construction implements block-encoding with Clifford+T circuits optimized alternatively for qubit count, T-count, or T-depth.The work also provides parameterized resource calculations with constant factors.
  • C. Overview of results: O(log(N/epsilon)) T-depth is achieved by the minimal-depth block-encoding construction, while reducing qubits and T-count to O(N) increases T-depth to O(N).The exponentially smaller depth carries O(N^2) ancilla-qubit and total T-count overhead.
  • C. Overview of results: The resource estimates include exact costs for random matrices of sizes 16 × 16, 256 × 256, and 4096 × 4096 at precision epsilon = 0.01.The parameterized table tracks qubits, T-count, and T-depth; Ry and t both scale as O(log(1/epsilon)).
  • D. Block-encoding strategy: Block-encoding is reduced to a product of controlled-state preparation unitaries, implemented by combining QRAM-like data loading with n-qubit state preparation.The construction uses UR to prepare row-dependent states and UL to prepare the corresponding column-side state; for the stated norm choice, UL is ordinary state preparation.

E. State preparation

The paper reviews fixed-precision state preparation and introduces pre-rotated preparation, which reduces T-depth from O(log^2(N/ε)) to O(log(N/ε)) by parallelizing rotations and delaying garbage uncomputation.

  • State-preparation approaches: Fixed-precision preparation performs successive controlled rotations whose angle descriptions are loaded and synthesized at finite precision.Its O(log^2(N/ε)) scaling comes from serial controlled rotations, controlled-swap loading, and rotation synthesis for each angle bit.
  • Controlled-state preparation: Controlled-state preparation must load a control-dependent subset of N−1 rotation angles before ordinary state preparation and unload them afterward.The loading step is a generalized QRAM query and supports both select-swap and bucket-brigade implementations with as little as O(log(N)) T-depth.
  • State-preparation approaches: O(log(N/ε)) T-depth replaces O(log^2(N/ε)) for pre-rotated state preparation and controlled-state preparation.The method pre-applies all possible rotations in parallel, then uses constant-depth controlled-swap networks for the logarithmic sequence of rotations.
  • Pre-rotated preparation: Pre-rotated preparation requires a flag mechanism to uncompute ancillas that were not injected into the state register.A related pre-rotation construction was explored previously, but it was not garbage-free.
  • Block-encoding variations: The broader resource framework supports T-depth–T-count tradeoffs, controlled block-encodings, symmetrized encodings, and q-norm normalization variants.The tunable tradeoff parameter λ enables minimal T-count O(N) with select-swap at λ=0, but the corresponding T-depth is O(N).

H. Outlook

The paper concludes with detailed QRAM and block-encoding resource analyses, while emphasizing that large-scale QRAM-based implementations remain distant from practical hardware. It frames these estimates as guidance for specialized hybrid architectures.

  • Outlook: Large-scale implementation of QRAM-based algorithms on actual hardware remains a significant distance away.The authors present this as a practical boundary for applying their resource estimates.
  • Scope of the work: The manuscript analyzes QRAM operations, data loading, state preparation, block-encoding resources, finite-precision errors, and concluding implications.Technical details and variants are deferred to Appendices A–C.
  • Select-swap data loading: Select-swap leaves garbage containing shuffled or phase-flipped classical data in an ancillary register, although the application does not require uncomputation.The garbage could be removed by copying the data and reversing the loading operation.
  • Select-swap data loading: Select-swap data loading trades depth for width through λ, using s select-control qubits and λ swap-control qubits.The circuit loads classical data into a D-qubit register, with select costing O(2^s) depth and swap costing O(λ) depth.
  • Implementation assumptions: Fanout CNOTs are treated as low-cost architectural primitives in surface-code systems, while architectures restricted to single-target CNOTs require logarithmic-depth decomposition.The resource assumptions therefore depend partly on the available architecture.

C. Bucket-brigade data loading

The bucket-brigade model loads classical data coherently while avoiding garbage and offers a depth–width tradeoff through λ. LOADF extends loading to angle-encoded single-qubit states conditioned on flags, enabling minimal-depth state preparation.

  • Bucket-brigade QRAM: Bucket-brigade QRAM loads classical data without garbage and can trade circuit depth for width using λ.Its motivation is improved noise resilience relative to select-swap QRAM, potentially reducing physical error-correction resources.
  • Flagged loading: LOADF loads cos(θ/2)|0⟩ + sin(θ/2)|1⟩ when both the address and flag select the target entry.The implementation uses doubly controlled rotations and prepares a one-hot ancilla state before applying the selected rotation.
  • Flagged loading: Parallel LOADF copies load D angle states with T-depth independent of D, while multiplying T-count by D.For controlled-state preparation, D is chosen as N −1 so separate flags condition the N −1 angle states.
  • Implementation: LOADF uses arbitrary-state controlled swaps rather than the phase-incorrect construction available for classical-bit loading.Its single-qubit rotations require Clifford+T synthesis whose depth scales as O(log(1/δ)) for precision δ.

E. QRAM resource estimates

The resource analysis compares QRAM and state-preparation implementations across qubit count, T-count, and T-depth, exposing explicit tradeoffs between minimal depth and minimal count. Classical binary-tree preprocessing supplies the rotation angles used by state preparation.

  • QRAM resource tradeoffs: LOADss reaches minimum T-count O(2^n/2) near λ≈n/2, whereas LOADbb requires Ω(2^n) T-count for every λ.For both models, T-depth is minimized at O(n) when λ=n; λ=0 gives minimal qubit count but maximal depth.
  • State-preparation resource tradeoffs: The fixed-precision and pre-rotated constructions use different resource regimes: SS- or BB-QRAM supports minimal T-count, while pre-rotation supports minimal T-depth.The pre-rotated state-preparation T-depth scales as O(log(N/ϵ)), improving over O(log^2(N/ϵ)).
  • Classical preprocessing: The binary tree stores |β_j|^2 and signs at leaves, child sums at internal nodes, and supports updates requiring recomputation of only O(log(N)) nodes.Classically precomputed angles enter the quantum circuit through coherent data loading, avoiding quantum arithmetic for angle calculation.
  • State-preparation construction: State preparation applies successive controlled Y rotations whose angles are determined by binary-tree node values and then corrects amplitude signs with a phase operation.At level w, the tree supplies the conditional angle for the next qubit, culminating in the target amplitudes up to signs.

C. Fixed-precision circuit

The fixed-precision circuit loads finite-bit descriptions of rotation angles and signs, applies controlled rotations, and restores the loaded data. An optimization reduces the swap-network depth from quadratic to linear in n.

  • Fixed-precision preparation: Fixed-precision preparation represents each of N−1 angles with t bits, loads the descriptions, applies controlled Ry rotations, and unloads the data.The input includes N sign bits, and controlled-state preparation loads a control-dependent angle and sign set using LOADss or LOADbb.
  • Controlled-state preparation: Each swap network Sp is controlled only by preceding data bits, allowing the angle data to be selected for the next rotation without fully undoing earlier work.Controlled-state preparation first loads the appropriate angle and sign data for each control setting, then uncomputes the loading operation.
  • Fixed-precision preparation: The circuit restores angle registers and applies a Z operation to the loaded sign bit before completing the state-preparation unitary.This sign-handling step is part of the fixed-precision protocol's final uncomputation sequence.
  • Depth optimization: Optimizing each Sp to O(1) depth reduces the overall swap-network T-depth from O(n^2) to O(n).The optimization uses a single common control for the relevant controlled swaps and avoids reversing the work already performed by Sp−1.

D. Pre-rotated circuit

The pre-rotated circuit encodes all possible rotation angles as amplitudes of ancilla qubits, replacing controlled rotations with Clifford swaps. Its flag mechanism then disentangles garbage and yields logarithmic T-depth.

  • Pre-rotated approach: Pre-rotated preparation achieves T-depth O(log(N/ϵ)), improving over the fixed-precision scaling O(log^2(N/ϵ)).It pre-applies N−1 single-qubit rotations in parallel and then performs the log(N) controlled steps using swaps.
  • Depth and garbage removal: Each Sp can be performed in O(1) T-depth, giving O(log(N)) depth before garbage uncomputation.A flag mechanism adds O(log(N/ϵ)) cost to disentangle the data and garbage registers.
  • Pre-rotated state preparation: Pre-rotated preparation replaces nt controlled-Ry rotations with n Clifford swap gates that inject pre-rotated angle states.The sign bit is incorporated into the angle states, so the separate sign-loading and Z operation can be omitted.
  • Controlled-state preparation: Controlled pre-rotated preparation loads N−1 angle states with LOADF, applies SPF, flips flags for injected angles, and reverses LOADF to reset ancillas.The protocol performs flag computation, reverse loading, and remaining uncomputation to obtain a garbage-free state.

E. State preparation resource estimates

The state-preparation resource estimates decompose costs into rotation synthesis and parallel controlled-swap operations for fixed-precision and pre-rotated constructions. Select-swap implementations preserve logarithmic-depth opportunities, whereas bucket-brigade state preparation loses that parallelism.

  • Controlled preparation: Controlled-state preparation prepends LOAD and LOAD†, or LOADF for the pre-rotated approach, to the state-preparation routine.The corresponding resource accounting uses the controlled-state-preparation circuits shown in the referenced figures.
  • Rotation synthesis: 2nRy gives the total T-depth and T-count contribution from the multiply-controlled-Ry gates.Each of the n multiply-controlled rotations is decomposed into t singly controlled rotations, with the single-qubit synthesis cost denoted Ry.
  • Controlled-swap costs: (2^n−n−1)t+(2^n−1) controlled-swaps occur in fixed-precision state preparation, while 2^n−n−1 occur in the pre-rotated construction.The fixed-precision count includes angle-data and sign-bit shuffling; the pre-rotated version uses parallel controlled-swaps with additional ancillas.
  • Resource parameters: The state-preparation table parameterizes resources by Ry and t, both scaling as O(log(1/epsilon)).Ry is the T-count for synthesizing an arbitrary single-qubit Y rotation, while t stores the classical data precision.
  • State-preparation approach: O(n^2) minimum T-depth makes bucket-brigade state preparation less favorable than the select-swap constructions considered here.Interleaved Ry rotations break the parallelism needed for logarithmic depth, and bucket-brigade versions also have higher constant factors for qubit and T-count.

IV. BLOCK-ENCODING RESOURCE ESTIMATES

The block-encoding estimates expose a depth–count tradeoff across QRAM models and encoding methods. Select-swap fixed-precision circuits can minimize either T-count or T-depth, while pre-rotation improves depth scaling but retains a quadratic T-count lower bound.

  • Fixed-precision resources: O(log(N)) T-depth requires O(N^2) T-count for select-swap fixed precision, whereas O(N) T-count is achievable with O(N) T-depth.The parameter lambda controls this tradeoff: lambda=n minimizes depth, while lambda=0 minimizes T-count for select-swap QRAM.
  • Fixed-precision resources: Bucket-brigade fixed-precision implementations require at least Omega(N^2) T-count in all cases and have higher constant factors than select-swap at minimal depth.Whether bucket-brigade reduces overall physical resources depends on architecture, error correction, and error requirements.
  • Pre-rotated resources: Pre-rotation achieves O(log N + Ry) approximately O(log(N/epsilon)) T-depth, compared with O(Ry t log N) approximately O(log N log^2(1/epsilon)) for fixed precision.The pre-rotated construction is evaluated only in its minimal-depth form and does not trade width for depth.
  • Pre-rotated resources: Pre-rotation still has an Omega(N^2) T-count lower bound because controlled-Ry rotations are required for all N(N−1) angles.The approach also improves constant factors for T-depth and qubit count.
  • Implementation optimization: Replacing Toffolis with Clifford CNOTs in controlled-state preparation saves T-depth 2 and T-count 2N(N−1).This simplification applies because all flags are initialized to 1.

D. Controlled block-encodings

Controlled block-encoding is implemented by conditionally replacing the loaded data with a zero state before state preparation. The construction supports efficient controls while accounting for rounding and gate-synthesis errors in the resulting unitary.

  • Controlled construction: A controlled-swap between the loaded data and a zero-valued QRAM register implements controlled block-encoding without doubling the QRAM size.The construction uses one control qubit, D zero-state ancillas, and one controlled-swap between D-qubit registers.
  • Approximation sources: The implemented unitary differs from exact UA through angle-register rounding and Ry gate-synthesis errors in fixed precision, but only synthesis error in pre-rotation.Thus the pre-rotated construction eliminates the rounding-error contribution.
  • Resource cost: The controlled-swap modification costs D ancilla qubits and D controlled-swap gates, with O(1) T-depth and O(D) T-count.If LOAD produces no garbage, its ancillas can be reused; additional controls support multiply-controlled block-encoding without extra ancillas.
  • Fixed-precision rotations: Fixed-precision controlled rotations load t bits of the rounded angle and apply controlled rotations for each binary precision component.Each controlled-Ry(pi 2^-j) is decomposed into two CNOTs and two single-qubit Ry(pi 2^-(j+1)) rotations.
  • Pre-rotated rotations: Pre-rotation uses 2^n−2 doubly controlled Ry rotations, with nearly all exactly undone and no rounding error.Its total state-preparation error is governed by the decomposition error accumulated over the logarithmic number of rotations.

D. Overall block-encoding error

The error analysis converts target block-encoding precision into angle-register precision and rotation-synthesis accuracy. It also identifies architectural assumptions that affect whether the asymptotic resource estimates are practical.

  • Fixed-precision error: Fixed-precision resources must substitute t=log(alpha pi/epsilon)+log(log(N))+1 and the corresponding Ry synthesis cost to meet error epsilon.The prescribed Ry expression scales with log(alpha/epsilon) and logarithmic corrections in N and epsilon.
  • Pre-rotated error: Pre-rotated implementations require delta_decomp=epsilon/(4 alpha log(N)), with Ry scaling given by the corresponding synthesis-length formula.Unlike fixed precision, this analysis has no rounding-error contribution.
  • Scope and motivation: The paper provides concrete resource counts and system sizes for two QRAM models because classical-data loading is a challenging part of quantum algorithms.The estimates combine QRAM with state preparation for block-encoding and distinguish T-count/depth optimization from noise-resilience considerations.
  • Architectural assumptions: Achieving polylogarithmic depth requires O(N^2) parallel T gates and assumes arbitrarily long-range fanout-CNOT gates can execute in one time step.Magic-state distillation, decoding latency, and lattice-surgery communication qubits may add substantial practical overhead.

Appendix A: Alternative Block-Encoding Strategies

The appendix extends block-encoding to nonsquare or Hermitian matrices and introduces q-norm variants with controlled state-preparation implementations.

  • Block-encoding the Hermitian square matrix ensures a Hermitian, square representation at the cost of one extra qubit.
  • The Frobenius encoding assumes M ≥ N and pads dimensions to powers of two, giving ℓ = m + 1.
  • For the off-diagonal Hermitian construction, the normalization factor is ||A||F rather than 2||A||F.
  • The q-norm block-encoding uses the qth power of the maximum q-norm of any row as its normalization factor.
  • Implementing the q-norm variant requires a controlled rotation by χj, together with LOAD and its adjoint and a controlled rotation.

3. Symmetrized q-norm block-encoding

The symmetrized q-norm construction block-encodes a Hermitian matrix while using state definitions chosen for simpler circuit implementation and integrating with the select-swap data-loading approach.

  • 3. Symmetrized q-norm block-encoding: The symmetrized q-norm construction produces a (µp(A), ⌈log(M + N + 1)⌉, ϵ) block-encoding of the Hermitian matrix.
  • 3. Symmetrized q-norm block-encoding: Its prepared states place amplitudes involving cos χ and sin χ across paired computational-basis registers indexed by j and k.
  • 3. Symmetrized q-norm block-encoding: The construction differs from Refs. in the rotated subspaces, enabling a controlled rotation followed by the main-text state-preparation procedure.
  • Select-swap: The select-swap circuit divides data loading into Select and Swap stages, with Swap moving the desired state into the top register.
  • Select-swap: Choosing Λ = O(1) enables the select-swap architecture to achieve an optimal T-count of O(N).

2. Bucket-brigade

The bucket-brigade QRAM routes address qubits through routers, and parallelization reduces its depth from the naive quadratic scaling to linear scaling in the address size.

  • 2. Bucket-brigade: The bucket-brigade circuit routes address qubits from the address space into individual routers in its qubit-based implementation.
  • Select-swap: The select-swap control register separates s select qubits from λ swap qubits, with 2s fanout CNOTs and 2s+1 multi-controlled Toffoli gates in Select.
  • 2. Bucket-brigade: Parallel routing makes each additional address qubit add only six controlled-swap layers, yielding O(m) controlled-swap depth.
  • Gate decompositions: Fixed-precision resource estimates use phase-incorrect swaps when phases are irrelevant, while pre-rotated estimates use phase-correct swaps.
  • Gate decompositions: The controlled-swap decomposition for multi-qubit registers has T-depth 4 and can parallelize its G gates and CNOT gates.
Loading 2206.03505v1…