Quantum Physics

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.

High-rate quantum low-density parity-check (qLDPC) codes offer significantly lower encoding overhead compared to their topological counterparts by relaxing locality constraints. However, achieving full-fledged logical computation with these codes in physical systems with low space-time costs remains a formidable challenge. In the first part of this talk, I will provide an overview of recent advancements in implementing qLDPC codes as quantum memories on realistic platforms, such as reconfigurable atom arrays. Next, I will present a new scheme for performing parallelizable and locally addressable logical operations on homological product codes. This scheme extends the transversal CNOT gate from two identical CSS codes to two distinct, yet structurally similar, qLDPC codes, enabling efficient local addressing of collectively encoded information. We demonstrate that this approach achieves lower overhead in not only the space- but also the overall space-time overhead compared to surface-code-based computations. Finally, I will discuss new strategies for achieving highly space-time-efficient computations with qLDPC codes by leveraging algorithm-specific fault tolerance, designing tailored protocols for structured quantum algorithms.