PaperlayerView exact revision on arXiv

Source-linked AI summary

Cayley access models for matrix functions: reachable class and cost

Gianna M. Del Corso

arXiv:2610.23429v1quant-phcs.NAmath.NA

TL;DR

When N is very large, forming or diagonalizing A is out of reach, motivating quantum algorithms with cost polynomial in log N. This paper uses a parameterized Cayley transform to turn Hermitian A into a unitary for generalized quantum signal processing, characterizes its reachable rational functions, and shows fixed-pole rational functions are exact at degree one.

  • Problem

    For very large N, forming or diagonalizing A is out of reach, motivating algorithms whose cost is polynomial in log N.

    Source: §1 · p. 2

  • Method

    The Cayley transform maps Hermitian A to a unitary, enabling generalized quantum signal processing to implement bounded Laurent polynomials that become rational functions of A.

    Source: §1 · p. 2

  • Results

    Fixed-pole rational functions are reached exactly at degree one, while the reachable class has poles at σ ± iγ of order at most d.

    Source: §1 · p. 2, §8 · p. 25

  • Takeaways & Limitations

    The parameters σ and γ let users tailor where spectral accuracy is concentrated, while the circle change of variable makes approximation a trigonometric approximation problem.

    Source: §1 · p. 2, §8 · p. 25

    A polylogarithmic circuit requires a low-complexity description of the encoding angles, and the proposed structured-unitary construction lacks known application examples of the specified kind.

    Source: §6.3 · p. 20

Abstract

from arXiv · show

We study how to compute $f(A)b$ on a quantum computer, where $A$ is Hermitian. When $f$ is nonsmooth or has localized difficulty in the spectrum, classical numerical linear algebra approximates it with rational functions rather than polynomials. We propose the Cayley transform, parameterized by $\sigma \in \mathbb{R}$ and $\gamma > 0$, as an alternative to the standard quantum access model. The two parameters let one concentrate accuracy where $f$ is difficult, which standard models can achieve only by raising the polynomial degree globally. This transformation converts Hermitian matrices to unitaries, allowing generalized quantum signal processing to apply Laurent polynomials bounded on the unit circle. We compare three access models (block encoding, matrix exponential, and Cayley encoding) in terms of query complexity and of the cost of their circuit realization. When the difficulty of $f$ is localized in the spectrum, the Cayley encoding reduces the required degree by a factor of three to four, and it represents the shifted resolvent exactly at degree one. For spectral projectors, the standard models cannot reach the target accuracy at fixed degree, because their approximants cannot concentrate resolution near the discontinuity. Realizing the Cayley encoding from a block encoding requires solving a shifted linear system, whose cost offsets its query-complexity gain over the standard models. For structured matrices arising in practice, however, low-depth circuits for the encoding can be constructed directly, and the gain is preserved at the circuit level.

1 Introduction

The paper asks whether rational approximation can be brought to quantum matrix-function computation, where polynomial approximants can be costly for difficult functions. It introduces the Cayley encoding and analyzes its reachable functions, query advantages, and realization costs.

1 Introduction

  • For very large N, forming or diagonalizing A is out of reach, motivating quantum algorithms with cost polynomial in log N.Classically, rational approximations are used when singularities are close to the spectrum or eigenvalues are poorly separated.Source: §1 · p. 2, §1.2 · pp. 3–4
  • For nonsmooth functions or functions with a nearby discontinuity or pole, polynomial approximation can converge slowly and require prohibitive degree.The paper asks whether rational approximation, used classically in such cases, can also be used on a quantum computer.Source: §1 · p. 2

1.2 Relation to prior work

  • The Cayley encoding makes the matrix-function task a unitary signal-processing problem, turning bounded Laurent polynomials of the encoding into rational functions of A.It uses one ancilla and avoids the overhead of implementing a linear combination of resolvents, while tying the numerator to the poles.Source: §1 · p. 2, §1.2 · p. 4

1.1 Contributions

  • The Cayley encoding with generalized quantum signal processing reaches rational functions of type (2d, 2d) with poles at σ ± iγ, each of order at most d.Its tunable parameters place approximation accuracy where f is difficult, unlike standard access models whose unitaries are fixed by A.Source: §1 · p. 2, §1.1 · p. 3
  • Products of Cayley factors yield exactly the rational functions that are unitary on every Hermitian matrix; on the targets considered, extra poles bring no advantage.The approach lies between polynomial signal processing and rational approximations with a free numerator; the latter cannot remain a rational unitary encoding on every Hermitian matrix.Source: §1.1 · p. 3, §1.2 · p. 4
  • The query-model degree is often lower than in standard models, but constructing the encoding from a block encoding requires a shifted solve that offsets the query saving on generic matrices.The advantage remains at circuit level only when matrix structure permits a direct low-depth Cayley circuit.Source: §1 · p. 2, §1.1 · p. 3

