Quantum block encoding for one-pair semiseparable matrices

Giacomo Antonioli; Gianna M. Del Corso; Margherita Porcelli; Paola Boito

REVIEW 2 major objections 4 minor 1 cited by

One-pair semiseparable matrices can be quantum block-encoded in polylog time via a triangular-diagonal factorization that uses only 2 log N + 7 ancillas.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 22:08 UTC pith:272RO7VL

load-bearing objection Solid first construction of a polylog-depth block encoding for one-pair semiseparable matrices; the O(N^{2}) scaling is the real limit, but the math and experiments hold up. the 2 major comments →

arxiv 2603.19130 v2 pith:272RO7VL submitted 2026-03-19 quant-ph cs.NAmath.NAmath.QA

Quantum block encoding for one-pair semiseparable matrices

Giacomo Antonioli , Paola Boito , Gianna M. Del Corso , Margherita Porcelli This is my paper

classification quant-ph cs.NAmath.NAmath.QA

keywords Quantum Block EncodingSemiseparable matricesQuantum Numerical Linear AlgebraStructured matricesRank structureLinear combination of unitariesBlock-encoding arithmetic

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Quantum algorithms that act on matrices must first embed them inside larger unitary circuits; this paper shows how to do that efficiently for one-pair semiseparable matrices, a common rank-structured class that appears in discretizations and integral operators. The authors factor any such matrix as the product of two diagonal matrices, a lower-triangular ones matrix, and a second diagonal of consecutive differences, then block-encode each factor with known or newly designed circuits and multiply them. Under the assumption that the two generating vectors can be loaded by polylog-depth oracles (or QRAM), the whole construction runs in polylogarithmic time, needs only 2 log N + 7 ancilla qubits, and produces an encoding whose error scales as O(N^{2}). The result matters because classical algorithms already exploit the same structure for linear cost, yet general-purpose quantum encoders still scale like O(N^{2}); closing that gap is a necessary step toward quantum linear-algebra routines that keep the exponential advantage for data-sparse problems.

Core claim

Any N-by-N one-pair semiseparable matrix S(u,v) admits an explicit (O(N^{2}), 2 log N + 7, O(N^{2} ε))-block encoding obtained by realizing the classical factorization S = D_u L Δ_z Lᵀ D_u as a product of block encodings of the diagonal factors, the triangular ones matrix L, and its adjoint; the construction is exact once the generators are supplied by suitable oracles.

What carries the argument

The classical factorization S(u,v) = D_u L Δ_z Lᵀ D_u (Proposition 4), which reduces the dense rank-structured matrix to a product of easily encoded diagonal and triangular pieces that can be multiplied by standard block-encoding arithmetic.

Load-bearing premise

The data oracles that load the two generators u and v (and the Boolean circuits that approximate arcsin) must themselves be realizable with only polylogarithmic depth, or a QRAM must be available.

What would settle it

Implement the circuit of Figure 7 for a family of random one-pair matrices of size 4 to 128, extract the top-left block after rescaling by the predicted α, and check whether the measured spectral error stays below the O(N^{2} ε) bound of Theorem 11 while the gate depth remains polylogarithmic.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Any quantum algorithm that already accepts a block-encoded matrix (HHL-style linear solvers, quantum singular-value transformation, etc.) can now take a one-pair semiseparable matrix as input with only polylog overhead instead of quadratic cost.
The same factorization-plus-product strategy immediately supplies block encodings for the inverses of these matrices, which are known to be tridiagonal.
The ancillary-qubit count 2 log N + 7 is small enough that the construction remains practical on near-term devices that already support a few dozen qubits.
Because the scaling factor α is asymptotically tight with respect to both matrix size and the conditioning of the generators, success probabilities for subsequent measurements cannot be improved by a better factorization of the same type.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same triangular-factor approach is likely to extend, with only modest extra ancillas, to the broader class of quasiseparable or generator-representable matrices that admit analogous LU-like factorizations.
If hierarchical semiseparable matrices can be recursively reduced to one-pair blocks, the present construction would give a natural building block for polylog-depth encodings of HSS matrices, which dominate large-scale integral-equation discretizations.
The observed gap between the theoretical O(N^{2} ε) error and the much smaller numerical error suggests that a refined error analysis (perhaps tracking the precise operator-norm accumulation rather than crude triangle inequalities) could tighten the success-probability estimates used by downstream algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Solid first construction of a polylog-depth block encoding for one-pair semiseparable matrices; the O(N^{2}) scaling is the real limit, but the math and experiments hold up.

