As quantum devices progress toward a quantum advantage regime, they become harder to benchmark. A particularly relevant challenge is to assess the quality of the whole computation, beyond testing the performance of each single operation. Here, we introduce a scheme for this task that combines the target computation with variants of it, which, when averaged, allow for classically solvable correlation functions. Importantly, the variants exactly preserve the circuit architecture and depth, without simplifying the gates into a classically simulable set. The method is based on replacing each gate by an ensemble of similar gates, which when averaged together form space-time channels [P. Kos and G. Styliaris, Quantum 7, 1020 (2023)]. We introduce explicit constructions for ensembles producing such channels, all applicable to arbitrary brickwork circuits, and provide a general recipe to find new ones through semidefinite programming. The resulting average computation retains important information about the original circuit and is able to detect noise beyond a Clifford benchmarking regime. Moreover, we provide evidence that estimating average-computation expectation values requires running only a limited number of different circuit realizations.

We propose applying the adiabatic algorithm to prepare high-energy eigenstates of integrable models on a quantum computer. We first review the standard adiabatic algorithm to prepare ground states in each magnetization sector of the prototypical XXZ Heisenberg chain. Based on the thermodynamic Bethe ansatz, we show that the algorithm circuit depth is polynomial in the number of qubits N, outperforming previous methods explicitly relying on integrability. Next, we propose a protocol to prepare arbitrary eigenstates of integrable models that satisfy certain conditions. For a given target eigenstate, we construct a suitable parent Hamiltonian written in terms of a complete set of local conserved quantities. We propose using such Hamiltonians as an input for an adiabatic algorithm. After benchmarking this construction in the case of the non-interacting XY spin chain, where we can rigorously prove its efficiency, we apply it to prepare arbitrary eigenstates of the Richardson-Gaudin models. In this case, we provide numerical evidence that the circuit depth of our algorithm is polynomial in N for all eigenstates, despite the models being interacting.

Understanding quantum phases of matter is a fundamental goal in physics. For pure states, the representatives of phases are the ground states of locally interacting Hamiltonians, which are also renormalization fixed points (RFPs). These RFP states are exactly described by tensor networks. Extending this framework to mixed states, matrix product density operators (MPDOs) that are RFPs are believed to encapsulate mixed-state phases of matter in one dimension, where nontrivial topological phases have already been shown to exist. However, to better motivate the physical relevance of those states, and in particular the physical relevance of the recently found non trivial phases, it remains an open question whether such MPDO RFPs can be realized as steady states of local Lindbladians. In this work, we resolve this question by analytically constructing parent Lindbladians for MPDO RFPs. These Lindbladians are local, frustration free, and exhibit minimal steady-state degeneracy. Interestingly, we find that parent Lindbladians possess a rich structure that distinguishes them from their Hamiltonian counterparts. In particular, we uncover an intriguing connection between the noncommutativity of the Lindbladian terms and the fact that the corresponding MPDO RFP belongs to a nontrivial phase.

Matrix-product unitaries (MPUs) are many-body unitary operators that, as a consequence of their tensor-network structure, preserve the entanglement area law in 1D systems. However, it is unknown how to implement an MPU as a quantum circuit since the individual tensors describing the MPU are not unitary. In this Letter, we show that a large class of MPUs can be implemented with a polynomial-depth quantum circuit. For an N-site MPU built from a repeated bulk tensor with open boundary, we explicitly construct a quantum circuit of polynomial depth T = O(N alpha) realizing the MPU, where the constant alpha depends only on the bulk and boundary tensor and not the system size N. We show that this class includes nontrivial unitaries that generate long-range entanglement and, in particular, contains a large class of unitaries constructed from representations of C*-weak Hopf algebras. Furthermore, we also adapt our construction to nonuniform translationally varying MPUs and show that they can be implemented by a circuit of depth O(N beta polyD) where beta <= 1 + log2 p /smin, with D being the bond dimension and smin the smallest ffiffiD nonzero Schmidt value of the normalized Choi state corresponding to the MPU.