2 Preliminary Results and Notation

This section sets notation for Hermitian matrices, spectra, and rational functions, then defines the Cayley encoding and generalized quantum signal processing. Together, the encoding and signal-processing transformation determine which functions of A are reachable.

2 Preliminary Results and Notation

  • The spectral set S is a known closed set containing the spectrum Λ(A), on which functions of A are approximated.The paper's experiments use finite unions of closed intervals.Source: §2 · p. 5
  • For a nonreal shift w = σ + iτ, the shifted system is well conditioned even when A is singular.Its shifted matrix is normal, and the moduli of its eigenvalues lie between |τ| and (∥A − σI∥² + τ²)^(1/2).Source: §2 · p. 5
  • The Cayley encoding maps a Hermitian A to a unitary that commutes with A and shares its eigenvectors, mapping each eigenvalue λj to (λj − σ − iγ)/(λj − σ + iγ).The inverse map takes unitaries without eigenvalue 1 back to Hermitian matrices.Source: §2 · p. 5
  • For degree d, the fixed-pole reachable class consists of type-(2d, 2d) rational functions with poles at σ ± iγ, each of order at most d.This is a linear space of dimension 2d + 1 and is strictly smaller than the full class with those poles for d ≥ 1.Source: §2 · p. 5

2.1 Signal processing

  • With controlled access to a unitary and its adjoint, GQSP implements Laurent polynomials bounded by one on the unit circle using one ancilla.When the unitary shares eigenvectors with A, the polynomial acts on the corresponding eigenphases; choosing the Cayley encoding therefore yields rational functions of A.Source: §2.1 · p. 6

3 The Cayley encoding

The Cayley encoding maps a Hermitian matrix to a unitary whose tunable parameters concentrate approximation resolution where the target function is difficult. GQSP then applies a bounded Laurent polynomial, yielding a prescribed-pole rational function; the method also reduces approximation to the unit circle and represents the shifted resolvent exactly at degree one.

3.1 The two parameters

  • The parameters σ and γ place the finest resolution near σ and set its spectral width; practical choices follow the target function's difficult region, with wider γ sometimes lowering effective cost.For the shifted resolvent, σ is the pole's real part and γ its distance from the real axis; smaller γ makes polynomial approximation harder but raises encoding cost per application.Source: §3.1 · p. 7

3.2 Computing f(A)

  • The procedure maps f to the circle, approximates it with a bounded degree-d trigonometric polynomial, compiles GQSP angles, and measures the ancilla branch to recover the output.The first four stages are classical precomputation; the circuit uses 2d controlled encoding applications and 2d+1 single-qubit rotations.Source: §3.2 · p. 8

3.3 The class reachable with a Cayley factor

  • A degree-d GQSP Laurent polynomial reaches every rational function bounded by one on R with poles at σ ± iγ, each of order at most d.The numerator is free up to degree 2d, subject to the normalization constraint; implementation uses 2d controlled encoding applications and one ancilla.Source: §3.3 · pp. 8–9

3.4 Approximation: reduction to the circle

  • Proposition 3.4 equates approximation on the spectrum with Laurent-polynomial approximation on its Cayley image, enabling standard circle-approximation methods.Geometric error decay applies when the transformed function extends analytically to an annulus; the nearest singularity to the real axis limits its width.Source: §3.4 · pp. 9–10
  • For unbounded spectra, continuity on the circle requires f to have equal limits at ±∞; finite spectra avoid this restriction because their image stays away from z = 1.Thus a function such as the sign function cannot be followed uniformly as the spectrum grows without bound.Source: §3.4 · p. 10

3.5 The shifted resolvent

  • At degree one, the Cayley encoding represents the shifted resolvent exactly, while polynomial methods need degree growing like 1/γ when its pole is γ from the spectrum.Recovering the resolvent still requires amplitude amplification because the implemented branch is subnormalized.Source: §3.5 · p. 10

4 The complete family of rational encodings: products of Cayley factors

Products of Cayley factors extend the encoding to multiple poles, and the paper proves these products characterize rational functions that are unitary on every Hermitian matrix. GQSP query counts stay independent of the number of factors, but the reachable functions remain restricted and each encoding's realization cost grows with that number.

