Case Study 2: The Exponential Compression That Cost a Linear Bill

The proposal

A team has a genuinely large classification problem: high-dimensional feature vectors, hundreds of thousands of samples, and a classical pipeline that is slow enough to be a bottleneck.

Someone points out that amplitude encoding stores $N$ features in $\log_2 N$ qubits.

The arithmetic is striking:

   1,024 features  ->  10 qubits
   1,048,576       ->  20 qubits

A million-dimensional feature vector in twenty qubits. Their whole dataset, in a register smaller than a current device. Written up as an exponential reduction in memory, which it is, the proposal is approved for a feasibility study.

What loading costs

Measured, with Qiskit's StatePreparation:

    N features   qubits   prep 2q gates   transpiled ecr
             4        2               1                1
             8        3               4                5
            16        4              11               19
            32        5              26               41
            64        6              57              100
           128        7             120              227

The logical gate counts are not approximately linear — they are exactly

$$\text{two-qubit gates} = N - \log_2 N - 1$$

which reproduces every row: 1, 4, 11, 26, 57, 120.

The qubit count is logarithmic and the gate count is linear. A million-dimensional vector needs 20 qubits and about one million two-qubit gates to load.

At Chapter 12's measured error rate of 0.0075, the 227-gate case already survives with probability 0.18. A million gates survive with probability $(1-0.0075)^{10^6}$, which is zero to any precision worth writing.

⚛️ Amplitude encoding compresses the register, not the work.

An arbitrary $N$-dimensional state vector has $N$ independent real parameters. Preparing it means specifying all of them, and no circuit can do that in fewer than $\mathcal{O}(N)$ gates — the information has to get in somehow.

The $\log_2 N$ is a statement about storage. The $\mathcal{O}(N)$ is a statement about loading. They are both true, and quoting the first without the second is the single most common error in QML exposition.

The exponential saving is real, and it is a saving in qubits, which were not the team's constraint. Their constraint was time, and loading costs exactly as much time as reading the data classically.

And it is per sample

The proposal's second assumption was that the dataset gets loaded once.

   iris       150 samples x  4 features  ->  60 steps  ->    9,000 state preparations
   digits    1797 samples x 64 features  ->  60 steps  ->  107,820 state preparations

Encoding happens once per sample, per forward pass, per optimizer step.

There is no "loading the dataset." Each training example must be prepared afresh every time the model sees it, because measurement destroys the state and the next sample needs different amplitudes. A hundred thousand samples at sixty steps is six million state preparations, each costing $\mathcal{O}(N)$ gates.

The exponential compression compresses one vector. Training uses all of them, repeatedly.

That is not a constant factor on the quantum advantage. It is the dominant term, and it is the same order as the classical cost of reading the data.

The escape that does not exist

The standard answer is QRAM: a hypothetical device that loads a classical vector into superposition in $\mathcal{O}(\log N)$ time. If it existed, this case study would not.

It does not exist. There is no credible proposal for building one at scale, and several analyses argue that a QRAM robust enough to be useful would itself require error correction — at which point Chapter 25's overhead applies to the loading step and dominates again.

A proposal that depends on QRAM is a proposal that depends on an unbuilt device. That is allowed — Chapter 23's Shor depends on fault tolerance, and says so — but it must be stated, because it moves the timeline from "current hardware" to "after a major unsolved engineering problem."

What the feasibility study should have computed

Three lines, before any code:

   1. LOADING COST PER SAMPLE.  N - log2(N) - 1 two-qubit gates. For their
      data: ~1e6 gates. Survival at Chapter 12's error rate: zero.

   2. LOADING COST PER TRAINING RUN.  samples x steps state preparations.
      For their data: ~6e6 preparations x 1e6 gates each.

   3. WHAT THE CONSTRAINT ACTUALLY IS.  They were short of TIME, not
      QUBITS. Amplitude encoding saves qubits.

Step 3 is the one that kills it fastest, and it requires no quantum knowledge at all. The optimization was aimed at a resource that was not scarce.

The project module makes step 1 unavoidable:

@dataclass
class EncodingCost:
    """Qubits AND gates. Never one without the other."""
    scheme: str
    n_features: int
    qubits: int
    two_qubit_gates: int

There is no way to ask for only the flattering half. encoding_cost("amplitude", 128).summary() returns both numbers and the survival probability in one string.

When amplitude encoding is right

The honest positive case, because there is one.

When the data is already quantum. If your input is a state produced by a physical process, or the output of another quantum computation — a molecular ground state from Chapter 24, say — there is no loading step at all. The input problem simply does not arise, and the exponential register saving is pure gain. This is the strongest surviving case for QML, and Chapter 35 returns to it.

When $N$ is small and qubits are the binding constraint. Sixteen features in four qubits for eleven gates is a perfectly reasonable trade if you are trying to fit a model onto a small device.

And when the loading cost is amortized across many measurements of the same state. Preparing once and measuring many observables changes the arithmetic — though Chapter 24 §24.3's shot budget then becomes the binding term instead.

The lessons

Quote both halves. $\log_2 N$ qubits and $N - \log_2 N - 1$ gates. Either alone is misleading, and the second is the one that gets omitted.

Ask which resource is actually scarce. An exponential saving in a resource you have plenty of is not a saving.

Check whether the cost is per-run or per-sample. Encoding is per sample, per step, and that multiplier is larger than anything else in the calculation.

Name your dependency on unbuilt hardware. QRAM would change everything and does not exist. Chapter 23 depends on fault tolerance and says so on every page; the same standard applies here.

And notice the pattern from Chapter 30. A quoted number is a statistic with choices behind it, and the flattering choice is the one that gets published. There it was median-versus-mean; here it is qubits-versus-gates. The defence is the same: compute both, and report the one that answers the question.

Reproduce it: code/example-01-the-input-problem.py measures the encoding costs and the per-sample multiplier; EncodingCost in code/vqelab/qml.py carries qubits and gates together, and test_the_gate_count_matches_the_measured_formula_exactly asserts $N - \log_2 N - 1$ against every measured row.