read the letter

This is a clean, usable first result: a concrete circuit that block-encodes one-pair semiseparable matrices in polylog depth (under the usual oracle/QRAM assumption) with 2 log N + 7 ancillas. No one had done this class before; the factorization S = Du L Δz Lᵀ Du plus the ad-hoc exact encoding of the lower-triangular ones matrix L is the actual novelty, not a routine LCU application.

The proofs chain correctly. Prop. 4 is classical, Thms. 6–7 recycle standard diagonal encodings with arcsin oracles, Thm. 9 gives an exact (N, log N + 1, 0) encoding of L via controlled shifts, Thm. 10 builds Δz by LCU difference of shifted diagonals, and Thm. 11 multiplies everything with the usual product lemma. Error and scaling come out exactly as the product of the factors; the authors themselves show the O(N^{2}) factor is asymptotically tight for this factorization because ||L||₂ ~ O(N). Code is public (QCLAB), numerics stay well below the theoretical bound, and the FABLE comparison is fair: they match accuracy without compression while keeping polylog depth and, more importantly, preserving the tridiagonal inverse structure that FABLE destroys.

Soft spots are real but openly stated. The O(N^{2}) scaling is larger than the true ||S||₂ = O(N), so success probability suffers; a direct encoding that avoids the triangular factors might do better, but that is future work, not a flaw in the present claim. Everything rests on polylog-depth generator oracles (or QRAM), the same modeling hypothesis used throughout the block-encoding literature. No hidden gaps, no circularity, no invented entities.

This is for people who actually build quantum linear-algebra circuits or who care about rank-structured matrices beyond sparsity. It is a natural seed for hierarchical or quasiseparable encodings. I would send it to referees without hesitation; the central claim is correct and the limitations are not papered over. Worth reading and citing if you work in this corner.

Referee Report

2 major / 4 minor

Summary. The paper constructs an explicit quantum block encoding for N imes N one-pair semiseparable matrices S(u,v) by exploiting the classical factorization S=Du L riangle z LT Du (Proposition 4). It supplies (N,log N+1,0)-encodings of the triangular factor L via controlled cyclic shifts (Theorem 9 and Figure 5), diagonal encodings of Du and of the successive differences that form riangle z via arcsin oracles plus LCU (Theorems 6–7,10 and Figure 6), and composes them by the product lemma (Lemma 8) to obtain a (2N^{2} Mu^{2} Mv/(c^{2} mu), 2 log N+7, O(N^{2}\epsilon))-block encoding (Theorem 11, circuit in Figure 7). Under the standard assumption that generator oracles and the arcsin Boolean circuits have polylog depth (or a QRAM model), the whole circuit has polylog depth. Numerical QCLAB experiments confirm that the realized error lies well below the analytic bound and that the encoding preserves the tridiagonal inverse structure better than the general-purpose FABLE package.

Significance. This is the first dedicated block-encoding construction for off-diagonal rank structure of semiseparable type, a class that arises in integral equations, discretized differential operators and many classical fast algorithms. If the result holds, it supplies a concrete polylog-depth primitive that can be plugged into quantum linear-algebra pipelines (HHL-style solvers, quantum singular-value transformation, etc.) whenever the matrix is known to be one-pair semiseparable. The manuscript ships fully explicit circuits, rigorous end-to-end error propagation, a publicly available QCLAB implementation, and a direct comparison with FABLE that demonstrates structure preservation—precisely the ingredients needed for subsequent algorithmic work on hierarchical and quasiseparable matrices.

major comments (2)

[Theorem 11 and §6.1] Theorem 11 and the discussion in §6.1 establish a scaling factor heta(N^{2}) while simultaneously proving that ||S||_{2}= heta(N). The resulting success probability for post-selecting the action of S is therefore O(1/N^{2}). Although the authors correctly show that the factor N is tight for the chosen factorization (via the bound ||L||_{2} o2N/ au), the claim of an “efficient” encoding would be more convincing if the manuscript either exhibited an alternative encoding of L that reduces the gap or quantified the application regimes in which the O(1/N^{2}) overhead remains tolerable.
[Abstract] The abstract states that the method “has an error of O(N^{2})”. Theorem 11 shows that the absolute error is O(N^{2} au) where au bounds the precision of the diagonal oracles. Without an explicit statement of how au must scale with N, the abstract claim is incomplete and potentially misleading; it should be aligned with the precise bound of Theorem 11.

