Search Talks

In this talk, I will discuss the complexity of a fermionic analogue of Quantum k-SAT. In this Fermionic k-SAT problem, one is given the task to decide whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on n fermionic modes, where each fermionic projector involves at most k fermionic modes. We prove that this problem can be solved efficiently classically for k = 2. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA_1-hard. 

The quantum marginal problem concerns the compatibility of given reduced states. In contrast, the entanglement transitivity problem takes compatible entangled marginals as input and ask if one can infer therefrom the entanglement of some other marginals. When this is possible, the input marginals are said to exhibit entanglement transitivity. Previous studies [Npj Quantum Inf 8, 98 (2022)] have demonstrated that certain families of states show entanglement transitivity. In this talk, we will show that when specific dimension constraints are satisfied, entanglement transitivity is possible and even generic among the marginals of pure state. To this end, we use the fact that given these constraints, the marginals of generic pure states (1) uniquely determine the global state and (2) are entangled. For the latter, our results generalize that of Aubrun et al. [Comm. Pure. Appl. Math. 67, 129 (2013)], which allows us to conclude further that sufficiently large parts of a generic multipartite pure state are entangled for any bipartition.

Complementarity is a phenomenon explaining several core features of quantum theory, such as the well-known uncertainty principle. Roughly speaking, two objects are said to be complementary if being certain about one of them necessarily forbids useful knowledge about the other. Two quantum measurements that do not commute form an example of complementary measurements, and this phenomenon can also be defined for ensembles of states. Although a key quantum feature, it is unclear whether complementarity can be understood more operationally, as a necessary resource in some quantum information task. Here we show this is the case, and relates to a task which we term unambiguous exclusion. As well as giving complementarity a clear operational definition, this also uncovers the foundational underpinning of unambiguous exclusion tasks for the first time.