PaperlayerView exact revision on arXiv

Source-linked AI summary

Block-encoding structured matrices for data input in quantum computing

Christoph Sünderhauf, Earl Campbell, Joan Camps

arXiv:2302.10949v2quant-ph

TL;DR

Data input can dominate quantum-algorithm runtime, and this paper studies block encoding as an input model for QSVT and related algorithms. It constructs arithmetic-oracle circuits for structured matrices, exploiting sparsity and repeated values; the schemes have matrix-dependent subnormalisations and can yield exponential efficiency gains when structure is sufficient.

  • Problem

    Data input can dominate quantum-algorithm runtime, motivating efficient circuit constructions for structured matrix data used by QSVT and related algorithms.

    Source: §1 · p. 2

  • Method

    The paper constructs several block-encoding schemes using arithmetic descriptions of matrix structure, with labels for distinct values and their repeated occurrences.

    Source: §1 · p. 3, §2.1 · p. 4, §4 · p. 21

  • Results

    The schemes incorporate sparsity in flag-qubit count and repeated values in data-loading cost; sufficient structure can yield exponentially more efficient circuits, while the best scheme depends on the matrix.

    Source: §1 · p. 3, §4 · p. 21

  • Takeaways & Limitations

    For symmetric matrices, the schemes can be adapted to Hermitian block encodings without extra data-loading cost or subnormalisation.

    Source: §4 · p. 21

    No scheme reaches the spectral-norm subnormalisation for arbitrary matrices, and the paper focuses on real matrices with structure in element patterns and positions, not values.

    Source: §4 · p. 21

Abstract

from arXiv · show

The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via block encoding circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix. We present schemes yielding different subnormalisations of the block encoding; a comparison shows that the best choice depends on the specific matrix. The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values, leading to an exponential improvement for certain matrices. We give examples of applying our block encoding schemes to a few families of matrices, including Toeplitz and tridiagonal matrices.

1 Introduction

Data input can limit the speedup of QSVT algorithms, whose matrix input model is block encoding. This work develops block-encoding circuits that exploit sparsity and repeated values in structured matrices.

1 Introduction

  • Data input and readout can severely limit quantum-algorithm speedups, while QSVT uses polynomial transformations of input-matrix singular values.The introduction frames structured-data input as the focus of the work.Source: §1 · p. 2
  • A block encoding embeds a possibly non-unitary matrix A, scaled by subnormalisation α, inside a larger unitary; its A-containing block is selected using flag qubits.The block is selected by initializing and postselecting the flag qubits in |0⟩.Source: §1 · p. 2
  • Arbitrary dense block encodings require O(2^n) T gates for a 2^n × 2^n matrix, and earlier constructions did not optimize for sparse or repeated-value structure.Black-box sparse-matrix constructions also leave oracle implementation unspecified.Source: §1 · pp. 2–3
  • The proposed oracle-based schemes exploit sparsity and repeated values, reduce flag-qubit requirements, and offer different subnormalisations whose best choice depends on the matrix.The work also explains how to implement the required oracles for matrix families as N increases.Source: §1 · p. 3
  • For chemistry applications, block encodings are often built as linear combinations of unitaries using PREPARE and UNPREPARE oracles, a viewpoint the paper connects to other schemes.The authors state that this connection can lead to improved subnormalisation.Source: §1 · p. 3
  • The paper assesses block-encoding cost by T-gate count because T and Toffoli gates are more expensive than Clifford gates in surface-code error correction.The authors note that the circuits are too long for direct execution on current noisy hardware.Source: §1 · p. 3

2 Block-encoding schemes

The section develops block-encoding schemes for real structured matrices with repeated values and arithmetic-described sparsity, including base encodings and two variants evaluated by data-loading cost times subnormalisation. It also describes an optimal PREP/UNPREP choice at p = 1/2 and modifications that yield Hermitian block encodings for symmetric matrices.

2.1.1 Simplified introductory case

  • The simplified encoding has subnormalisation S||A||max and 1 + log2 S flag qubits, and implements the matrix exactly apart from finite rotation accuracy.It assumes equal data multiplicities and row and column sparsities that are powers of two.Source: §2.1.1 · pp. 5–6

