A quantum kernel method encodes classical data into quantum states and computes inner products in the quantum Hilbert space. What potential advantage does this provide over classical kernel methods?
AQuantum kernels are always more expressive than classical kernels
BThe quantum feature space is exponentially large (2^n dimensions for n qubits), potentially capturing complex patterns inaccessible to polynomial-dimensional classical feature maps
CQuantum kernels can be computed in O(1) time regardless of data dimensionality
DQuantum kernels eliminate the need for training data
An n-qubit quantum circuit maps data into a 2^n-dimensional Hilbert space, which could in principle capture complex feature interactions that would require exponentially large classical feature maps. However, this potential advantage is not automatic: the quantum kernel must align with the structure of the actual learning problem, and there are classical kernels that can simulate many quantum kernels efficiently. The advantage depends on the specific data structure and encoding scheme.
Question 2 True / False
The barren plateau problem does not affect quantum machine learning models — it only applies to quantum chemistry algorithms like VQE.
TTrue
FFalse
Answer: False
Barren plateaus are a general problem for parameterized quantum circuits: for sufficiently random or deep circuits, the gradient of the cost function vanishes exponentially with the number of qubits. This affects QML models (quantum neural networks) at least as severely as VQE. In fact, QML models with global cost functions on many qubits are particularly susceptible. Barren plateaus are a fundamental obstacle to scaling variational QML approaches and are an active area of research.
Question 3 Short Answer
What is the 'data loading' or 'input problem' in quantum machine learning, and why does it threaten quantum speedup claims?
Think about your answer, then reveal below.
Model answer: Most quantum ML algorithms assume the classical data is already loaded into a quantum state (amplitude encoding: N classical values encoded as amplitudes of log(N) qubits). But actually loading N classical data points into a quantum state requires O(N) operations, which can negate the quantum speedup for the subsequent computation. If data loading takes as long as classical processing, the overall speedup disappears. This is the same state preparation bottleneck that limits the practical utility of the QFT for classical data.
The data loading problem has led to 'dequantization' results (Tang 2018 and follow-ups) showing that several quantum ML speedups — including the HHL-based quantum recommendation algorithm — can be matched classically if the classical algorithm is given the same data access model (sample-and-query access). This does not mean quantum ML is useless, but it forces the field to look for advantages in native quantum data (quantum sensing, quantum chemistry output) or in settings where data is naturally quantum.