Lorenzo Leone

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 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.

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.

High-fidelity quantum entanglement enables key quantum networking capabilities such as secure communication and distributed quantum computing, but long-distance entanglement distribution is limited by noise and loss. Entanglement distillation protocols address this problem by extracting high-fidelity Bell pairs from multiple noisy ones. The primary objective is minimizing the resource overhead: the number of noisy input pairs needed to distill each high-fidelity output pair. While protocols achieving optimal overhead are known in theory, they often require complex decoding operations that make practical implementation challenging. We circumvent this challenge by introducing protocols that use quantum scrambling --- the spreading of quantum information under chaotic dynamics --- through random Clifford operations. Based on this scrambling mechanism, our protocol maintains asymptotically \emph{constant} overhead, independent of the desired output error rate $\bar{\varepsilon}$, and can be implemented with shallow quantum circuits of depth $O(\poly \log \log \bar{\varepsilon}^{-1})$ and memory $O(\poly \log \bar{\varepsilon}^{-1})$. Our protocol remains effective even with noisy quantum gates. By incorporating error correction, our protocol achieves state-of-the-art performance: starting with pairs of 10\% initial infidelity, we require only 7 noisy inputs per output pair to distill a single Bell pair with infidelity $\bar{\varepsilon}=10^{-12}$, substantially outperforming existing schemes. We demonstrate the utility of our protocols for quantum repeater networks.

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.

Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.