minor comments (4)

[§2] Definition 1 and several later displayed equations contain rendering artefacts (sequences of black rectangles). These should be cleaned for the final version.
[Figure 9] Figure 9 caption refers to both the infinity-norm and the 2-norm, yet the plotted curves are not clearly labelled; a legend would help.
[§4.2] The constant c= au( au^{2}-1)/ au appears repeatedly; a single definition early in §4.2 would improve readability.
[§7] In the comparison with FABLE the authors note that their circuit uses more ancillas (2log N+7 versus log N+1). It would be useful to state explicitly which of those ancillas can be uncomputed and reused, as already hinted in the proofs of Theorems 6–7.

Circularity Check

0 steps flagged

No significant circularity; the claimed block encoding is a direct, non-circular composition of a classical factorization with standard quantum primitives.

full rationale

The central claim (Theorem 11) follows by chaining an independent classical factorization (Proposition 4: S = Du L Δz LT Du) with explicit circuit constructions for each factor (Theorem 9 for the exact (N, log N + 1, 0) encoding of the lower-triangular Toeplitz factor L; Theorems 6–7 for the diagonal factors via controlled rotations and arcsin oracles; Theorem 10 for Δz via LCU difference of two diagonal encodings) and the standard product lemma (Lemma 8). Scaling and error bounds are obtained by multiplying the individual factors and are shown to be asymptotically tight for this factorization (via the independent ||L||2 = O(N) estimate). No parameter is fitted to data and then re-used as a prediction; no uniqueness theorem or ansatz is imported from the authors’ prior work; the only modeling hypothesis (polylog-depth oracles / QRAM for the generators) is stated explicitly and is the same hypothesis used throughout the block-encoding literature. Numerical comparisons are performed against the independent FABLE package. The derivation is therefore self-contained and free of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The result rests on standard quantum-circuit primitives, a classical matrix factorization that is decades old, and the usual oracle/QRAM model for loading classical data. No free parameters are fitted; the only non-standard ingredients are the concrete controlled-shift circuit for L and the product composition of the five factors.

axioms (4)

standard math A matrix admits an (α,m,ε)-block encoding if and only if there exists a unitary whose top-left block approximates A/α to precision ε (Def. 1).
Standard definition used throughout the quantum-algorithm literature.
standard math The classical factorization S(u,v)=D_u L Δ_z L^T D_u holds whenever all u_i ≠ 0 (Prop. 4).
Well-known identity for generator-representable semiseparable matrices; proved by direct verification.
domain assumption Oracles that load the generators u,v (and Boolean circuits approximating arcsin) can be realized with polylog depth, or a QRAM is available.
Explicitly stated in the abstract and before Theorems 6–7; without it the claimed polylog runtime fails.
standard math The product of two block encodings is again a block encoding whose parameters multiply (Lemma 8).
Standard composition lemma from the quantum singular-value transformation literature.

pith-pipeline@v1.1.0-grok45 · 23133 in / 2193 out tokens · 23178 ms · 2026-07-13T22:08:41.747382+00:00 · methodology

0 comments

read the original abstract

Quantum block encoding (QBE) is a crucial step in the development of most quantum algorithms, as it provides an embedding of a given matrix into a suitable larger unitary matrix. Historically, the development of efficient techniques for QBE has mostly focused on sparse matrices; less effort has been devoted to data-sparse (e.g., rank-structured) matrices. In this work we examine a particular case of rank structure, namely, one-pair semiseparable matrices. We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors. To encode the matrix, the algorithm needs $2\log(N)+7$ ancillary qubits. Assuming that the data input oracles can be implemented with polylogarithmic depth, or that a QRAM input model is available, our proposed method requires $\mathcal{O}({\rm polylog} (N))$ time and has an error of $\mathcal{O}(N^2)$, where $N$ is the matrix size.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

A Quantum Spectral Framework for Solving PDEs
quant-ph 2026-04 unverdicted novelty 5.0

