Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Even a 4×4 linear system needs about 10^15 non-Clifford gates under a randomized Fourier-sampling quantum solver, the paper argues.

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

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

A randomized Fourier-series quantum linear-systems solver needs on the order of 10^15 non-Clifford gates even for a 4×4 matrix with condition number 100, making the scheme impractical despite formally bounded errors.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection The paper's qualitative case against Fourier-series randomized QLS solvers is solid and matches its own numerics, but Lemma 7 has a real quadrature error that invalidates the exact resource counts (the corrected figures are larger, not smaller). the 3 major comments →

arxiv 2510.13766 v2 pith:FNJXVE56 submitted 2025-10-15 quant-ph

The Practicality of Randomized Quantum Linear Systems Solvers

Siddharth Hariprakash , Roel Van Beeumen , Katherine Klymko , Daan Camps This is my paper
classification quant-ph MSC 81P6868Q12
keywords randomized quantum algorithmsquantum linear systemsFourier series approximationHamiltonian simulationproduct formulasrandom Taylor expansionnon-Clifford gate complexitysample complexity
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.

The reading

The paper derives explicit, non-asymptotic error bounds for every algorithmic parameter of a randomized quantum linear-systems solver that estimates ⟨ϕ|A⁻¹|ψ⟩ by sampling from a Fourier series and simulating the resulting time evolutions. Using these bounds, it computes end-to-end resource counts and shows that even a 4×4 Hermitian matrix with condition number 100 requires on the order of 10^15 non-Clifford gates to converge, with sampling complexity that can grow exponentially. The authors conclude that randomized Fourier-series-based schemes of this kind are impractical for quantum linear systems, despite earlier hopes that they would be well-suited to early fault-tolerant hardware. They also compare two Hamiltonian-simulation kernels, product formulas and random Taylor expansion, and find that random Taylor expansion reaches a given target error with roughly ten times fewer total gates, although neither approach is practical.

Core claim

The paper's central claim is that the resource cost of the randomized Fourier-series QLS solver is dominated by the variance of Fourier-coefficient sampling, which is controlled by the normalization parameters Ny and Nz, together with the maximum Fourier time tmax = 2κ ln(3κ/ϵT). By combining a Gauss-Legendre/trapezoid discretization of the integral representation of x⁻¹ with either a second-order product formula or a random Taylor expansion for the time evolution, the paper obtains explicit formulas for the required number of samples NS and the non-Clifford gates per sample NCP. For a concrete 4×4 matrix with κ = 100, λ ≈ 2.09, and Fourier error ϵF = 2×10⁻³, these formulas yield roughly 10^

What carries the argument

The central object is the Fourier representation of the inverse function as a normalized double integral over scaled variables y and z, discretized with Gauss-Legendre quadrature in y and the trapezoidal rule in z. The key identity is the normalization-variance bound in Lemma 7: the sampling variance is controlled by the product Ny Nz, with Ny pinned to ymax/√(2π) and Nz bounded using the trapezoid discretization. Together with tmax = 2κ ln(3κ/ϵT), this bound determines the sample complexity and non-Clifford gate counts in Theorems 10 and 12. For RTE, the secondary sampling from a truncated Taylor expansion of the time evolution adds the normalization factor e^{τ²/r}, which drives the expone

Load-bearing premise

The quantitative resource formulas rest on Lemma 7's bound for the normalization constant Nz, which approximates a trapezoid sum by an integral without keeping the quadrature weight 1/Δz; if that bound is too small, the exact gate and sample counts change, though the impracticality conclusion would likely become stronger.

What would settle it

Compute the actual value of Nz = Δz Σ_k |z_k e^{-z_k²/2}| for the κ=100, ϵF=2×10⁻³ case and compare it with the Lemma 7 upper bound; if it exceeds the bound by a large factor, then the sample-count and gate-count predictions in Theorems 10 and 12 are not literally valid. Alternatively, run the full estimator with Ns = 10^8 shots at the paper's parameters and check whether the RMSE indeed approaches roughly 0.1, as in the paper's PF simulation; a mismatch of orders of magnitude would indicate a flaw in the variance analysis.

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

