The set of two-body reduced states of translation invariant, infinite quantum spin chains can be approximated from inside and outside using matrix product states and marginals of finite systems, respectively. These lead to hierarchies of algebraic approximations that become tight only in the limit of infinitely many auxiliary variables. We show that this is necessarily so for any algebraic ansatz by proving that the set of reduced states is not semialgebraic. We also provide evidence that additional elementary transcendental functions cannot lead to a finitary description.

The vast majority of quantum states and unitaries have circuit complexity exponential in the number of qubits. In a similar vein, most of them also have exponential minimum description length, which makes it difficult to pinpoint examples of exponential complexity. In this work, we construct examples of constant description length but exponential circuit complexity. We provide infinite families such that each element requires an exponential number of two-qubit gates to be generated exactly from a product and where the same is true for the approximate generation of the vast majority of elements in the family. The results are based on sets of large transcendence degree and discussed for tensor networks, diagonal unitaries and maximally coherent states.

For information-theoretic quantities with an asymptotic operational characterization, the question arises whether an alternative single-shot characterization exists, possibly including an optimization over an ancilla system. If the expressions are algebraic and the ancilla is finite, this leads to semialgebraic level sets. In this work, we provide a criterion for disproving that a set is semialgebraic based on an analytic continuation of the Gauss map. Applied to the von Neumann entropy, this shows that its level sets are nowhere semialgebraic in dimension d >= 3, ruling out algebraic single-shot characterizations with finite ancilla (e.g., via catalytic transformations). We show similar results for related quantities, including the relative entropy, and discuss under which conditions entropy values are transcendental, algebraic, or rational.

"In this work, we investigate the question of which objects can be discriminated by totally ""interaction-free"" measurements. To this end, we interpret the Elitzur-Vaidman bomb-tester experiment as a quantum channel discrimination problem and generalize the notion of ""interaction-free"" measurement to arbitrary quantum channels. Our main result is a necessary and sufficient criterion for when it is possible or impossible to discriminate quantum channels in an ""interaction-free"" manner (i.e., such that the discrimination error probability and the ""interaction"" probability can be made arbitrarily small). For the case where our condition holds, we devise an explicit protocol with the property that both probabilities approach zero with an increasing number of channel uses, N. More specifically, the ""interaction"" probability in our protocol decays as 1/N, and we show that this rate is the optimal achievable one. Furthermore, our protocol only needs at most one ancillary qubit and might thus be implementable in near-term experiments. For the case where our condition does not hold, we prove an inequality that quantifies the trade-off between the error probability and the ""interaction"" probability."

We construct families of translationally invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson's aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians.

"A universal programmable quantum processor uses ""program"" quantum states to apply an arbitrary quantum channel to an input state. We generalize the concept of a finite-dimensional programmable quantum processor to infinite dimension assuming an energy constraint on the input and output of the target quantum channels. By proving reductions to and from finite-dimensional processors, we obtain upper and lower bounds on the program dimension required to approximately implement energy-limited quantum channels. In particular, we consider the implementation of Gaussian channels. Due to their practical relevance, we investigate the resource requirements for gauge-covariant Gaussian channels. Additionally, we give upper and lower bounds on the program dimension of a processor implementing all Gaussian unitary channels. These lower bounds rely on a direct information-theoretic argument, based on the generalization from finite to infinite dimension of a certain ""replication lemma"" for unitaries."

In classical statistical learning theory, one of the most well-studied problems is that of binary classification. The information-theoretic sample complexity of this task is tightly characterized by the Vapnik-Chervonenkis (VC) dimension. A quantum analog of this task, with training data given as a quantum state has also been intensely studied and is now known to have the same sample complexity as its classical counterpart. We propose a novel quantum version of the classical binary classification task by considering maps with classical input and quantum output and corresponding classical-quantum training data. We discuss learning strategies for the agnostic and for the realizable case and study their performance to obtain sample complexity upper bounds. Moreover, we provide sample complexity lower bounds which show that our upper bounds are essentially tight for pure output states. In particular, we see that the sample complexity is the same as in the classical binary classification task w.r.t. its dependence on accuracy, confidence and the VC-dimension.

We describe how to extend the notion of infinitesimal Markovian divisibility from quantum channels to general linear maps and compact and convex sets of generators. We give a general approach toward proving necessary criteria for (infinitesimal) Markovian divisibility. With it, we prove two necessary criteria for infinitesimal divisibility of quantum channels in any finite dimension d: an upper bound on the determinant in terms of a Theta (d)-power of the smallest singular value and in terms of a product of Theta (d) smallest singular values. These allow us to analytically construct, in any given dimension, a set of channels that contains provably non-infinitesimal Markovian divisible ones. Moreover, we show that, in general, no such non-trivial criteria can be derived for the classical counterpart of this scenario.

The Darmois-Skitovich theorem is a simple characterization of the normal distribution in terms of the independence of linear forms. We present here a non-commutative version of this theorem in the context of Gaussian bosonic states and show that this theorem is strongly stable under small errors in its underlying conditions. An explicit estimate of the stability constants which depend on the physical parameters of the problem is given.

It d-pends. Wigner's symmetry theorem implies that transformations that preserve transition probabilities of pure quantum states are linear maps on the level of density operators. We investigate the stability of this implication. On the one hand, we show that any transformation that preserves transition probabilities up to an additive epsilon in a separable Hilbert space admits a weak linear approximation, i.e., one relative to any fixed observable. This implies the existence of a linear approximation that is 4 epsilon d-close in Hilbert-Schmidt norm, with d the Hilbert space dimension. On the other hand, we prove that a linear approximation that is close in norm and independent of d does not exist in general. To this end, we provide a lower bound that depends logarithmically on d.

The quantum Zeno effect, in its original form, uses frequent projective measurements to freeze the evolution of a quantum system that is initially governed by a fixed Hamiltonian. We generalize this effect simultaneously in three directions by allowing open system dynamics, time dependent evolution equations, and general quantum operations in place of projective measurements. More precisely, we study Markovian master equations with bounded generators whose time dependence is Lipschitz continuous. Under a spectral gap condition on the quantum operation, we show how frequent measurements again freeze the evolution outside an invariant subspace. Inside this space, the evolution is described by a modified master equation. Published under license by AIP Publishing.