PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum oblique eigenprojection

Alexander M. Dalzell, Yuan Su

arXiv:2609.40254v1quant-phcs.DSphysics.chem-ph

TL;DR

Standard resolvent integration can require an inflated normalization factor for oblique eigenprojection, raising the cost when used within larger computations. The paper uses two-sided block preconditioning to obtain near-linear inverse-gap query complexity and near-optimal normalization, with applications to eigenstate preparation and matrix equations.

  • Problem

    Standard resolvent integration exposes only the projector block, leaving the other blocks undetermined and forcing a large normalization factor that increases algorithm cost.

    Source: §3 · p. 7, §2 · p. 7

  • Method

    A two-sided block preconditioning characterizes every block through a discrete Fourier transform of the matrix resolvent, suppressing inverse-gap growth in normalization.

    Source: §1 · p. 5, §6 · p. 16

  • Results

    The method achieves query complexity nearly linear in 1/δ and normalization close to Θ(∥Π∥), quadratically improving standard resolvent integration and matching known orthogonal-projection results.

    Source: §1 · p. 4, §6 · p. 16

  • Takeaways & Limitations

    Applications include complex-spectrum eigenstate preparation beyond Low and Su [28], Riccati-equation solving with a cubic improvement over prior work [35], and Sylvester-equation solving with a quadratic improvement over [51].

    Source: §1 · p. 5

    The algorithm requires the input spectrum to remain separated from the target region's boundary by a gap, so its cost depends on that input-matrix gap.

    Source: §6 · p. 17

Abstract

from arXiv · show

Every square matrix decomposes its underlying Hilbert space into generalized, nonorthogonal eigensubspaces. We show that a quantum computer can perform such an oblique eigenprojection $\Pi$ given block encoding access to the input matrix. Our approach has a query complexity nearly linear in the inverse gap and a normalization factor close to $\lVert\Pi\rVert$ under a spectral-set condition on the input. This covers common assumptions on the numerical range or diagonalizability and matches known results for orthogonal eigenprojections. We achieve this with a two-sided block preconditioning that uses a discrete Fourier transform of the matrix resolvent. We describe applications to: (i) preparing eigenstates of matrices with complex eigenvalues, extending the quantum eigenvalue transformation algorithm of Low and Su beyond real spectra; (ii) solving continuous-time algebraic Riccati equations, cubically speeding up a prior solver of Rodenas-Ruiz, Zhao, and Lee; and (iii) solving ordinary Sylvester equations, quadratically improving a direct augmented method of Wang and Liu. Our result suggests a promising route to applying nonanalytic matrix functions on quantum computers.

1 Introduction

The paper addresses oblique eigenprojection for general matrices, where complex spectra obstruct the polynomial indicator approach used for real spectra. It gives a block-encoding method with near-linear inverse-gap query complexity and normalization close to the projection norm, then applies it to eigenstate preparation and matrix equations.

1 Introduction

  • The paper frames eigenprojection as a matrix-function task, contrasting Hermitian QSVT’s polynomial transformations with the challenges of non-normal matrices.For Hermitian matrices, QSVT uses degree-O(1/δ) polynomials for optimal orthogonal eigenprojection; general non-normal matrices have unrelated eigenvalues and singular values and typically oblique generalized eigensubspaces.Source: §1 · p. 3
  • For complex spectra, polynomial indicator approximation is obstructed, unlike the real-spectrum setting where QSVT can achieve optimal-in-gap orthogonal eigenprojection.Oblique eigenprojections select generalized eigensubspaces and support eigenstate preparation and solutions to Sylvester and Riccati equations.Source: §1 · p. 3, Figure 1 · p. 4
  • Standard resolvent integration recovers the oblique eigenprojection but incurs normalization Θ(∥Π∥/δ), increasing costs when projection is a subroutine.The paper contrasts this with analytic-function QSVT and QEVT, which can use normalization as small as ∥f(A)∥.Source: §1 · p. 4
  • The method performs oblique eigenprojection with near-linear inverse-gap query complexity and normalization close to ∥Π∥ under a spectral-set condition.The condition covers common assumptions on the numerical range or diagonalizability, and the normalization is nearly optimal.Source: §1 · p. 4
  • Two-sided block preconditioning uses a discrete Fourier transform of the matrix resolvent to reduce normalization growth while retaining the standard approach’s query complexity.The method characterizes every block of the resolvent-based encoding, exposing a circulant structure for preconditioning.Source: §1 · p. 5
  • Applications extend Low and Su’s QEVT beyond real spectra and improve prior continuous-time algebraic Riccati and ordinary Sylvester equation solvers.The reported improvements are cubic for the Riccati solver of Rodenas-Ruiz, Zhao, and Lee [35] and quadratic for Wang and Liu’s direct augmented Sylvester method [51].Source: §1 · p. 5