4 The complete family of rational encodings: products of Cayley factors

  • Multiplying Cayley factors permits poles at any finite set off the real axis while retaining a single system-register unitary.The paper's purpose for the extension is to establish that these products exhaust rational unitary encodings, not to improve the considered targets.Source: §4 · p. 11
  • Every rational function unitary on every Hermitian matrix is, up to a unimodular constant, a ratio q*/q with q having no real roots.Conversely, every such ratio is unitary on every Hermitian matrix.Source: §4 · p. 11
  • With m Cayley factors, degree-d GQSP uses 2d encoding applications and 2d+1 angles, independent of m, while realizing each application costs more with m.The reachable functions occupy a 2d+1-dimensional subspace of a rational-function space of dimension 2md+1.Source: §4 · pp. 11–12
  • For m ≥ 2, the multi-pole family does not reach the full type-(2md, 2md) class because its numerator is constrained by its denominator.A linear combination of resolvents reaches that wider class at the cost of ⌈log2 m⌉ ancillas and an ℓ1 subnormalization factor.Source: §4 · p. 12
  • Crank–Nicolson and diagonal Padé propagators are classical examples of products of Cayley factors, with poles fixed by the approximation order rather than chosen for f.The paper notes a quantum implementation of such approximants through a linear-system solver.Source: §4 · p. 12

5 Comparison with the standard access models

The three access models differ in how their transformations map spectral regions and allocate accuracy. Unlike the fixed block-encoding and uniformly bounded exponential densities, the Cayley density can be placed around a difficult spectral region.

5 Comparison with the standard access models

  • The exponential and Cayley models process a commuting unitary through GQSP, differing in the change of variable from λ to phase; block encoding instead uses QSVT on singular values.The block encoding does not fit the same unitary-processing template because its unitary acts on ancillas and does not commute with A.Source: §5 · p. 12
  • The block-encoding density is fixed by A and rises toward ±α, while the exponential density is uniform and capped by the no-aliasing condition t = π/α.The Cayley density peaks at σ with value 2/γ and half-width γ, and is the only density that can be placed.Source: Figure 1 · p. 13
  • With m Cayley pole pairs, the density becomes a sum of m bells while the reachable class still has dimension 2d + 1.The figure caption describes the single-pair density; the multi-pair extension is stated in the text.Source: §5 · p. 13
  • Over [σ − γ, σ + γ], the Cayley encoding maps half the circle, versus 2γπ/α for the exponential model at its ceiling.The ratio α/(2γ) grows as the window narrows; Figure 1 plots the models’ accuracy densities.Source: §5 · p. 13, Figure 1 · p. 13

6 The cost of realizing the Cayley encoding

The generic block-encoding construction realizes the Cayley transform through a shifted solve, which can erase the query-degree savings when the function’s difficulty is localized. For structured matrices, direct or circuit-based realizations can preserve an advantage under the stated conditions.

6 The cost of realizing the Cayley encoding

  • A block encoding of A yields a Cayley encoding at cost eO(αM/γ) queries, with inversion of the shifted matrix M carrying the main cost.The construction inverts M to encode the resolvent, forms I − 2iγR, then amplifies the subnormalized block to a unitary.Source: §6 · pp. 14–15, Figure 2 · p. 15
  • Preparing the normalized state f(A)b uses the block encoding at cost eO(dαM/γ) and amplitude amplification scaled by η/ℓ, where ℓ is a lower bound on ∥f(A)b∥.For a spectral projector, this norm can be arbitrarily small and is estimated rather than used as a guaranteed lower bound.Source: §6 · p. 16

6.1 When does the Cayley encoding help?

  • A 3–4× degree reduction for localized difficulty is offset by the generic shifted-solve cost, leaving total cost of the same order as standard models.The generic realization costs eO(αM/γ) per application, while the degree scales as Θ(γ/∆).Source: §6.1 · p. 17
  • For the shifted resolvent, degree one gives 1/(λ + iγ), with relative error at most γκ on the spectrum; balancing width and degree gives total query count eO(κ).This is the same order as the polynomial method in the stated setting.Source: §6.1 · p. 17

6.2 Structured families

  • For Sturm–Liouville matrices with generators prepared at polylogarithmic depth, choosing γ = Θ(∆) gives degree O(log(1/ε)) and can yield eO(N) cost when the stated factors remain bounded.The comparison given is eO(N) for Cayley versus eO(N^2) for QSVT and the matrix-exponential model.Source: §6.2 · p. 18

