Pith. sign in

REVIEW 2 major objections 6 minor 43 references

Reviewed by Pith at T0; open to challenge.

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

T0 review · glm-5.2

Quantum linear system solver breaks free of the condition number

2026-07-09 02:08 UTC pith:BU3TURE4

load-bearing objection Two beyond-κ quantum linear system solvers: one via effective truncation (with an unverified VTAA step), one via filtering with a clean constant-prefactor analysis. The filtering solver is the stronger contribution. the 2 major comments →

arxiv 2607.07691 v1 pith:BU3TURE4 submitted 2026-07-08 quant-ph cs.DScs.NAmath.NA

Faster quantum linear system solver beyond the condition number

Alexander M. Dalzell , Jianqiang Li , Yuan Su This is my paper
classification quant-ph cs.DScs.NAmath.NA
keywords rangleepsilonkappanumberconditionfraclinearquantum
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.

This paper presents two quantum algorithms for solving linear systems Ax=b whose query complexity does not scale with the spectral condition number κ — the standard worst-case cost parameter that has governed all prior quantum linear system solvers. The first algorithm, the truncation-based solver, introduces an effective condition number κ_eff ≤ κ that captures how much of the solution actually lives on near-singular directions. It runs a conventional solver configured with κ_eff instead of κ, and the authors prove a family of upper bounds on κ_eff in terms of singular value transformations of the solution vector, indexed by a tunable parameter t. The second algorithm, the filtering-based solver, uses eigenstate filtering over the unit circle with an effective spectral gap, achieving a leading-order query complexity of 6||A^{-1†}x||/(||x||ε)·ln(1/ε) with a small constant prefactor. Both solvers substantially improve the prior beyond-κ approach, which had 1/ε² scaling; the new solvers achieve 1/ε or 1/ε·ln(1/ε) scaling. The authors also provide a solution norm estimator with the same asymptotic cost, making the results self-contained when the solution norm is unknown.

Core claim

The central object is the effective condition number κ_eff, defined as the smallest threshold such that singular vector components below that threshold contribute at most an ε-fraction of the solution's weight. This is a quantile of the weighted singular value distribution of A^{-1}|b⟩, and it can be much smaller than κ when the initial vector |b⟩ has little overlap with the most singular directions of A. The truncation-based solver exploits this by running a conventional solver with κ_eff as the condition number parameter, leveraging a weak truncation property that guarantees correctness when the initial state is effectively supported on the non-truncated subspace. The filtering-based sidss

What carries the argument

Effective condition number κ_eff defined as a quantile of the weighted inverse singular value distribution; weak and strong truncation properties for quantum linear system solvers; eigenstate filtering over the unit circle via Dolph-Chebyshev polynomials applied to the shifted operator (W−I)/2; effective gap lemma for the unitary W=(2Π₀−I)(I−2Π₁); affine dilation model jointly encoding A and |b⟩; Palais matrix for constructing truncated state preparation oracles.

Load-bearing premise

The truncation-based solver relies on the claim that variable time amplitude amplification (VTAA) satisfies a weak truncation property when configured with κ_eff < κ, meaning it correctly produces the solution state given the promise that the initial vector is supported on singular vectors with singular values above κ_eff^{-1}. The paper states that verifying this property is straightforward because the proof from prior work carries over 'line by line' within the truncatedsub

What would settle it

Construct a linear system and initial vector where the effective condition number κ_eff is small but the VTAA-based solver, configured with κ_eff, produces an output state far from the true solution. This would falsify the weak truncation property claim and break the truncation-based solver. Alternatively, find an instance where the effective gap lemma fails to provide sufficient suppression for the filtering-based solver, causing the error bound to be violated.

If this is right

  • Ill-conditioned linear systems where the condition number κ is exponentially large but the solution vector has limited support on near-singular directions become feasible for quantum solution, broadening the class of problems where quantum linear system solvers offer practical advantage.
  • The affine dilation model opens a new design space for quantum preconditioning: rather than reducing κ itself, preconditioners can redistribute how |b⟩ aligns with singular vectors of A to reduce κ_eff, potentially yielding speedups even when classical preconditioning fails to reduce the condition number.
  • The filtering-based solver's simplicity (constant prefactor 6, no variable-time amplitude amplification) makes it a concrete candidate for circuit-level resource estimation on fault-tolerant quantum hardware, which could reveal whether beyond-κ solvers offer tangible advantage on small-scale instances.
  • The hierarchy of upper bounds on κ_eff indexed by t allows trading off between vector-norm computation cost and accuracy dependence: choosing t=Θ(log(1/ε)/log log(1/ε)) yields polylogarithmic dependence on 1/ε, while t=1 recovers the simplest bound κ_eff ≤ ||A^{-1†}x||/(||x||ε).

