The Input Problem: A Permanent Bottleneck for Quantum Machine Learning

• URL: http://arxiv.org/abs/2608.08433v1
• Date: Sun, 09 Aug 2026 03:04:03 GMT
• Title: The Input Problem: A Permanent Bottleneck for Quantum Machine Learning
• Abstract summary: Quantum algorithms are presented with their input state supplied for free.<n>We show 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.<n>We argue that the resulting $(N)$ bound is a counting theorem rather than an engineering limitation that improved hardware will remove.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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 $Θ(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 $Θ(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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Resource Implications of Different Encodings for Quantum Computational Fluid Dynamics [0.0]
  It is often proposed amplitude encoding w.r.t. multiple qubits for problems in which the task is to compute an entire field of values.<n>It is presented in particular that the insights from this work lead to a new encoding approach, which is proposed specifically for a quantum algorithm for the lattice Boltzmann method.
  arXiv  Detail & Related papers  (2026-04-07T08:17:21Z)
• Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates [3.0711566483997066]
  A common strategy is amplitude encoding, which embeds a classical input vector of size N=2textsuperscriptn in the amplitudes of an n-qubit register.<n>We propose a general-purpose procedure with sublinear average depth in N, increasing the window of utility.<n>Our amplitude encoding method encodes arbitrary complex vectors of size N=2textsuperscriptn at any desired binary precision using a register with n qubits plus 2 ancillas and a sublinear number of multi-controlled NOT (MCX) gates.
  arXiv  Detail & Related papers  (2025-05-09T13:49:16Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design [63.02824918725805]
  Quantum computing is recognized for the significant speedup it offers over classical computing through quantum algorithms.<n>QCircuitBench is the first benchmark dataset designed to evaluate AI's capability in designing and implementing quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-10T14:24:30Z)
• Quantum encoder for fixed Hamming-weight subspaces [0.0]
  We present an exact $n$-qubit computational-basis amplitude encoder of real- or complex data vectors of $d=binomnk$valued into a subspace of fixed Hamming weight $k$.<n>We show how our encoder can improve the performance of variational quantum algorithms for problems that include particle-string symmetries.<n>Our results constitute a versatile framework for quantum data compression with various potential applications in fields such as quantum chemistry, quantum machine learning, and constrained $k$ optimizations.
  arXiv  Detail & Related papers  (2024-05-30T18:26:41Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  A classical vector $mathbfb$ is encoded in the amplitudes of a quantum state. An arbitrary state of $Q$ qubits generally requires approximately $2Q$ entangling gates. We present a deterministic (nonvariational) algorithm that allows one to flexibly reduce the quantum resources required for state preparation.
  arXiv  Detail & Related papers  (2021-10-26T07:37:54Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.