Jens Eisert

Our capacity to process information depends on the computational power at our disposal. Information theory captures our ability to distinguish states or communicate messages when it is unconstrained with unrivaled beauty and elegance. For computationally bounded observers the situation is quite different -- they can, for example, be fooled to believe that distributions are more random than they actually are. Existing mathematical approaches in computational information theory largely follow the single-shot paradigm that, while being operationally meaningful, also gives complicated statements and is difficult to build intuition for. In our work, we take a new direction in computational quantum information theory that captures the essence of complexity-constrained information theory while retaining the look and feel of the unbounded asymptotic theory. As our foundational quantity, we define the computational relative entropy as the optimal error exponent in asymmetric hypothesis testing when restricted to polynomially many copies and quantum gates, defined in a mathematically rigorous way. Building on this foundation, we prove a computational analogue of Stein's lemma, establish computational versions of fundamental inequalities like Pinsker's bound, and demonstrate a computational smoothing property showing that computationally indistinguishable states yield equivalent information measures. We derive a computational entropy that operationally characterizes optimal compression rates for quantum states under computational limitations and show that our quantities apply to computational entanglement theory, proving a computational version of the Rains bound. Our framework reveals striking separations between computational and unbounded information measures, including quantum-classical gaps that arise from cryptographic assumptions, demonstrating that computational constraints fundamentally alter the information-theoretic landscape and open new research directions at the intersection of quantum information, complexity theory, and cryptography.

The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group—a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with $k$-fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of $k$, constrained by the number of qubits $n$. In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary $n$ and $k$. We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations— which generate the unitary group commutant— and at most three other operators. Additionally, we develop a \emph{graphical calculus} allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all \emph{measurable} magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension. This submission merges two of our recent works: one presenting a complete theory of the Clifford commutant with applications, and one focused on showcasing a major application to state $k$-design convergence.

Identifying the symmetry properties of quantum states is a central theme in quantum information theory and quantum many-body physics. In this work, we investigate quantum learning problems in which the goal is to identify a hidden symmetry of an unknown quantum state. Building on the recent formulation of the state hidden subgroup problem (StateHSP), we focus on abelian groups and develop an efficient quantum algorithm that learns any hidden symmetry subgroup using a generalized form of Fourier sampling. We showcase the versatility of the approach in three concrete applications: These are learning (i) qubit and qudit stabilizer groups, (ii) cuts along which a state is unentangled, and (iii) hidden translation symmetries. Through these applications, we reveal that well-known quantum learning primitives, such as Bell sampling and Bell difference sampling, are in fact special cases of Fourier sampling. Our results highlight the broad potential of the StateHSP framework for symmetry-based quantum learning tasks.

The precise quantification of the limits to manipulating quantum resources lies at the core of quantum information theory. However, standard information-theoretic analyses do not consider the actual computational complexity involved in performing certain tasks. Here, we address this issue within the realm of entanglement theory, finding that accounting for computational efficiency substantially changes what can be achieved using entangled resources. We consider two key figures of merit: the computational distillable entanglement and the computational entanglement cost. These measures quantify the optimal rates of entangled bits that can be extracted from or used to dilute many identical copies of n-qubit bipartite pure states, using computationally efficient local operations and classical communication. We demonstrate that computational entanglement measures diverge significantly from their information-theoretic counterparts. While the information-theoretic distillable entanglement is determined by the von Neumann entropy of the reduced state, we show that the min-entropy governs the computationally efficient setting. On the other hand, computationally efficient entanglement dilution requires maximal consumption of entangled bits, even for nearly unentangled states. Furthermore, in the worst-case scenario, even when an efficient description of the state exists and is fully known, one gains no advantage over state-agnostic protocols. Our findings establish sample-complexity bounds for measuring and testing the von Neumann entropy, fundamental limitations on efficient state compression, and efficient local tomography protocols.

Quantum state tomography, aimed at deriving a classical description of an unknown state from measurement data, is a fundamental task in quantum physics. In this work, we analyse the ultimate achievable performance of tomography of continuous-variable systems, such as bosonic and quantum optical systems. We prove that tomography of these systems is extremely inefficient in terms of time resources, much more so than tomography of qudit systems: the minimum number of state copies needed for tomography not only scales exponentially with the number of modes but also exhibits a dramatic scaling with the trace-distance error, even for low-energy states. On a more positive note, we prove that tomography of Gaussian states is efficient. To accomplish this, we answer a fundamental question for the field of continuous-variable quantum information: if we know with a certain error the first and second moments of an unknown Gaussian state, what is the resulting trace-distance error that we make on the state? Lastly, we demonstrate that tomography of non-Gaussian states prepared through Gaussian unitaries and a few local non-Gaussian evolutions is efficient and experimentally feasible.

