We present a tensor-network-based classical algorithm (equipped with guarantees) for simulating $n$-qubit quantum circuits with arbitrary single-qubit noise. Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states from which we stochastically sample a pure quantum state. Each single qubit noise process acting on a pure state is then represented by the ensemble of states that achieve the minimal average entanglement (the entanglement of formation) between the noisy qubit and the rest of the system. This approach provides a connection between the entanglement of formation and the accuracy of the simulation algorithm. For a given maximum bond dimension $\chi$ and circuit, our algorithm comes with an upper bound on the simulation error (in total variation distance), runs in $poly(n,\chi)$-time and improves upon related prior work (1) in scope: by extending from the three commonly considered noise models to general single qubit noise (2) in performance: by employing a state-dependent locally-entanglement-optimal unraveling and (3) in conceptual contribution: by showing that the fixed unraveling used in prior work becomes equivalent to our choice of unraveling in the special case of depolarizing and dephasing noise acting on a maximally entangled state. This is joint work with Simon Cichy, Paul K. Faehrmann, Lennart Bittel and Jens Eisert.
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.