2.1.2 Full block encoding

  • For unequal multiplicities and sparsities, padding aligns the index ranges and an out-of-range oracle flags invalid labels; the full scheme uses 2 + log2 S flag qubits.Here S = max(Sc, Sr).Source: §2.1.2 · pp. 6–7
  • When D ≤ N, the base scheme has a lower data-loading-cost–subnormalisation product than the quantum-data-structure scheme, while using 2 + log2 S rather than 3 + log2 N flag qubits versus Gilyén et al. [7].The comparison uses the same subnormalisation for the base scheme and Gilyén et al.; the data-structure scheme’s data-loading cost is N^2 + N items.Source: §2.1.2 · pp. 7–8
  • Unlike the circulant construction [15], which requires each value to appear exactly once per column, this scheme covers other types of structured matrices.Source: §2.1.2 · p. 8

2.2 Preamplified scheme

  • Preamplification separately amplifies two circuit parts, multiplying subnormalisation reductions while increasing data-loading cost; it can improve the product when values vary strongly in magnitude.Whether it outperforms the base scheme, and the best choice of p, depend on the matrix.Source: §2.2 · pp. 8–9

2.3 PREP/UNPREP scheme

  • When D ≤ Sc, Sr and the row/column oracles commute with the rotations, PREP/UNPREP can reduce the base scheme’s subnormalisation.The section extends PREP/UNPREP operators previously used in quantum chemistry Hamiltonian block encodings [17] to more general structured matrices.Source: §2.3 · p. 10
  • PREP/UNPREP requires two data loads, for PREP and UNPREP, but no repeated loading for singular-value amplification.At the optimal p = 1/2, data-loading cost matches the base scheme; otherwise it increases by a factor of 2.Source: §2.3 · pp. 10–11
  • At p = 1/2, PREP/UNPREP has a single matrix-independent optimum, improving subnormalisation while matching the base scheme’s data-loading cost.The subnormalisation improves as p approaches 1/2.Source: §2.3 · pp. 10–11
  • PREP/UNPREP always lowers subnormalisation versus the base scheme, with stronger reductions for widely varying matrix magnitudes; its figure-of-merit advantage over preamplification depends on the matrix.When D ≤ Sc, Sr and the row and column oracles commute with data loading, the authors recommend p = 1/2 over the base scheme.Source: §2.3 · p. 11

2.4 Hermitian block encoding for symmetric matrices

  • For symmetric matrices, a transposition oracle maps each labelled element to its transposed partner; its involution property supports constructing a Hermitian row oracle from the column oracle.On diagonal elements the oracle leaves the label unchanged.Source: §2.4 · p. 11
  • Adding a Z gate makes the base block encoding Hermitian without changing its data-loading cost, subnormalisation, or flag-qubit count.The Z gate does not affect the encoded matrix when the flag qubit is initialized to |0⟩, but makes the full unitary Hermitian.Source: §2.4 · p. 11
  • The Hermitian preamplified counterpart keeps the flag-qubit count and subnormalisation unchanged but adds data-loading cost D for a separate sign oracle.The sign oracle applies the sign of Ad; the two subcircuits to be amplified are made Hermitian conjugates.Source: §2.4 · p. 12
  • The PREP/UNPREP block encoding is already Hermitian at p = 1/2 with matching PREP and UNPREP operators and the specified row oracle; its Hermitian counterpart has the same costs.The sign oracle is integrated into PREP.Source: §2.4 · p. 12
  • A generic construction to make a block encoding Hermitian adds one flag qubit and doubles gate complexity and data-loading cost, with further control overhead.The additional cost is for controlling U and U†.Source: §2.4 · p. 12

3 Example block encodings

This section presents example block encodings that translate matrix-specific sparsity and repeated-value structure into arithmetic labels and oracles, illustrating different data-loading, normalization, and flag-qubit requirements across matrix families. For the 2-dimensional Laplacian, it gives an exact block encoding up to finite data-loading accuracy with O(log N + log Ny) gates, exploiting repeated matrix elements.