2 Resolvent integral and its block encoding

The section formulates oblique eigenprojection as a matrix-function task and reviews a resolvent-integral construction using block encodings. Its normalization can be much larger than the projector norm, increasing algorithm cost.

2 Resolvent integral and its block encoding

  • The target is the oblique eigenprojection onto generalized eigensubspaces selected by which eigenvalues lie inside the unit circle.The projector is represented by a contour integral of the matrix resolvent, the Riesz projector.Source: §2 · p. 6
  • The standard construction discretizes the resolvent integral, inverts a block-diagonal matrix of shifted copies of A, and averages its diagonal blocks.The resulting block encoding places the eigenprojection in the top-left block, while the other blocks remain unspecified.Source: §2 · pp. 6–7
  • The standard approach incurs normalization Θ(αres), which can greatly exceed the projector norm and increase the cost of algorithms using it.Even for normal A, αres scales as 1/δ while the projector norm is 1.Source: §2 · p. 7

3 Two-sided block preconditioning of resolvent integral

The section exploits structure in the full Fourier-transformed resolvent to precondition its inverse on both sides. Under a spectral-set condition, this reduces normalization toward the projector norm while retaining nearly the standard query complexity.

3 Two-sided block preconditioning of resolvent integral

  • The method addresses the standard construction’s inefficiency: it normalizes unspecified blocks even though only the top-left block contains the desired projector.Block preconditioning selectively reduces normalization by amplifying the blocks of interest.Source: §3 · pp. 7–9
  • Fourier conjugation exposes a complete, structured array of resolvent blocks, rather than only the projector-bearing top-left block.The blocks are determined by the difference between their indices and are discrete Fourier modes of the shifted resolvent.Source: §3 · pp. 7–8
  • Two-sided scaling exploits the bounded Fourier modes and projector-like top-left entry to reduce the norm of the preconditioned inverse.The scalings act nontrivially on the top-left entry, while the remaining row and column are controlled by individual modes.Source: §3 · p. 9
  • For numerical-range-separated blocks, the analysis bounds the modes and discretization error, and yields a reduced preconditioned condition number.The broader guarantee applies under a spectral-set condition; for diagonalizable matrices, the spectral-set constant can be the eigenbasis condition number.Source: §3 · pp. 10–11
  • The preconditioned algorithm retains almost the standard query complexity while reducing normalization to nearly the optimal value ∥Πin∥.The normalization is necessarily bounded below by the projector norm for any block encoding.Source: §3 · pp. 9–10

4 Quantum oblique eigenprojection for more general regions

The section reduces projection onto general spectrum regions to the unit-disk construction by applying a separating function to the matrix. Low-degree rational maps can make this reduction inexpensive, provided the spectral gap is preserved.

