Pith. sign in

REVIEW 3 major objections 4 minor 16 references

Quantum search can determine the minimum working precision required to correctly round an elementary function, running in time O~(2^{n/2}) and beating classical methods for periodic functions in large binades.

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 ↗

T0 review · deepseek-v4-flash

2026-08-03 09:34 UTC pith:XK3RGEEH

load-bearing objection Fresh idea but the bad-case oracle in Section 4 misses m_n=0 midpoint cases, so Theorem 1 as stated fails; the flaw is concrete and fixable. the 3 major comments →

arxiv 2601.13306 v2 pith:XK3RGEEH submitted 2026-01-19 quant-ph cs.NAmath.NA

The table maker's quantum search

Benjamin C. A. Morrison , Stefanos Kourtis This is my paper
classification quant-ph cs.NAmath.NA
keywords quantum searchtable maker's dilemmahardness to roundcorrect roundingelementary functionsfloating-point arithmeticquantum arithmeticbinary search
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 paper asks: how many extra bits of precision must an elementary function be evaluated to before the correctly rounded value at n-bit precision is guaranteed for every input? This quantity, the 'hardness to round,' is expensive to compute classically, and for periodic functions in large binades the best known algorithms run in exponential time with exponent roughly 0.676n. The paper proves that quantum search answers the question in time O~(2^{n/2}) for functions related to the exponential (exp, log, sin, cos), a modest but genuine asymptotic speedup. The algorithm treats the working precision as a search parameter: it builds a quantum oracle that flags inputs for which a given precision p leaves rounding ambiguous, and binary-searches on p using quantum search as the emptiness test. A concrete resource estimate for double-precision sin and cos shows the current version would require unrealistically long qubit coherence times, so the result is primarily a theoretical demonstration that this problem has quantum structure.

Core claim

Theorem 1 states that for any elementary function f, on a binade of n-bit floating-point inputs, Algorithm 1 returns the hardness to round (or an upper bound if none exists) with probability 1−δ using O(2^{n/2} log(⌊log p_max⌋+1 / δ)) oracle calls; when a polynomial upper bound on the hardness exists, e.g., for exponential/logarithmic/trigonometric functions, it runs in O~(2^{n/2} log(1/δ)). The key to the result is that the number of 'bad rounding cases' — inputs whose p-bit approximation ends in a long run of 0s or 1s — is non-increasing in p, so the smallest p with no bad cases can be found by binary search. Each emptiness query is a quantum search run on a superposition of all n-bit sign

What carries the argument

The central object is the hardness to round, htr_{f,I}(n): the smallest working precision p such that evaluating f to p bits guarantees correct rounding to n bits for every input in a binade I. The carrying mechanism is Algorithm 1, which runs a binary search over p and uses quantum search as an emptiness test at each step. The membership oracle is built from two circuits: a reversible arithmetic circuit that evaluates f(x) to p significant digits coherently across a superposition of all n-bit significands, and a pattern detector that flags inputs whose p-bit approximation ends in a long run of 0s or 1s (110...0 or 101...1 under round-to-nearest, ties-to-even), which are exactly the 'bad rou

Load-bearing premise

The membership oracle assumes that the only obstruction to correct rounding is a long trailing run of 0s or 1s in the p-bit approximation (patterns 110...0 or 101...1 for round-to-nearest ties-to-even), and that the set of inputs producing these patterns shrinks monotonically as p grows; if that characterization is not exactly equivalent to the definition of hardness-to-round, the binary search may return the wrong value.

What would settle it

For a small target precision n (say n=8) and a simple transcendental function such as sin over a small binade, exhaustively compute the true hardness to round by evaluating f to very high precision for every input, and compare it to the value Algorithm 1 would return (simulated classically); any input where rounding is ambiguous at some p but the p-bit approximation does not end in the specified long-run patterns would falsify the oracle's completeness.

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