3.1 Checkerboard matrix

  • D = 2 data loads suffice for the checkerboard encoding, whose oracles have zero T-gate count and whose base block encoding is Hermitian, with subnormalisation N max(|A0|, |A1|).PREP/UNPREP improves the subnormalisation when matrix elements have varying magnitudes; an out-of-range oracle also adapts the scheme to zeroed corner entries.Source: §3.1 · p. 13

3.2 Toeplitz matrix

  • With 2+log2 D flag qubits, the Toeplitz encoding uses D data loads and logarithmic-in-N Toffoli arithmetic, versus Gilyén et al.'s 3+log2 N flag qubits.The circuit can reuse the overflow qubit as the delete flag, simplifying the Toeplitz encoding.Source: §3.2 · p. 15

3.3 Tridiagonal matrix

  • 4 flag qubits suffice for the tridiagonal encoding, versus Gilyén et al.'s 3+log2 N; its arithmetic Toffoli cost is logarithmic in N, while loading D = 2N items dominates.PREP/UNPREP cannot be applied because S > D and data loading does not commute with the oracles; a further simplification removes the delete flag and out-of-range oracle by loading A_2N−1 = 0.Source: §3.3 · p. 16

3.4 Extended binary tree matrix

  • For arbitrary power-of-two N, the scheme constructs a Hermitian block encoding of the balanced binary-tree adjacency matrix, extending the non-Hermitian N = 8 example considered in [15].The matrix has three distinct values, and PREP/UNPREP is unavailable with the stated oracles because their multiplexed rotations do not commute with the row oracle.Source: §3.4 · pp. 17–18

3.5 2-dimensional Laplacian

  • Three distinct values in the 2-dimensional grid Laplacian are padded to D = 4, while maximum sparsity 5 is padded to S = 8 and maximum multiplicity 2N − 2 to M = 2N.The labeling separates upper- and lower-triangular entries using a high bit of the repetition index.Source: §3.5 · p. 19
  • Splitting the mlo register into log2 Ny- and log2 Nx-bit registers makes the out-of-range conditions easier to implement.The split also simplifies the −Nx term in Oc to a −1 on the log2 Ny-bit register.Source: §3.5 · p. 20
  • When data-loading and row/column oracles commute, PREP/UNPREP improves subnormalisation in the symmetric p = 1/2 case.Source: §3.5 · p. 21
  • The exact 2-dimensional Laplacian block encoding uses O(log N + log Ny) gates, while the approximate approach in [39] appears to scale exponentially worse.The method exploits repeated elements that sparse [7] or dense [10, 11] treatments do not harness, and the matrix is not in the class considered in [15].Source: §3.5 · p. 21

4 Conclusions and Outlook

The paper presents block-encoding schemes built from arithmetic oracles and data loading, with costs shaped by matrix sparsity and repeated values. It illustrates the schemes on four structured matrix families and notes open scope for improving subnormalisation and exploiting further structure.

4 Conclusions and Outlook

  • Arithmetic circuits map a (d, m) labelling of matrix structure to row and column indices, alongside a data-loading oracle.The paper presents base, preamplified, PREP/UNPREP, and Hermitian-extension schemes.Source: §4 · p. 21
  • Sparsity determines flag-qubit requirements, while data loading scales with distinct matrix values; the best subnormalisation scheme depends on the matrix.Symmetric matrices can use Hermitian adaptations without extra data-loading cost or subnormalisation.Source: §4 · p. 21
  • Examples demonstrate the schemes on Toeplitz, tridiagonal, extended binary tree, and 2D Laplacian matrices.The paper hopes the schemes will prove useful for additional matrix families and application areas.Source: §4 · p. 21
  • None of the schemes reaches the spectral-norm lower bound on subnormalisation for arbitrary matrices, and further structure in matrix values could permit more efficient circuits.The stated exactness is up to finite data-loading accuracy and, for preamplification, singular-value-amplification accuracy.Source: §4 · p. 21

A Implementation of data loading step

Data loading supplies matrix-element values to the structure provided by the arithmetic oracles. The appendix uses the number of loaded data items as a stand-in for block-encoding circuit complexity.

A Implementation of data loading step

A.1 Multiplexed rotations

