Quantum Learning Challenges Reveal Limits of Computational Inference Methods

Researchers established a link between state designs and computational hardness, demonstrating information-computation gaps for learning quantum states from sparse Hamiltonians and random circuits with adaptive measurements. They also proved hardness for error mitigation and identified computational thresholds for learning stabiliser states and product states.

The efficient extraction of information from data represents a fundamental challenge across numerous scientific disciplines. Recent research indicates inherent limitations in this process, suggesting scenarios where computational efficiency fundamentally restricts our ability to learn even with abundant data – an ‘information-computation gap’. Sitan Chen, Weiyuan Gong, Jonas Haferkamp, and Yihui Quek investigate these limitations within the context of quantum systems, extending established classical techniques – specifically the ‘low-degree method’ – to analyse the hardness of learning complex quantum states. Their work, entitled ‘Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood’, establishes connections between state design and computational hardness, demonstrating these gaps for learning states arising from random quantum circuits, sparse Hamiltonians, and in the context of error mitigation and learning product states.

Limits to Quantum Inference Established Through Connection to Classical Hardness

Researchers have identified fundamental limitations in extracting information from quantum systems, linking these challenges to concepts from classical computational complexity. The work, conducted by Jonas Helsen, Christian Gogolin, and colleagues, establishes a direct relationship between the design of quantum states – probabilistic mixtures defining the system’s properties – and ‘low-degree hardness’, a well-established difficulty in classical statistical inference.

This connection allows for a rigorous analysis of computational bottlenecks in quantum inference – the process of determining the state of a quantum system through measurement. The team demonstrates the existence of an ‘information-computation gap’ for learning Gibbs states associated with sparse, non-local Hamiltonians. Hamiltonians describe the total energy of a quantum system and are crucial for understanding its behaviour; sparsity and non-locality refer to specific structural properties of the Hamiltonian that influence computational complexity. The findings indicate a substantial barrier to efficiently extracting information from these complex systems.

The research extends to demonstrating computational hardness for states generated by random shallow quantum circuits – sequences of quantum operations. Importantly, this holds true even within a model permitting adaptively chosen measurement bases. Adaptive measurement, where the choice of measurement depends on previous results, represents an improvement over previous classical approaches to establishing low-degree hardness, offering a more refined understanding of quantum information processing.

To facilitate their analysis, the researchers developed a generalization of the ‘planted biclique’ problem. This involves identifying a hidden, complete bipartite graph – a graph where nodes can be divided into two sets with connections only between different sets – within a larger, sparse graph. They pinpointed the threshold at which this problem becomes computationally intractable for protocols employing only local measurements – measurements that act on individual components of the system.

The study reveals a shift in computational complexity when moving beyond local measurements to strategies utilising more complex, ‘single-copy’ measurements – measurements that extract information from the entire system in a single operation. This highlights a crucial relationship between measurement strategies and computational difficulty.

Furthermore, the team extended their analysis to the field of quantum error mitigation. They demonstrated computational hardness for strategies relying on single-qubit measurements, indicating the inherent cost associated with correcting errors in quantum systems. Rigorous proof of average-case hardness was established for learning both noisy quantum stabilizer states – states with specific symmetry properties – and simple product states, solidifying the broader implications for quantum machine learning.

This work provides a theoretical framework for understanding the limits of quantum learning and offers a roadmap for developing more efficient and robust algorithms, with potential applications in areas such as materials discovery and cryptography.