Computational complexity of exterior products and multiparticle amplitudes of noninteracting fermions in entangled states

Noninteracting bosons were proposed to be used for a demonstration of quantum-computing supremacy in a boson-sampling setup. A similar demonstration with fermions would require that the fermions are initially prepared in an entangled state. I suggest that pairwise entanglement of fermions would be sufficient for this purpose. Namely, it is shown that computing multiparticle scattering amplitudes for fermions entangled pairwise in groups of four single-particle states is #P-hard. In linear algebra, such amplitudes are expressed as exterior products of two-forms of rank 2. In particular, a permanent of a $N\times N$ matrix may be expressed as an exterior product of $N^2$ two forms of rank 2 in dimension $2N^2$, which establishes the #P-hardness of the latter.

Figure 1

(a) The Boson-Sampling setup. The square represents the scattering matrix with rows corresponding to the input channels and columns corresponding to the output channels. The dashed lines represent one of the multiparticle processes participating in the interference. (b) The four-channel entanglement of Eq. (2) [the factor $1/\sqrt{2}$ is omitted for simplicity]. (c) The fermion-sampling setup with entangled quadruplets.

Figure 2

The construction of the two-color directed graph for the function (3, 4) [panel (b)] from the graph for a permanent [panel (a)]. The weights of the directed edges are labeled as $a_{ij}$. The unlabeled edges have weight one. The nodes of the two-color directed graph are grouped in pairs: 1A together with 1B, 1A2 together with 1B2, and so on (every node labeled with letter A is paired with the corresponding node with letter B). Within each pair, the color of the outgoing edges in the cycle cover must be unique.