The appendix describes multiplexed rotations for loading values in the base and preamplified schemes. It outlines direct decompositions and a three-step lookup approach, whose QROM cost scales linearly with the number of values D.

A.1 Multiplexed rotations

  • In the base and preamplified schemes, the data-loading oracle implements multiplexed rotations.The rotation angles are given as α_d = 2 arccos A_d/||A||max.Source: §A.1 · p. 25
  • Multiplexed rotations on D values can be decomposed into D uncontrolled rotations and D CNOT gates without ancillas when D is a power of 2.The T cost then includes synthesis of the D arbitrary rotations to accuracy ε.Source: §A.1 · p. 25
  • An alternative three-step implementation loads angle bitvalues into ancillas, rotates the data qubit, then uncomputes the lookup.The angle register uses b qubits with b ∼ log2(1/ε); the passage also describes QROM and select-swap lookup options.Source: §A.1 · pp. 25–26
  • With QROM, the three-step procedure has T cost O(D), so the number of loaded items is a sensible stand-in for circuit length.The three steps are performed in sequence, adding rather than multiplying the rotation-accuracy term and the data-lookup term.Source: §A.1 · p. 26

A.2 State preparation

The PREP/UNPREP scheme merges the data-loading oracle and diffusion operator into a state-preparation operator, loading data as amplitudes rather than multiplexed rotations. State preparation can use multiplexed rotations or alternative methods.

A.2 State preparation

  • PREP/UNPREP merges the data-loading oracle Odata and diffusion operator HS into a state-preparation operator, reducing subnormalisation.Unlike the base and preamplified schemes, it does not load data with multiplexed rotations on a data flag qubit.Source: §A.2 · p. 26
  • An arbitrary state |ψ⟩ can be prepared from |0⟩⊗log2 D using multiplexed rotations whose angles are precomputed from its amplitudes.Source: §A.2 · p. 26
  • Alternative state-preparation methods include coherent alias sampling and prerotation.Source: §A.2 · p. 26

A.3 Data loading oracle in Gilyén et. al.’s sparse scheme

The sparse-scheme data-loading oracle maps row and column indices to a matrix entry’s bitstring, but its implementation is not described in the cited earlier work. For structured matrices, arithmetic can reduce loading to D data values with O(polylog N) overhead.

A.3 Data loading oracle in Gilyén et al.’s sparse scheme

  • The data-loading oracle OA takes row and column indices i and j and loads the b-bit bitstring Aij.Source: §A.3 · p. 26
  • The cited construction does not discuss how to implement OA.Source: §A.3 · p. 26
  • For a structured matrix, the oracle can use only D data loads plus O(polylog N) arithmetic overhead, rather than loading repeated entries separately.Source: §A.3 · p. 26

B Singular value amplification

Singular value amplification uses QSVT to multiply singular values by γ, trading a lower block-encoding subnormalisation for a longer circuit. Numerical Chebyshev truncations confirm the scaling and estimate its constant, while the chosen analytic construction may not give the lowest degree.

B Singular value amplification

  • Amplifying singular values by γ reduces block-encoding subnormalisation by γ while increasing circuit length by roughly γ, up to logarithmic factors and constants.Source: B Singular value amplification · p. 27
  • The degree analysis uses circuit cost multiplied by subnormalisation as a figure of merit, with equation (4) serving as its proxy.The product is motivated as approximately constant under singular value amplification.Source: B Singular value amplification · p. 27
  • For singular values ζi in [0, (1 − δ)/γ], QSVT produces an ε-approximation of γA with relative accuracy ε for each amplified singular value.Source: B Singular value amplification · p. 27
  • Singular value amplification applies to general projected matrices, including uniform amplitude amplification.Source: B Singular value amplification · p. 27
  • Approximately 3 γ/δ log(γ/ε) polynomial degree is required for singular value amplification, with log denoting the natural logarithm.Numerical Chebyshev truncations confirm the asymptotic scaling and estimate its constant factor.Source: B Singular value amplification · p. 28, Figure 2 · p. 29
  • The analytic rectangle-function construction may not yield the lowest degree; outside the accuracy region, the polynomial need only remain bounded by ±1.Source: B Singular value amplification · p. 28

Related papers

Loading 2302.10949v2…