pith. sign in

arxiv: 2406.12086 · v2 · submitted 2024-06-17 · 🪐 quant-ph

A shortcut to an optimal quantum linear system solver

Alexander M. Dalzell This is my paper

Pith reviewed 2026-05-23 23:45 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum linear system solverblock encodingeigenstate filteringquery complexitycondition numberkernel reflectionnorm estimationoptimal quantum algorithms
0
0 comments X

The pith

When the solution norm is known, a quantum linear system solver achieves near-optimal query complexity with a single kernel reflection.

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

This paper presents a simplified quantum algorithm for solving linear systems Ax = b that prepares a quantum state with amplitudes proportional to the solution vector x. It avoids variable-time amplitude amplification and adiabatic path-following by using kernel reflection, an extension of eigenstate filtering. When the solution norm is known exactly, the method requires only one application of kernel reflection to achieve query complexity (1+O(ε))κ ln(2√2/ε). For unknown norms, efficient estimation leads to overall optimal O(κ log(1/ε)) complexity. The results include explicit bounds and make the algorithm conceptually simpler.

Core claim

The paper claims that a conceptually simple QLSS can be built using kernel reflection. If ||x|| is known exactly, it requires only a single application of kernel reflection and achieves query complexity (1+O(ε))κ ln(2√2/ε). If the norm is unknown, norm estimation with O(κ) complexity or O(log log(κ)) kernel projections yields an optimal QLSS with O(κ log(1/ε)) complexity without using the adiabatic theorem. An explicit upper bound of 56κ + 1.05κ ln(1/ε) + o(κ) is given for the optimal QLSS.

What carries the argument

Kernel reflection, a straightforward extension of eigenstate filtering, which allows preparation of the solution state with a single application of the block-encoding oracle.

If this is right

  • The query complexity is (1+O(ε))κ ln(2√2/ε) with one kernel reflection when the norm is known.
  • Norm estimation to constant factor uses O(log log(κ)) applications of kernel projection for near-optimal total complexity.
  • O(κ) complexity for norm estimation yields optimal O(κ log(1/ε)) total complexity.
  • An explicit upper bound of 56κ + 1.05κ ln(1/ε) + o(κ) holds for the optimal version.

Where Pith is reading between the lines

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

  • This simplification could reduce implementation overhead in quantum algorithms that use linear system solvers as subroutines.
  • The approach might be adapted to improve other quantum algorithms based on filtering or block encodings.
  • Explicit constants enable more accurate resource estimates for practical quantum computing applications.

Load-bearing premise

The linear system is provided via a block-encoding oracle that allows efficient implementation of kernel reflection and projection operations.

What would settle it

A specific block-encoded linear system with known solution norm for which the query complexity exceeds (1+O(ε))κ ln(2√2/ε).

Figures

Figures reproduced from arXiv: 2406.12086 by Alexander M. Dalzell.

