Locality constrains the flow of information between different parts of many-body quantum systems. In quantum computers, this affects the ability to perform arbitrary interactions for quantum information processing tasks. A crucial challenge for scalable quantum architectures is thus to minimize the overheads due to locality constraints. Locality constraints also affect the way information and entanglement can be spread in many body quantum systems, and our ability to make predictions about such systems. One way to implement arbitrary interactions in locality-constrained architectures is by permuting qubits, also known as performing quantum routing. In the first part of this thesis, we investigate quantum routing strategies using emerging architectural capabilities beyond swap gates. We first investigate the use of mid-circuit measurements and classical feedback, which enable quantum teleportation. We prove upper bounds on the speedup afforded by the use of quantum teleportation for routing. We also design architectural connectivities which can exploit teleportation-based speedups. We then consider quantum routing by continuous-time Hamiltonian evolution, designing a routing algorithm that achieves a polynomial speedup in routing time over gate-based routing methods in architectures with a bottleneck, which is an intermediate region that constrains interactions between the rest of the device. We improve the lower bound on the time taken for routing in such systems, and develop a matching upper bound on the closely related task of generating and distributing entanglement. In the second part of this thesis, we investigate the behavior of finite-sized systems evolving by local Hamiltonians for a long duration. A major direction of research in condensed matter physics is the investigation of whether isolated systems thermalize (i.e., reach a state of thermal equilibrium). Various theoretical proposals such as information scrambling, entanglement between subsystems, and the eigenstate thermalization hypothesis have attempted to explain the conditions under which systems equilibrate. At the same time, notable counter-examples to thermalization have been found, such as systems that are integrable, exhibit many-body localization, or quantum many-body scars. We approach this question from a complexity-theoretic perspective. We show that the problem of deciding whether or not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum computer. Our results indicate that the proposed conditions leading to thermalization are either difficult to decide, or are not generic indicators of thermalization.
Locality constrains the flow of information between different parts of many-body quantum systems. In quantum computers, this affects the ability to perform arbitrary interactions for quantum information processing tasks. A crucial challenge for scalable quantum architectures is thus to minimize the overheads due to locality constraints. Locality constraints also affect the way information and entanglement can be spread in many body quantum systems, and our ability to make predictions about such systems. One way to implement arbitrary interactions in locality-constrained architectures is by permuting qubits, also known as performing quantum routing. In the first part of this thesis, we investigate quantum routing strategies using emerging architectural capabilities beyond swap gates. We first investigate the use of mid-circuit measurements and classical feedback, which enable quantum teleportation. We prove upper bounds on the speedup afforded by the use of quantum teleportation for routing. We also design architectural connectivities which can exploit teleportation-based speedups. We then consider quantum routing by continuous-time Hamiltonian evolution, designing a routing algorithm that achieves a polynomial speedup in routing time over gate-based routing methods in architectures with a bottleneck, which is an intermediate region that constrains interactions between the rest of the device. We improve the lower bound on the time taken for routing in such systems, and develop a matching upper bound on the closely related task of generating and distributing entanglement. In the second part of this thesis, we investigate the behavior of finite-sized systems evolving by local Hamiltonians for a long duration. A major direction of research in condensed matter physics is the investigation of whether isolated systems thermalize (i.e., reach a state of thermal equilibrium). Various theoretical proposals such as information scrambling, entanglement between subsystems, and the eigenstate thermalization hypothesis have attempted to explain the conditions under which systems equilibrate. At the same time, notable counter-examples to thermalization have been found, such as systems that are integrable, exhibit many-body localization, or quantum many-body scars. We approach this question from a complexity-theoretic perspective. We show that the problem of deciding whether or not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum computer. Our results indicate that the proposed conditions leading to thermalization are either difficult to decide, or are not generic indicators of thermalization.
Quantum many-body systems exhibit highly complex interactions that give rise to emergent collective phenomena beyond the behavior of individual particles. One of the most intriguing challenges in modern quantum physics is understanding how isolated quantum systems evolve toward thermal equilibrium despite following fundamentally reversible quantum dynamics. Quantum entanglement has emerged as a central mechanism governing information propagation, thermalization, and the development of statistical equilibrium in isolated many-body systems. Simultaneously, recent advances in quantum information science have enabled researchers to investigate the relationship between entanglement dynamics, information scrambling, and emergent quantum behavior using computational and analytical approaches. This study proposes a Quantum Information Analytics Framework for investigating thermalization processes in isolated many-body quantum systems through the integration of entanglement dynamics, quantum information measures, statistical mechanics, and computational modeling. The proposed framework evaluates system evolution using multiple performance indicators, including entanglement entropy, information propagation, thermal equilibrium, quantum coherence, and computational stability. The findings indicate that quantum entanglement plays a fundamental role in driving thermalization while preserving the underlying unitary evolution of isolated quantum systems. The proposed analytical framework contributes to a deeper understanding of emergent quantum dynamics and provides valuable insights for quantum computing, quantum simulation, condensed matter physics, and next-generation quantum information technologies.
This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable X into a sum of n iid random variables Yi, i.e. X=∑i=1nYi, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
Over the past twenty years, experimental and technological progresses have motivated a renewed attention to the study of non-equilibrium isolated many-body systems, leading to a relatively well-established paradigm in the case of local Hamiltonians. In the present thesis, I have used quantum information theoretical tools to study out-of-equilibrium dynamics, with particular attention on long-range interacting many-body systems. I have explored the dynamics of bipartite and multipartite entanglement in connection to chaos and scrambling in various long-range (clean and disordered) models. The results contained in this thesis contribute to establishing semi-classical tools as powerful techniques for the description of the quantum information spreading in long-range systems. I have further considered a different, yet connected question, concerning the multipartite entanglement structure of chaotic eigenstates and its generic evolution.
The quantum circuit complexity of an evolving many-body quantum system is believed to exhibit a sustained growth, maintained for timescales much longer than the onset of thermalization. Most previous works have focused on models which violate energy conservation, such as random unitary circuits. Here we study generic, local time-independent Hamiltonian dynamics. We unconditionally prove that for generic local Hamiltonians and typical initial product states at high effective temperature, the robust quantum circuit complexity must grow over a very long period of time, attaining an exponentially large value at late times. Our approach relies on two structural properties that we prove rigorously: (i) generic local Hamiltonians satisfy generalized spectral no-resonance conditions of arbitrary order, and (ii) typical high-temperature product states are effectively supported in exponentially many energy eigenstates. These properties have been widely assumed without proof in prior works. As corollaries of this result, we show the late-time state displays robust volume-law entanglement that is irremovable by polynomial-size circuits, and we establish a no fast-forwarding result for generic local Hamiltonians. We also lower bound the complexity of preparing sufficiently large subsystems with local quantum channels, in contrast with sufficiently small thermalizing regions which we show retain low complexity at late times.
The study of quantum many-body systems is crucial to our understanding of nature at the microscopic scale. As analytical solutions quickly become intractable, the development of efficient computational simulation techniques is indispensable to predict the behaviour of quantum systems. This task is particularly challenging as the dimension of the underlying Hilbert space grows exponentially with the system size. While classical computational methods have achieved remarkable success in specific regimes, their applicability is fundamentally limited by this exponential scaling. Quantum computers offer a natural platform for representing and simulating quantum systems, but current devices are constrained by noise and limited qubit counts, drastically restricting the algorithms that can be run. In this context, hybrid quantum-classical algorithms provide a promising approach to combine the strengths of both paradigms. This thesis develops hybrid quantum-classical algorithms for the simulation of quantum many-body systems. The key idea is to perform classically difficult tasks on near-term quantum devices, while leveraging classical computational power to control, correct, and extend the obtained results. Within this framework, we introduce two complementary approaches for the simulation of quantum dynamics. The first method employs circuit knitting techniques to distribute variational quantum simulations across multiple quantum devices. The entanglement between weakly coupled clusters of highly correlated spins is recovered in classical post-processing, where the overhead is controlled through a constrained optimisation problem. The second method combines a simplified, Trotterised quantum dynamics simulation with a parametrised classical ansatz trained to correct for the approximations made on the quantum device. We show that this method can be employed to correct Trotter errors, implement long-range gates with hardware-efficient circuits, or simulate larger systems by incorporating additional degrees of freedom purely classically. In addition, we present a hybrid approach to computing thermal properties of quantum many-body systems via the Quantum Finite Temperature Lanczos Method. A Krylov subspace is generated on a quantum computer by combining the efficient preparation of typical states with real-time evolution. A classical computer then diagonalises the system in the low-dimensional subspace and estimates the finite-temperature expectation values through trace estimation. The results presented in this thesis demonstrate that hybrid quantum-classical algorithms can expand the range of systems that can be studied on near-term quantum devices. Conversely, we show that incorporating quantum subroutines into classical simulation techniques can improve their efficiency. These results suggest that, rather than treating classical and quantum simulation as competing paradigms, their careful integration can provide a more effective route toward practical quantum many-body simulation.
The determination of structures that can emerge out of the interactions among the constituents of a quantum many-body system is a foundational task of condensed matter physics.One of the most advanced proposals within this paradigm is the holographic generation of spacetime in some strongly coupled chaotic systems with particular patterns of entanglement and quantum complexity, which is historically motivated by the holographic principle and by the AdS/CFT correspondence.As a part of this scenario, this thesis is dedicated to the analysis of some concepts that are relevant to such proposal, where they are separately applied to some lattice models.Concretely, the matter is divided into three main studies: first, the calculation of the time-dependent circuit complexity in the Ising model with a periodically driven transverse field, where we establish the effectiveness of this quantity for the detection of nonequilibrium quantum phase transitions.Our results provide hints for understanding how universal features out of equilibrium are captured by the complexity of quantum states.Second, the derivation of a bound on the maximal rate of entanglement entropy production for a class of one-dimensional quantum circuits with periodic dynamics.An example of a circuit that saturates the bound is composed by parallel SWAP gates acting on entangled pairs.Out of inequalities obeyed by the entropy, in addition to considerations on multipartite entanglement, we indicate that the effect of a chaotic dynamics cannot result in the increase on the rate of entanglement production.Third, the construction of a class of supersymmetric many-body systems using symmetric inverse semigroups.For particular toy models built out of this structure, we study some questions regarding supersymmetric phases, integrability, disorder, spreading of quantum information and many-body localization.Finally, besides those three works, we include an essay addressing the problem of emergent holographic spaces out of two-dimensional conformal field theories, where the mediation between the two parts is performed by means of a Riemannian structure defined in the Hilbert space of the field theory.