If this is right

  • For elementary functions related to the exponential (exp, log, sin, cos, and similar), the hardness to round over a binade can be computed in O~(2^{n/2}) time, an asymptotic improvement over the classical O~(2^{0.676n}) heuristic and O~(2^{4n/5}) algorithm for periodic functions in large binades.
  • By superposing the d-bit exponent instead of hard-coding it, the same algorithm computes the hardness to round over all binades of a format in O~(2^{(n+d)/2}) time.
  • Because the hardness to round for a given function and format is a one-time computation, the cost of implementing and optimizing the quantum circuits can be amortized over every future use.
  • The algorithm can be focused on the most likely range [n+1, 2n] of working precisions first, reducing the number of binary search steps in practice.
  • Standalone quantum search (without a classically structured inner algorithm) achieves a speedup here, a comparatively rare situation.

Where Pith is reading between the lines

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

  • The same oracle construction could be extended to complex-valued elementary functions or to multi-argument functions like pow(x,y), where classical hardness results are sparser, potentially making quantum search an even more useful tool there.
  • A hybrid design that uses quantum search only for large binades, where classical polynomial approximation fails, could cut the coherence-time burden enough to make a near-term demonstration plausible.
  • If hardness-to-round is genuinely connected to factoring, a number-theoretic quantum algorithm might reduce the exponential 2^{n/2} scaling to polynomial, a much larger payoff than the current quadratic speedup.

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 / 4 minor

Summary. The paper proposes a quantum algorithm, Algorithm 1, that computes the hardness to round an elementary function over a binade of precision-n floating-point inputs by binary-searching the working precision p and using Grover search at each level to test whether any input is a bad rounding case. Theorem 1 claims O~(2^{n/2} log(1/δ)) query complexity, with an asymptotic speedup over the best known classical algorithms for periodic functions in large binades. The abstract also promises a fault-tolerant resource estimate for sin/cos in double precision, but the body does not contain such an estimate.

Significance. If the main theorem were correct, the paper would provide a rare example of standalone Grover search outperforming the best known classical algorithms for a problem of practical interest in computer arithmetic. The algorithmic structure is simple and the claimed quadratic speedup is plausible given the BBHT framework. The paper also avoids fitted parameters and builds on known rigorous upper bounds. However, the correctness of the whole construction rests on the oracle's characterization of bad rounding cases, and that characterization is both incomplete and not rigorously connected to the definition of hardness to round. The missing resource-estimation section is also a stated contribution that is absent from the manuscript.

major comments (3)
  1. [Section 4, Eq. (9)] The bad-case patterns for round-to-nearest, ties-to-even are incomplete. For n=2, p=4, the midpoint B=1.0010_2 between 1.00_2 and 1.01_2 has trailing bits 010...0, i.e., m_n=0, guard=1, tail=0. This approximation is not in the set {110...0, 101...1} that C_bad tests, yet it is a bad case: if the true value is B+ε with small ε>0, it rounds up, while the approximation B ties-to-even with m_n=0 rounds down. Thus the oracle fails to mark genuine bad inputs, and Algorithm 1 can incorrectly conclude that no bad case exists at the true hardness, returning a value below htr. This directly falsifies Theorem 1 as stated. Section 3's own criterion (last p−n−1 digits all 0 or all 1) would flag this example, so the two sections are internally inconsistent.
  2. [Section 2 and Section 5] The correctness of the binary search relies on the assertion that 'the number of bad rounding cases is a non-increasing function of p.' But the oracle C_bad tests the particular p-bit approximation \tilde f(x), not the exact distance from f(x) to a rounding boundary. A larger p can in principle produce an approximation that is accidentally closer to a midpoint, so monotonicity of the flagged set S_p is not automatic. The paper cites [MBdD+09] for the characterization, but never proves that the trailing-bit pattern of \tilde f(x) is equivalent to the exact condition that f(x) is within 2^{-p} of a midpoint. Without such an equivalence, the binary search does not compute htr. This is a load-bearing gap, not a presentation issue.
  3. [Abstract vs. body] The abstract promises: 'We then estimate the resources required for a fault-tolerant implementation of the proposed algorithm for the sin and cos functions in double precision. We find that ... it requires qubit coherence times that are unrealistically long.' No such section, table, or numerical estimate appears anywhere in the manuscript. The practical conclusion claimed in the abstract is therefore unsupported. This needs to be either added in revision or removed from the abstract.
