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

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.Source: B. Model · p. 2

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.Source: C. Overview of results · p. 2, B. Model · p. 2
• 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.Source: C. Overview of results · p. 2
• 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)).Source: C. Overview of results · p. 2, Table I · p. 3

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.Source: D. Block-encoding strategy · p. 3, Figure 1 · p. 4

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.Source: E. State preparation · p. 4

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.Source: E. State preparation · p. 4

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.Source: F. Improved state preparation · p. 4, E. State preparation · p. 4

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.Source: F. Improved state preparation · pp. 4–5

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).Source: G. Variations and extensions · p. 5

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.Source: H. Outlook · p. 6

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.Source: §I · p. 6, A. Overview · p. 6

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.Source: B. Select-swap data loading · pp. 6–7
• 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.Source: Figure 3 · p. 7, B. Select-swap data loading · p. 7

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.Source: B. Select-swap data loading · p. 7

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.Source: C. Bucket-brigade data loading · pp. 7–8

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.Source: D. QRAM operation with flags · pp. 8–9
• 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.Source: D. QRAM operation with flags · p. 9

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 δ.Source: Figure 5 · p. 9, D. QRAM operation with flags · p. 10, Figure 6 · p. 10

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.Source: E. QRAM resource estimates · p. 10

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/ϵ)).Source: A. Overview · p. 11

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.Source: B. Rotation angles and binary tree… · pp. 11–13

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.Source: B. Rotation angles and binary tree… · pp. 12–13

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.Source: C. Fixed-precision circuit · pp. 13–15

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.Source: C. Fixed-precision circuit · pp. 14–15

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.Source: C. Fixed-precision circuit · p. 15

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.Source: Figure 9 · p. 14, C. Fixed-precision circuit · p. 15

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.Source: D. Pre-rotated circuit · p. 15

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.Source: D. Pre-rotated circuit · p. 16

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.Source: D. Pre-rotated circuit · p. 16

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.Source: D. Pre-rotated circuit · p. 17

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.Source: E. State preparation resource estimates · p. 18

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.Source: E. State preparation resource estimates · p. 18

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.Source: E. State preparation resource estimates · p. 18

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.Source: Table III · p. 18

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.Source: E. State preparation resource estimates · p. 19

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.Source: B. Fixed precision resources · p. 19, Table IV · p. 19
• 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.Source: B. Fixed precision resources · p. 19

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.Source: C. Pre-rotated resources · p. 20, Table V · p. 20
• 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.Source: C. Pre-rotated resources · p. 20

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.Source: C. Pre-rotated resources · p. 20

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.Source: D. Controlled block-encodings · p. 20, Figure 15 · p. 21

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.Source: A. Overview · p. 20

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.Source: Figure 15 · p. 21

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.Source: C. Gate synthesis error · p. 21

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.Source: C. Gate synthesis error · p. 22

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.Source: D. Overall block-encoding error · p. 22

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.Source: D. Overall block-encoding error · p. 22

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.Source: §VI · pp. 22–23

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.Source: §VI · p. 23

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

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.Source: §3 · p. 26
• Its prepared states place amplitudes involving cos χ and sin χ across paired computational-basis registers indexed by j and k.Source: §3 · pp. 26–27
• The construction differs from Refs. in the rotated subspaces, enabling a controlled rotation followed by the main-text state-preparation procedure.Source: §3 · p. 27

Select-swap

• The select-swap circuit divides data loading into Select and Swap stages, with Swap moving the desired state into the top register.Source: §1 · p. 27
• Choosing Λ = O(1) enables the select-swap architecture to achieve an optimal T-count of O(N).Source: §1 · p. 27

2. Bucket-brigade

• The bucket-brigade circuit routes address qubits from the address space into individual routers in its qubit-based implementation.Source: §2 · p. 27

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.Source: Figure 16 · p. 28

2. Bucket-brigade

• Parallel routing makes each additional address qubit add only six controlled-swap layers, yielding O(m) controlled-swap depth.Source: §2 · p. 27, §28 · p. 28, Figure 17 · p. 29

Gate decompositions

• Fixed-precision resource estimates use phase-incorrect swaps when phases are irrelevant, while pre-rotated estimates use phase-correct swaps.Source: Appendix C · p. 28
• The controlled-swap decomposition for multi-qubit registers has T-depth 4 and can parallelize its G gates and CNOT gates.Source: Figure 21 · p. 30, Figure 22 · p. 31