Motivated by realistic hardware considerations of the pre-fault-tolerant era, we comprehensively study the impact of uncorrected noise on quantum circuits. We first show that any noise `truncates' most quantum circuits to effectively logarithmic depth, in the task of computing Pauli expectation values. We then prove that quantum circuits under any non-unital noise exhibit lack of barren plateaus for cost functions composed of local observables. But, by leveraging the effective shallowness, we also design a classical algorithm to estimate Pauli expectation values within inverse-polynomial additive error with high probability over the ensemble. Its runtime is independent of circuit depth and it operates in polynomial time in the number of qubits for one-dimensional architectures and quasi-polynomial time for higher-dimensional ones. Taken together, our results showcase that, unless we carefully engineer the circuits to take advantage of the noise, it is unlikely that noisy quantum circuits are preferable over shallow quantum circuits for algorithms that output Pauli expectation value estimates, like many variational quantum machine learning proposals. Moreover, we anticipate that our work could provide valuable insights into the fundamental open question about the complexity of sampling from (possibly non-unital) noisy random circuits.

We provide practical and powerful schemes for learning properties of a quantum state using a small number of measurements. Specifically, we present a randomized measurement scheme modulated by the depth of a random quantum circuit in one spatial dimension. This scheme interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. We focus on the regime where depth scales logarithmically in the system size and provide evidence that this retains the desirable sample complexity properties of both extremal schemes while also being experimentally feasible. We present methods for two key tasks; estimating expectation values of certain observables from generated classical shadows and, computing upper bounds on the depth-modulated shadow norm, thus providing rigorous guarantees on the accuracy of the output estimates. We achieve our findings by bringing together tools of shadow estimation, random circuits, and tensor networks.

Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n-qubit group, one often resorts to t-designs. Unitary t-designs mimic the Haar-measure up to t-th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject O(t^4log^2(t)log(1/e)) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an e-approximate t-design. Strikingly, the number of non-Clifford gates required is independent of the system size -- asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t-th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.

Abstract Noise in quantum metrology reduces the sensitivity to which one can determine an unknown parameter in the evolution of a quantum state, such as time. Here, we consider a probe system prepared in a pure state that evolves according to a given Hamiltonian. We study the resulting local sensitivity of the probe to time after the application of a given noise channel. We show that the decrease in sensitivity due to the noise is equal to the sensitivity that the environment gains with respect to the energy of the probe. We obtain necessary and sufficient conditions for when the probe does not suffer any sensitivity loss; these conditions are analogous to, but weaker than, the Knill-Laflamme quantum error correction conditions. New upper bounds on the sensitivity of the noisy probe are obtained via our uncertainty relation, by applying known sensitivity lower bounds on the environments system. Our time-energy uncertainty relation also generalizes to any two arbitrary parameters whose evolutions are generated by Hermitian operators. This uncertainty relation asserts a general trade-off between the sensitivities that two parties can achieve for any two respective parameters of a single quantum system, in terms of the commutator of the associated generators. We consider applications to strongly interacting many-body probes. We find probe states for general interaction graphs of Ising and Heisenberg interactions that are robust to any single located error. For a 1D spin chain with nearest-neighbor interactions subject to amplitude damping noise on each site, we verify numerically that our probe state does not lose any sensitivity to first order in the noise parameter.

We report on an experimental demonstration of a recently proposed (n, n)-QSS (quantum secret sharing) protocol, which can be shown to be secure against participant attacks, using a four-photon GHZ state. Our work leverages the generation of high-quality and high-brightness non-linear single photon sources to achieve a secure key rate of 745 bits/sec in the asymptotic regime marking an important step toward scalable quantum-secure communication in networks.

Whilst the use of multi-partite entanglement is known to offer an advantage over bi-partite protocols in certain contexts, the quest to find practical advantage scenarios is ongoing and substantial difficulties in generalising some bi-partite security proofs remain. We present rigorous results that address both these challenges. First, we prove the security of a variant of the GHZ state based secret sharing protocol against general attacks, including participant attacks which break the security of the original GHZ state scheme. We then identify parameters for a performance advantage over realistic bottleneck networks in terms of extractable secret bits per network use. We show that whilst channel losses limit the advantage region to short distances over direct transmission networks, the addition of quantum repeaters unlocks the performance advantage of multi-partite entanglement over point-to-point approaches for long distance quantum cryptography.

Quantum repeaters have long been established to be essential for distributing entanglement over longdistances. Consequently, their experimental realization constitutes a core challenge of quantum communi-cation. However, there are numerous open questions about implementation details for realistic near-termexperimental setups. In order to assess the performance of realistic repeater protocols, here we presentReQuSim, a comprehensive Monte Carlo–based simulation platform for quantum repeaters that faithfullyincludes loss and models a wide range of imperfections such as memories with time-dependent noise. Ourplatform allows us to perform an analysis for quantum repeater setups and strategies that go far beyondknown analytical results: This refers to being able to both capture more realistic noise models and analyzemore complex repeater strategies. We present a number of findings centered around the combination ofstrategies for improving performance, such as entanglement purification and the use of multiple repeaterstations, and demonstrate that there exist complex relationships between them. We stress that numericaltools such as ours are essential to model complex quantum communication protocols aimed at contributingto the quantum Internet.