4 Quantum oblique eigenprojection for more general regions

  • A separating function maps the target and complementary spectral components inside and outside the unit disk, reducing the general-region projector to the unit-disk construction.The two projectors coincide because A and f(A) share invariant subspaces and the spectral mapping theorem preserves the inside/outside assignment [17, Theorem 12.7.1][36, Theorem 8.3].Source: §4 · p. 11
  • The separating map need only distinguish the spectral components by modulus, so it can be a low-degree rational function rather than an injective or conformal map.In the oracle model, analyticity is required on the two block numerical ranges separately, allowing singularities between them even inside the full numerical range.Source: §4 · pp. 11–12
  • For half-planes, disks, strips, and sectors, separating maps can be built from elementary Möbius factors without approximation.The half-plane case is worked out because it underlies the Riccati and Sylvester applications.Source: §4 · p. 12
  • For a split across the imaginary axis, f(z) = (z − 1)^2/(z + 1)^2 maps the right half-plane inside and the left half-plane outside the unit circle.When the spectrum is separated from the axis by δ, the map preserves a gap δf = Θ(δ) under the stated normalization.Source: §4 · pp. 12–13, Figure 3 · p. 13

5 Applications

The oblique eigenprojection improves three quantum applications: it enables eigenstate preparation for complex spectra and reduces the gap dependence of Riccati and Sylvester solvers. Two-sided preconditioning brings projector normalization close to optimal, lowering the total costs.

5 Applications

  • Two-sided block preconditioning reduces projector normalization close to its optimal value, carrying through to lower overall costs in the three applications.The applications include complex-spectrum eigenstate preparation and continuous-time algebraic Riccati and Sylvester equation solving.Source: §5 · pp. 13–14

5.1 Eigenstate preparation for complex spectra

  • eO(1/δ) queries prepare eigenstates for complex spectra, matching Low and Su’s scaling for real spectra and quadratically improving on the resolvent-integral approach.Near-optimal projector normalization keeps amplitude amplification to eO(1) rounds; the prior approach incurred 1/δ both in projector construction and amplification.Source: §5.1 · pp. 14–15

5.2 Continuous-time algebraic Riccati equations

  • eO(1/δ) queries solve the continuous-time algebraic Riccati equation, a cubic improvement over the prior resolvent-integral solver.The half-plane construction and two-sided preconditioning bring projector normalization close to ∥Πin∥, so the pseudoinverse condition number and solution normalization no longer grow with the inverse gap.Source: §5.2 · p. 15

5.3 Ordinary Sylvester equations

  • eO(1/δ) queries solve ordinary Sylvester equations, quadratically improving on the direct augmented method.The solution is read from a projector block, avoiding a further pseudoinverse; near-normalization also avoids the O(1/δ) amplification cost.Source: §5.3 · p. 16

6 Discussion

The discussion presents oblique eigenprojection as a near-linearly gap-dependent primitive for non-normal matrices, supported by a full Fourier description of the resolvent block encoding. Its reach is bounded by the preconditioning construction and the input spectrum’s separation from the target-region boundary.

6 Discussion

  • The method implements oblique eigenprojection for non-normal matrices with near-linear inverse-gap query complexity and normalization close to ∥Πin∥, improving resolvent integration and matching known orthogonal-projection results.The stated applications improve recent quantum algorithms for complex-spectrum eigenstate preparation and Riccati and Sylvester equations by quadratic to cubic factors.Source: §6 · p. 16
  • The discrete Fourier transform characterizes every block of the resolvent encoding, enabling two-sided preconditioning rather than extracting only the projector-bearing top-left block.The discussion relates attention to full block-encoding structure to prior work on ancilla overhead, arithmetic composition, and reproducing encoded-matrix powers.Source: §6 · pp. 16–17
  • Preconditioning does not directly extend to Wang and Liu’s matrix-sign construction, which uses a product of two resolvents without an analogous closed-form discrete Fourier transform.Adapting preconditioning to that setting is identified as an open direction.Source: §6 · p. 17
  • For more general spectral regions, the current construction inherits cost and spectral-set hypotheses through the separating map f(A); direct resolvent integration would require geometry-specific preconditioning.The discussion identifies avoiding explicit block encoding of f(A) as a desired direction, not an existing result.Source: §6 · p. 17
  • Unlike the Hermitian QSVT contrast described, this algorithm’s cost depends on the input gap from the region boundary, rather than only on target-function geometry.The stated reason is that the construction controls the resolvent on the region boundary and requires spectral separation there.Source: §6 · p. 17
  • The indicator of a spectral region is discontinuous and nonanalytic, while the resolvent construction sidesteps the obstruction to direct polynomial or singular-value implementation.Whether the Fourier-transform and preconditioning ideas extend to other nonanalytic matrix functions remains open.Source: §6 · p. 17

