The Input Problem: A Permanent Bottleneck for Quantum Machine Learning

Muhammad Faryad

REVIEW 3 major objections 3 minor 16 references

The Input Problem: A Permanent Bottleneck for Quantum Machine Learning

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Loading classical data into a quantum computer costs $$\Theta(N)$$ gates, provably, and that bill erases the quadratic speedup of quantum Monte Carlo.

desk verdict Good synthesis and benchmark, but the QAE speedup-cancellation claim collapses on the lognormal case because the normal CDF is efficiently approximable. read the letter →

arxiv 2608.08433 v1 pith:UIHEAHPW submitted 2026-08-09 quant-ph

Muhammad Faryad This is my paper · ORCID

classification quant-ph

keywords quantummachinelearningstatepreparationamplitudeencodingGrover-RudolphloadingestimationMonteCarlointegrationdequantizationinputmodels

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

That 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.

There 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.

Who 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).

My 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.

Referee Report

3 major / 3 minor

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.

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 (3)

[Sec. IV-V, Eq. (9)] 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.
[Sec. III vs. Sec. V] 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.
[Sec. VI, kernel methods] 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.

minor comments (3)

[Table I] 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.
[Abstract and Table I] 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.
[Sec. VII heading and Sec. VIII] The section heading appears as 'WHA T SUR VIVES' and Sec. VIII contains 'af ternoon'; these typos should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the input-cost bound is an independent counting argument and the QAE conclusion is arithmetic over prior bounds.

full rationale

The paper's central Θ(N) cost claim is a self-contained dimension/information-counting argument (Sec. III), not an assumption built from the conclusion. The Grover–Rudolph recursion and its oracle cost are cited from independent prior work (Grover–Rudolph, Möttönen et al.) and reproduced with explicit equations. Table I reports actual transpiled gate counts and classical angle counts; these are measurements, not fitted parameters relabeled as predictions. Equation (9) combines the standard QAE query bound O(1/ε) with the Sec. III per-oracle lower bound Θ(N) with N∼1/ε; the multiplication is arithmetic, and it is explicitly credited to Herbert [5] as an independent prior argument. No load-bearing step reduces by construction to its own input, and there are no self-citations or imported uniqueness theorems. A possible weakness—whether the lognormal CDF can be loaded in polylogarithmic cost via efficient classical approximations, which would undermine Eq. (9)—is a correctness/factual concern about transferring the arbitrary-state lower bound to a specific low-parameter distribution, not a circularity in the derivation chain.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper relies on established complexity theorems and standard numerical-analysis assumptions; it introduces no free parameters or invented entities.

assumptions (3)

standard math Preparing an arbitrary n-qubit state from |0⟩⊗n requires Ω(2^n) two-qubit gates (dimension-counting lower bound).
Cited to Shende et al. and Möttönen et al.; used in Sec. III to establish the Θ(N) gate bound for generic states.
domain assumption The lognormal CDF has no elementary closed form, so the Grover-Rudolph efficient oracle is not available for it.
Stated in Sec. IV; this makes the Θ(N) cost apply to the lognormal example used in the QAE argument.
domain assumption Relative precision ε in Monte Carlo requires N ~ 1/ε discretization bins.
Assumed in Sec. V to convert the Θ(N) state-prep cost into a Θ(1/ε) per-query cost; not proven in the paper but standard in numerical integration.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Input Problem: A Permanent Bottleneck for Quantum Machine Learning." pith.science (2026). https://pith.science/paper/UIHEAHPW

@misc{pith2026260808433,
  author       = {Pith},
  title        = {Pith review of: The Input Problem: A Permanent Bottleneck for Quantum Machine Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UIHEAHPW}},
  note         = {Machine review of arXiv:2608.08433}
}

abstract

Quantum algorithms are conventionally presented with their input state supplied for free. When the input is classical data, this convention conceals a cost that is frequently larger than the algorithm it precedes. We review what the three standard encodings, such as basis encoding, amplitude encoding, and Grover--Rudolph distribution loading, actually cost once transpiled to a hardware gate set, and argue that the resulting $\Theta(N)$ bound is a counting theorem rather than an engineering limitation that improved hardware will remove. Measured gate counts for a representative loading task are reported: an optimal library implementation requires $247$ CNOT gates at $n=8$ qubits and doubles with each additional qubit, while the classical preprocessing that produces the rotation angles requires reading the entire input vector. We show how this cost eliminates the quadratic advantage of quantum amplitude estimation for Monte Carlo integration, and argue that the same accounting constrains quantum machine learning more broadly: the strong input models that make quantum algorithms fast on classical data also enable classical dequantization, and quantum kernel methods carry a $\Theta(M^2)$ state-preparation cost for the Gram matrix that does not amortize. We explain that the efficiently preparable states, device-generated distributions, variationally learned loading, and amortized preparation are required to get advantage from quantum machine learning and close with a checklist for evaluating input-dependent advantage claims. Executable notebooks reproducing every construction and measurement discussed here are available.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 12 canonical work pages