If this is right

  • Explicit parameter choices now exist for the Fourier truncation and discretization of the inverse, so the Fourier-series step can be implemented and its cost quantified for any given κ and error budget.
  • With product formulas, the sample count scales like (NyNz)²/λ² and the per-sample non-Clifford cost grows as 2rL, with a tunable tradeoff between samples and circuit depth.
  • With random Taylor expansion, sample count can scale exponentially with tmax²/r, while choosing larger r moves the cost into a per-sample gate depth of NCP = r.
  • Even a 4×4 instance with κ = 100 needs about 10^15 non-Clifford gates, putting the scheme beyond practicality for near-term or early fault-tolerant hardware.
  • RTE reaches a given target error with roughly an order of magnitude smaller total gate budget than PF, but both are impractical in the parameter regime tested.

Where Pith is reading between the lines

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

  • If the Lemma 7 bound on Nz turns out to be optimistic, the stated 10^15-gate figure shifts upward by a factor of roughly Nz², strengthening the qualitative conclusion of impracticality while invalidating the exact numerical claims in Theorems 10 and 12.
  • One extension the authors leave implicit is that applying classical preconditioners or working on matrices with small effective spectral range would shrink tmax and could bring the crossover point within reach; the paper mentions preconditioning only as a direction.
  • The explicit gate counts enable a fair apples-to-apples comparison with block-encoding-based Chebyshev solvers, a comparison the paper motivates but does not carry out.
  • A testable refinement is to assign each sampled Fourier time its own Trotter number r(t) rather than a fixed tmax-dependent value; the paper notes this idea but does not quantify its effect on total cost.
Share X Bluesky LinkedIn Reddit HN

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

3 major / 5 minor

Summary. The paper analyzes a randomized hybrid quantum linear systems (QLS) solver in which A^{-1} is approximated by a discretized Fourier integral, Fourier times are sampled with probabilities derived from the Fourier coefficients, and each sampled exponential e^{-i\tilde{A}t} is implemented either by a second-order product formula (PF) or by a random Taylor expansion (RTE). The authors derive non-asymptotic bounds for the Fourier truncation/discretization parameters (Theorems 4 and 5), for the sampling normalization factors (Lemma 7), and for the sample and non-Clifford gate counts (Theorems 10 and 12). They report numerical checks on 4x4 matrices with condition numbers up to 1000 and end-to-end simulations for a 4x4 instance with \kappa=100, concluding that such randomized schemes require enormous resources—on the order of 10^15 non-Clifford gates—and that RTE gives only a modest constant-factor improvement, so neither is practical.

Significance. If the analysis were fully correct, the paper would provide a valuable, quantitative negative result for a class of early-fault-tolerant quantum linear algebra proposals, together with a reusable template for non-asymptotic resource estimation. The explicit formulas for ymax, zmax, J, K, NS, and NCP, and the numerical verification of the Fourier approximation error, are useful contributions. However, the central quantitative claim rests on Lemma 7, and that lemma contains a concrete quadrature error. Correcting the error increases the predicted resource counts by about two orders of magnitude, which strengthens the paper's qualitative conclusion but invalidates the stated 'exact' resource numbers and the abstract's specific 10^15-gate figure. The paper's own numerics, which show RMSE \approx 0.1 after 10^8 shots for a 10^{-3} target, are consistent with the corrected variance rather than with Lemma 7 as printed.