6.3 The reverse direction: structured unitaries

  • A CMV unitary with 1 ∉ Λ(U) has a Hermitian Cayley preimage that is one-pair semiseparable plus diagonal.The circuit realization has no ancilla or subnormalization, but polylogarithmic depth requires low-complexity coefficients; the paper reports no application-derived examples of this kind.Source: §6.3 · pp. 19–20
  • The CMV route needs a low-complexity description of its coefficients: a generic sequence of N independent values requires Θ(N) gates.The paper presents this construction as a possible direction, not a realized application example.Source: §6.3 · p. 20

7 Numerical experiments

The experiments compare the best approximations reachable by the three access models and their effective costs. Cayley performs best when difficulty is localized, while a structured tridiagonal family shows how that query advantage can survive circuit realization under stated conditions.

7.2 The query model

  • The query-model tests normalize functions on spectral sets within [−1, 1] and compare the smallest effective cost 2d η needed to reach error 10^-6.The test set includes four functions with localized difficulty, two square-root cases, and two controls varying across the spectral set.Source: §7 · p. 20, §7.2 · p. 21

7.1 Method

  • The best approximations are computed as minimax problems over each model’s reachable basis, with rescaling η traded against error and Lawson iteration used to bound the minimax error.The spectral grid is augmented near the Cayley center to capture its rapid oscillations; the iteration stops when its bounds agree within relative 10^-4.Source: §7.1 · pp. 20–21

7.2 The query model

  • On the four functions with localized difficulty, Cayley is cheapest and reaches the resolvent exactly at 2d = 2; the cheapest model depends on the target and its spectral difficulty.For e^-λ the polynomial model is cheapest, while the exponential model is cheapest for e^-8iλ.Source: §7.2 · pp. 22–23

7.3 A family in which the encoding costs polylogarithmically

  • The circuit-level advantage is conditional: constructing Cayley from a block encoding requires a shifted solve that cancels the query saving generically, whereas the structured family permits direct realization from resolvent generators.The claimed below-classical gate cost also assumes b is supplied as a quantum state and the result is used as one.Source: §7.3 · pp. 23–24
  • On the structured family, the generator balance lies between 3.2 and 3.9, while generator-reproduction degrees range from 4 to 52 and do not depend on N.The family uses three-point discretizations of Sturm–Liouville operators with four positive bounded coefficients; the result concerns functions concentrated near the smallest eigenvalue.Source: §7.3 · pp. 23–24
  • For the structured Sturm–Liouville family, the Cayley effective cost is eO(κ^1/4), versus eO(κ) for polynomial and exponential approaches; it remains cheaper by κ^1/4 even when positive-definite structure lets QSVT reduce its degree.The comparison assumes generator balance remains bounded and generators can be prepared at polylogarithmic depth.Source: §7.3 · pp. 23–24

8 Conclusions and open problems

The conclusions characterize the Cayley model’s reachable rational functions and its trade-off between query savings and encoding cost. They identify data loading, the full rational class, and gate-level accounting as open constraints or directions.

Conclusions

  • Cayley processing reaches type (2d, 2d) rational functions with poles at σ ± iγ, each of order at most d, using one ancilla and no parity restriction.Its two parameters let the encoding tailor accuracy to where the target function is difficult.Source: §8 · pp. 24–25
  • Products of Cayley factors are exactly the rational functions unitary on every Hermitian matrix, while their transformed approximation problem becomes trigonometric approximation on the circle.The resulting numerator is constrained by unitarity rather than freely chosen.Source: §8 · p. 25
  • A fixed-pole rational function is reached exactly at degree one in the query model, but generic realization from a block encoding cancels the degree gain; structure can bypass that construction.Source: §8 · p. 25

Open problems

  • Polylogarithmic-depth loading of tridiagonal resolvent generators requires regularity shown for the studied analytic-coefficient operators but not guaranteed in general.Source: §8 · p. 25
  • The full rational class can be reached by combining GQSP circuits with additional ancillas, but reaching it with fewer ancillas and degree-proportional queries remains open.Source: §8 · p. 25
  • Concrete gate counts and the trade-off between direct processing of a block-encoded resolvent and unitary encoding remain to be assessed.Source: §8 · p. 25

Funding

The work reports partial support from an INdAM–GNCS project and the U.S. Department of Energy’s SQMS center.

Funding

  • Partial support came from an INdAM–GNCS project and the U.S. Department of Energy’s SQMS center.Source: Funding · pp. 25–26
Loading 2610.23429v1…