Predictive supremacy of informationally-restricted quantum perceptron

1. Problem Statement

The paper addresses a fundamental gap in the comparison between classical and quantum machine learning. While many quantum algorithms demonstrate speedups in training or sample complexity (e.g., quadratic improvements for linearly separable data), there is no universal proof that a quantum neural network can learn any function faster than a classical one. Furthermore, previous demonstrations of quantum advantage often rely on functions that classical perceptrons cannot implement at all (e.g., XOR), which reflects a difference in representational capacity rather than a genuine advantage in learning or prediction efficiency.

The authors pose the following question: If a classical and a quantum perceptron are restricted to the same information resources, learn the same function, and undergo the same training procedure, can the quantum perceptron achieve higher predictive accuracy?

2. Methodology: The Informationally-Restricted Measurement-Based Perceptron (IMP)

To answer this, the authors introduce a specific model called the Informationally-Restricted Measurement-Based Perceptron (IMP). This model is designed to enforce strict resource limitations to isolate the source of any quantum advantage.

• Input Structure: Each input node ($i=1, 2$) holds two classical bits, denoted as $x_{i,0}$ and $x_{i,1}$.
• The Node and Query: A query variable $s \in \{0, 1\}$ is provided to the node after the inputs have been transmitted. Based on $s$, the perceptron must decide which bit to evaluate (either the 0-th or 1-th bit of each input).
• Informational Restriction: The channel connecting the inputs to the node is restricted to transmitting only one bit (classical) or one qubit (quantum) per input. This means the system cannot transmit both $x_{i,0}$ and $x_{i,1}$ simultaneously; it must encode them into a single low-dimensional state.
• Operation:
  • Classical IMP: Inputs send a single bit based on a strategy. The node measures this bit to produce an output $y_{i,s}$.
  • Quantum IMP (Q-IMP): Inputs encode the two bits into a quantum state $\rho_{x_{i,0}x_{i,1}}$. The node performs a measurement $\{M^s_{y}\}$ dependent on $s$ to extract the output.
• Prediction Witness ($p_{cor}$): The performance metric is the probability that the perceptron correctly predicts the function output $z_s = f(y_{1,s}, y_{2,s})$ given the hidden inputs. The goal is to maximize this probability ($\beta_C$ for classical, $\beta_Q$ for quantum).

3. Key Contributions

1. Provable Predictive Supremacy: The paper establishes the first rigorous proof that a quantum perceptron can strictly outperform a classical perceptron in predictive accuracy, even when both implement the exact same hypothesis and face identical information-theoretic constraints.
2. Universality of Advantage: The authors demonstrate that this advantage is universal for all non-trivial Boolean functions implementable by a classical perceptron (excluding XOR/XNOR which are not linearly separable). This includes single-variable functions, AND/OR types, and asymmetric functions.
3. Model Uniformity: The quantum advantage is achieved using a single set of quantum states and measurements (up to basis rotations) for all function types. This suggests the advantage is intrinsic to the quantum encoding strategy rather than being tailored to specific functions.
4. Bridging Theories: The work links Quantum Information Theory (specifically accessible information and optimal state discrimination) with Statistical Learning Theory (generalization error), showing that quantum learners extract more predictive information per bit of data access.

4. Key Results

The authors analyze specific cases to quantify the gap between classical ($\beta_C$) and quantum ($\beta_Q$) performance:

• Single-Variable Functions:

  • Scenario: The function depends only on one input bit (e.g., $f(y_1, y_2) = y_1$).
  • Classical Limit: The best classical strategy involves sending one bit perfectly and guessing the other randomly.
    • $\beta_C = 3/4 = 0.75$ (75% accuracy).
  • Quantum Strategy: Using specific qubit states (rotated by Pauli operators) and measurements in the $Z$ and $X$ bases.
    • $\beta_Q = \frac{1}{2}(1 + \frac{1}{\sqrt{2}}) \approx 0.853$ (85.3% accuracy).
  • Result: A significant ~10% improvement in prediction accuracy.

• And-Type Functions:

  • Scenario: The function is an AND gate ($f = y_1 \cdot y_2$).
  • Classical Limit: $\beta_C = 13/40 = 0.325$.
  • Quantum Strategy: Using the same state encoding and measurements adapted for the AND logic.
    • $\beta_Q = \frac{1}{40}(11 + 2\sqrt{2}) \approx 0.341$.
  • Result: While the absolute numbers are lower due to the complexity of the function, the quantum strategy still strictly exceeds the classical bound.

• Universality:

  • The paper proves in Appendix B that for all 14 linearly separable Boolean functions (excluding constant functions which are trivial), the quantum IMP achieves a higher prediction witness than the classical IMP.
  • The same quantum states (Eq. 6) and measurement sets (Eq. 7/11) are sufficient to demonstrate this advantage across all function classes.

5. Significance and Implications

• Beyond Representational Power: Unlike previous works where quantum advantage came from solving problems classical computers cannot solve (like XOR), this work shows an advantage in problems classical computers can solve, but do so less efficiently under information constraints.
• Fundamental Separation: The separation is information-theoretic, not just computational complexity-based. It implies that quantum systems can store and retrieve more "predictive information" from a limited channel than classical systems.
• Scalability: The authors suggest that while the advantage is observed in a single perceptron, the gap is expected to scale and widen in deeper neural networks, potentially offering a path to more efficient quantum machine learning architectures.
• Resource Efficiency: The findings suggest that in scenarios where communication bandwidth or energy (information) is restricted, quantum perceptrons offer a superior predictive capability, which is crucial for future edge AI and low-power computing.

In conclusion, the paper provides a rigorous theoretical framework demonstrating that quantum perceptrons possess an inherent predictive supremacy over classical counterparts when constrained by identical information resources, marking a shift from "quantum speedup" to "quantum predictive superiority."