major comments (3)
  1. [Appendix C.4, Lemma 7, Eq. (27)] The upper bound on Nz is incorrect. From Eq. (23), Nz = \Delta z \sum_k |z_k| e^{-z_k^2/2} with \Delta z = 2zmax/(K-1). In the proof, after bounding |z_k| \le zmax, the sum \sum_k e^{-z_k^2/2} is replaced by the integral \int e^{-z^2/2}dz without the trapezoidal weight 1/\Delta z. Since \sum_k e^{-z_k^2/2} \approx (1/\Delta z)\int e^{-z^2/2}dz, the printed bound Nz \le 4\sqrt{2\pi}/(K-1)\ln(3\tilde\kappa/\epsilon_T) is too small by a factor of order 1/\Delta z. At the paper's own parameters (\kappa=100, \lambda=2.09, \epsilon_T=10^{-3}, K=856; Table 1 and Section 6.2), Eq. (27) gives Nz \le 0.16, while the actual sum is Nz \approx 2. Because Theorems 9-12 and Eqs. (38)-(39) and (53)-(54) all scale with Nz or Nz^2, the stated sample counts and the abstract's 'on the order of 10^15 non-Clifford gates' are not established as written. Correcting Nz increases NS by a factor of roughly (2/0.16
  2. [Theorems 10 and 12; Section 6.2, Fig. 3] The numerical verification is consistent with the corrected Nz, not with the printed Lemma 7. With Nz \approx 0.16, the sampling variance after 10^8 shots with exact exponentials and readout noise should be well below 10^{-2}; the observed RMSE \approx 0.1 at 10^8 shots matches the variance predicted by Nz \approx 2. Thus Fig. 3 confirms the corrected prefactor but does not support the quantitative resource bounds stated in the abstract. The authors should recompute all resource tables and the abstract's headline numbers after fixing Lemma 7, and should state the corrected Nz bound explicitly.
  3. [Abstract and Section 7, RTE comparison] The claim that RTE reaches a given target error with roughly an order-of-magnitude smaller total gate budget is not verified end-to-end. Section 6.2 explicitly states that the RTE subroutine could not be simulated for the 4x4 \kappa=100 instance; Fig. 4 is a proxy with tmax=100 and exact overlap evaluation, and it in fact shows breakdown for \tau^2/r \ge 1. The analytical comparison is therefore bound-based and inherits the Lemma 7 error. This statement should either be re-derived with the corrected Nz or explicitly labeled as a bound-only comparison, with the experimental evidence described as a partial check at smaller time scales.
minor comments (5)
  1. [Eq. (39)] The denominator has an unbalanced parenthesis: '(\epsilon/2 - |B_PF|))2' should read '(\epsilon/2 - |B_PF|)^2'.
  2. [Fig. 3 legend] The legend entries 'PF, r = 0.1 2' and 'PF, r = 0.05 2' should be written as \lceil 0.1\tau^2\rceil and \lceil 0.05\tau^2\rceil, and the caption should state how the RMSE averaging over trials is performed.
  3. [Section 6.2, Hadamard noise model] The text says a Gaussian of width 1 is added to simulate a single Hadamard-test shot. A single shot is a binary \pm1 outcome; the Gaussian model should be justified or replaced with Bernoulli sampling to avoid confusion about the noise model.
  4. [Appendix C.4, Eq. (103)] Even after correcting the missing 1/\Delta z factor, the proof should replace the '\approx' with a rigorous trapezoidal quadrature bound, since the current equality is an uncontrolled asymptotic replacement.
  5. [General notation] The symbol NCP is used both as the number of controlled Pauli rotations and, in Eq. (39), as an upper bound; please distinguish the exact count from the upper-bound notation in the text.

Circularity Check

0 steps flagged

No material circularity: the resource bounds are derived from stated quadrature and sampling error theorems, not extracted from the conclusions they predict.

full rationale

The paper's central resource claims are obtained by a derived chain: the Fourier approximation parameters come from Theorems 4 and 5 (based on integral-representation bounds and quoted quadrature error estimates), the normalization parameters Ny, Nz are defined in Eq. (23) and bounded in Lemma 7, and the sample/non-Clifford counts in Theorems 10 and 12 follow from Hoeffding bounds and the variance bounds, with no parameter fitted to the target impracticality conclusion. The numerical demonstrations in Section 6.1 use the theoretically chosen Fourier parameters (J, K) and observe that the numerical error is about 20% of the claimed bound, which is a consistency test rather than a fit. The RTE and PF subroutines inherit their error bounds from external prior work [28, 33, 37], not from the authors' own conclusions. The only self-citations in the text (e.g., refs. [21, 39]) are illustrative examples about pessimistic Trotter bounds and block encodings, and are not load-bearing for the resource formulas. The paper's admitted limitations, such as being unable to run the RTE end-to-end simulation, weaken the empirical confirmation but do not constitute circular reasoning. The possible issue in Lemma 7 raised by the skeptical analysis is a mathematics/error-bound concern, not a circularity concern: an incorrect bound is not a reduction of the output to the input by definition. Overall, the derivation is self-contained in the sense relevant to circularity analysis, so a low score is appropriate.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No free parameters fitted to data: every constant in Theorems 4, 5, 7, 9-12 is set analytically (error-split choices ϵ1=ϵT/3, ϵ2=2ϵT/3, quadrature slack (ρ,σ)=(zmax,√2), balanced ϵS=ϵF=ϵ/2 are proof-level slack, not fits). The quantitative claims rest on: (i) the cited quadrature error bounds [37,33] applied at C.2; (ii) the input model (Pauli decomposition, κ*, λ, Λ(A) ⊆ Dκ*); (iii) the [28] RTE bounds (NRTE ≤ e^{τ²/r}, tail bound) and the r ≥ tmax constraint; (iv) the single-shot Hadamard noise model. No invented entities. The flagged weakness is that the 'variance bound' in (ii)-adjacent Lemma 7 is itself erroneous, so the axiom 'the estimator variance is ≤ (NyNz)²/λ² as bounded in Lemma 7' is not satisfied by the paper's own numerics.

axioms (5)
  • standard math Trapezoidal-rule exponential convergence (Eq. 77, [37]) and Gauss-Legendre Bernstein-ellipse error bound (Eq. 78, [33]) hold as invoked.
    These are the external bounds behind Theorem 5's J and K formulas; if either is misapplied (e.g., domain of analyticity not matching Dκ), the claimed ϵD and with it ϵF collapse.
  • domain assumption Input model of Problem 1: known Pauli decomposition (cℓ, Pℓ), Pauli weight λ, upper bound κ* ≥ κ, ∥A∥ ≥ 1, and Λ(A) ⊆ Dκ* (after λ-rescaling when ∥A∥ > 1).
    Section 2.1 and Lemma 6; the Fourier approximation only bounds error on Dκ*, so every eigenvalue of A must lie in the domain for Eq. (6) to hold.
  • domain assumption State-preparation cost is constant and excluded from NCP; non-Clifford cost is counted in controlled single-qubit Pauli rotations.
    Section 2.2 cost model; the 10^15 headline counts only these rotations, so the practicality conclusion is conditional on this cost metric.
  • domain assumption RTE sampling normalization NRTE ≤ e^{τ²/r} and the Poisson-tail bound (Eq. A4 in [28], Corollary 6 of [44]) used in Theorem 11; requires r ≥ tmax.
    Eq. (48) and Appendix C.7; the exponential e^{tmax²/r} prefactor that drives RTE's sample complexity comes from [28], not from this paper.
  • domain assumption Single Hadamard-test shots are simulated as the exact overlap plus Gaussian noise of width 1 (variance ≤ 1 per shot).
    Section 6.2; reasonable for ±1 Bernoulli outcomes, but it is the only link between the classical simulation and true quantum single-shot statistics.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of The Practicality of Randomized Quantum Linear Systems Solvers." pith.science (2026). https://pith.science/paper/FNJXVE56

@misc{pith2026251013766,
  author       = {Pith},
  title        = {Pith review of: The Practicality of Randomized Quantum Linear Systems Solvers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FNJXVE56}},
  note         = {Machine review of arXiv:2510.13766}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Randomized quantum algorithms have been proposed for quantum linear algebra with the goal of constructing shallower circuits than methods based on block encodings, and have been speculated to offer benefits in the early fault-tolerant era. In this work, we derive explicit, non-asymptotic error bounds on every algorithmic parameter of a randomized quantum linear systems solver that combines sampling from a Fourier series with Hamiltonian simulation, and confirm these bounds numerically. We show that even a $4 \times 4$ instance with condition number $\kappa = 100$ requires on the order of $10^{15}$ non-Clifford gates to converge, calling into question the practicality of such randomized schemes. Comparing the two Hamiltonian-simulation kernels, product formulas (PFs) and the random Taylor expansion (RTE), both our analytical bounds and experiments show RTE reaches a given target error with roughly an order of magnitude smaller total gate budget, although neither is practical. Our analysis bridges asymptotic proposals and hardware implementation.

Figures

Figures reproduced from arXiv: 2510.13766 by Daan Camps, Katherine Klymko, Roel Van Beeumen, Siddharth Hariprakash.

Figure 1
Figure 1. Figure 1: Randomized framework for sampling from solutions to the quantum linear systems (QLS) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Flowchart outlining the randomized quantum algorithm for estimating [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Convergence in the root mean squared error (RMSE) as a function of the total number of [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Convergence in the root mean squared error (RMSE) as a function of the total number of [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. Pauli-structured preconditioning for quantum linear system solvers

    quant-ph 2026-06 unverdicted novelty 5.0

    Pauli-structured preconditioning enables regrouped Pauli representations that reduce coefficient weight of the preconditioned operator and alter normalization parameters in quantum linear system solvers.

Reference graph

Works this paper leans on

48 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [1]

    Quantum Chemistry in the Age of Quantum Computing

    Yudong Cao et al. “Quantum Chemistry in the Age of Quantum Computing”. In: Chemical Reviews 119.19 (Aug. 2019), pp. 10856–10915.issn: 1520-6890. doi: 10.1021/acs.chemrev. 8b00803. url: http://dx.doi.org/10.1021/acs.chemrev.8b00803

    doi:10.1021/acs.chemrev 2019

  2. [2]

    Quantum Computing for High-Energy Physics: State of the Art and Challenges

    Alberto Di Meglio et al. “Quantum Computing for High-Energy Physics: State of the Art and Challenges”.In: PRX Quantum5(3Aug.2024),p.037001. doi: 10.1103/PRXQuantum.5.037001. url: https://link.aps.org/doi/10.1103/PRXQuantum.5.037001

    doi:10.1103/prxquantum.5.037001 2024

  3. [3]

    Quantum simulation of fundamental particles and forces

    Christian W. Bauer et al. “Quantum simulation of fundamental particles and forces”. In:Nature Rev. Phys.5.7 (2023), pp. 420–432.doi: 10.1038/s42254- 023- 00599- 8. arXiv: 2404.06298 [hep-ph]

    Pith/arXiv arXiv 2023

  4. [4]

    Quantum Simulation for High-Energy Physics

    Christian W. Bauer et al. “Quantum Simulation for High-Energy Physics”. In:PRX Quantum 4.2 (2023), p. 027001.doi: 10.1103/PRXQuantum.4.027001. arXiv: 2204.03381 [quant-ph]

    Pith/arXiv arXiv 2023

  5. [5]

    Quantum-centric supercomputing for materials science: A perspective on challenges and future directions

    Yuri Alexeev et al. “Quantum-centric supercomputing for materials science: A perspective on challenges and future directions”. In:Future Generation Computer Systems160 (2024), pp. 666–

    2024

  6. [6]

    Quantum algorithms: an overview

    Ashley Montanaro. “Quantum algorithms: an overview”. In:npj Quantum Information2.1 (Jan. 2016). issn: 2056-6387. doi: 10.1038/npjqi.2015.23 . url: http://dx.doi.org/10.1038/ npjqi.2015.23

    doi:10.1038/npjqi.2015.23 2016

  7. [7]

    Quantum Linear System Solvers: A Survey of Algorithms and Applications

    Mauro E. S. Morales et al. “Quantum Linear System Solvers: A Survey of Algorithms and Applications”. In: (Nov. 2024). arXiv:2411.02522 [quant-ph]

    Pith/arXiv arXiv 2024

  8. [8]

    Quantum Algorithm for Linear Systems of Equations

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum Algorithm for Linear Systems of Equations”. In:Phys. Rev. Lett.103 (15 Oct. 2009), p. 150502.doi: 10.1103/PhysRevLett. 103.150502. url: https://link.aps.org/doi/10.1103/PhysRevLett.103.150502

    doi:10.1103/physrevlett 2009

  9. [9]

    Quantum Krylov Algorithm for Szegö Quadrature

    William Kirby et al. “Quantum Krylov Algorithm for Szegö Quadrature”. In: (Sept. 2025). arXiv: 2509.19195 [quant-ph]. 21

    arXiv 2025

  10. [10]

    Quantum singular value transformation and beyond: exponential improve- ments for quantum matrix arithmetics

    András Gilyén et al. “Quantum singular value transformation and beyond: exponential improve- ments for quantum matrix arithmetics”. In:Proceedings of the 51st Annual ACM SIGACT Sym- posium on Theory of Computing. STOC 2019. Phoenix, AZ, USA: Association for Computing Machinery, 2019, pp. 193–204. isbn: 9781450367059. doi: 10 . 1145 / 3313276 . 3316366. ur...

    arXiv 2019

  11. [11]

    Theory of Trotter Error with Commutator Scaling

    Andrew M. Childs et al. “Theory of Trotter Error with Commutator Scaling”. In:Phys. Rev. X 11 (1 Feb. 2021), p. 011020.doi: 10.1103/PhysRevX.11.011020 . url: https://link.aps. org/doi/10.1103/PhysRevX.11.011020

    doi:10.1103/physrevx.11.011020 2021

  12. [12]

    Random Compiler for Fast Hamiltonian Simulation

    Earl Campbell. “Random Compiler for Fast Hamiltonian Simulation”. In:Phys. Rev. Lett.123 (7 Aug. 2019), p. 070503.doi: 10.1103/PhysRevLett.123.070503. url: https://link.aps. org/doi/10.1103/PhysRevLett.123.070503

    doi:10.1103/physrevlett.123.070503 2019

  13. [13]

    Efficient Quantum Algorithms for Simulating Sparse Hamiltonians

    Dominic W. Berry et al. “Efficient Quantum Algorithms for Simulating Sparse Hamiltonians”. In: Communications in Mathematical Physics270.2 (Dec. 2006), pp. 359–371.issn: 1432-0916. doi: 10.1007/s00220-006-0150-x. url: http://dx.doi.org/10.1007/s00220-006-0150-x

    doi:10.1007/s00220-006-0150-x 2006

  14. [14]

    Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

    Dominic W. Berry, Andrew M. Childs, and Robin Kothari. “Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters”. In:Proceedings of the 2015 IEEE 56th Annual Sym- posium on Foundations of Computer Science (FOCS). FOCS ’15. USA: IEEE Computer So- ciety, 2015, pp. 792–809. isbn: 9781467381918. doi: 10 . 1109 / FOCS . 2015 . 54. url: https : ...

    doi:10.1109/focs.2015.54 2015

  15. [15]

    Optimal Hamiltonian Simulation by Quantum Signal Processing

    Guang Hao Low and Isaac L. Chuang. “Optimal Hamiltonian Simulation by Quantum Signal Processing”. In:Phys. Rev. Lett.118 (1 Jan. 2017), p. 010501.doi: 10.1103/PhysRevLett.118. 010501. url: https://link.aps.org/doi/10.1103/PhysRevLett.118.010501

    doi:10.1103/physrevlett.118 2017

  16. [16]

    Hamiltonian Simulation by Qubitization

    Guang Hao Low and Isaac L. Chuang. “Hamiltonian Simulation by Qubitization”. In:Quantum 3 (July 2019), p. 163. issn: 2521-327X. doi: 10 . 22331 / q - 2019 - 07 - 12 - 163. url: https : //doi.org/10.22331/q-2019-07-12-163

    doi:10.22331/q-2019-07-12-163 2019

  17. [17]

    Grand Unification of Quantum Algorithms

    John M. Martyn et al. “Grand Unification of Quantum Algorithms”. In:PRX Quantum2 (4 Dec. 2021), p. 040203.doi: 10.1103/PRXQuantum.2.040203. url: https://link.aps.org/doi/10. 1103/PRXQuantum.2.040203

    doi:10.1103/prxquantum.2.040203 2021

  18. [18]

    Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

    Daan Camps et al. “Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices”. In: SIAM Journal on Matrix Analysis and Applications45.1 (2024), pp. 801–827.doi: 10.1137/ 22M1484298. eprint: https://doi.org/10.1137/22M1484298 . url: https://doi.org/10. 1137/22M1484298

    doi:10.1137/22m1484298 2024

  19. [19]

    Block-encoding structured matrices for data input in quantum computing

    Christoph Sünderhauf, Earl Campbell, and Joan Camps. “Block-encoding structured matrices for data input in quantum computing”. In:Quantum 8 (Jan. 2024), p. 1226.issn: 2521-327X. doi: 10.22331/q-2024-01-11-1226. url: https://doi.org/10.22331/q-2024-01-11-1226

    doi:10.22331/q-2024-01-11-1226 2024

  20. [20]

    Block encoding bosons by signal processing

    Christopher F. Kane et al. “Block encoding bosons by signal processing”. In:Quantum 9 (2025), p. 1747. doi: 10.22331/q-2025-05-15-1747. arXiv: 2408.16824 [quant-ph]

    Pith/arXiv arXiv 2025

  21. [21]

    Strategies for simulating the time evolution of Hamiltonian lattice field theories

    Siddharth Hariprakash et al. “Strategies for simulating the time evolution of Hamiltonian lattice field theories”. In:Phys. Rev. A111.2 (2025), p. 022419.doi: 10.1103/PhysRevA.111.022419. arXiv: 2312.11637 [quant-ph]

    Pith/arXiv arXiv 2025

  22. [22]

    Exponential Improvements in the Simulation of Lattice Gauge Theories Using Near-Optimal Techniques

    Mason L. Rhodes, Michael Kreshchuk, and Shivesh Pathak. “Exponential Improvements in the Simulation of Lattice Gauge Theories Using Near-Optimal Techniques”. In:PRX Quantum 5.4 (2024), p. 040347.doi: 10.1103/PRXQuantum.5.040347. arXiv: 2405.10416 [quant-ph]

    Pith/arXiv arXiv 2024

  23. [23]

    An efficient quantum circuit for block encoding a pairing Hamiltonian

    Diyi Liu et al. “An efficient quantum circuit for block encoding a pairing Hamiltonian”. In: Journal of Computational Science85 (2025), p. 102480. issn: 1877-7503. doi: https://doi. org / 10 . 1016 / j . jocs . 2024 . 102480. url: https : / / www . sciencedirect . com / science / article/pii/S1877750324002734. 22

    2025

  24. [24]

    Quantum Resources Required to Block-Encode a Matrix of Classical Data

    B. David Clader et al. “Quantum Resources Required to Block-Encode a Matrix of Classical Data”. In:IEEE Transactions on Quantum Engineering3 (2022), pp. 1–23.doi: 10.1109/TQE. 2022.3231194

    arXiv 2022

  25. [25]

    Hamiltonian simulation using linear combinations of unitary operations

    Andrew M. Childs and Nathan Wiebe. “Hamiltonian simulation using linear combinations of unitary operations”. In:Quantum Info. Comput.12.11–12 (Nov. 2012), pp. 901–924.issn: 1533- 7146

    2012

  26. [26]

    Filippo Della Chiara et al.Efficient LCU block encodings through Dicke states preparation. 2025. arXiv: 2507.20887 [quant-ph]. url: https://arxiv.org/abs/2507.20887

    Pith/arXiv arXiv 2025

  27. [27]

    Hamiltonian dynamics on digital quantum computers with- out discretization error

    Etienne Granet and Henrik Dreyer. “Hamiltonian dynamics on digital quantum computers with- out discretization error”. In:npj Quantum Information10.1 (Sept. 2024).issn: 2056-6387. doi: 10.1038/s41534-024-00877-y. url: http://dx.doi.org/10.1038/s41534-024-00877-y

    doi:10.1038/s41534-024-00877-y 2024

  28. [28]

    Randomized Quantum Algorithm for Statisti- cal Phase Estimation

    Kianna Wan, Mario Berta, and Earl T. Campbell. “Randomized Quantum Algorithm for Statisti- cal Phase Estimation”. In:Phys. Rev. Lett.129.3 (2022), p. 030503.doi: 10.1103/PhysRevLett. 129.030503. arXiv: 2110.12071 [quant-ph]

    Pith/arXiv arXiv 2022

  29. [29]

    Qubit-Efficient Randomized Quantum Algo- rithms for Linear Algebra

    Samson Wang, Sam McArdle, and Mario Berta. “Qubit-Efficient Randomized Quantum Algo- rithms for Linear Algebra”. In:PRX Quantum5 (2 2024), p. 020324.doi: 10.1103/PRXQuantum. 5.020324. arXiv: 2302.01873 [quant-ph]

    Pith/arXiv arXiv 2024

  30. [30]

    Implementing any Linear Combination of Unitaries on Intermediate- term Quantum Computers

    Shantanav Chakraborty. “Implementing any Linear Combination of Unitaries on Intermediate- term Quantum Computers”. In:Quantum 8 (2024), p. 1496.doi: 10.22331/q- 2024- 10- 10-

    doi:10.22331/q- 2024

  31. [31]

    Randomized Quantum Singular Value Transformation

    Xinzhao Wang et al. “Randomized Quantum Singular Value Transformation”. In: (Oct. 2025). arXiv: 2510.06851 [quant-ph]

    arXiv 2025

  32. [32]

    Halving the cost of quantum algorithms with randomization

    John M. Martyn and Patrick Rall. “Halving the cost of quantum algorithms with randomization”. In:npj Quantum Inf.11.1 (2025), p. 47.doi: 10.1038/s41534-025-01003-2. arXiv:2409.03744 [quant-ph]

    Pith/arXiv arXiv 2025

  33. [33]

    Yizhi Shen et al.Quantum Rational Transformation Using Linear Combinations of Hamiltonian Simulations. 2024. arXiv:2408.07742 [quant-ph]. url: https://arxiv.org/abs/2408.07742

    arXiv 2024

  34. [34]

    Toward the first quantum simulation with quantum speedup

    Andrew M. Childs et al. “Toward the first quantum simulation with quantum speedup”. In:Proc. Nat. Acad. Sci.115.38 (2018), pp. 9456–9461.doi: 10.1073/pnas.1801723115

    doi:10.1073/pnas.1801723115 2018

  35. [35]

    Phase estimation with partially randomized time evolution

    Jakob Günther et al. Phase estimation with partially randomized time evolution. 2025. arXiv: 2503.05647 [quant-ph]. url: https://arxiv.org/abs/2503.05647

    Pith/arXiv arXiv 2025

  36. [36]

    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”. In:SIAM J. Comput. 46.6 (2017), pp. 1920–1950.doi: 10.1137/16M1087072. arXiv: 1511.02306 [quant-ph]

    Pith/arXiv arXiv 2017

  37. [37]

    The Exponentially Convergent Trapezoidal Rule

    Lloyd N. Trefethen and J. A. C. Weideman. “The Exponentially Convergent Trapezoidal Rule”. In: SIAM Review 56.3 (2014), pp. 385–458. doi: 10.1137/130932132 . eprint: https://doi. org/10.1137/130932132. url: https://doi.org/10.1137/130932132

    doi:10.1137/130932132 2014

  38. [38]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010

    2010

  39. [39]

    Obtaining continuum physicsfromdynamicalsimulationsofHamiltonianlatticegaugetheories

    Christopher F. Kane, Siddharth Hariprakash, and Christian W. Bauer. “Obtaining continuum physicsfromdynamicalsimulationsofHamiltonianlatticegaugetheories”.In:(June2025).arXiv: 2506.16559 [hep-lat]

    Pith/arXiv arXiv

  40. [40]

    Iteration-Free Computation of Gauss–Legendre Quadrature Nodes and Weights

    I. Bogaert. “Iteration-Free Computation of Gauss–Legendre Quadrature Nodes and Weights”. In: SIAM Journal on Scientific Computing36.3 (2014), A1008–A1026. doi: 10.1137/140954969. eprint: https://doi.org/10.1137/140954969. url: https://doi.org/10.1137/140954969

    work page doi:10.1137/140954969 2014

  41. [41]

    Efficient Measurement-Driven Eigenenergy Estimation with Classical Shad- ows

    Yizhi Shen et al. “Efficient Measurement-Driven Eigenenergy Estimation with Classical Shad- ows”. In: (Sept. 2024). arXiv:2409.13691 [quant-ph]. 23

    arXiv 2024

  42. [42]

    Approximation Theory and Approximation Practice, Extended Edition.Philadel- phia,PA:SocietyforIndustrialandAppliedMathematics,2019

    LloydN.Trefethen. Approximation Theory and Approximation Practice, Extended Edition.Philadel- phia,PA:SocietyforIndustrialandAppliedMathematics,2019. doi: 10.1137/1.9781611975949. eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611975949. url: https://epubs. siam.org/doi/abs/10.1137/1.9781611975949

    doi:10.1137/1.9781611975949 2019

  43. [43]

    Probability Inequalities for Sums of Bounded Random Variables

    Wassily Hoeffding. “Probability Inequalities for Sums of Bounded Random Variables”. In:Journal of the American Statistical Association58.301 (1963), pp. 13–30.doi: 10.1080/01621459.1963. 10500830

    arXiv 1963

  44. [44]

    Improved Inequalities for the Poisson and Binomial Distribution and Upper Tail Quantile Functions

    Michael Short. “Improved Inequalities for the Poisson and Binomial Distribution and Upper Tail Quantile Functions”. In:International Scholarly Research Notices2013.1 (2013), p. 412958.doi: https://doi.org/10.1155/2013/412958. A Choosing the number of shots per Hadamard test Suppose we wish to estimate the following quantity: ⟨0| U † ψF (A)Uϕ |0⟩ = X s∈[S]...

    work page doi:10.1155/2013/412958 2013

  45. [47]

    Bounding the first term, we see that: e−(xymax)2/2 |x| ≤ κe−y2 max/2κ2 ≤ ϵ1 (73) 25 and thus ymax ≥ κ s 2 ln κ ϵ1 (74)

  46. [48]

    C.2 Proof of Theorem 5 Proof

    Bounding the second term, we see that: 2e−z2/2 |x| ≤ 2κe−z2 max/2 ≤ ϵ2 (75) and thus zmax ≥ s 2 ln 2κ ϵ2 (76) Since any allowedϵ1, ϵ2 will work, we setϵ1 = ϵT /3 and ϵ2 = 2ϵT /3 to arrive at the desired result. C.2 Proof of Theorem 5 Proof. We begin the proof by first discussing the relevant error bounds we use to characterize the total discretization err...

  47. [710]

    doi: https://doi.org/10.1016/j.future.2024.04.060

    issn: 0167-739X. doi: https://doi.org/10.1016/j.future.2024.04.060 . url: https: //www.sciencedirect.com/science/article/pii/S0167739X24002012

    doi:10.1016/j.future.2024.04.060 2024

  48. [1496]

    arXiv: 2302.13555 [quant-ph]

    Pith/arXiv arXiv

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.