minor comments (4)
  1. [Section 3] The additive error 'within 2^{-p}' should specify whether the bound is strict or non-strict and whether it is absolute or relative. The distinction matters for approximations exactly at B ± 2^{-p}.
  2. [Section 4] The statement that C_bad can be implemented with O(n) Toffoli gates is imprecise: the relevant string length is p-n+1, and the overall circuit size should be stated as a function of p as well.
  3. [Section 4, Eq. (8)-(11)] The notation O_{f,\bullet}_{n,e} is awkward and the subscript/superscript placement is easy to confuse with the oracle family. Consider a cleaner notation such as \mathcal{O}_{n,e}^{f}.
  4. [Section 6] The final paragraph mentions generalizations to all binades in O~(2^{(n+d)/2}) time, but does not discuss the cost of constructing the more complex arithmetic circuits for argument reduction. This is probably future work and should be labeled as such.

Circularity Check

0 steps flagged

No circularity: Algorithm 1 is a self-contained reduction of hardness-to-round computation to Grover search; the oracle criterion is an assumption about correct rounding, not a fitted or renamed input.

full rationale

The paper's derivation chain is not circular. htr_f,I(n) is defined externally in Section 3 as the smallest working precision p such that correct rounding is guaranteed for all inputs in I. Algorithm 1 binary-searches over p using oracles O_{f,p}_{n,e} that coherently evaluate f to precision p and mark inputs whose p-bit approximations display the trailing-string patterns 110...0 or 101...1 (Section 4). The theorem equates the absence of marked inputs with p >= htr; that equivalence is the paper's substantive correctness claim, supported by the error analysis in Section 3 and by the standard table-maker's dilemma treatment in [MBdD+09]. No parameter is fitted to htr: p_max is an externally supplied upper bound from [NW00]/[BHMZ25], and the oracle circuits are assumed reversible arithmetic implementations whose construction cost is polynomial in n and p. The quantum runtime O~(2^{n/2} log(1/delta)) is derived from the standard Grover/BBHT analysis and a Chernoff bound, not from htr. There are no self-citations by the authors, and the cited uniqueness/bound results are external mathematical facts. The possible flaw that the trailing-string characterization omits bad cases with n-th bit 0 (e.g. 010...0) would be a correctness or rigor gap in Theorem 1, not a circularity: the algorithm still computes the minimal p with no marked items, and the paper's claim that this equals htr rests on an independent characterization of rounding ambiguity. Section 6's caveats about exponential scaling, prefactors, and coherence times are limitations, not evidence of circularity. Hence the derivation is self-contained apart from the correctness assumptions it states, and no circular step is present.

Axiom & Free-Parameter Ledger

1 free parameters · 5 axioms · 0 invented entities

The central claim rests on standard quantum search, an external transcendence-based upper bound, and the standard table-maker's-dilemma characterization of bad rounding cases. No new physical or mathematical entities are introduced. The main uncharged assumptions are the exactness of the bad-case pattern test and the polynomial overhead of reversible function evaluation.

free parameters (1)
  • C (Nesterenko-Waldschmidt constant in p_max = C n^2) = unspecified
    The theorem that htr_f,I(n) ≤ C n^2 for exponential-related functions is cited to [NW00, BHMZ25] but the constant C is not computed in the paper; it sets the upper bound p_max used in Algorithm 1 and is needed for any resource estimate.
axioms (5)
  • standard math Grover's algorithm can decide emptiness of a set S⊆{0,1}^n with O(2^{n/2} log(1/δ')) oracle calls.
    Invoked in Sections 4 and 5 via [Gro96, BBHT98]; foundational quantum-computing result.
  • domain assumption A p-bit evaluation with error ≤2^{-p} is sufficient for correct rounding to n bits iff no input's p-bit significand ends in 110...0 or 101...1 (round-to-nearest, ties-to-even).
    Used to build the membership oracle in Section 4; cited to [MBdD+09], not proved or formally stated in this paper. This is the key link between the circuit-level oracle and the hardness definition.
  • domain assumption The set of bad rounding cases is non-increasing as working precision p increases.
    Stated in Section 2 and used for the binary search invariant in Algorithm 1; no proof given. Needs the preceding characterization to be exact.
  • domain assumption Effective upper bound htr_f,I(n) ≤ C n^2 for functions related to the exponential function.
    Taken from [NW00, BHMZ25] in Sections 2 and 5; used to set p_max=poly(n) and obtain the O~(2^{n/2}) claim. The constant C is not computed.
  • domain assumption Arbitrary-precision elementary function evaluation can be implemented as a reversible circuit of size poly(n,p).
    Stated in Section 4 using [BZ10, Ben89, LS90]; required for the oracle cost to be absorbed into the tilde notation. Exception handling for exceptional inputs is assumed included.