A.1 Resolvent integral and generalized eigensubspaces

  • The Riesz projector recovers the enclosed generalized eigensubspaces and annihilates the excluded ones, acting as an oblique projection between those subspaces.Its integral is the resolvent around a closed curve enclosing the selected part of the spectrum.Source: §A.1 · p. 19

A.2 Block encoding of resolvent integral

The standard block encoding approximates the oblique eigenprojection by discretizing a resolvent integral, with cost governed by the resolvent norm. Spectral-set assumptions bound that norm; the Fourier representation of the full encoding exposes the structure used for preconditioning.

A.2 Block encoding of resolvent integral

  • The unit-circle resolvent integral is discretized at roots of unity, and geometric convergence means the node count affects ancilla size but not the construction’s query complexity.The stated query cost depends on the block-encoding normalization factor and target precision.Source: §A.2 · p. 20
  • Linear combinations and products of block encodings support the construction, while inversion uses queries determined by the inverse bound and desired accuracy.The linear-combination normalization is the sum of coefficient-weighted input normalizations; product normalization is the product of the two factors.Source: §A.2 · p. 20
  • The numerical range and the spectrum of a diagonalizable matrix are spectral sets, with constants supplied respectively by the Crouzeix–Palencia bound and the eigenbasis condition number.These conditions let the resolvent norm be controlled through spectral-set constants and the gap.Source: §A.2 · p. 22
  • The standard construction block encodes the projector with normalization O(αres), where αres is the maximum resolvent norm on the unit circle.Its query count is given in the proposition in terms of the input block encoding and target precision.Source: §A.2 · pp. 21, 24
  • If the inner matrix and inverse outer matrix have spectral sets with common constant c and gap δ, then αres = O(c ∥Πin∥/δ).The numerical-range and diagonalizability conditions provide standard instances of spectral sets; the diagonalizable bound can use prefactor 2κV.Source: §A.2 · pp. 22–24

B.1 Block encoding matrix resolvent in the Fourier basis

  • Conjugating the block-diagonal shifted-resolvent encoding by the quantum Fourier transform yields a block-circulant operator.Its entries are Fourier modes of the resolvent; the standard method extracts only the zeroth mode, whereas the full transform determines the remaining modes needed for preconditioning.Source: §B.1 · p. 25

B.2 Discrete Fourier transform of matrix resolvent

The discrete Fourier modes of the matrix resolvent arise by aliasing its continuous Fourier coefficients. Their closed form separates contributions from the inner and outer invariant subspaces, enabling bounds on the projector approximation and on every mode.

B.2 Discrete Fourier transform of matrix resolvent

  • Each discrete Fourier mode is the sum of continuous Fourier coefficients whose indices differ from it by integer multiples of the node count.This aliasing identity follows from the resolvent Fourier series and the orthogonality of roots of unity.Source: §B.2 · pp. 25–26
  • The continuous coefficients are powers of the inner compression for nonnegative indices and negative inverse powers of the outer compression for indices at most −1.The discrete transform combines these coefficients through aliasing to give its closed-form modes.Source: §B.2 · p. 26
  • Under the stated spectral-set gap assumptions, the zeroth Fourier mode approximates the eigenprojection and every Fourier mode is uniformly bounded.The assumptions also hold under the numerical-range and diagonalizability conditions described for the matrix compressions.Source: §B.2 · p. 27

