Wave function network description and Kolmogorov complexity of quantum many-body systems
Tiago Mendes-Santos, Markus Schmitt, Adriano Angelone, Álex Rodríguez, Pascal Scholl, H. J. Williams, Daniel Barredo, Thierry Lahaye, Antoine Browaeys, Markus Heyl, Marcello Dalmonte
Programmable quantum devices are now able to probe wave functions at unprecedented levels. This is based on the ability to project the many-body state of atom and qubit arrays onto a measurement basis which produces snapshots of the system wave function. Extracting and processing information from such observations remains, however, an open quest. One often resorts to analyzing low-order correlation functions—that is, discarding most of the available information content. Here, we introduce wave-function networks—a mathematical framework to describe wave-function snapshots based on network theory. For many-body systems, these networks can become scale-free—a mathematical structure that has found tremendous success and applications in a broad set of fields, ranging from biology to epidemics to Internet science. We demonstrate the potential of applying these techniques to quantum science by introducing protocols to extract the Kolmogorov complexity corresponding to the output of a quantum simulator and implementing tools for fully scalable cross-platform certification based on similarity tests between networks. We demonstrate the emergence of scale-free networks analyzing experimental data obtained with a Rydberg quantum simulator manipulating up to 100 atoms. Our approach illustrates how, upon crossing a phase transition, the simulator complexity decreases while correlation length increases—a direct signature of buildup of universal behavior in data space. Comparing experiments with numerical simulations, we achieve cross-certification at the wave-function level up to timescales of 4 μs with a confidence level of 90% and determine experimental calibration intervals with unprecedented accuracy. Our framework is generically applicable to the output of quantum computers and simulators with in situ access to the system wave function and requires probing accuracy and repetition rates accessible to most currently available platforms.
Programmable quantum devices are now able to probe wave functions at unprecedented levels. This is based on the ability to project the many-body state of atom and qubit arrays onto a measurement basis which produces snapshots of the system wave function. Extracting and processing information from such observations remains, however, an open quest. One often resorts to analyzing low-order correlation functions—that is, discarding most of the available information content. Here, we introduce wave-function networks—a mathematical framework to describe wave-function snapshots based on network theory. For many-body systems, these networks can become scale-free—a mathematical structure that has found tremendous success and applications in a broad set of fields, ranging from biology to epidemics to Internet science. We demonstrate the potential of applying these techniques to quantum science by introducing protocols to extract the Kolmogorov complexity corresponding to the output of a quantum simulator and implementing tools for fully scalable cross-platform certification based on similarity tests between networks. We demonstrate the emergence of scale-free networks analyzing experimental data obtained with a Rydberg quantum simulator manipulating up to 100 atoms. Our approach illustrates how, upon crossing a phase transition, the simulator complexity decreases while correlation length increases—a direct signature of buildup of universal behavior in data space. Comparing experiments with numerical simulations, we achieve cross-certification at the wave-function level up to timescales of 4 μs with a confidence level of 90% and determine experimental calibration intervals with unprecedented accuracy. Our framework is generically applicable to the output of quantum computers and simulators with in situ access to the system wave function and requires probing accuracy and repetition rates accessible to most currently available platforms.
Programmable quantum devices are now able to probe wave functions at unprecedented levels. This is based on the ability to project the many-body state of atom and qubit arrays onto a measurement basis which produces snapshots of the system wave function. Extracting and processing information from such observations remains, however, an open quest. One often resorts to analyzing low-order correlation functions—that is, discarding most of the available information content. Here, we introduce wave-function networks—a mathematical framework to describe wave-function snapshots based on network theory. For many-body systems, these networks can become scale-free—a mathematical structure that has found tremendous success and applications in a broad set of fields, ranging from biology to epidemics to Internet science. We demonstrate the potential of applying these techniques to quantum science by introducing protocols to extract the Kolmogorov complexity corresponding to the output of a quantum simulator and implementing tools for fully scalable cross-platform certification based on similarity tests between networks. We demonstrate the emergence of scale-free networks analyzing experimental data obtained with a Rydberg quantum simulator manipulating up to 100 atoms. Our approach illustrates how, upon crossing a phase transition, the simulator complexity decreases while correlation length increases—a direct signature of buildup of universal behavior in data space. Comparing experiments with numerical simulations, we achieve cross-certification at the wave-function level up to timescales of 4 μs with a confidence level of 90% and determine experimental calibration intervals with unprecedented accuracy. Our framework is generically applicable to the output of quantum computers and simulators with access to the system wave function and requires probing accuracy and repetition rates accessible to most currently available platforms. Published by the American Physical Society 2024
Quantum computers and simulators offer unparalleled capabilities of probing quantum many-body states, by obtaining snapshots of the many-body wave function via collective projective measurements. The probability distribution obtained by such snapshots (which are fundamentally limited to a negligible fraction of the Hilbert space) is of fundamental importance to determine the power of quantum computations. However, its relation to many-body collective properties is poorly understood. Here, we develop a theoretical framework to link quantum phases of matter to their snapshots, based on a combination of data complexity and network theory analyses. The first step in our scheme consists of applying Occam's razor principle to quantum sampling: given snapshots of a wave function, we identify a minimal-complexity measurement basis by analyzing the information compressibility of snapshots over different measurement bases. The second step consists of analyzing arbitrary correlations using network theory, building a wave-function network from the minimal-complexity basis data. This approach allows us to stochastically classify the output of quantum computers and simulations, with no assumptions on the underlying dynamics, and in a fully interpretable manner. We apply this method to quantum states of matter in one-dimensional translational invariant systems, where such classification is exhaustive, and where it reveals an interesting interplay between algorithmic and computational complexity for many-body states. Our framework is of immediate experimental relevance, and can be further extended both in terms of more advanced network mathematics, including discrete homology, as well as in terms of applications to physical phenomena, such as time-dependent dynamics and gauge theories.
Recent advances in quantum simulator experiments enable unprecedented access to quantum many-body states through snapshot measurements of individual many-body configurations. Here, we introduce an exact renormalization group (RG) transformation that can be directly applied to any such snapshot dataset. Our SnapshotRG operates in real space, but can also be directly translated to an RG in the abstract dataspace of measurement configurations, providing a framework for the characterization of quantum many-body systems on a more general level. We demonstrate that snapshot datasets in dataspace exhibit self-similarity at continuous phase transitions, providing an explanation for the recently observed scale-freeness of so-called wavefunction networks. As a consequence, scale invariance extends beyond traditional low-order correlation functions to encompass the full statistical structure of quantum states as contained in their snapshot datasets. Our SnapshotRG can be readily implemented with snapshot data generated by numerical method such as neural quantum states or any quantum simulation platform, offering a versatile tool for characterizing quantum phase transitions and critical phenomena in quantum matter.
We review methods that allow one to detect and characterize quantum correlations in many-body systems, with a special focus on approaches which are scalable. Namely, those applicable to systems with many degrees of freedom, without requiring a number of measurements or computational resources to analyze the data that scale exponentially with the system size. We begin with introducing the concepts of quantum entanglement, Einstein-Podolsky-Rosen steering, and Bell nonlocality in the bipartite scenario, to then present their multipartite generalization. We review recent progress on characterizing these quantum correlations from partial information on the system state, such as through data-driven methods or witnesses based on low-order moments of collective observables. We then review state-of-the-art experiments that demonstrate the preparation, manipulation and detection of highly-entangled many-body systems. For each platform (e.g. atoms, ions, photons, superconducting circuits) we illustrate the available toolbox for state preparation and measurement, emphasizing the challenges that each system poses. To conclude, we present a list of timely open problems in the field.
Simulating quantum many-body systems is essential for understanding complex phenomena in condensed matter, chemistry, and materials science. Quantum computing offers a way to overcome the limitations of classical methods by operating directly in exponentially large Hilbert spaces. In particular, classical methods often fail to capture the dynamics of strongly correlated systems, which makes quantum algorithms a promising alternative for exploring these challenging regimes. This thesis uses quantum dynamics simulations to probe the behaviour of many-body systems. We first introduce a spectroscopy-based protocol to extract excitation spectra from the time evolution of observables and analyse its performance on near-term quantum devices. We show that the protocol requires only short evolution times and is resilient to errors, facilitating its implementation on real hardware. Building on this, we simulate fermionic excitation spectra using current quantum devices, introducing resource optimisations - including an approximate free-fermion initial state, a unitary quench without ancillae, and reduced Trotter steps - that significantly lower circuit depth. These improvements enable simulations at system sizes competitive with the state of the art, yielding results that match classical benchmarks. While most studies focus on unitary dynamics of isolated systems, open quantum dynamics is increasingly relevant for describing non-equilibrium processes across biology, materials science, and quantum control. We extend our scope to systems coupled to an environment and governed by Lindbladian evolution. By studying simulation complexity through physically meaningful quantities - such as correlation length and mixing time - we explore whether open-system dynamics can be as tractable as their unitary counterparts. These findings provide insights into the computational complexity landscape of open-system simulation and highlight regimes where quantum methods offer a clear advantage.
Analog quantum simulators natively return large collections of single-shot projective measurements, the wave-function snapshots. These are high-dimensional configurations drawn from the Born distribution of the state they prepare. These collections carry far more information than is retained when they are simply compressed into low-order observables fixed in advance. Moreover, this procedure requires knowing beforehand what one is looking for. This thesis chooses to take a different route, asking what structure a dataset of snapshots possesses as a set of points in configuration space, and what kind of physics that structure reflects. The tools used here are drawn from un supervised learning and network theory, namely principal component analysis (PCA), intrinsic-dimension estimators (TWO-NN and BID), and the wave-function networks obtained by promoting snapshots to nodes and activating links according to the met ric structure of configuration space. They are chosen under two constraints, namely interpretability at every step, and the smallest possible amount of physical input: no order parameter, no symmetry, and no knowledge of the Hamiltonian. At equilibrium, wave-function networks are used to build a classification of one dimensional quantum phases based on snapshots alone. The scheme first selects, in the spirit of Occam’s razor, the measurement basis carrying the minimal information content, and then analyses the networks constructed in that basis. Paramagnetic and symmetry-broken phases display low complexity and “probability” networks, symmetry protected topological phases high complexity and Erdős–Rényi networks, and critical points high complexity and scale-free networks. Interestingly, gapped and gapless mat ter are treated on the same footing, and real-space decimation enters the scheme to resolve massive phases rather than flowing towards criticality. Out of equilibrium, the dynamical exponent governing transport of a conserved quan tity is shown to be imprinted on the singular-value spectrum of the snapshot matrix. In particular, it is shown that the PCA entropy, and in fact the leading eigenvalue alone, grows with the same exponent as the underlying spin or energy transport, at modest system sizes, evolution times and sample numbers. Ergodicity breaking is then ad dressed through the binary intrinsic dimension (BID) of the snapshots, in the quantum sun model: the BID grows and saturates at the Thouless time, reaching its maximum in the ergodic phase, remaining system-size independent in the non-ergodic one, and growing sub-maximally at criticality, where the data occupy an extensive but lower dimensional manifold. The associated networks reproduce the equilibrium dichotomy, being random in the ergodic phase and scale-free at the transition, whose location can be identified by the BID within a few percent of spectral estimates. Preliminary experimental observations, not reported here, show analogous features. Taken together, these results indicate that datasets orders of magnitude smaller than the Hilbert-space dimension suffice to identify collective properties of quantum matter through the study of the structure of the data points in configuration space. Moreover, the same structural classes recur across ground states and quenched dynamics, with no order parameter supplied and under realistic experimental imperfections. The final chapter elaborates on another aspect of quantum simulator capabilities, that is, that to realize gauge theory dynamics. There, one-dimensional U(1) lattice gauge theories with a topological θ term are mapped exactly onto kinetically con strained fermions in an emergent Stark potential. The mapping accounts for the slow relaxation reported in recent Rydberg experiments: prethermalization near an inte grable point at θ = 0, and Stark localization with Hilbert-space fragmentation at θ ̸ =0.