A quantum method solves linear PDEs by block-encoding Fourier filters with reversible arithmetic, positioned as a structure-exploiting alternative to standard QSVT-based matrix inversion.

Reference graph

Works this paper leans on

24 extracted references · cited by 1 Pith paper

[1]

��

Sanjeev Arora and Boaz Barak. �� . Cambridge University Press, USA, 1st edition, 2009

2009
[2]

��

Mario Bebendorf. �� . Springer, 2008

2008
[3]

Explicit quantum circuits for block encodings of certain sparse matrices

Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. �� , 45(1):801–827, 2024

2024
[4]

F ABLE: Fast approximate quantum cir- cuits for block-encodings

Daan Camps and Roel Van Beeumen. F ABLE: Fast approximate quantum cir- cuits for block-encodings. In �� , pages 104–113. IEEE, 2022

2022
[5]

Chandrasekaran, M

S. Chandrasekaran, M. Gu, and T. Pals. A fast UL V decomposition solver for hierarchically semiseparable representations. �� , 28(3):603 – 622, 2006

2006
[6]

Childs and Nathan Wiebe

Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear com- binations of unitary operations. �� , 12(11 & 12), November 2012

2012
[7]

��

Yuli Eidelman, Israel Gohberg, and Iulian Haimovici. �� . Springer, 2014

2014
[8]

A brief introduction to quasiseparable ma- trices, 2011

Dario Fasino. A brief introduction to quasiseparable ma- trices, 2011. https://www.mat.uniroma2.it/∼tvmsscho/Rome- Moscow_School/2011/files/quasisep-fasino-notes.pdf

2011
[9]

Structural and computational properties of possibly singular semiseparable matrices

Dario Fasino and Luca Gemignani. Structural and computational properties of possibly singular semiseparable matrices. �� , 340(1-3):183–198, 2002

2002
[10]

��

Felix R Gantmacher and Mark G Krein. �� . American Mathematical Society Rhode Island, 2002

2002
[11]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In �� , pages 193–204, 2019

2019
[12]

Harrow, A vinatan Hassidim, and Seth Lloyd

Aram W. Harrow, A vinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. �� , 103(15):150502, 2009

2009
[13]

Qclab: A matlab toolbox for quantum computing, 2025

Sophia Keip, Daan Camps, and Roel Van Beeumen. Qclab: A matlab toolbox for quantum computing, 2025

2025
[14]

On eﬀicient quantum block encoding of pseudo-differential operators

Haoya Li, Hongkang Ni, and Lexing Ying. On eﬀicient quantum block encoding of pseudo-differential operators. ��, 7:1031, June 2023

2023
[15]

Lecture notes on quantum algorithms for scientific computation

Lin Lin. Lecture notes on quantum algorithms for scientific computation. �� , 2022. 24

2022
[16]

Losonczi

L. Losonczi. Eigenvalues and eigenvectors of some tridiagonal matrices. �� , 60(3-4):309–322, 1992

1992
[17]

HM-toolbox: Matlab software for HODLR and HSS matrices

Stefano Massei, Leonardo Robol, and Daniel Kressner. HM-toolbox: Matlab software for HODLR and HSS matrices. �� , 42(2):C43–C68, 2020

2020
[18]

Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals

Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi Sasaki Usuda. Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals. �� , 2021

2021
[19]

Fast inversion, preconditioned quantum linear system solvers, fast green’s-function computation, and fast eval- uation of matrix functions

Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. Fast inversion, preconditioned quantum linear system solvers, fast green’s-function computation, and fast eval- uation of matrix functions. �� , 104:032422, Sep 2021

2021
[20]

A note on the represen- tation and definition of semiseparable matrices

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi. A note on the represen- tation and definition of semiseparable matrices. �� , 12(8):839–858, 2005

2005
[21]

�� , volume 1

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi. �� , volume 1. JHU Press, 2008

2008
[22]

Block-encoding-based quantum algorithm for linear systems with displace- ment structures

Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen. Block-encoding-based quantum algorithm for linear systems with displace- ment structures. �� , 104(6):062414, 2021

2021
[23]

Quantum linear system algorithm for dense matrices

Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. Quantum linear system algorithm for dense matrices. �� , 120(5):050502, 2018

2018
[24]

Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S. Li. Fast algo- rithms for hierarchically semiseparable matrices. �� , 17(6):953–976, 2010. 25