B.3 Two-sided block preconditioning of resolvent integral

Two-sided block preconditioning uses the resolvent’s discrete Fourier structure to encode an oblique eigenprojection with normalization near its norm while preserving near-inverse-gap query complexity. The guarantee holds under spectral-set and gap conditions.

B.3 Two-sided block preconditioning of resolvent integral

  • The preconditioned construction gives normalization O(c ∥Πin∥) while retaining query complexity nearly linear in the inverse gap under the theorem’s conditions.The guarantee applies when the relevant compressions admit spectral sets with constant c and the required gap.Source: §B.3 · pp. 28, 30
  • The discrete Fourier transform reveals a circulant structure in the resolvent blocks, which two-sided scaling exploits to reduce the extracted projector’s normalization.Unlike extracting only the resolvent integral’s top-left block, the method characterizes every block before preconditioning.Source: §B.3 · p. 28
  • The scaling parameters trade off growth in the preconditioned inverse against a smaller normalization for the extracted block.The theorem chooses t1 = t2 = 1/√n; the supplied proof passages state that the extracted normalization then becomes O(c ∥Πin∥).Source: §B.3 · pp. 29–30
  • The guarantee also covers diagonalizable inputs when the spectral sets satisfy the stated conditions, with c = κV and δ = δeig/2.These are the theorem’s stated diagonalizability parameters.Source: §B.3 · p. 30

C.1 Reduction to the unit disk

For a general spectral region, an analytic separating map reduces its eigenprojection problem to the unit-disk case. Under spectral-set and gap conditions, the resulting construction guarantees a block encoding of the same projector.

C.1 Reduction to the unit disk

  • The separating map preserves the target projector: the eigenprojection of A equals that of f(A) for the spectrum mapped inside the unit circle.The proof uses spectral mapping and preservation of invariant subspaces.Source: §C.1 · p. 31
  • Theorem 3 applies the unit-disk construction to f(A) when an analytic map separates the inside and outside spectra by modulus.The map must place the target set inside and the other set outside the unit circle with a gap.Source: §C.1 · p. 31
  • Theorem 3 yields a block encoding with the unit-disk construction’s normalization and query guarantees for the mapped matrix.The mapped compressions must have spectral sets with constant c and satisfy the modulus gap condition.Source: §C.1 · pp. 31–32
  • The proof uses spectral sets rather than numerical ranges because mapping a numerical range need not produce the numerical range of the mapped matrix.The passage notes that the mapped set may be nonconvex, while the numerical range of f(Ain) may even meet the unit circle.Source: §C.1 · p. 32

C.2 Half-plane construction

A rational separating map reduces a right-half-plane eigenprojection problem to the unit-disk construction. The resulting guarantee applies when the spectral sets of the two compressions lie on opposite sides of the imaginary axis with a gap.

C.2 Half-plane construction

  • The degree-two rational map sends the right half-plane into the unit disk, the imaginary axis to the unit circle, and the left half-plane outside.Its double zero is at 1 and its double pole is at −1.Source: §C.2 · p. 32
  • For ∥A∥ ≤ 1/2, the map is implemented directly as f(A) = (A − I)^2(A + I)^−2 with normalization O(1).The supplied construction uses O(log(1/ε)) queries to the block encoding of A.Source: §C.2 · p. 33
  • The map transfers half-plane separation into a modulus gap, allowing Theorem 3 to apply to the transformed matrix.The map is analytic on the relevant sets when its pole at −1 lies outside the disk containing them.Source: §C.2 · pp. 33–34
  • The half-plane corollary covers right-half-plane projectors when the inside and outside spectral sets lie in opposite half-planes and have gap δ.The stated sufficient cases use either per-block numerical ranges or spectra of diagonalizable compressions satisfying the separation condition.Source: §C.2 · pp. 33–34

D.1 Eigenstate preparation