[1]

How many numbers are computed classically before the circuit exists? If the answer is Θ(N), the entire input has already been read

work page
[2]

Were the gate counts taken after transpilation to a hardware basis? Abstract counts conceal multi- controlled gates completely

work page
[3]

Was the method benchmarked against the library implementation, or against nothing?

work page
[4]

Was it benchmarked against the classical algo- rithm, or against a weaker quantum one?

work page
[5]

Are state error, discretization error, and shot noise reported separately? They routinely differ by ten orders of magnitude, and typically only the smallest is quoted

work page
[6]

The input problem is permanent

If the speedup is stated in query complexity, what does the query cost? Applied to the literature, most papers address two of the six. The input problem is permanent. It is a counting ar- gument rather than a hardware limitation, and it will constrain quantum machine learning for as long as quan- tum machine learning is applied to classical data. This is ...

work page
[7]

Quantum Associative Memory

D. Ventura and T. Martinez,Initializing the amplitude distribution of a quantum state, arXiv:quant-ph/9807053 (1998)

work page Pith review arXiv 1998
[8]

M¨ ott¨ onen, J

M. M¨ ott¨ onen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa,Transformation of quantum states using uniformly controlled rotations, arXiv:quant-ph/0407010 (2004)

arXiv 2004

Show all 16 references

[9]

Grover and T

L. Grover and T. Rudolph,Creating superpositions that correspond to efficiently integrable probability distribu- tions, arXiv:quant-ph/0208112 (2002)

2002 arXiv
[10]

Brassard, P

G. Brassard, P. Høyer, M. Mosca, and A. Tapp,Quantum amplitude amplification and estimation, Contemp. Math. 305, 53 (2002); arXiv:quant-ph/0005055

2002 arXiv
[11]

Herbert,No quantum speedup with Grover–Rudolph state preparation for quantum Monte Carlo integration, Phys

S. Herbert,No quantum speedup with Grover–Rudolph state preparation for quantum Monte Carlo integration, Phys. Rev. E103, 063302 (2021)

2021
[12]

Aaronson,Read the fine print, Nat

S. Aaronson,Read the fine print, Nat. Phys.11, 291 (2015)

2015
[13]

Tang,A quantum-inspired classical algorithm for recommendation systems, inProc

E. Tang,A quantum-inspired classical algorithm for recommendation systems, inProc. 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), p. 217; arXiv:1807.04271

2019 arXiv
[14]

Plesch and ˇC

M. Plesch and ˇC. Brukner,Quantum-state preparation with universal gate decompositions, Phys. Rev. A83, 032302 (2011)

2011
[15]

V. V. Shende, S. S. Bullock, and I. L. Markov,Synthesis of quantum-logic circuits, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.25, 1000 (2006)

2006
[16]

Zoufal, A

C. Zoufal, A. Lucchi, and S. Woerner,Quantum genera- tive adversarial networks for learning and loading random distributions, npj Quantum Inf.5, 103 (2019)

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

How many numbers are computed classically before the circuit exists? If the answer is Θ(N), the entire input has already been read

work page

[2] [2]

Were the gate counts taken after transpilation to a hardware basis? Abstract counts conceal multi- controlled gates completely

work page

[3] [3]

Was the method benchmarked against the library implementation, or against nothing?

work page

[4] [4]

Was it benchmarked against the classical algo- rithm, or against a weaker quantum one?

work page

[5] [5]

Are state error, discretization error, and shot noise reported separately? They routinely differ by ten orders of magnitude, and typically only the smallest is quoted

work page

[6] [6]

The input problem is permanent

If the speedup is stated in query complexity, what does the query cost? Applied to the literature, most papers address two of the six. The input problem is permanent. It is a counting ar- gument rather than a hardware limitation, and it will constrain quantum machine learning for as long as quan- tum machine learning is applied to classical data. This is ...

work page

[7] [7]

Quantum Associative Memory

D. Ventura and T. Martinez,Initializing the amplitude distribution of a quantum state, arXiv:quant-ph/9807053 (1998)

work page Pith review arXiv 1998

[8] [8]

M¨ ott¨ onen, J

M. M¨ ott¨ onen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa,Transformation of quantum states using uniformly controlled rotations, arXiv:quant-ph/0407010 (2004)

arXiv 2004