pith-pipeline@v1.3.0-alltime-deepseek · 10111 in / 18042 out tokens · 179310 ms · 2026-08-03T09:34:49.090189+00:00 · methodology

0 comments
read the original abstract

We show that quantum search can be used to compute the hardness to round an elementary function, that is, to determine the minimum working precision required to compute the values of an elementary function correctly rounded to a target precision of $n$ digits for all possible precision-$n$ floating-point inputs in a given interval. For elementary functions $f$ related to the exponential function, quantum search takes time $\tilde O(2^{n/2} \log (1/\delta))$ to return, with probability $1-\delta$, the hardness to round $f$ over all $n$-bit floating-point inputs in a given binade. For periodic elementary functions in large binades, standalone quantum search yields an asymptotic speedup over the best known classical algorithms and heuristics. We then estimate the resources required for a fault-tolerant implementation of the proposed algorithm for the $\sin$ and $\cos$ functions in double precision. We find that, although the algorithm can in principle compete with the fastest known practical method for computing the hardness to round over all binades in the format, it requires qubit coherence times that are unrealistically long for present technology.

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

16 extracted references · 3 canonical work pages

  1. [7]

    1145/237814.237866

    Association for Computing Machinery.doi:10. 1145/237814.237866. 9 [HLSZ07] Guillaume Hanrot, Vincent Lefevre, Damien Stehle, and Paul Zimmermann. Worst cases of a periodic function for large arguments. In18th IEEE Symposium on Computer Arith- metic (ARITH ’07), pages 133–140, 2007.doi:10.1109/ARITH.2007.37. [Kah04] W. Kahan. A logarithm too clever by half,

    arXiv 2007

  2. [14]

    [BHMT02] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp

    Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.doi:10.1007/ 978-3-540-88702-7_1. [BHMT02] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude ampli- fication and estimation,

    2009

  3. [15]

    10 [Ste06] Damien Stehlé

    doi:10.1109/TC.2005.55. 10 [Ste06] Damien Stehlé. On the randomness of bits generated by sufficiently smooth functions. In Florian Hess, Sebastian Pauli, and Michael Pohst, editors,Algorithmic Number Theory, pages 257–274, Berlin, Heidelberg,

    work page doi:10.1109/tc.2005.55 2005

  4. [1933]

    [LS90] Robert Y

    URL:http://www.jstor.org/stable/ 2301023. [LS90] Robert Y . Levine and Alan T. Sherman. A note on bennett’s time-space tradeoff for reversible computation.SIAM Journal on Computing, 19(4):673–677, 1990.doi: 10.1137/0219046. [MBdD+09] Jean-Michel Muller, Nicolas Brisebarre, Florent de Dinechin, Claude-Pierre Jeannerod, Vincent Lefèvre, Guillaume Melquiond,...

    work page doi:10.1137/0219046 1990

  5. [1991]

    [Sho94] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124– 134, 1994.doi:10.1109/SFCS.1994.365700. [SLZ05] D. Stehle, V . Lefevre, and P. Zimmermann. Searching worst cases of a one-variable func- tion using lattice reduction.IEEE Transactions...

    arXiv 1994

  6. [1992]

    Boolean satisfiability solvers and their applications in model checking.Proceedings of the IEEE, 103(11):2021–2035,

    [VWM15] Yakir Vizel, Georg Weissenbacher, and Sharad Malik. Boolean satisfiability solvers and their applications in model checking.Proceedings of the IEEE, 103(11):2021–2035,

    2021

  7. [1996]

    [Für08] Martin Fürer

    Springer Berlin Heidelberg. [Für08] Martin Fürer. Solving np-complete problems with quantum search. In Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, and Luerbio Faria, editors,LATIN 2008: Theoretical Informatics, pages 784–792, Berlin, Heidelberg,

    2008

  8. [1998]

    [Ben89] Charles H

    URL:http: //dx.doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493:: AID-PROP493>3.0.CO;2-P,doi:10.1002/(sici)1521-3978(199806) 46:4/5<493::aid-prop493>3.0.co;2-p. [Ben89] Charles H. Bennett. Time/space trade-offs for reversible computation.SIAM Journal on Computing, 18(4):766–776, 1989.doi:10.1137/0218053. [Ber09] Daniel J. Bernstein.Introduction to post-q...

    doi:10.1002/(sici)1521-3978(199806)46:4/5 1989

  9. [1999]

    [NC10] Michael A

    URL:https://www.aeaweb.org/articles?id=10.1257/jel.37.2.633, doi:10.1257/jel.37.2.633. [NC10] Michael A. Nielsen and Isaac L. Chuang.Quantum search algorithms, page 248–276. Cambridge University Press,

    doi:10.1257/jel.37.2.633

  10. [2000]

    [Reg25] Oded Regev

    URL:https://arxiv.org/ abs/math/0002047,arXiv:math/0002047. [Reg25] Oded Regev. An efficient quantum factoring algorithm.J. ACM, 72(1), January

    Pith/arXiv arXiv

  11. [2002]

    [BHMZ25] PhD Brisebarre, Nicolas, Guillaume Hanrot, Jean-Michel Muller, and Paul Zimmermann

    URL:http://dx.doi.org/10.1090/conm/305/ 05215,doi:10.1090/conm/305/05215. [BHMZ25] PhD Brisebarre, Nicolas, Guillaume Hanrot, Jean-Michel Muller, and Paul Zimmermann. Correctly-rounded evaluation of a function: Why, how, and at what cost?ACM Comput. Surv., 58(1), September 2025.doi:10.1145/3747840. [BZ10] Richard P. Brent and Paul Zimmermann.Elementary an...

    doi:10.1090/conm/305/ 2025

  12. [2004]

    berkeley.edu/~wkahan/LOG10HAF.TXT

    URL:https://people.eecs. berkeley.edu/~wkahan/LOG10HAF.TXT. [Lef05] V . Lefevre. New results on the distance between a segment and z ² . application to the exact rounding. In17th IEEE Symposium on Computer Arithmetic (ARITH’05), pages 68–75, 2005.doi:10.1109/ARITH.2005.32. [Leh33] D. H. Lehmer. A note on trigonometric algebraic numbers.The American Mathe-...

    work page doi:10.1109/arith.2005.32 2005

  13. [2005]

    [Amb04] A

    Springer-Verlag.doi:10.1007/11560548_20. [Amb04] A. Ambainis. Quantum search algorithms.SIGACT News, 35(2):22–35, June 2004.doi: 10.1145/992287.992296. [BBHT98] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quan- tum searching.Fortschritte der Physik, 46(4–5):493–505, June

    arXiv 2004

  14. [2010]

    IEEE standard for floating-point arithmetic.IEEE Std 754-2019 (Revision of IEEE 754-2008), pages 1–84, 2019.doi:10.1109/ IEEESTD.2019.8766229

    [Com19] Microprocessor Standards Committee. IEEE standard for floating-point arithmetic.IEEE Std 754-2019 (Revision of IEEE 754-2008), pages 1–84, 2019.doi:10.1109/ IEEESTD.2019.8766229. [Cop96] Don Coppersmith. Finding a small root of a bivariate integer equation; factoring with high bits known. In Ueli Maurer, editor,Advances in Cryptology — EUROCRYPT ’...

    arXiv 2019

  15. [2015]

    [WLL+25] Siyi Wang, Xiufan Li, Wei Jie Bryan Lee, Suman Deb, Eugene Lim, and Anupam Chat- topadhyay

    doi:10.1109/JPROC.2015.2455034. [WLL+25] Siyi Wang, Xiufan Li, Wei Jie Bryan Lee, Suman Deb, Eugene Lim, and Anupam Chat- topadhyay. A comprehensive study of quantum arithmetic circuits.Philosophical Trans- actions A, 383(2288):20230392,

    arXiv 2015

  16. [2025]

    [Sch91] Eric Schmitt

    doi:10.1145/3708471. [Sch91] Eric Schmitt. After the war; army is blaming patriot’s computer for failure to stop the dhahran scud.The New York Times, pages NA–NA,

    doi:10.1145/3708471