{"id":"ecdf61cb-9282-40b0-a781-e1b4661d06b7","arxiv_id":"2608.08433","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Preparing a generic classical data vector as a quantum state provably costs Θ(N) gates, so algorithms that claim O(polylog N) total time on classical data are dominated by their own input stage.","lead":"This paper argues that loading classical data into a quantum computer costs a number of operations that grows linearly with the data size, which can erase claimed quantum speedups such as the quadratic advantage in Monte Carlo integration. Generalists should read it to understand why 'input for free' assumptions dominate many quantum machine learning advantage claims.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lognormal CDF is efficiently approximable, so Eq. (9)'s Θ(N) per-oracle cost is not forced and the claimed elimination of QAE's speedup does not follow.","rationale":"The reader correctly identified the load-bearing assumption: the paper needs the lognormal to have no efficiently computable CDF and no approximate loader whose error can be absorbed into the Monte Carlo tolerance. That assumption is false as stated. Sec. IV's own criterion is poly(n)-size classical computability, and the standard normal CDF satisfies that criterion through well-known rational approximations; elementary form is not the relevant notion. Consequently, Eq. (9)'s Θ(1/ε) per-oracle cost is not established for the paper's central application, and the abstract's claim that the input cost eliminates the quadratic advantage of quantum amplitude estimation is unsupported. The Sec. III counting lower bound applies to arbitrary amplitude-encoded states and does not constrain a two-parameter structured family such as the lognormal. This is an internal inconsistency in the argument rather than a mere disagreement with consensus. I recommend REJECT because the advertised headline result is invalid as written; a revised version that either replaces the lognormal example with a distribution family whose CDF is genuinely Ω(N)-hard to approximate, or explicitly restricts the no-advantage claim to that setting, could be re-evaluated.","tokens_in":6015,"tokens_out":10939,"duration_ms":130024,"concrete_test":"Implement Grover–Rudolph loading for the lognormal using a reversible fixed-point circuit for Φ((ln x−μ)/σ), built from a standard rational approximation to erf (e.g., Cody's algorithm), with n-bit precision and total-variation error below the QAE tolerance ε. Transpile to {cx,rz,sx,x} at optimization level 1 and count CNOT gates for n=8, 16, 32, and 64. If the CNOT count grows polynomially in n rather than doubling with each added qubit, then the per-oracle cost in Eq. (9) is polylog(1/ε), directly falsifying the paper's claim that the QAE speedup for its lognormal option-pricing example is eliminated.","verdict_should_be":"REJECT","load_bearing_attack":"The central quantitative conclusion in Secs. IV–V rests on a category error. Sec. IV defines an efficient Grover–Rudolph loader by requiring the CDF to be 'computable by a classical circuit of size poly(n)', but it then dismisses the lognormal because its CDF has no elementary form. The absence of an elementary antiderivative is irrelevant to computational tractability: the lognormal CDF is Φ((ln x−μ)/σ), and the standard normal CDF admits rational and polynomial approximations that evaluate Φ to n-bit precision with poly(n)-size circuits. A reversible implementation of such an approximation supplies exactly the oracle U_P of Eq. (8), making the bisection construction run in O(n·poly(n)) gates. Choosing the approximation error at the QAE tolerance ε keeps the total error within budget, so the per-query cost of A for the paper's own lognormal example is polylog(1/ε), not Θ(1/ε). Equation (9) then becomes O(1/ε)·polylog(1/ε) rather than O(1/ε^2), and the claimed elimination of the quadratic advantage for quantum Monte Carlo does not follow. The Sec. III lower bound concerns arbitrary exact states and cannot be transferred to a two-parameter distribution family.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that quantum machine learning and quantum Monte Carlo analyses routinely omit the cost of encoding classical data into quantum states. It reviews basis, amplitude, and Grover-Rudolph encodings, proves via dimension counting that exact preparation of an arbitrary n-qubit state costs Ω(2^n) two-qubit gates, reports transpiled CNOT counts for a sine distribution, and uses these counts to argue that quantum amplitude estimation for a lognormal Monte Carlo problem costs O(1/ε^2) rather than O(1/ε). It extends the argument to quantum kernel methods and concludes with a checklist for evaluating input-dependent advantage claims. Executable notebooks are provided for reproducibility.","tokens_in":6287,"tokens_out":5470,"duration_ms":58454,"significance":"The paper makes a useful and partly novel accounting point: classical input loading is a real cost that is frequently omitted from quantum machine learning complexity claims. The dimension-count lower bound, the distinction between hard-coded angle lists and reversible-arithmetic loading, and the reproducible gate-count benchmark are valuable contributions. The paper also gives a practical checklist that could influence how future input-dependent advantage claims are evaluated. However, the central quantitative conclusion about quantum Monte Carlo is not supported as stated, because the lognormal example is treated as intractable based on the absence of an elementary CDF, which is not a computational-complexity statement. The manuscript therefore needs substantive revision before its strongest claims can be accepted.","major_comments":[{"comment":"The claim that the lognormal CDF is not efficiently integrable because it has no elementary form conflates analytic closed form with computational tractability. The lognormal CDF is Φ((ln x - μ)/σ), and the standard normal CDF Φ admits uniform rational and polynomial approximations that can be evaluated to n-bit accuracy by poly(n)-size reversible circuits. Under the paper's own definition in Sec. IV of an efficiently integrable density as one whose CDF is computable by a classical circuit of size poly(n), this supplies the oracle U_P of Eq. (8), so the Grover-Rudolph bisection construction runs in O(n·poly(n)) gates. Choosing the approximation error at the QAE tolerance ε keeps the total error within budget. Therefore the per-query cost of A in Eq. (9) need not be Θ(1/ε), the total cost can remain O(1/ε) polylog(1/ε), and the claimed elimination of the quadratic advantage does not follow for the paper's own example.","section":"Sec. IV-V, Eq. (9)"},{"comment":"The Ω(2^n) lower bound applies to arbitrary target states and cannot be transferred to a two-parameter family such as lognormal densities. The lower bound is a dimension-counting argument over the full manifold of normalized states; it establishes the existence of hard states, not that every classical distribution is hard. The passage from the lower bound to the statement that the lognormal loader costs Θ(N) requires a genericity assumption that is not stated or proved. The paper should either prove a per-family lower bound for lognormal loading or explicitly restrict the QAE discussion to unstructured data.","section":"Sec. III vs. Sec. V"},{"comment":"The claim that quantum kernel methods carry a Θ(M^2) state-preparation cost 'that does not amortize' is not by itself an input bottleneck if each feature state is prepared by a short data-dependent circuit such as an angle-encoded feature map. The M^2 count is a query count for estimating the Gram matrix and may be intrinsic to the estimation procedure; without specifying the per-state preparation cost, the argument does not establish a Θ(N) input cost for kernel methods. This claim should be either qualified or supported with the concrete per-feature-state preparation cost.","section":"Sec. VI, kernel methods"}],"minor_comments":[{"comment":"The first column is labeled 'nbins' but contains the values 3, 5, 7, 8, which are qubit counts; the corresponding bin counts are 8, 32, 128, 256. The header should be corrected to avoid confusion.","section":"Table I"},{"comment":"The statement that the library StatePreparation count 'doubles with each additional qubit' is not supported by the measured rows: the count grows from 4 at n=3 to 26 at n=5 and from 26 at n=5 to 120 at n=7. Only the n=7 to n=8 step is close to doubling. The sentence should be qualified as an asymptotic statement.","section":"Abstract and Table I"},{"comment":"The section heading appears as 'WHA T SUR VIVES' and Sec. VIII contains 'af ternoon'; these typos should be corrected.","section":"Sec. VII heading and Sec. VIII"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is readable and the lower-bound and benchmark portions are likely publishable, but the lognormal argument is the crux of the QAE section and is currently incorrect: absence of an elementary antiderivative does not imply absence of a poly-size classical circuit, and the standard normal CDF has well-known efficient approximations. I recommend requiring the author to address this point before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the cleanest part is a useful review: the three encoding costs, the dimension-count lower bound, and the distinction between hard-coding angles and actually building reversible arithmetic for Grover-Rudolph loading. The benchmark table and the notebooks are a nice touch, and the checklist in Sec. VIII is genuinely practical. Second, the paper's main quantitative claim, that amplitude estimation for Monte Carlo loses its quadratic speedup because loading costs Theta(N), does not hold for the paper's own lognormal example. The stress-test note is right: the lognormal CDF is Phi((ln x - mu)/sigma), and Phi has polynomial-size rational approximations. So the oracle U_P in Eq. (8) can be implemented with a poly(n) reversible circuit, making each query cost polylog(1/epsilon) rather than Theta(1/epsilon). Eq. (9) then becomes O(1/epsilon) polylog(1/epsilon), and the quadratic advantage survives.\n\nThat is a load-bearing error, not a typo. The broad claim that generic classical data costs Theta(N) to load is fine as a counting theorem. But the paper overreaches when it applies that bound to specific distributions with efficient CDF approximations. The lognormal is exactly the case where Grover-Rudolph works as advertised once you use a reversible evaluation of the CDF rather than a hard-coded angle list. The author's own Sec. IV defines 'efficiently integrable' correctly as poly(n)-computable CDF, then dismisses the lognormal for lacking an elementary antiderivative, which is a category error.\n\nThere are smaller issues: Table I's first row lists 8 angles for 3 qubits (should be 7), and the 'permanent' framing in the title is stronger than the paper's own Sec. VII boundaries justify. The kernel-claims section is too brief to carry its weight.\n\nWho gets value? Anyone thinking about data-loading costs in QML and the fine print of input assumptions. The paper is a good seminar topic and a useful reference for the checklist, but not for Eq. (9).\n\nMy recommendation: send it to peer review, but the referee should insist the QAE section be fixed or substantially softened. The reproducible benchmark and the synthesis are worth keeping; the cancellation claim is not.","headline":"Good synthesis and benchmark, but the QAE speedup-cancellation claim collapses on the lognormal case because the normal CDF is efficiently approximable.","tokens_in":6738,"tokens_out":2975,"would_cite":false,"duration_ms":29906,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Loading classical data into a quantum computer costs $\\(\\Theta(N)\\)$ gates, provably, and that bill erases the quadratic speedup of quantum Monte Carlo.","keywords":["quantum machine learning","state preparation","amplitude encoding","Grover-Rudolph loading","quantum amplitude estimation","Monte Carlo integration","dequantization","input models"],"falsifier":"Construct a state-preparation routine for a lognormal distribution on $N=2^n$ bins whose transpiled two-qubit gate count grows as $o(N)$—for example a trained shallow generative circuit—while keeping the induced pricing error inside the Monte Carlo tolerance, and measure whether the total cost to reach relative error $\\epsilon$ is $o(1/\\epsilon^2)$; if it is, the claim that quantum amplitude estimation for Monte Carlo collapses to classical scaling fails.","tokens_in":5854,"feed_emoji":"⚛️","tokens_out":13530,"duration_ms":119369,"temperature":0.7,"pith_summary":"Quantum algorithms are usually analyzed as if their input state were free, but when the input is classical data the preparation stage has a real cost. This paper argues that this cost is $\\(\\Theta(N)\\)$ two-qubit gates for generic $\\N$-element data—a counting theorem, not a hardware limitation—and that basis encoding, amplitude encoding, and Grover–Rudolph distribution loading all pay it once transpiled to a hardware gate set. The argument also counts the classical preprocessing: computing the rotation angles for the latter two requires reading the entire input vector. If the paper is right, the quadratic speedup of quantum amplitude estimation for Monte Carlo integration disappears, because the $O(1/\\epsilon)$ oracle queries each cost $\\Theta(1/\\epsilon)$ gates, leaving total cost $O(1/\\epsilon^2)$, the same scaling as classical sampling. The same accounting is extended to quantum machine learning, where strong input models enable classical dequantization and quantum kernel Gram matrices carry a $\\Theta(M^2)$ preparation cost.","feed_headline":"Data loading costs $\\Theta(N)$ gates; quantum Monte Carlo's edge dies","feed_subtitle":"Better qubits won't fix it—the $\\Theta(N)$ input bill must appear in every quantum advantage claim","key_machinery":"The load-bearing object is a counting lower bound: because the manifold of normalized $n$-qubit states has $2^{n+1}-2$ real parameters and a circuit of $g$ gates from a fixed two-qubit gate set spans only $O(g)$ parameters, any exact preparation of an arbitrary state requires $g=\\Omega(2^n)$ gates; known constructions such as the uniformly controlled rotation tree and the ancilla-based superposition routine make the bound tight, so the cost is $\\Theta(N)$. The Grover–Rudolph bisection recursion is the third encoding, and its efficiency depends entirely on whether the target distribution has an efficiently integrable cumulative distribution function; when the angles are instead computed classically, the classical preprocessing has already read the whole vector. The machinery that carries the argument is this pairing of a dimension-count lower bound with an explicit accounting of classically computed angles, which no compiler pass can remove.","core_discovery":"The paper's central claim is that preparing a generic classical input—whether a length-$N$ amplitude vector, a set of $M$ basis patterns, or a discretized probability density—costs $\\Theta(N)$ two-qubit gates, and that this is a lower bound on information injection rather than an artifact of current hardware. The supporting argument is a dimension count: an arbitrary $n$-qubit state carries $2^{n+1}-2$ real parameters, while a circuit of $g$ gates from a fixed two-qubit gate set is specified by $O(g)$ continuous parameters, so $g=\\Omega(2^n)$ is required and known constructions make the bound tight. Applying this to quantum amplitude estimation for Monte Carlo integration, the paper obtains total cost $O(1/\\epsilon^2)$ (Eq. 9), matching classical sampling exactly. For quantum machine learning, the claim is that the same bill closes the exponential gap: a polylogarithmic algorithm on generic classical data is dominated by its $\\Theta(N)$ input stage, strong input models that enable quantum speedups also enable classical dequantization, and quantum kernel Gram matrices require $\\Theta(M^2)$ non-amortizing state preparations.","pith_inferences":["The same $\\Theta(N)$ input bill should apply to other data-consuming routines, such as loading covariance matrices or recommendation-system vectors, so claimed advantages in those settings would need to be re-derived with the input stage included.","A testable extension of the argument would be a systematic benchmark of learned loaders (trained generative ansätze) against exact loading for the same densities: if a trained circuit prepares a lognormal within tolerance at subexponential gate count, the 'permanent' part of the bound would apply only to exact amplitude lists, not to approximate states.","The accounting suggests that comparisons between quantum algorithms should report total pipeline cost rather than oracle-query count, since an algorithm with more queries but cheaper per-query preparation can beat one with fewer expensive queries."],"forward_implications":["Any quantum algorithm that consumes a generic classical vector of length $N$ in $O(\\operatorname{polylog} N)$ time is dominated by its own input stage, which costs $\\Theta(N)$ gates.","Quantum amplitude estimation for Monte Carlo integration has total cost $O(1/\\epsilon^2)$, matching classical Monte Carlo sampling, once each query to the state-preparation oracle is charged $\\Theta(1/\\epsilon)$ gates.","Quantum kernel methods require $\\Theta(M^2)$ state preparations to fill the Gram matrix over $M$ training points, and this cost does not amortize across the dataset.","Advantage can survive only for genuinely efficiently preparable states, device-generated distributions, variationally learned loading, or amortized preparation; no exponential advantage survives on generic classical input.","Strong input models that grant fast quantum access to a dataset also grant fast classical sampling access, which is why several exponential quantum machine learning speedups are matched by dequantized classical algorithms."],"supporting_citations":[{"why":"supplies the ancilla-based superposition routine used to load $M$ basis-encoded patterns, grounding the linear depth cost for basis encoding.","marker":"[1]"},{"why":"provides the uniformly controlled rotation tree that implements amplitude encoding and yields the $2^n-1$ classically computed angle count.","marker":"[2]"},{"why":"introduces the bisection construction for loading probability distributions whose efficiency depends on an efficiently integrable cumulative distribution function.","marker":"[3]"},{"why":"defines quantum amplitude estimation and its $O(1/\\epsilon)$ query complexity, the speedup whose cancellation the paper computes.","marker":"[4]"},{"why":"argues independently that Grover–Rudolph state preparation removes the quantum advantage for Monte Carlo integration, the result the paper reproduces and extends.","marker":"[5]"},{"why":"surveys hidden assumptions in quantum machine learning claims, including the cost of input access and the QRAM assumption.","marker":"[6]"},{"why":"provides the dequantization result showing strong input assumptions that enable quantum speedups also enable classical algorithms.","marker":"[7]"},{"why":"supplies a universal gate decomposition that meets the exponential lower bound, showing the $\\Theta(N)$ cost is tight.","marker":"[8]"},{"why":"gives a synthesis algorithm for quantum-logic circuits that also meets the lower bound, confirming the bound is asymptotically optimal.","marker":"[9]"}],"fun_headline_variants":["Input encoding's Θ(N) cost kills quantum ML speedups","Quantum ML's edge dies when you price in data loading","The input bill: Θ(N) gates that no hardware upgrade fixes","Quantum Monte Carlo's speedup dies when input loading counts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on the premise that, for generic classical data—specifically densities such as the lognormal used in the Monte Carlo example—there is no efficiently integrable cumulative distribution function and no approximate loading scheme whose error can be absorbed into the downstream tolerance, so every query to the state-preparation oracle genuinely costs $\\Theta(N)$ gates.","fun_headline_variants_meta":{"raw":{"variants":["Input encoding's Θ(N) cost kills quantum ML speedups","Quantum ML's edge dies when you price in data loading","The input bill: Θ(N) gates that no hardware upgrade fixes","Quantum Monte Carlo's speedup dies when input loading counts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001133,"raw_usage":{"total_tokens":4759,"prompt_tokens":1052,"completion_tokens":3707,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":668,"completion_tokens_details":{"reasoning_tokens":3637}},"tokens_in":668,"tokens_out":3707,"duration_ms":30424,"temperature":1.0,"reasoning_tokens":3637,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:34:59.447255+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a state-preparation routine for a lognormal distribution on $N=2^n$ bins whose transpiled two-qubit gate count grows as $o(N)$—for example a trained shallow generative circuit—while keeping the induced pricing error inside the Monte Carlo tolerance, and measure whether the total cost to reach relative error $\\epsilon$ is $o(1/\\epsilon^2)$; if it is, the claim that quantum amplitude estimation for Monte Carlo collapses to classical scaling fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the ancilla-based superposition routine used to load $M$ basis-encoded patterns, grounding the linear depth cost for basis encoding."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the uniformly controlled rotation tree that implements amplitude encoding and yields the $2^n-1$ classically computed angle count."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the bisection construction for loading probability distributions whose efficiency depends on an efficiently integrable cumulative distribution function."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines quantum amplitude estimation and its $O(1/\\epsilon)$ query complexity, the speedup whose cancellation the paper computes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"argues independently that Grover–Rudolph state preparation removes the quantum advantage for Monte Carlo integration, the result the paper reproduces and extends."},{"cited_title":"The input problem is permanent","cited_arxiv_id":null,"evidence_quote":"surveys hidden assumptions in quantum machine learning claims, including the cost of input access and the QRAM assumption."},{"cited_title":"Quantum Associative Memory","cited_arxiv_id":"quant-ph/9807053","evidence_quote":"provides the dequantization result showing strong input assumptions that enable quantum speedups also enable classical algorithms."}],"review_version":1}