The Input Problem: A Permanent Bottleneck for Quantum Machine Learning

Quantum algorithms are frequently analyzed under the assumption that the input state is provided for free. This paper argues that for classical data, the cost of preparing the corresponding quantum state is not merely an engineering hurdle but a fundamental complexity-theoretic constraint. Regardless of hardware improvements, loading arbitrary classical data into a quantum state requires a gate count that scales with the size of the input, effectively nullifying the theoretical speedups promised by many quantum machine learning (QML) and quantum estimation algorithms.

The paper examines three standard encoding methods: basis encoding, amplitude encoding, and Grover-Rudolph distribution loading. It demonstrates that these methods incur a cost of at least Theta(N) gates, where N is the number of data points. Crucially, this cost is not just in the quantum circuit; it includes significant classical preprocessing—such as calculating rotation angles—that requires reading the entire input vector. The author shows that for quantum amplitude estimation, this preparation cost scales in a way that eliminates the quadratic advantage over classical Monte Carlo methods, bringing the total cost back to classical levels.

The author contends that the 'input problem' is a primary reason why many QML speedup claims fail to materialize in practice. The strong input models often assumed in QML—such as the ability to access data in superposition—are not only physically unrealized but also enable classical 'dequantization' algorithms that achieve similar performance. By failing to account for the cost of state preparation, researchers often overlook that the input stage dominates the entire runtime of the algorithm.

To address this, the paper provides a checklist for researchers to evaluate their own advantage claims. It emphasizes that a working quantum circuit does not equate to a useful one if the input preparation cost is ignored. The author concludes that while quantum advantage remains possible for specific tasks—such as those involving device-generated data or learned loading—the field must move toward more rigorous accounting of input-dependent costs to distinguish between genuine breakthroughs and illusory speedups.