Where Pith is reading between the lines

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

  • The effective condition number κ_eff is an instance-specific quantity that cannot be computed without knowledge of the singular value decomposition of A and the overlaps of |b⟩ with the left singular vectors. The paper provides upper bounds, but determining which bound is tightest for a given instance may itself require classical computation comparable to solving the system.
  • The two solvers have structurally different error profiles — truncation discards small-singular-value components entirely, while filtering preserves the full solution but incurs incomplete-suppression errors. For applications where the discarded components carry physically meaningful information (e.g., Green's functions in many-body physics), the truncation-based solver's bias may be unacceptable
  • The weak truncation property for VTAA is verified by claiming the proof from prior work carries over 'line by line' within the truncated subspace. If this verification fails for specific VTAA implementations or configurations, the truncation-based solver's correctness guarantee would require independent proof.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. This paper presents two quantum linear system solvers whose query complexity is independent of the spectral condition number κ. The first (truncation-based) solver introduces an effective condition number κ_eff ≤ κ, defined as a quantile of the weighted singular value distribution, and invokes a conventional solver (VTAA) configured with κ_eff. A family of upper bounds on κ_eff is proven via the weighted power mean inequality. The second (filtering-based) solver uses eigenstate filtering over the unit circle with an effective gap, achieving a leading-order query complexity of 6||A^{-1†}x||/(||x||ε) ln(1/ε). Both solvers substantially improve the prior beyond-κ solver of Li [24], which had O(||A^{-1†}x||/(||x||ε²)) scaling. A solution norm estimator with comparable cost is also provided.

Significance. The paper makes a genuine contribution to the quantum linear systems literature. The effective condition number framework (Theorem 1) is a clean conceptual contribution: defining κ_eff via a quantile of the weighted singular value distribution and bounding it via the power mean inequality is natural and well-executed. The filtering-based solver is notably simple and ships a detailed constant-prefactor analysis (Section 4.4, Appendix D), including an optimized error budget split via the Lambert-W function. The solution norm estimator (Section 4.5) makes the result self-contained. The improvement from ε^{-2} to ε^{-1} ln(1/ε) over Li's solver is substantial and practically relevant. The affine dilation model (Section 2.2) and its analysis (Appendix B) provide a useful generalization.

major comments (2)
  1. Section 3.5, final paragraph: The claim that 'verifying the weak truncation property for VTAA is straightforward: the proof from [29] carries over line by line within Im(Π_left,[κ_eff^{-1},1])' is the load-bearing step for the truncation-based solver (Theorem 3, Corollary 7). While the claim is plausible—when |b⟩ is promised to lie in Im(Π_left,[κ_eff^{-1},1]), the restricted operator has effective condition number at most κ_eff, so the VTAA analysis calibrated to κ_eff should apply—the assertion is stated without any formal justification. The paper itself acknowledges (Section 3.3) that establishing the strong truncation property for VTAA is 'highly nontrivial' and that VTAA 'amplifies first and then truncates, rather than truncating first and then amplifying.' The weak truncation property sidesteps this, but the reader needs at least a sketch of why the promise on |b⟩ resolves the non-
  2. Section 3.3, Eq. (72): The paper describes the output of VTAA configured with κ_eff as a state proportional to (1/Θ(ακ_eff))|0⟩ Σ_{σ_j ≥ α^{-1}κ_eff} σ_j^{-1} w_j |v_j⟩ + |1⟩ Σ_{σ_j < α^{-1}κ_eff} w_j |v_j⟩, and notes that 'both components are amplified in VTAA.' This is presented as motivation for the weak truncation approach, but it also reveals that VTAA does interact with components below κ_eff^{-1} even when configured with κ_eff. The paper should clarify how the weak truncation promise (|b⟩ ∈ Im(Π_left,[κ_eff^{-1},1])) eliminates this interaction entirely, or whether residual interactions with small singular value components (e.g., through imperfect stopping conditions in VTAA) could introduce errors not captured by the 'line by line' argument.
minor comments (6)
  1. The notation (A)^{-t}_{sv} for singular value transformation (Eq. 50) is non-standard; a brief reminder that this denotes QSVT with function σ ↦ σ^{-t} would help readers less familiar with [16].
  2. Table 1 is comprehensive but does not consistently indicate which results assume known ||x||. A footnote or column annotation would improve clarity.
  3. Section 4.4, Eq. (139): The full expression for the query complexity is quite unwieldy. While the simplification to leading order (Eq. 140) is clear, the intermediate expression could benefit from being broken into named components (amplitude amplification factor × filtering cost).
  4. Appendix C introduces generalized truncation properties (Definitions 4–5) that are stronger than those in the main text. The relationship between the generalized and non-generalized versions could be stated more explicitly, including whether the generalized versions are needed for any result in the main text.
  5. Section 5, Eq. (154)–(155): The toy example illustrating the affine dilation model advantage is instructive. It would be helpful to also state the effective condition number κ_eff for this example in the standard model, to directly compare with the Θ(1) result in the affine dilation model.
  6. Several references are to works dated 2025–2026. The bibliographic details should be verified for accuracy, especially for works that may still be in preprint at the time of submission.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for a careful and constructive report. We address both major comments below. In brief: (1) we agree that the weak truncation property for VTAA deserves a proof sketch and will add one; (2) we will clarify how the promise on |b⟩ eliminates interaction with small singular value components and address the concern about residual errors from imperfect stopping conditions.

read point-by-point responses

  1. Referee: Section 3.5, final paragraph: The claim that 'verifying the weak truncation property for VTAA is straightforward: the proof from [29] carries over line by line within Im(Π_left,[κ_eff^{-1},1])' is the load-bearing step for the truncation-based solver (Theorem 3, Corollary 7). While the claim is plausible... the assertion is stated without any formal justification. The paper itself acknowledges (Section 3.3) that establishing the strong truncation property for VTAA is 'highly nontrivial'... The reader needs at least a sketch of why the promise on |b⟩ resolves the difficulty.

    Authors: We agree with the referee that this step deserves more than a passing remark. We will add a proof sketch in the revised manuscript. The key observation is as follows. The difficulty identified in Section 3.3 concerns the *strong* truncation property, where the input |b⟩ may have support on singular values below κ_eff^{-1}. In that setting, VTAA amplifies both the desired components (σ_j ≥ κ_eff^{-1}) and the undesired components (σ_j < κ_eff^{-1}), producing the two-branch output of Eq. (72), and the interaction between these branches during the recursive amplification schedule is what makes the analysis nontrivial. However, under the *weak* truncation property, we are given the promise that |b⟩ ∈ Im(Π_left,[κ_eff^{-1},1]), meaning w_j = 0 for all σ_j < κ_eff^{-1}. In this case, the second sum in Eq. (72) vanishes identically—there are no small singular value components to amplify. The VTAA procedure from [29] operates on a walk operator whose spectral decomposition, when restricted to Im(Π_left,[κ_eff^{-1},1]), has all eigenphases bounded by O(κ_eff^{-1}). Concretely, the restricted operator A|_{Im(Π_left,[κ_eff^{-1},1])} has condition number at most κ_eff, and the VTAA analysis of [29, Section 4] depends only on the spectral gap of the walk operator and the solution norm, both of which are controlled by κ_eff (rather than κ) under this promise. The variable-time amplification schedule, the stopping condition analysis, and the error bounds from [29] all go through with κ replaced by κ_eff, because every step of the proof only invokes properties of the walk operator within the subspace on which the input is supported. We will include this argument as a formal lemma with proof sketch in Section 3.5 of the revision. revision: yes

  2. Referee: Section 3.3, Eq. (72): The paper describes the output of VTAA configured with κ_eff as a state proportional to (1/Θ(ακ_eff))|0⟩ Σ_{σ_j ≥ α^{-1}κ_eff} σ_j^{-1} w_j |v_j⟩ + |1⟩ Σ_{σ_j < α^{-1}κ_eff} w_j |v_j⟩, and notes that 'both components are amplified in VTAA.' This is presented as motivation for the weak truncation approach, but it also reveals that VTAA does interact with components below κ_eff^{-1} even when configured with κ_eff. The paper should clarify how the weak truncation promise (|b⟩ ∈ Im(Π_left,[κ_eff^{-1},1])) eliminates this interaction entirely, or whether residual interactions with small singular value components (e.g., through imperfect stopping conditions in VTAA) could introduce errors not captured by the 'line by line' argument.

    Authors: We thank the referee for raising this important point, which we will address explicitly in the revision. The resolution has two parts. First, regarding the interaction shown in Eq. (72): when the weak truncation promise holds (|b⟩ ∈ Im(Π_left,[κ_eff^{-1},1])), all coefficients w_j for σ_j < κ_eff^{-1} are zero, so the second sum in Eq. (72) vanishes. The output of VTAA is then purely proportional to Σ_{σ_j ≥ κ_eff^{-1}} σ_j^{-1} w_j |v_j⟩, which is exactly A^{-1}|b⟩ restricted to the promised subspace—i.e., the desired solution. There is no interaction with small singular value components because there are none in the input. Second, regarding the concern about residual errors from imperfect stopping conditions: the VTAA analysis of [29] accounts for approximation errors in the variable-time stopping conditions through a global error parameter. This error analysis bounds the total deviation of the output state from the ideal amplified state, and the bound depends on the spectral properties of the walk operator *within the subspace on which the input is supported*. Under the promise, this subspace has spectral gap Ω(κ_eff^{-1}), so the error bounds from [29] apply with κ_eff in place of κ. In particular, any leakage into the small singular value subspace would require the walk operator to map vectors from Im(Π_left,[κ_eff^{-1},1]) into its orthogonal complement, but the walk operator preserves the left singular vector subspaces of A (it is built from the block encoding of A), so no such leakage occurs. We will add a remark to Section 3.3 clarifying that Eq. (72) is presented as motivation for the *difficulty* of the strong truncation property, and that the weak truncation promise eliminates the second term entirely, along with the above explanation of why imperfect VTAA停止 revision: no

Circularity Check

0 steps flagged

No significant circularity found; derivation is self-contained against external benchmarks.

full rationale

The paper's two main derivation chains are not circular. (1) The effective condition number κ_eff is defined as a quantile of the weighted singular value distribution (Eq. 41), and the family of upper bounds (Eq. 51) follows from the weighted power mean inequality (Lemma 3) applied to this definition—this is a genuine mathematical derivation, not a fit renamed as prediction. (2) The filtering-based solver's complexity (Section 4.4) is derived from the effective gap lemma (Lemma 10), which is proved in the paper itself via Hermitian qubitization, combined with the constrained orthogonal decomposition (Corollary 9, derived from first principles) and standard Dolph-Chebyshev QSVT filtering. The constant prefactor of 6 is obtained through an explicit optimization (Appendix D). The most load-bearing self-citation is to [29] (Low and Su, with Yuan Su as co-author) for the claim that VTAA satisfies the weak truncation property because 'the proof from [29] carries over line by line within Im(Π_left)' (Section 3.5). This is a correctness assertion about whether an existing analysis applies in a restricted subspace, not a circular definition. The citation to [24] (Li, a co-author) is as prior art being improved upon (from O(ε^{-2}) to O(ε^{-1} ln(1/ε))), which is a genuine asymptotic improvement. The citation to [22] (Lee et al., no author overlap) for the effective gap lemma is external. No step reduces to its own inputs by construction. The minor self-citation to [29] for the VTAA carry-over claim is not load-bearing for circularity purposes—it raises a correctness concern (does the proof truly carry over?), not a circularity concern (is the result defined in terms of itself?). Score 1 reflects the minor self-citation that is not circular but could benefit from more explicit verification.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 3 invented entities

The paper introduces one genuinely new mathematical object (κ_eff, defined constructively from the SVD) and one new input model (affine dilation, a formalization of prior work). The free parameters (t, β, γ, c) are algorithm design choices, not fitted constants. The key ad hoc assumption is the weak truncation property for VTAA, which is claimed but not fully proven in the main text.

free parameters (4)
  • t (truncation parameter) = t = Θ(log(1/ε) / log log(1/ε)) for polylogarithmic ε-scaling; t = 1 for simplest bound
    Tunable parameter indexing the family of upper bounds on κ_eff. Not fitted to data but chosen by the algorithm designer to trade off vector norm growth against ε-dependence.
  • β (rescaling scalar in filtering solver) = β = α_x = Θ(||x||) when solution norm is known
    Controls the augmented matrix βA - |b⟩. Set to the estimated solution norm to balance success amplitude against filtering cost.
  • γ (error budget split) = γ₀ = 1 + 1/W_{-1}(-ε/e) (Lambert-W optimum)
    Fraction of error budget allocated to effective gap vs. filtering accuracy. Optimized in Appendix D to minimize the constant prefactor.
  • c (affine dilation scalar) = c = α(||x||² + 1)/||x|| in Appendix B.3
    Controls the invertibility of the affine dilated matrix. Chosen to match truncation-based and filtering-based complexities in the affine dilation model.
axioms (5)
  • domain assumption Block encoding input model: A is accessed through a unitary O_A with A = G₁† O_A G₀, ||A|| ≤ 1
    Standard input model for quantum linear algebra, invoked in Section 2.1.
  • domain assumption Solution norm ||x|| is known to constant multiplicative accuracy (or can be estimated)
    Required for the filtering-based solver to set β = Θ(||x||). Addressed by the solution norm estimator in Section 4.5 when unknown.
  • ad hoc to paper Weak truncation property holds for VTAA configured with κ_eff
    Section 3.5 states the proof from [29] carries over 'line by line' within the truncated subspace Im(Π_left,[κ_eff^{-1}, 1]). This is the key unproven-in-text assumption for the truncation-based solver.
  • standard math Effective gap lemma [22, Lemma 4.2] applies to W = (2Π₀ - I)(I - 2Π₁)
    External result from quantum query complexity, invoked in Section 4.2. The paper provides a self-contained proof via Hermitian qubitization.
  • standard math Dolph-Chebyshev polynomials achieve the claimed filtering guarantees
    Cited from [15, Appendix B.2], with properties stated in Lemma 11. Standard result in approximation theory.
invented entities (3)
  • Effective condition number κ_eff independent evidence
    purpose: Instance-specific complexity measure replacing κ, defined as the quantile of the weighted inverse singular value distribution (Eq. 41)
    κ_eff is defined constructively from the SVD of A and the overlaps of |b⟩ with left singular vectors. It makes a falsifiable prediction: the truncated solution Π_right,[κ_eff^{-1},1] A^{-1}|b⟩ is within O(ε) of the full solution, which is proven in Theorem 1.
  • Affine dilation model independent evidence
    purpose: Input model where A and |b⟩ are block encoded jointly as [A -|b⟩; 0 c], allowing optimized normalization
    The model is a formalization of the augmented matrix approach from [24], extended with an invertibility parameter c. The toy example in Section 5 demonstrates a concrete separation from the standard model.
  • Strong/weak truncation properties independent evidence
    purpose: Abstract properties that a quantum linear system solver must satisfy to be used as a beyond-κ solver via effective truncation
    These are definitions, not postulated physical entities. Their satisfiability is verified for VTAA (weak property) and shown to imply the strong property under optimal state preparation (Theorem 3).

pith-pipeline@v1.1.0-glm · 50065 in / 3775 out tokens · 554986 ms · 2026-07-09T02:08:54.544986+00:00 · methodology

0 comments
read the original abstract

The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution $|x\rangle$ of linear system $Ax=| b \rangle$ to accuracy $\epsilon$ with complexity independent of the condition number $\kappa=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(\kappa_{\mathrm{eff}}\operatorname{polylog}\left(\frac{\kappa_{\mathrm{eff}}}{\epsilon}\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $\kappa_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{\epsilon^{1/t}}$ for positive even integer $t$ and $\kappa_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{\epsilon^{1/t}}$ for positive odd $t$, overcoming the $\kappa$-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity $6\frac{\lVert A^{-1\dagger}|x\rangle\rVert}{\epsilon}\ln\left(\frac{1}{\epsilon}\right)$ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.

Figures

Figures reproduced from arXiv: 2607.07691 by Alexander M. Dalzell, Jianqiang Li, Yuan Su.

Figure 1
Figure 1. Figure 1: Illustration of the definition of effective condition number. The step function represents the [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the algorithmic template for constructing beyond- [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A non-decreasing function and its generalized inverses. Plateaus of [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of QSVT-based eigenstate filtering over the unit circle by shifting. [PITH_FULL_IMAGE:figures/full_fig_p032_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Qualitative behavior of g(γ) for constant-prefactor optimization for the filtering-based solver. D Constant-prefactor optimization for filtering with effective gap In this appendix, we optimize the constant prefactor of the query complexity for eigenstate filtering with effective gap. Recall from the main text (Section 4.4) that, in order to prepare the normalized solution state with accuracy ϵ, we choose … view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 31 internal anchors

  1. [1]

    Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues

    Abhijeet Alase and Salini Karuvade,Resolvent-based quantum phase estimation: Towards esti- mation of parametrized eigenvalues, 2024, arXiv:2410.04837, DOI:10.48550/arXiv.2410.04837. (Cited on page 3)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2410.04837 2024

  2. [2]

    Andris Ambainis,Variable time amplitude amplification and quantum algorithms for linear algebra problems, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), vol. 14, pp. 636–647, 2012, arXiv:1010.4458, DOI:10.4230/LIPIcs.STACS.2012.636. (Cited on pages 3 and 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.stacs.2012.636 2012

  3. [3]

    Andris Ambainis, Martins Kokainis, and Jevg¯ enijs Vihrovs,Improved algorithm and lower bound for variable time quantum search, 18th Conference on the Theory of Quantum Com- putation, Communication and Cryptography (TQC 2023), vol. 266, pp. 7:1–7:18, 2023, arXiv:2302.06749, DOI:10.4230/LIPIcs.TQC.2023.7. (Cited on page 27)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.tqc.2023.7 2023

  4. [4]

    Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

    Dong An and Lin Lin,Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm, ACM Transactions on Quantum Computing3(2022), 1–28, arXiv:1909.05500, DOI:10.1145/3498331. (Cited on page 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/3498331 2022

  5. [6]

    Quantum algorithm for linear differential equations with exponentially improved dependence on precision

    Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang,Quantum algorithm for linear differential equations with exponentially improved dependence on preci- sion, Communications in Mathematical Physics356(2017), 1057–1081, arXiv:1701.03684, DOI:10.1007/s00220-017-3002-y. (Cited on page 3)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00220-017-3002-y 2017

  6. [7]

    Quantum Amplitude Amplification and Estimation

    Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp,Quantum amplitude amplifica- tion and estimation, Contemporary Mathematics305(2002), 53–74, arXiv:quant-ph/0005055, DOI:10.1090/conm/305/05215. (Cited on page 27)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1090/conm/305/05215 2002

  7. [8]

    Shantanav Chakraborty, Andr´ as Gily´ en, and Stacey Jeffery,The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol. 132, pp. 33:1– 33:14, 2019, arXiv:1804.01973, DOI:10.4230/LIPIcs.ICALP.2019.33. (Cited on pages 5 and 11)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.icalp.2019.33 2019

  8. [9]

    Quantum Regularized Least Squares

    Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri,Quantum regularized least squares, Quantum7(2023), 988, arXiv:2206.13143, DOI:10.22331/q-2023-04-27-988. (Cited on page 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.22331/q-2023-04-27-988 2023

  9. [10]

    Bounds on the Lambert function and their application to the outage analysis of user cooperation

    Ioannis Chatzigeorgiou,Bounds on the Lambert function and their application to the out- age analysis of user cooperation, IEEE Communications Letters17(2013), no. 8, 1505–1508, arXiv:1601.04895, DOI:10.1109/LCOMM.2013.070113.130972. (Cited on page 48)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/lcomm.2013.070113.130972 2013

  10. [11]

    Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Andrew M. Childs, Robin Kothari, and Rolando D. Somma,Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM Journal on Computing46(2017), 1920–1950, arXiv:1511.02306, DOI:10.1137/16M1087072. (Cited on page 5). 49

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/16m1087072 2017

  11. [12]

    Pedro C.S. Costa, Dong An, Ryan Babbush, and Dominic Berry,The discrete adiabatic quan- tum linear system solver has lower constant factors than the randomized adiabatic solver, Quan- tum9(2025), 1887, arXiv:2312.07690, DOI:10.22331/q-2025-10-20-1887. (Cited on page 3)

    work page doi:10.22331/q-2025-10-20-1887 2025

  12. [13]

    Optimal scaling quantum linear systems solver via discrete adiabatic theorem

    Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry,Optimal scaling quantum linear-systems solver via discrete adiabatic theorem, PRX Quantum3(2022), 040303, arXiv:2111.08152, DOI:10.1103/PRXQuantum.3.040303. (Cited on pages 3, 4, 5, and 34)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/prxquantum.3.040303 2022

  13. [14]

    Joseph Cunningham and J´ er´ emie Roland,Eigenpath traversal by Poisson-distributed phase randomisation, 19th Conference on the Theory of Quantum Computation, Communi- cation and Cryptography (TQC 2024), vol. 310, pp. 7:1–7:20, 2024, arXiv:2406.03972, DOI:10.4230/LIPIcs.TQC.2024.7. (Cited on pages 3, 4, and 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.tqc.2024.7 2024

  14. [15]

    A shortcut to an optimal quantum linear system solver

    Alexander M. Dalzell,A shortcut to an optimal quantum linear system solver, 2024, arXiv:2406.12086, DOI:10.48550/arXiv.2406.12086. (Cited on pages 3, 4, 5, 10, 14, 32, 37, and 39)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2406.12086 2024

  15. [16]

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

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe,Quantum singular value trans- formation and beyond: exponential improvements for quantum matrix arithmetics, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193–204, 2019, arXiv:1806.01838, DOI:10.1145/3313276.3316366. (Cited on pages 5, 7, 12, and 19)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/3313276.3316366 2019

  16. [17]

    (Cited on page 11)

    Paul R Halmos,Normal dilations and extensions of operators, Summa Brasiliensis Math2 (1950), 125–134. (Cited on page 11)

    work page 1950

  17. [18]

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd,Quantum algorithm for lin- ear systems of equations, Physical Review Letters103(2009), 150502, arXiv:0811.3171, DOI:10.1103/PhysRevLett.103.150502. (Cited on pages 3, 4, and 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.103.150502 2009

  18. [19]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson,Matrix analysis, Cambridge University Press, 2012, DOI:10.1017/CBO9781139020411. (Cited on pages 11, 23, and 24)

    work page doi:10.1017/cbo9781139020411 2012

  19. [20]

    (Cited on page 3)

    Hari Krovi,Improved quantum algorithms for linear and nonlinear differential equations, Quan- tum7(2023), 913, arXiv:2202.01054, DOI:10.22331/q-2023-02-02-913. (Cited on page 3)

    work page doi:10.22331/q-2023-02-02-913 2023

  20. [21]

    1, 20240026, DOI:doi:10.1515/spma-2024-0026

    Shuhei Kudo,Complex Palais matrix and a new unitary transform with bounded component norms, Special Matrices12(2024), no. 1, 20240026, DOI:doi:10.1515/spma-2024-0026. (Cited on page 23)

    work page doi:10.1515/spma-2024-0026 2024

  21. [22]

    Quantum query complexity of state conversion

    Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert ˇSpalek, and Mario Szegedy,Quantum query complexity of state conversion, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 344–353, 2011, arXiv:1011.3020, DOI:10.1109/FOCS.2011.75. (Cited on pages 10 and 30)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/focs.2011.75 2011

  22. [23]

    Quantum phase discrimination with applications to quantum search on graphs

    Guanzhong Li, Lvzhou Li, and Jingquan Luo,Quantum phase discrimination with applications to quantum search on graphs, 2025, arXiv:2504.15194, DOI:10.48550/arXiv.2504.15194. (Cited on pages 10, 32, and 36)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2504.15194 2025

  23. [24]

    (Cited on pages 4, 5, 6, 10, 12, 13, 30, 41, and 42)

    Jianqiang Li,A new quantum linear system algorithm beyond the condition number and its application to solving multivariate polynomial systems, 2025, arXiv:2510.05588, DOI:10.48550/arXiv.2510.05588. (Cited on pages 4, 5, 6, 10, 12, 13, 30, 41, and 42). 50

    work page doi:10.48550/arxiv.2510.05588 2025

  24. [25]

    Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

    Lin Lin and Yu Tong,Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems, Quantum4(2020), 361, arXiv:1910.14596, DOI:10.22331/q- 2020-11-11-361. (Cited on page 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.22331/q- 2020

  25. [26]

    Hamiltonian Simulation by Uniform Spectral Amplification

    Guang Hao Low and Isaac L. Chuang,Hamiltonian simulation by uniform spectral amplifica- tion, 2017, arXiv:1707.05391, DOI:10.48550/arXiv.1707.05391. (Cited on page 11)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1707.05391 2017

  26. [27]

    Optimal Hamiltonian Simulation by Quantum Signal Processing

    Guang Hao Low and Isaac L. Chuang,Optimal Hamiltonian simulation by quan- tum signal processing, Physical Review Letters118(2017), 010501, arXiv:1606.02685, DOI:10.1103/PhysRevLett.118.010501. (Cited on page 10)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.118.010501 2017

  27. [28]

    1, 135–215, arXiv:2401.06240, DOI:10.1137/24M1689363

    Guang Hao Low and Yuan Su,Quantum eigenvalue processing, SIAM Journal on Computing 55(2026), no. 1, 135–215, arXiv:2401.06240, DOI:10.1137/24M1689363. (Cited on page 3)

    work page doi:10.1137/24m1689363 2026

  28. [29]

    Guang Hao Low and Yuan Su,Quantum linear system algorithm with optimal queries to initial state preparation, Quantum10(2026), 2041, arXiv:2410.18178, DOI:10.22331/q-2026-03-23-

    work page doi:10.22331/q-2026-03-23- 2026

  29. [30]

    (Cited on pages 3, 4, 5, 23, 27, and 30)

    work page

  30. [31]

    The methodology of resonant equiangular composite quantum gates

    Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang,Methodology of resonant equian- gular composite quantum gates, Physical Review X6(2016), 041067, arXiv:1603.03996, DOI:10.1103/PhysRevX.6.041067. (Cited on page 10)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevx.6.041067 2016

  31. [32]

    A Grand Unification of Quantum Algorithms

    John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang,Grand uni- fication of quantum algorithms, PRX Quantum2(2021), 040203, arXiv:2105.02859, DOI:10.1103/PRXQuantum.2.040203. (Cited on page 32)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/prxquantum.2.040203 2021

  32. [33]

    (Cited on page 3)

    Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, and Matthias Rosenkranz,Sparsity- dependent complexity lower bound of quantum linear system solvers, 2026, arXiv:2601.16697, DOI:10.48550/arXiv.2601.16697. (Cited on page 3)

    work page doi:10.48550/arxiv.2601.16697 2026

  33. [34]

    Generalized Quantum Signal Processing

    Danial Motlagh and Nathan Wiebe,Generalized quantum signal processing, PRX Quantum5 (2024), 020368, arXiv:2308.01501, DOI:10.1103/PRXQuantum.5.020368. (Cited on page 10)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/prxquantum.5.020368 2024

  34. [35]

    (Cited on page 18)

    Art of Problem Solving,Power mean inequality, 2024, https://artofproblemsolving.com/wiki/ index.php/Power Mean Inequality, Last accessed on 2026-05-08. (Cited on page 18)

    work page 2024

  35. [36]

    On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number

    Davide Orsucci and Vedran Dunjko,On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number, Quantum5(2021), 573, arXiv:2101.11868, DOI:10.22331/q-2021-11-08-573. (Cited on page 41)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.22331/q-2021-11-08-573 2021

  36. [37]

    (Cited on page 18)

    J Michael Steele,The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities, Cambridge University Press, 2004, DOI:10.1017/CBO9780511817106. (Cited on page 18)

    work page doi:10.1017/cbo9780511817106 2004

  37. [38]

    Yi˘ git Suba¸ sı, Rolando D. Somma, and Davide Orsucci,Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing, Physical Review Letters122(2019), 060504, arXiv:1805.10549, DOI:10.1103/PhysRevLett.122.060504. (Cited on page 5)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.122.060504 2019

  38. [39]

    Quantum algorithm for matrix functions by Cauchy's integral formula

    Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi S. Usuda,Quantum algo- rithm for matrix functions by Cauchy’s integral formula, Quantum Information and Compu- tation20(2020), 14–36, arXiv:2106.08075, DOI:10.26421/QIC20.1-2-2. (Cited on page 3). 51

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.26421/qic20.1-2-2 2020

  39. [40]

    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, arXiv:2106.08076, DOI:10.48550/arXiv.2106.08076. (Cited on page 3)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2106.08076 2021

  40. [41]

    Fast inversion, preconditioned quantum linear system solvers, and fast evaluation 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 evalua- tion of matrix functions, Physical Review A104(2021), 032422, arXiv:2008.13295, DOI:10.1103/PhysRevA.104.032422. (Cited on page 3)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physreva.104.032422 2021

  41. [42]

    Please, not \textit{another} note about Generalized Inverses

    Philipp Wacker,Please, notanothernote about generalized inverses, 2023, arXiv:2306.06989, DOI:10.48550/arXiv.2306.06989. (Cited on pages 15, 16, and 17)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2306.06989 2023

  42. [43]

    Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

    Yanqiao Wang and Jin-Peng Liu,Sign embedding quantum algorithms for matrix equations and matrix functions, 2026, arXiv:2604.25333, DOI:10.48550/arXiv.2604.25333. (Cited on page 3)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2604.25333 2026

  43. [44]

    Quantum Phase Processing and its Applications in Estimating Phase and Entropies

    Youle Wang, Lei Zhang, Zhan Yu, and Xin Wang,Quantum phase processing and its applications in estimating phase and entropies, Physical Review A108(2023), 062413, arXiv:2209.14278, DOI:10.1103/PhysRevA.108.062413. (Cited on page 10). 52

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physreva.108.062413 2023