Five Jupyter Notebooks showing classical data encoding is the permanent bottleneck of Quantum ML

Every quantum algorithm that claims to beat a classical one on classical data has to answer a question before it can start: how does the data get in?

Most courses skip it. They write |ψ (x)⟩ and move on to the interesting part. That convention is harmless when the input is a small integer or a black-box oracle, and it becomes actively misleading the moment the input is a length-N vector of real numbers from an actual dataset — because then the cost of producing |ψ (x)⟩ is a cost of the algorithm, and it is frequently the dominant one.

These five notebooks build the three standard encodings from scratch, verify each against a closed-form answer, and then do the thing that is usually left out: transpile everything to a hardware gate set, count, and put the numbers in the same table as the speedup claim. In one important case — quantum Monte Carlo integration by way of Grover-Rudolph state preparation — the subtraction removes the speedup entirely.

I wrote the first versions of these two years ago while preparing a course, and then never taught them. Something about them bothered me and I could not name it. Working out what it was, and fixing the bugs I found in the process, became this bundle.

Lab 01 — Basis encoding. Fixed-point decimal-to-binary conversion with a sign bit, single-datum encoding, and the Ventura-Martinez routine that loads M patterns into an equal superposition using a two-qubit ancilla. The construction turns on a telescoping angle θi = 2 arcsin(1/√(M−i)) chosen so that the amplitude peeled off at each step stays constant at 1/√M. Ends with a counting argument for why loading M arbitrary patterns costs Ω(M) depth, which is the first place a speedup can quietly die.

Lab 02 — Amplitude encoding. The binary tree of uniformly controlled Ry rotations that sets the magnitudes, then the controlled-phase cascade that sets the arguments, so that arbitrary complex vectors can be loaded. Includes a derivation of the phase angles φi,j = wj+2i − wj and — more usefully — a demonstration of the bug that appears when you forget that the base case W(0) = 0 is forced. Both versions run side by side: on a test vector with a real first component they agree to 5×10−16, and on random complex input the unshifted one is wrong by up to 0.92. That bug was in my own code for two years and passed every test I gave it.

Lab 03 — Grover-Rudolph distribution loading. Preparing Σk √pk |k⟩ by bisection, verified bin by bin against the exact integral of (π/2)·sin(πx) to 5×10−17. This lab is careful about a distinction the literature is often not: the version built here computes its 2n − 1 rotation angles classically and is therefore exponential, while the paper's efficiency claim depends on computing them inside the circuit with reversible arithmetic on the CDF. Both things get called "Grover-Rudolph."

Lab 04 — Gaussian and general densities. Generalising the loader to any density on any interval, which brings in two new error sources: truncating infinite support, and numerical quadrature where no closed-form CDF exists. Then the case that motivates the whole field — a lognormal terminal price distribution, loaded, used to price a European call, and compared against Black-Scholes. The state is exact to 10−16 and the price is off by 0.5%. Working out whose fault that is turns out to be the most useful half hour in the bundle.

Lab 05 — The honest benchmark. Everything transpiled to {cx, rz, sx, x} and counted. The hand-built loader against Qiskit's StatePreparation: 82× worse at n = 8. Then the column that belongs to neither circuit — the 2n − 1 angles computed in Python before a single gate exists. Then the consequence: quantum amplitude estimation needs O(1/ε) queries to a state-preparation oracle that itself costs Θ(1/ε), giving O(1/ε2) total, which is what classical Monte Carlo already costs. Ends with a six-point checklist for evaluating input-dependent advantage claims.

Three reasons, in increasing order of importance.

They run, and they check themselves. Every notebook was executed end to end to produce the outputs you see, and every result is compared against a closed-form answer with an assertion that fails loudly if it drifts. There is no cell whose output you have to take on trust. If you have ever inherited a teaching notebook with stale outputs from a run that no longer matches the code above it, you know why this matters.

They contain the failure modes, not just the constructions. The phase-encoding bug in Lab 02 is the kind of thing that passes review, passes your own testing, and then produces silently wrong results for someone else. It is in the bundle deliberately, running, so you can watch it fail. So is a non-idempotent cell that mutated its own input, and a fixed-point converter that used to truncate on overflow without saying so. A verification cell that only ever runs one hard-coded input is not a verification cell, and the fastest way to learn that is to see it happen.

They price the thing everyone assumes is free. This is the actual argument. Correctness told us nothing about usefulness in any of these labs — every circuit was right to machine precision, and the interesting question was always what it cost. The control experiment is what turned five working notebooks into a defensible claim, and it is the habit I would most like people to take away: transpile the alternative, count the same quantities, put them in one table, and do it before you write the abstract rather than after a referee asks.

D. Ventura and T. Martinez, arXiv:quant-ph/9807053 — the two-ancilla routine for loading a set of patterns into equal superposition

M. Möttönen, J. J. Vartiainen, V. Bergholm and M. M. Salomaa, Transformation of quantum states using uniformly controlled rotations, arXiv:quant-ph/0407010 — the uniformly controlled rotation tree. The notebook builds an ancilla-based decomposition for legibility; the paper's Gray-code construction is the one StatePreparation implements, and Lab 05 measures the gap

L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, arXiv:quant-ph/0208112 — the bisection recursion. The notebooks implement the classical-angle version and are explicit that this is not the efficient one

G. Brassard, P. Høyer, M. Mosca and A. Tapp, Quantum amplitude amplification and estimation, arXiv:quant-ph/0005055 — the O(1/ε) query bound whose oracle cost the lab prices

S. Herbert, No quantum speedup with Grover-Rudolph state preparation for quantum Monte Carlo integration, Phys. Rev. E 103, 063302 (2021) — the argument that the oracle cost closes the quadratic gap