For eigenstate preparation with complex eigenvalues, a linear shift and rescaling turn a target disk into the unit-disk setting. The resulting method has 1/δ gap dependence, compared with 1/δ^2 for resolvent integration when ρ = Θ(1).

D.1 Eigenstate preparation

  • The target disk is mapped to the unit disk by f(A) = (A − z0I)/ρ, after which the unit-disk theorem encodes the same projector.The rescaling factor ρ cancels between the mapped block-encoding normalization and the relative gap.Source: §D.1 · pp. 34–35
  • The preparation guarantee assumes spectral sets for Ain − z0I and (Aout − z0I)^−1 with constant c and gap 0 < δ < ρ.The stated theorem prepares the normalized projected state Πin|ψ⟩/η to accuracy ε.Source: §D.1 · pp. 34–35
  • The initial-state overlap η sets the success amplitude of projection and the number of amplification rounds needed to prepare the normalized state.The passage gives O(c ∥Πin∥/η) applications for fixed-point amplitude amplification.Source: §D.1 · p. 35
  • For ρ = Θ(1), eigenstate preparation has 1/δ gap dependence with preconditioning, versus 1/δ^2 for the resolvent integral.The resolvent-integral method also uses O(ρ ∥Πin∥/(ηδ)) queries to the initial-state preparation unitary and its inverse; the preconditioned count is gap-independent.Source: §D.1 · p. 35

D.2 Continuous-time algebraic Riccati equation

The Riccati solution is obtained from the antistable invariant-subspace projector of an associated Hamiltonian matrix. Under spectral-set and singular-value conditions, preconditioning reduces the solver’s gap dependence compared with the resolvent-integral construction.

D.2 Continuous-time algebraic Riccati equation

  • The stabilizing solution is X = -Π₂⁺Π₁, formed from the column blocks of the projector onto the Hamiltonian’s antistable invariant subspace.The pseudoinverse step uses a lower bound σ/αΠ on the nonzero singular values of Π₂/αΠ.Source: §D.2 · p. 36
  • The solution’s block-encoding normalization is reported to be independent of the gap, unlike the resolvent-integral normalization O(∥Πin∥/δ).The bound is stated for the Riccati solution under the paper’s assumptions.Source: §D.2 · pp. 36–37
  • The result assumes spectral sets for the Hamiltonian compressions and a positive lower bound σ on the smallest nonzero singular value of Π₂.The compressions must satisfy the stated spectral-set condition with constant c and gap δ.Source: §D.2 · p. 36
  • Preconditioning reduces the Riccati solver’s overall gap dependence from 1/δ^3 to 1/δ compared with the resolvent-integral construction.The comparison attributes the reduction to removing two gap-dependent factors driven by the projector normalization.Source: §D.2 · p. 37

D.3 Sylvester equation

The Sylvester solution is extracted as the top-right block of an invariant-subspace projector for an augmented matrix. Under spectral separation and spectral-set assumptions, preconditioning removes a gap-dependent normalization factor while keeping query complexity essentially unchanged.

D.3 Sylvester equation

  • The Sylvester solution X is the top-right block of the projector onto the augmented matrix’s A-branch invariant subspace, so no pseudoinverse is needed.The augmented matrix has spectrum given by the union of the spectra of A and −B.Source: §D.3 · p. 37
  • The result assumes spectra of A and −B in opposite half-planes and spectral sets for the augmented matrix’s invariant-subspace compressions.The spectral-set condition uses constant c and gap δ.Source: §D.3 · p. 37
  • The projector’s top-right block yields a block encoding of X with the same normalization factor and accuracy, without additional queries.The proof extracts it by restricting the output register to the first block and the input register to the second.Source: §D.3 · p. 37
  • Preconditioning removes the direct augmented method’s 1/δ normalization factor while keeping query complexity essentially unchanged.The direct method encodes the same projector through resolvent integration.Source: §D.3 · p. 37
Loading 2609.40254v1…