Figure 1
Figure 1. Figure 1: Illustration of the conceptual idea of our quan [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Success probability of Algorithm 1 and of the kernel projection protocol of Eq. (26), as a function of the approximation ratio t/∥x∥, in the limit that the pre￾cision parameter η → 0. 5 Estimating the norm To achieve O(κ log(1/ε)) query complexity, Algorithm 1 requires that the input parameter t is chosen to approx￾imate ∥x∥ up to a constant multiplicative factor. How￾ever, ∥x∥ is generally not known, othe… view at source ↗
Figure 3
Figure 3. Figure 3: Quantum circuit implementing (1, a + 1)-block-encoding of G. To verify the correctness of the circuit, note that the final three gates implement I2 ⊗ I2 a ⊗ (I2 s − |b⟩⟨b|) + X ⊗ I2 a ⊗ |b⟩⟨b|. By sandwiching this operation with ⟨0| · |0⟩ on the first qubit, the second term vanishes, and we see it constitutes a block-encoding of I2 s − bb† with block-encoding factor 1. The whole circuit then is a simple pr… view at source ↗
Figure 4
Figure 4. Figure 4: Quantum circuit implementing (1, a+ 1)-block-encoding of At. The controlled-⊕m−n gate denotes a series of at most s CNOT gates controlled by the first register and acting on different bits of the final s-qubit register, which transform |en⟩ into |em⟩ if the control bit is set to 1. to |0⟩ and considering possible input and output states on the s-qubit sytem. If the input state is not |en⟩, then UA 15 [PIT… view at source ↗
Figure 5
Figure 5. Figure 5: Quantum circuit implementing a state-preparation unitary [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Quantum circuit implementing (1, a + 2)-block-encoding of Gt. A.5 Block-encoding of A¯ σ The (1, a+ 1)-block-encoding of the matrix A¯ σ is the most complex, and depicted in [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Quantum circuit implementing (1, a + 1)-block-encoding of A¯ σ, which acts on a s + 1-qubit system. B Implementation of kernel projection and kernel reflection B.1 Quantum singular value tranformation The formalism of quantum singular value transformation (QSVT) [16] allows for polynomial transformations of the singular values of a block-encoded matrix. Let UH be an (1, aH)-block-encoding of a matrix H = P… view at source ↗
Figure 8
Figure 8. Figure 8: Quantum circuit implementing the QSVT unitary [PITH_FULL_IMAGE:figures/full_fig_p017_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Example of F∆,ℓ(x) (kernel projection) and R∆,ℓ(x) (kernel reflection) for ∆ = 0.1 and ℓ = 21, implying η ≤ 0.03. Lemma 1. The polynomial F∆,ℓ is guaranteed to satisfy 1. For all x ∈ [−1, 1], it holds that |F∆,ℓ(x)| ≤ 1 2. For all x ∈ [∆, 1], it holds that |F∆,ℓ(x)| ≤ Tℓ( 1+∆2 1−∆2 ) −1 ≤ η. 3. F∆,ℓ(0) = 1. Proof. This builds on and improves upon Lemma 13 of Ref. [8].3 Note that the Chebyshev polynomial Tℓ… view at source ↗
Figure 10
Figure 10. Figure 10: Quantum circuit implementing Algorithm 1. The gate U (Gt) K∆,ℓ is the QSVT circuit depicted in [PITH_FULL_IMAGE:figures/full_fig_p021_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Geometric argument for rigorous lower bound on overlap, see text. The angle [PITH_FULL_IMAGE:figures/full_fig_p022_11.png] view at source ↗
read the original abstract

Given a linear system of equations $A\boldsymbol{x}=\boldsymbol{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $|\boldsymbol{x}\rangle$ for which the amplitudes are proportional to the solution vector $\boldsymbol{x}$. Asymptotically optimal QLSSs have query complexity $O(\kappa \log(1/\varepsilon))$, where $\kappa$ is the condition number of $A$, and $\varepsilon$ is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm $\lVert\boldsymbol{x}\rVert$ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is $(1+O(\varepsilon))\kappa \ln(2\sqrt{2}/\varepsilon)$. If the norm is unknown, our method allows it to be estimated up to a constant factor using $O(\log\log(\kappa))$ applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal $O(\kappa \log\log(\kappa)\log\log\log(\kappa)+\kappa\log(1/\varepsilon))$ total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(\kappa)$ complexity can be achieved for norm estimation, yielding an optimal QLSS with $O(\kappa\log(1/\varepsilon))$ complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of $56\kappa+1.05\kappa \ln(1/\varepsilon)+o(\kappa)$ for the complexity of our optimal QLSS.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents a quantum linear system solver (QLSS) constructed from kernel reflection (an extension of eigenstate filtering) and kernel projection. When the solution norm ||x|| is known exactly, a single kernel reflection yields query complexity (1+O(ε))κ ln(2√2/ε). When the norm is unknown, O(log log κ) kernel projections suffice for constant-factor norm estimation, giving near-optimal total complexity O(κ log log κ log log log κ + κ log(1/ε)); alternatively, an adiabatic-path concept (without invoking the theorem) yields O(κ) norm estimation and an optimal QLSS with explicit upper bound 56κ + 1.05κ ln(1/ε) + o(κ). All constructions remain in the standard block-encoding oracle model and avoid variable-time amplitude amplification.

Significance. If the stated bounds hold, the work supplies a conceptually simpler route to asymptotically optimal QLSS with explicit constants and favorable prefactors. The explicit upper bound of 56κ + 1.05κ ln(1/ε) + o(κ) and the avoidance of variable-time amplification and the adiabatic theorem are concrete strengths that could ease both analysis and implementation. The internal consistency of the error analysis (kernel reflection defined directly from eigenstate filtering, norm estimation reusing known path ideas without the theorem) supports the central claims.

minor comments (2)
  1. [Abstract] The transition from the known-norm case to the unknown-norm case in the abstract would benefit from an explicit pointer to the section deriving the O(κ) norm-estimation bound.
  2. [Section 3] Notation for the kernel reflection operator (e.g., its relation to the projection onto the kernel) should be introduced once with a displayed equation before its first use in the complexity analysis.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and encouraging review, which accurately summarizes the contributions of our manuscript. We are pleased that the referee recognizes the conceptual simplicity, explicit constants, and avoidance of variable-time amplitude amplification and the adiabatic theorem as strengths.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central derivations for query complexity—(1+O(ε))κ ln(2√2/ε) with known norm via single kernel reflection, and O(κ log(1/ε)) with unknown norm via kernel projection or adiabatic-path concept reuse—are obtained through direct error analysis and oracle query counting in the block-encoding model. Kernel reflection is explicitly defined as an extension of prior eigenstate filtering without self-referential closure, and no steps reduce by construction to fitted inputs, self-citations, or imported uniqueness theorems. The explicit bound 56κ+1.05κ ln(1/ε)+o(κ) follows from the same independent analysis. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard quantum computing assumptions and extends eigenstate filtering without introducing new free parameters or entities.

axioms (1)
  • domain assumption The matrix A is accessible via a block-encoding unitary oracle with known normalization factor.
    This is the standard access model assumed for implementing the reflections and projections in the QLSS.

pith-pipeline@v0.9.0 · 5887 in / 1298 out tokens · 29445 ms · 2026-05-23T23:45:27.976752+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 10 Pith papers

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

  1. Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

    quant-ph 2026-05 conditional novelty 8.0

    Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.

  2. Halving the cost of QROM

    quant-ph 2026-05 unverdicted novelty 7.0

    New SelectCopy architecture and qubit-constrained optimizations reduce QROM Toffoli cost from ~2N/λ to ~(1 + 1/b)N/λ while preserving the ability to trade dirty qubits for lower gate count.

  3. Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation

    quant-ph 2026-05 unverdicted novelty 7.0

    A new LCNU-to-LCU decomposition enables a generalized quantum framework for Carleman-linearized polynomial systems like the lattice Boltzmann equation, with Ns scaling as O(α² Q²) independent of spatial and temporal d...

  4. Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation

    quant-ph 2026-05 unverdicted novelty 7.0

    A new LCNU-to-LCU decomposition yields a quantum framework for Carleman-linearized lattice Boltzmann equations whose term count scales as O(α² Q²) and is independent of spatial or temporal grid points.

  5. Constrained Optimal Polynomials for Quantum Linear System Solvers

    math.NA 2026-04 unverdicted novelty 7.0

    Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding...

  6. Probabilistic quantum algorithm for Lyapunov equations and matrix inversion

    quant-ph 2025-08 unverdicted novelty 7.0

    Probabilistic quantum algorithm prepares mixed states proportional to Lyapunov equation solutions and matrix inverses using oracles for input matrices and a deterministic stopping rule.

  7. Quantum Koopman Algorithms

    quant-ph 2026-05 unverdicted novelty 6.0

    Quantum Koopman Algorithms define an observable-space quantum framework for simulating linear quantum and nonlinear classical dynamics with polylog gate costs in some cases.

  8. Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation

    quant-ph 2026-05 unverdicted novelty 6.0

    A matrix decomposition into linear combinations of non-unitaries produces an LCU for any Carleman-linearized polynomial system and yields an O(α² Q²) term count for the 3D lattice Boltzmann equation independent of spa...

  9. Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface

    quant-ph 2026-04 unverdicted novelty 6.0

    The Eclipse Qrisp BlockEncoding interface provides high-level programming abstractions for block-encodings, enabling easier implementation of quantum algorithms such as QSVT, matrix inversion, and Hamiltonian simulation.

  10. Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice

    quant-ph 2026-04 unverdicted novelty 4.0

    Adiabatic solver slightly outperforms shortcut when solution norm unknown; shortcut significantly better for non-Hermitian matrices when norm known.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · cited by 8 Pith papers · 18 internal anchors

  1. [1]

    Quantum algorithm for solving linear systems of equations

    Harrow, A. W., Hassidim, A., and Lloyd, S. “Quantum algorithm for linear systems of equa- tions.”Phys. Rev. Lett. 103 (2009), 150502. arXiv:0811.3171

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  2. [2]

    Focus beyond Quadratic Speedups for Error-Corrected Quan- tumAdvantage

    Babbush, R., McClean, J. R., Newman, M., Gid- ney, C., Boixo, S., and Neven, H. “Focus beyond Quadratic Speedups for Error-Corrected Quan- tumAdvantage.”PRX Quantum2(2021),010103. arXiv:2011.04149

    work page arXiv 2021

  3. [3]

    Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

    Ambainis, A. “Variable time amplitude ampli- fication and quantum algorithms for linear al- gebra problems.” In: STACS (2012), 636–647. arXiv:1010.4458

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  4. [4]

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

    Childs, A. M., Kothari, R., and Somma, R. D. “Quantum Algorithm for Systems of Linear Equa- tions withExponentially Improved Dependence on Precision.”SIAM J. Comp.46 (2017), 1920–1950. arXiv:1511.02306

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  5. [5]

    Chakraborty, A

    Chakraborty, S., Gilyén, A., and Jeffery, S. “The power of block-encoded matrix powers: Im- proved regression techniques via faster Hamilto- nian simulation.” In:ICALP (2019), 33:1–33:14. arXiv:1804.01973

    work page arXiv 2019

  6. [6]

    Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing

    Subaşı, Y., Somma, R. D., and Orsucci, D. “Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Com- puting.”Phys. Rev. Lett. 122 (2019), 060504. arXiv:1805.10549

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  7. [7]

    Quantum Linear System Solver Based on Time-Optimal Adiabatic Quan- tum Computing and Quantum Approximate Op- timization Algorithm

    An, D. and Lin, L. “Quantum Linear System Solver Based on Time-Optimal Adiabatic Quan- tum Computing and Quantum Approximate Op- timization Algorithm.” ACM Trans. Quantum Comput. 3 (2022). arXiv:1909.05500

    work page arXiv 2022

  8. [8]

    Optimal Polynomial Based Quantum Eigenstate Fil- tering with Application to Solving Quantum Linear Systems

    Lin, L. and Tong, Y. “Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems.” Quantum 4 (2020), 361. arXiv:1910.14596

    work page arXiv 2020

  9. [9]

    Optimal Scal- ing Quantum Linear-Systems Solver via Discrete Adiabatic Theorem

    Costa, P. C., An, D., Sanders, Y. R., Su, Y., Babbush, R., and Berry, D. W. “Optimal Scal- ing Quantum Linear-Systems Solver via Discrete Adiabatic Theorem.”PRX Quantum 3 (2022), 040303. arXiv:2111.08152

    work page arXiv 2022

  10. [10]

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

    Orsucci, D. and Dunjko, V. “On solving classes of positive-definite quantum linear sys- tems with quadratically improved runtime in the condition number.”Quantum 5 (2021), 573. arXiv:2101.11868

    work page arXiv 2021

  11. [11]

    Adiabatic Quantum Computing

    Albash, T. and Lidar, D. A. “Adiabatic quantum computation.”Rev. Mod. Phys.90 (2018), 015002. arXiv:1611.04471

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  12. [12]

    Efficient quan- tum linear solver algorithm with detailed running costs

    Jennings, D., Lostaglio, M., Pallister, S., Sorn- borger, A. T., and Subasi, Y. “Efficient quan- tum linear solver algorithm with detailed running costs.” arXiv:2305.11352 (2023)

    work page arXiv 2023

  13. [13]

    End-To-End Re- source Analysis for Quantum Interior-Point Meth- ods and Portfolio Optimization

    Dalzell, A. M., Clader, B. D., Salton, G., Berta, M., Lin, C. Y.-Y., Bader, D. A., Stamatopoulos, N., Schuetz, M. J. A., Brandão, F. G. S. L., Katz- graber, H. G., and Zeng, W. J. “End-To-End Re- source Analysis for Quantum Interior-Point Meth- ods and Portfolio Optimization.”PRX Quantum 4 (2023), 040325. arXiv:2211.12489

    work page arXiv 2023

  14. [14]

    The cost of solving linear differential equations on a quantum com- puter: fast-forwarding to explicit resource counts

    Jennings, D., Lostaglio, M., Lowrie, R. B., Pallis- ter, S., and Sornborger, A. T. “The cost of solving linear differential equations on a quantum com- puter: fast-forwarding to explicit resource counts.” arXiv:2309.07881 (2023)

    work page arXiv 2023

  15. [15]

    The discrete adiabatic quantum linear system solver has lower constant factors than the random- ized adiabatic solver

    Costa, P. C. S., An, D., Babbush, R., and Berry, D. “The discrete adiabatic quantum linear system solver has lower constant factors than the random- ized adiabatic solver.” arXiv:2312.07690 (2023)

    work page arXiv 2023

  16. [16]

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

    Gilyén, A., Su, Y., Low, G. H., and Wiebe, N. “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.” In:STOC (2019), 193–204. arXiv:1806.01838

    work page arXiv 2019

  17. [17]

    Grand Unification of Quantum Algorithms

    Martyn, J. M., Rossi, Z. M., Tan, A. K., and Chuang, I. L. “Grand Unification of Quantum Algorithms.”Phys. Rev. X 2 (2021), 040203. arXiv:2105.02859

    work page arXiv 2021

  18. [18]

    Optimal Quantum Measurements of Expectation Values of Observables

    Knill, E., Ortiz, G., and Somma, R. D. “Opti- mal quantum measurements of expectation values of observables.”Phys. Rev. A 75 (2007), 012328. arXiv:quant-ph/0607019

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  19. [19]

    A fast quantum mechanical algorithm for database search

    Grover, L. K. “A Fast Quantum Mechanical Al- gorithm for Database Search.” In:STOC (1996), 212–219. arXiv:quant-ph/9605043

    work page internal anchor Pith review Pith/arXiv arXiv 1996

  20. [20]

    Fixed-point quantum search with an optimal number of queries

    Yoder,T.J.,Low,G.H.,andChuang,I.L.“Fixed- Point Quantum Search with an Optimal Number of Queries.”Phys. Rev. Lett.113 (2014), 210501. arXiv:1409.3305

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  21. [21]

    An interval estimation problem for controlled observations

    Burnashev, M. V. and Zigangirov, K. “An interval estimation problem for controlled observations.” Problemy Peredachi Informatsii10 (1974), 51–61. In Russian, see [23] for key proof in English

    work page 1974

  22. [22]

    Quantum Search in an Ordered List via Adaptive Learning

    Ben-Or, M. and Hassidim, A. “The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well).” In: 2008 49th Annual IEEE Symposium on Foun- dations of Computer Science (2008), 221–230. arXiv:quant-ph/0703231

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  23. [23]

    Noisy Sorting Capacity

    Wang, Z., Ghaddar, N., and Wang, L. “Noisy Sorting Capacity.” In:ISIT (2022), 2541–2546. arXiv:2202.01446

    work page arXiv 2022

  24. [24]

    Sharp Noisy Bi- nary Search with Monotonic Probabilities

    Gretta, L. and Price, E. “Sharp Noisy Bi- nary Search with Monotonic Probabilities.” arXiv:2311.00840 (2023)

    work page arXiv 2023

  25. [25]

    Fast Amplification of QMA

    Nagaj, D., Wocjan, P., and Zhang, Y. “Fast Am- plification of QMA.”Quantum Inf. Comput. 9 (2009), 1053–1068. arXiv:0904.1549. 13

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  26. [26]

    Mean estima- tion when you have the source code; or, quantum Monte Carlo methods

    Kothari, R. and O’Donnell, R. “Mean estima- tion when you have the source code; or, quantum Monte Carlo methods.” In:SODA (2023), 1186–

    work page 2023

  27. [27]

    Quantum Amplitude Amplification and Estimation

    Brassard, G., Høyer, P., Mosca, M., and Tapp, A. “Quantum Amplitude Amplification and Esti- mation.” In:Quantum Computation and Quantum Information: A Millennium Volume(2002),53–74. arXiv:quant-ph/0005055

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  28. [28]

    Quantum algorithms: A survey of applications and end-to-end complexities

    Dalzell, A. M., McArdle, S., Berta, M., et al. “Quantum algorithms: A survey of applications and end-to-end complexities.” arXiv:2310.03011 (2023)

    work page arXiv 2023

  29. [29]

    High-order quantum algorithm for solving linear differential equations

    Berry, D. W. “High-order quantum algorithm for solving linear differential equations.”J. Phys. A 47 (2014), 105301. arXiv:1010.2745

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  30. [30]

    Quantum algorithms and the finite element method

    Montanaro, A. and Pallister, S. “Quantum algo- rithms and the finite element method.”Phys. Rev. A 93 (2016), 032324. arXiv:1512.05903

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  31. [31]

    Preconditioned quantum linear system algorithm

    Clader, B. D., Jacobs, B. C., and Sprouse, C. R. “Preconditioned quantum linear system al- gorithm.”Phys. Rev. Lett. 110 (2013), 250504. arXiv:1301.2340

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  32. [32]

    Quantum assisted Gaussian process regression

    Zhao, Z., Fitzsimons, J. K., and Fitzsimons, J. F. “Quantum-assisted Gaussian process re- gression.” Phys. Rev. A 99 (2019), 052331. arXiv:1512.03929

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  33. [33]

    Quantum algorithms for training Gaussian Processes

    Zhao, Z., Fitzsimons, J. K., Osborne, M. A., Roberts, S. J., and Fitzsimons, J. F. “Quantum algorithms for training Gaussian processes.”Phys. Rev. A 100 (2019), 012304. arXiv:1803.10520

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  34. [34]

    Quantum support vector machine for big data classification

    Rebentrost, P., Mohseni, M., and Lloyd, S. “Quan- tum support vector machine for big data clas- sification.”Phys. Rev. Lett. 113 (2014), 130503. arXiv:1307.0471

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  35. [35]

    Nielsen, M. A. and Chuang, I. L.Quantum compu- tation and quantum information. Cambridge Uni- versity Press (2000)

    work page 2000

  36. [36]

    The quantum query complexity of approximating the median and related statistics

    Nayak, A. and Wu, F. “The quantum query complexity of approximating the median and related statistics.” In: STOC (1999), 384–393. arXiv:quant-ph/9804066. 14 A Block-encoding and state-preparation constructions Here we provide circuits for block-encoding and state preparation of various matrices and vectors used in our analysis. We assume access to the(α =...

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  37. [37]

    For all x ∈ [−1, 1], it holds that|F∆,ℓ(x)| ≤ 1

    work page

  38. [38]

    For all x ∈ [∆, 1], it holds that|F∆,ℓ(x)| ≤ Tℓ( 1+∆2 1−∆2 )−1 ≤ η

    work page

  39. [39]

    F∆,ℓ(0) = 1. Proof. This builds on and improves upon Lemma 13 of Ref. [8].3 Note that the Chebyshev polynomialTℓ(z) is bounded on [−1, 1] when z ∈ [−1, 1]. Moreover, for z ≥ 1 it is monotonically increasing. Thus, the numerator achieves its maximum onx ∈ [−1, 1] when x = 0, where F∆,ℓ = 1 by construction, verifying properties 1 and 3. To verify Property 2...

    work page

  40. [40]

    We acknowledge communciation with Yu Tong on how the constant prefactor in their bound could be improved, a fact that was also pointed out in Ref

    Additionally, we no longer require the restriction∆ ∈ (0, 1/ √ 12]. We acknowledge communciation with Yu Tong on how the constant prefactor in their bound could be improved, a fact that was also pointed out in Ref. [9, Section V]. 18 H all of which have singular valuesςj in (∆, 1). By Property 2 of Lemma 1, for everyj, F∆,ℓ(ςj) lies in the interval [−η, η...

    work page

  41. [41]

    For all x ∈ [−1, 1], it holds that|K∆,ℓ(x)| ≤ 1

    work page

  42. [42]

    For all x ∈ [∆, 1], it holds that|K∆,ℓ(x)| ≤ − 1 + 4 Tℓ( 1+∆2 1−∆2 )+1 ≤ −1 + 4η 1+η

    work page

  43. [43]

    K∆,ℓ(0) = 1. Proof. Property 3 is readily verified by plugging inx = 0. Property 1 follows from the fact that forx ∈ [−1, 1], the maximum of Tℓ( 1+∆2−2x2 1−∆2 ) is achieved atx = 0 and the minimum is−1 (as noted in proof of Lemma 1). To verify Property 2, first note that for allx ∈ [∆, 1], Tℓ( 1+∆2−2x2 1−∆2 ) ∈ [−1, 1]. Moreover, the denominator evaluates...

    work page

  44. [44]

    sin(θt)|yt⟩ + δ′ 2 sin(θt)|z⟩ (74) where |z⟩ is some state orthogonal to both |xt⟩ and |yt⟩, δ′ 1 ≤ 4η/(1 + η), and δ′ 2 ≤ p δ′ 1(4η/(1 + η) − δ′ 1). Furthermore, since the kernel ofA is contained in the kernel ofGt = Qb′ At and yt is orthogonal to the kernel of A, the image ofyt under any QSVT sequence will remain orthogonal to the kernel ofA. In particu...

    work page

  45. [45]

    We verify the bounds in reverse order

    cos(θt) sin(θt) i |x⟩ + δ′ 2 sin(θt)|z⟩ (75) = 1 − δ′ 1 2 sin(2θt)|x⟩ + δ′ 2 sin(θt)|z⟩ (76) This state is orthogonal to the kernel ofA since both x and z are orthogonal to the kernel ofA. We verify the bounds in reverse order. The overall probability of success is given by the squared norm of the right-hand side of Eq. (76). The lower bound in Eq. (71) f...

    work page

  46. [46]

    These terms achieve maximum norm atδ′ 1 = 0 and δ′ 2 = 2η/(1 + η), yielding the stated upper bound

    ≤ 4η2/(1+η)2. These terms achieve maximum norm atδ′ 1 = 0 and δ′ 2 = 2η/(1 + η), yielding the stated upper bound. To show Eq. (70), to condense some notation, define M = η/(1 + η), ξ1 = δ′ 1/2 − M, ξ2 = δ′ 2/2, and γ = 1/ cos(θt). We haveξ2 1 +ξ2 2 ≤ M2. After normalizing|˜x⟩ appropriately, and noting thatδ′ 2 sin(θt) = sin(2θt)γξ2, we see that the overla...

    work page

  47. [47]

    succeeds

    This confirms Eq. (82). We can now compute an upper bound on the probability that the algorithm succeeds and outputs an estimate for t greater than β∥x∥, which we denote byP>. For this to be the case, first of all, the random choice ofτ must be greater thanβ∥x∥. Then, conditoned on such a choice ofτ, the probability of successQt is upper bounded by Eq. (7...

    work page