Many-body open quantum systems, described by Lindbladian master equations, are a rich class of physical models that display complex equilibrium and out-of-equilibrium phenomena which remain to be understood. In this paper, we theoretically analyze noisy analog quantum simulation of geometrically local open quantum systems and provide evidence that this problem both is hard to simulate on classical computers and could be approximately solved on near-term quantum devices. First, given a noiseless quantum simulator, we show that the dynamics of local observables and the fixed-point expectation values of rapidly mixing local observables in geometrically local Lindbladians can be obtained to a precision of epsilon in time that is poly(epsilon-1) and uniform in system size. Furthermore, we establish that the quantum simulator would provide a superpolynomial advantage, in run-time scaling with respect to the target precision and either the evolution time (when simulating dynamics) or the Lindbladian's decay rate (when simulating fixed points), over any classical algorithm for these problems, assuming BQP # BPP. We then consider the presence of noise in the quantum simulator in the form of additional geometrically local Lindbladian terms. We show that the simulation tasks considered in this paper are stable to errors,. i.e., they can be solved to a noise-limited, but system-size independent, precision. Finally, we establish that, assuming BQP # BPP, there are stable geometrically local Lindbladian simulation problems such that, as the noise rate on the simulator is reduced, classical algorithms must take time superpolynomially longer in the inverse noise rate to attain the same precision as the analog quantum simulator.

Two matrix product states (MPS) are in the same phase in the presence of symmetries if they can be transformed into one another via symmetric short-depth circuits. We consider how symmetry-preserving measurements with feedforward alter the phase classification of MPS in the presence of global on-site symmetries. We demonstrate that, for all finite Abelian symmetries, any two symmetric MPS belong to the same phase. We give an explicit protocol that achieves a transformation between any two phases and that uses only a depth-two symmetric circuit, a single round of symmetric measurements, and a constant number of auxiliary systems per site. In the case of non-Abelian symmetries, symmetry protection prevents one from deterministically transforming symmetry-protected topological (SPT) states to product states directly via measurements, thereby complicating the analysis. Nonetheless, we provide protocols that allow for asymptotically deterministic transformations between the trivial phase, SPT phases, and GHZ phases of some non-Abelian nilpotent groups.

Matrix-product unitaries (MPU) are 1D tensor networks describing time evolution and unitary symmetries of quantum systems, while their action on states by construction preserves the entanglement area law. MPU which are formed by a single repeated tensor are known to coincide with 1D quantum cellular automata (QCA), i.e., unitaries with an exact light cone. However, this correspondence breaks down for MPU with open boundary conditions, even if the resulting operator is translation-invariant. Such unitaries can turn short- to long-range correlations and thus alter the underlying phase of matter. Here we make the first steps towards a theory of MPU with uniform bulk but arbitrary boundary. In particular, we study the structure of a subclass with a directsum form which maximally violates the QCA property. We also consider the general case of MPU formed by site-dependent (nonuniform) tensors and show a correspondence between MPU and locally maximally entanglable states.

We introduce protocols to prepare many-body quantum states with quantum circuits assisted by local operations and classical communication. We show that by lifting the requirement of exact preparation, one can substantially save resources. In particular, the so-called W and, more generally, Dicke states require a circuit depth and number of ancillas per site that are independent of the system size. As a by-product of our work, we introduce an efficient scheme to implement certain nonlocal, non-Clifford unitary operators. We also discuss how similar ideas may be applied in the preparation of eigenstates of well-known spin models, both free and interacting.

Efficient characterization of higher dimensional many-body physical states presents significant challenges. In this Letter, we propose a new class of projected entangled pair states (PEPS) that incorporates two isometric conditions. This new class facilitates the efficient calculation of general local observables and certain two-point correlation functions, which have been previously shown to be intractable for general PEPS, or PEPS with only a single isometric constraint. Despite incorporating two isometric conditions, our class preserves the rich physical structure while enhancing the analytical capabilities. It features a large set of tunable parameters, with only a subleading correction compared to that of general PEPS. Furthermore, we analytically demonstrate that this class can encode universal quantum computation and can represent a transition from topological to trivial order.

Preparing long-range entangled states poses significant challenges for near-term quantum devices. It is known that measurement and feedback (MF) can aid this task by allowing the preparation of certain paradigmatic long-range entangled states with only constant circuit depth. Here, we systematically explore the structure of states that can be prepared using constant-depth local circuits and a single MF round. Using the framework of tensor networks, the preparability under MF translates to tensor symmetries. We detail the structure of matrix-product states (MPSs) and projected entangled-pair states (PEPSs) that can be prepared using MF, revealing the coexistence of Clifford-like properties and magic. In one dimension, we show that states with Abelian-symmetry-protected topological order are a restricted class of MF-preparable states. In two dimensions, we parametrize a subset of states with Abelian topological order that are MF preparable. Finally, we discuss the analogous implementation of operators via MF, providing a structural theorem that connects to the well-known Clifford teleportation.