Marco Fanizza

We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. As a corollary, there is a boolean constraint system (BCS) nonlocal game for which the value of the Navascués, Pironio, and Acín (NPA) hierarchy does not attain the commuting operator value at any finite level. Our contribution involves establishing a computable mapping from Turing machines to BCS nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. Our techniques are algebraic and distinct from those used to establish MIP*=RE. As a first step, we construct a mapping from Turing machines to elements of the tensor product of free algebras, showing that deciding positivity of those elements is coRE-hard. As a second step, we extend this mapping to further realize these elements as game polynomials for BCS games.

We study hypothesis testing (aka state certification) in the \emph{non-identically distributed} setting. A recent work (Garg et~al.~2023) considered the classical case, in which one is given (independent) samples from $T$ unknown probability distributions $p_1, \dots, p_T$ on $[d] = \{1, 2, \dots, d\}$, and one wishes to accept/reject the hypothesis that their average $p_{\textnormal{avg}}$ equals a known hypothesis distribution~$q$. Garg et al.~showed that if one has just $c = 2$ samples from each $p_i$, and provided $T \gg \frac{\sqrt{d}}{\eps^2} + \frac{1}{\eps^4}$, one can (whp) distinguish $p_{\textnormal{avg}} = q$ from $\dtv{p_{\textnormal{avg}}}{q} > \eps$. This nearly matches the optimal result for the classical iid setting (namely, $T \gg \frac{\sqrt{d}}{\eps^2}$). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical \emph{quantum} states. Here we uncover an unexpected phenomenon: for any $d$-dimensional hypothesis state~$\sigma$, and given just a \emph{single} copy ($c = 1$) of each state $\rho_1, \dots, \rho_T$, one can distinguish $\rho_{\textnormal{avg}} = \sigma$ from $\Dtr{\rho_{\textnormal{avg}}}{\sigma} > \eps$ provided $T \gg d/\eps^2$. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with $c = 1$ is provably impossible in the classical case. A technical tool we introduce may be of independent interest: an Efron--Stein inequality, and more generally an Efron--Stein decomposition, in the quantum setting.

The field of quantum learning theory has advanced rapidly in recent years, at the intersection of quantum information science, statistical learning, and computational complexity. A key task in this area is quantum process tomography, which seeks to learn unitary transformations of quantum states efficiently. Efficient process tomography would be highly valuable: for instance, learning an unknown natural process could enable its efficient implementation and simulation on a quantum computer. However, learning arbitrary unitary operators is generally prohibitively expensive, with several sample- and time-complexity lower bounds showing the task is intractable. Thus, work typically focuses on more structured classes of operators when computational efficiency is desired. Two especially important such classes are bosonic and fermionic Gaussian unitaries. These operators have compact parametrizations, rich algebraic structure, and enough expressiveness to capture many relevant physical processes. As a result, they are ubiquitous in quantum information theory. In this work, we advance the learning theory of bosonic and fermionic unitaries in two ways: (1) We give the first time-efficient algorithm to learn bosonic Gaussian unitaries. The complexity of the algorithm scales polynomially in the number of modes, a total photon number bound (which is critical in defining an energy-constrained distance measure), and a squeezing parameter which captures how much the operator increases the mean energy of a vacuum state. (2) We give a first-of-its-kind algorithm to learn fermionic unitaries prepared with at most t non-Gaussian gates. Our algorithm scales polynomially in the number of modes and exponentially in t, and we argue that this scaling is optimal up to polynomial factors. Both algorithms produce an output whose distance to the input unitary is small in the worst-case (diamond) distance. Our results are organized into two separate manuscripts: one is arXiv:2504.11318 (Mildly-Interacting Fermionic Unitaries are Efficiently Learnable), and the other will be released on arXiv within a month (Efficient Learning of Bosonic Gaussian Unitary Channels).

Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory state is a finite dimensional quantum state, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.

The task of testing the validity of a hypothesis underlies numerous applications in quantum information theory. The most commonly investigated approach is that of gathering all the available (quantum) data and making a final decision based on a collective measurement. However, such offline strategies are often far from practical, both in the amount of data required as well as in the complexity of the required measurement. In some settings, when the goal is quick detection, offline algorithms are not applicable at all, as they can only make a decision once all samples are received. Sequential methods offer the use of online strategies, where samples are requested on a need-to-know basis, drastically reducing the number of required samples in order to guarantee the, task specific, associated performance criteria. While extensively investigated and applied in the classical setting, we know far less about the optimal performance of such online strategies when quantum data is available. In this joint submission we present major recent progress on sequential methods for the fundamental tasks of quantum state discrimination, channel discrimination and quickest change point detection. In summary, we provide a comprehensive picture of the optimal asymptotic performance of online strategies in these settings under different performance criteria.