Source-linked AI summary
Block encoding of semiseparable matrices via their generators
Giacomo Antonioli, Gianna M. Del Corso, Roel Van Beeumen
TL;DR
Generator-representable semiseparable matrices are dense yet specified by only two vectors, motivating an explicit block encoding directly from those generators. The construction uses cyclic shifts, swaps, and Hadamard gates; for N = 2^n it achieves polylogarithmic depth with 2n + 2 ancillas. Its block-encoding scale is 2√N, and its error depends on generator state-preparation accuracy.
Problem
Although earlier structured-matrix encodings exist, the prior encoding for generator-representable semiseparable matrices uses a factorization whose subnormalization and error grow as O(N^2).
Source: §1 · p. 2Method
Results
2√N subnormalization, 2n + 2 ancillas, O(polylog N) depth, and error 2√2 ε for state-preparation accuracy ε.
Source: §9 · p. 26Takeaways & Limitations
The same construction extends to unsymmetric one-pair matrices using controlled state preparation and a suitable rotation on the triangular qubit.
Source: §9 · p. 26For the unsymmetric case, independently unit-normalizing all four generators generally breaks diagonal compatibility unless the two generator-norm products coincide.
Source: §6 · p. 18
Abstract
from arXiv · showhide
We present an explicit quantum circuit that constructs a block encoding of a generator-representable semiseparable (one-pair) matrix directly from its two generators. For an $N\times N$ semiseparable matrix with $N=2^{n}$, the circuit uses $2n+2$ ancilla qubits and has $O({\rm polylog} N)$ depth, and it realizes a $(2\sqrt{N},\,2n+2,\,2 \sqrt{2}\ \varepsilon)$-block encoding, where $\varepsilon$ is controlled by the accuracy of the state-preparation routines that load the generators. The building blocks of the circuit are cyclic shifts, swaps, and Hadamard gates, each admitting an efficient implementation through the binary decomposition of the relevant indices.
1. Introduction.
The introduction places generator-representable semiseparable matrices among data-sparse but dense structured matrices, and presents a direct encoding from their two generators. The proposed construction avoids the earlier factorization-based approach and reduces its resource costs.
1. Introduction.
- Prior work encoded circulant, Toeplitz, and Hankel matrices using generators and quantum Fourier transform connections, and displacement-structured matrices using shift decompositions.Other approaches use arithmetic descriptions of sparsity and repeated values [25].Source: §1 · p. 1
- For hierarchical low-rank kernel matrices, prior methods combine encodings of low-rank blocks or reduce oracle access from O(N^2) to O(N) entries.The introduction argues that data sparsity, rather than nonzero count, governs quantum cost, as it does classical complexity.Source: §1 · p. 2
- The direct construction uses O(polylog N) depth and 2n + 2 ancillas, with subnormalization 2√N independently of N’s matrix structure.The earlier factorization-based encoding has subnormalization and error that grow as O(N^2).Source: §1 · p. 2
- Generator-representable semiseparable matrices are dense, full-rank matrices specified by two length-N vectors.The introduction cites applications including boundary-value Green’s functions, covariance matrices, mechanical vibrations, and orthogonal polynomials.Source: §1 · p. 2
- The paper proceeds from quantum preliminaries and matrix definitions to building blocks, symmetric and unsymmetric encodings, comparisons, experiments, and conclusions.The preliminaries are included for readers with numerical linear algebra backgrounds and limited quantum-computing experience.Source: §1 · p. 2, §2 · p. 2
2. Quantum Computing preliminaries.
The preliminaries introduce the qubit and gate conventions used in the paper, then define block encoding as embedding a scaled target matrix in a unitary’s leading block.
2. Quantum Computing preliminaries.
- An n-qubit register has computational basis states indexed by integers through their n-bit binary expansions and represents a vector in C^N, where N = 2^n.Its joint state carries 2^n complex amplitudes.Source: §2 · p. 3
- The circuits use single- and two-qubit gates, including CNOT and SWAP; a controlled gate applies its target operation only on the selected control state.C-SWAP conditionally exchanges two target qubits according to a control qubit.Source: §2 · p. 3
- A block encoding embeds A/α as the top-left block of a larger unitary, with α at least the spectral norm of A.The formal definition specifies an ancilla register and an approximation error.Source: §2 · pp. 3–4
3. Semiseparable Matrices.
This section defines the one-pair semiseparable class and situates it within related matrix structures. Its symmetric form is specified by two generators, while the unsymmetric form uses two generator pairs.
3. Semiseparable Matrices.
- A one-pair matrix S(u,v) is symmetric and is specified by two length-N vectors whose products determine its entries.Its entries use u_i v_j for i ≤ j and v_i u_j for i ≥ j.Source: §3 · p. 4
- The inverse of an irreducible symmetric tridiagonal matrix is a one-pair matrix, and the inverse of an invertible one-pair matrix is irreducible symmetric tridiagonal.The tridiagonal off-diagonal entries must be nonzero.Source: §3 · p. 4
- The unsymmetric analogue uses independent generator pairs for the two triangular parts and includes inverses of nonsymmetric irreducible tridiagonal matrices.The four generators must satisfy diagonal compatibility u_i v_i = x_i y_i.Source: §3 · pp. 4–5
- Semiseparable matrices have rank-at-most-one triangular submatrices, while quasiseparable matrices leave the diagonal free and HODLR/HSS impose bounded off-diagonal rank hierarchically.The paper targets the smallest class in the stated hierarchy; its first inclusion is strict because nonzero diagonal matrices are semiseparable but not generator-representable.Source: §3 · p. 5
4. Building blocks.
The building blocks construct structured shifts and permutations from binary-index-controlled operations. Together they discard unwanted generator products and route the surviving matrix entries into their intended positions.
4.1. The Cyclic shift and its circuit.
- The cyclic shift and its inverse permute basis entries in opposite cyclic directions and are implemented with cascades of multi-controlled gates.The binary decomposition lets the circuit construct shift powers from controlled factors.Source: §4 · p. 5, §4.1 · p. 6
4.2. The square-and-multiply principle.
- The square-and-multiply principle uses each binary index digit to select the corresponding power of the shift, constructing all indexed powers with n controlled factors.The ℓ-th digit selects the factor Z^(2^ℓ).Source: §4.2 · p. 7
4.3. The block-shift operators Zblk and Zrblk.
- Zblk applies index-dependent shifts to blocks, while Zrblk reverses their direction; the block-shift construction uses O(log N) structured factors.The reverse operator can be obtained from a half-period shift rather than built independently.Source: §4.2 · p. 7, §4.3 · pp. 7–8
4.4. The operator Zsel and its circuit.
- Zsel combines the forward and reverse block-shift structures, and its circuit assembles them using controlled shifts in O(n^3) depth.A block-selective half-period shift avoids independently constructing Zrblk.Source: §4.3 · p. 8, §4.4 · p. 8
4.5. The operator Zfix and its circuit.
- Zfix applies index-selected inverse shifts only to each block’s leading component, leaving its trailing component unchanged.An additional selection qubit restricts the controlled shifts to the leading component.Source: §4.4 · p. 9, §4.5 · pp. 9–10
4.6. The operator Zflip and its circuit.
- Zflip uses the binary block index to control a pattern of Pauli-X flips, implemented with disjoint CNOT gates of depth O(1).The remaining subsystem is left as the identity.Source: §4.6 · p. 11, §4.7 · p. 12
4.7. The UC-SWAP operator.
- UC-SWAP exchanges generator registers on the selected branch, turning u_i v_j products into v_j u_i products; its circuit has depth O(n).The assembled encoding has depth O(log^3 N) + Dsp, where Dsp is the state-preparation depth.Source: §4.7 · pp. 11–12
5. Block encoding of semiseparable matrices.
The construction builds a block encoding of a symmetric semiseparable matrix from its two generators using shifts, swaps, and Hadamard gates. Its polylogarithmic depth depends on efficient state preparation; the paper also describes generator preparation for an analytic-coefficient discretization and extends the construction to the unsymmetric case.
5. Block encoding of semiseparable matrices.
- With efficient state preparation, the circuit acts on 3n + 2 qubits and has O(polylog N) depth; exact generator loading gives an exact block encoding.When the generators are approximated, the state-preparation error is the source of encoding inexactness.Source: §5 · p. 12, §5.3 · pp. 17–18
5.1. Idea of the construction.
- Hadamard branching, controlled swaps, and shifts separate the desired triangular entries from spurious products, then assemble and route the matrix columns into the leading block.The final Hadamard layer superposes the replicated copies to place the columns side by side.Source: §5.1 · pp. 12, 14, §5.3 · p. 17
5.2. Efficient state preparation.
- For analytic g, generator samples can be prepared at polylogarithmic depth when the polynomial degree grows polylogarithmically and the function’s maximum modulus is comparable to its grid RMS.The described routine encodes the grid-coordinate diagonal operator, applies a polynomial through quantum singular value transformation, and amplifies the successful branch.Source: §5.2 · p. 14
- For a three-point Sturm–Liouville discretization with analytic p bounded away from zero, the inverse matrix has generators derived from cumulative sums approximating the integral solutions U and V.The midpoint-quadrature generators differ from the exact generators by a relative O(N^-2), adding to the state-preparation error.Source: §5.2 · pp. 14–15
5.3. Assembly and proof of Theorem 5.1.
- The unsymmetric construction uses controlled generator preparation and replaces the triangular-register Hadamards with a rotation, while retaining the same overall construction framework.The paper states that arbitrary generators can be handled without carrying over the symmetric theorem’s unit-norm assumption.Source: §6 · p. 18
6. The unsymmetric case.
The unsymmetric construction handles one-pair matrices with arbitrary nonzero generators by separately scaling their lower and strict upper triangular parts. It uses controlled state preparation and a rotation to combine the branches, with their scales included in the block-encoding subnormalization.
6. The unsymmetric case.
- Normalizing all four generators independently can violate diagonal compatibility unless the lower- and upper-pair norm products coincide.The compatibility condition is u_i v_i = x_i y_i on the diagonal.Source: §6 · p. 18
- The matrix is decomposed into lower and strict upper triangular parts, weighted by the respective generator-pair norm products before recombination.The diagonal is supplied by the lower branch, and compatibility is imposed on the original generators.Source: §6 · p. 18
- Controlled preparation selects the generator pair for each branch, and a rotation replaces the symmetric construction’s Hadamards without adding a qubit.The circuit retains 3n + 2 total qubits and O(polylog N) depth under the stated state-preparation assumptions.Source: §6 · p. 19
- The remaining shifts and column-placement steps are unchanged, and the resulting leading block contains the matrix scaled by a common factor incorporating both branch weights.The symmetric construction is recovered when the two generator pairs coincide.Source: §6 · p. 19
7. Comparison with other encoding.
The comparison weighs the generator-based construction against one-pair, dense-matrix, hierarchical, and inverse-encoding alternatives, highlighting trade-offs in normalization, depth, error, and data access.
7. Comparison with other encoding.
- The earlier one-pair encoding achieves polylogarithmic depth but uses O(N^2) subnormalization and 2 log N + 7 ancillas; this construction uses the generators without factorization.Its matrix-dependent inputs are two generator state-preparation routines, with no classical matrix preprocessing.Source: §7 · p. 20
- The construction’s encoding error is 2ε independent of matrix size, versus O(N^2ε) for the earlier one-pair scheme.The comparison also notes that the earlier scheme has polylogarithmic depth but incurs O(N^2) subnormalization.Source: §7 · p. 20
- The hierarchical scheme of has O(log N) subnormalization for unit-norm generators, but requires multiplexed block-specific state preparations and partial-norm data.Its oracle inaccuracies are amplified by subnormalization and accumulated across hierarchy levels.Source: §7 · p. 20
- Against FABLE, the construction replaces O(N^2) controlled rotations with polylogarithmic depth on generator-representable semiseparable matrices.FABLE compiles classical matrix entries and has no general compression guarantee.Source: §7 · p. 21
- For the tested inverse family, direct encoding uses one polylogarithmic-depth circuit, while QSVT requires about O(κ) queries to the encoding of A.With amplitude amplification, the paper reports an approximately O(N^(3/2)) advantage for its approach on the stated second-order discretization family.Source: §7 · pp. 21–22
8. Numerical experiments.
The experiments test encoding correctness, error-bound tightness, and circuit cost across three semiseparable generator families. They report roundoff-level error with exact generator loading, error bounded independently of matrix size, and lower depth and size than FABLE at larger sizes.
8. Numerical experiments.
- The tests use Random, Tridiagonal, and Exponential generator families; normalized exponential generators form a product state prepared with n Ry rotations and no entangling gates.The tridiagonal family is derived from inverses of random symmetric irreducible diagonally dominant tridiagonal matrices; the exponential family uses θ=3 in the tests.Source: §8 · p. 22
8.1. Correctness.
- With generators loaded to machine precision, absolute encoding error is O(10^-15) across all three families and tested sizes, consistent with roundoff.The authors interpret this as confirming an exact block encoding when the generators are loaded exactly.Source: §8.1 · p. 22, Figure 8.1 · p. 23
8.2. Tightness of the error bound.
- For N=64, error grows linearly with ε yet stays below 2ε; at ε=10^-6 it remains below the bound across sizes without growing with N.The tested curves lie roughly a factor of three below the bound, which the authors describe as conservative but of the correct order of magnitude.Source: §8.2 · pp. 23–24, Figure 8.2 · p. 23
8.3. Comparison with FABLE.
- At N=1024, FABLE depth and size exceed the exponential-loader circuit by more than two orders of magnitude; the transpiled curves cross near N=32.For exponential generators, the dedicated loader’s depth and size follow polylogarithmic growth; the general-purpose loader is more expensive but still grows more slowly than FABLE.Source: §8.3 · pp. 24–25, Figure 8.4 · p. 25
9. Conclusions.
The conclusion presents a direct generator-based block encoding for one-pair semiseparable matrices, with polylogarithmic depth and an extension to the unsymmetric case. It identifies extensions to other structured matrices and hierarchical encodings as future directions.
9. Conclusions.
- The circuit constructs a one-pair semiseparable block encoding directly from its generators, using 2n+2 ancillas and O(polylog N) depth for N=2^n.The construction avoids forming a factorization or using hierarchical decompositions.Source: §9 · p. 26
- The construction extends to unsymmetric one-pair matrices using controlled state preparation and a suitable Ry rotation in place of triangular-qubit Hadamards.The authors describe extensions to r-semiseparable and generator-representable plus diagonal matrices as straightforward, while non-generator-representable structure remains open.Source: §9 · p. 26
- Recursive application across HODLR or HSS levels, avoiding level-by-level linear combinations of unitaries, is proposed as a direction for future work.The one-pair case is the flat, single-level instance of the broader rank-structured family.Source: §9 · p. 26
Data Availability.
- No datasets were generated or analyzed, and the implemented algorithm’s code is available.The code is linked in the paper’s data-availability statement.Source: Data Availability · p. 26, Code Availability · p. 26