2010

[1] [1]

��

Sanjeev Arora and Boaz Barak. �� . Cambridge University Press, USA, 1st edition, 2009

2009

[2] [2]

��

Mario Bebendorf. �� . Springer, 2008

2008

[3] [3]

Explicit quantum circuits for block encodings of certain sparse matrices

Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. �� , 45(1):801–827, 2024

2024

[4] [4]

F ABLE: Fast approximate quantum cir- cuits for block-encodings

Daan Camps and Roel Van Beeumen. F ABLE: Fast approximate quantum cir- cuits for block-encodings. In �� , pages 104–113. IEEE, 2022

2022

[5] [5]

Chandrasekaran, M

S. Chandrasekaran, M. Gu, and T. Pals. A fast UL V decomposition solver for hierarchically semiseparable representations. �� , 28(3):603 – 622, 2006

2006

[6] [6]

Childs and Nathan Wiebe

Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear com- binations of unitary operations. �� , 12(11 & 12), November 2012

2012

[7] [7]

��

Yuli Eidelman, Israel Gohberg, and Iulian Haimovici. �� . Springer, 2014

2014

[8] [8]

A brief introduction to quasiseparable ma- trices, 2011

Dario Fasino. A brief introduction to quasiseparable ma- trices, 2011. https://www.mat.uniroma2.it/∼tvmsscho/Rome- Moscow_School/2011/files/quasisep-fasino-notes.pdf

2011

[9] [9]

Structural and computational properties of possibly singular semiseparable matrices

Dario Fasino and Luca Gemignani. Structural and computational properties of possibly singular semiseparable matrices. �� , 340(1-3):183–198, 2002

2002

[10] [10]

��

Felix R Gantmacher and Mark G Krein. �� . American Mathematical Society Rhode Island, 2002

2002

[11] [11]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In �� , pages 193–204, 2019

2019

[12] [12]

Harrow, A vinatan Hassidim, and Seth Lloyd

Aram W. Harrow, A vinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. �� , 103(15):150502, 2009

2009

[13] [13]

Qclab: A matlab toolbox for quantum computing, 2025

Sophia Keip, Daan Camps, and Roel Van Beeumen. Qclab: A matlab toolbox for quantum computing, 2025

2025

[14] [14]

On eﬀicient quantum block encoding of pseudo-differential operators

Haoya Li, Hongkang Ni, and Lexing Ying. On eﬀicient quantum block encoding of pseudo-differential operators. ��, 7:1031, June 2023

2023

[15] [15]

Lecture notes on quantum algorithms for scientific computation

Lin Lin. Lecture notes on quantum algorithms for scientific computation. �� , 2022. 24

2022

[16] [16]

Losonczi

L. Losonczi. Eigenvalues and eigenvectors of some tridiagonal matrices. �� , 60(3-4):309–322, 1992

1992

[17] [17]

HM-toolbox: Matlab software for HODLR and HSS matrices

Stefano Massei, Leonardo Robol, and Daniel Kressner. HM-toolbox: Matlab software for HODLR and HSS matrices. �� , 42(2):C43–C68, 2020

2020

[18] [18]

Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals

Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi Sasaki Usuda. Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals. �� , 2021

2021

[19] [19]

Fast inversion, preconditioned quantum linear system solvers, fast green’s-function computation, and fast eval- uation of matrix functions

Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. Fast inversion, preconditioned quantum linear system solvers, fast green’s-function computation, and fast eval- uation of matrix functions. �� , 104:032422, Sep 2021

2021

[20] [20]

A note on the represen- tation and definition of semiseparable matrices

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi. A note on the represen- tation and definition of semiseparable matrices. �� , 12(8):839–858, 2005

2005

[21] [21]

�� , volume 1

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi. �� , volume 1. JHU Press, 2008

2008

[22] [22]

Block-encoding-based quantum algorithm for linear systems with displace- ment structures

Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen. Block-encoding-based quantum algorithm for linear systems with displace- ment structures. �� , 104(6):062414, 2021

2021

[23] [23]

Quantum linear system algorithm for dense matrices

Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. Quantum linear system algorithm for dense matrices. �� , 120(5):050502, 2018

2018

[24] [24]

Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S. Li. Fast algo- rithms for hierarchically semiseparable matrices. �� , 17(6):953–976, 2010. 25

2010