Are indistinguishable bosons and fermions computationally equivalent to distinguishable qubits?

Question

From the middle-late decades of the last century, many researchers such as Bennett, Benoif, Deutsch, Feynman, Manin, Wiesner, among others, had some intuition that qubits are computationally more powerful or more interesting than classical bits.

Physically embodied qubits as we understand and intuit nowadays are fundamentally distinguishable "particles" or "atoms". For example, at a high level we need to separate and index the wires in our circuit diagrams, but also more concretely we can point to individual ions in a trap or individual transmons and identify and label them as separate and distinguished.

But, quantum mechanics is also concerned with two classes of indistinguishable particles - namely fermions and bosons.

Going back all the way to the 1920's, Jordan and Wigner provided a mapping between the wavefunction in a Hilbert space spanned by a number of qubits and the wavefunction in a Fock space spanned by fermions. Feynman also hinted that a qubit could be defined by the presence or absence of such a particle. But, for fermions at least the sign problem is a separate issue that needs to be carefully addressed - e.g. whenever two fermions are swapped, the wavefunction picks up a negative phase.

Furthermore regarding bosons, Aaronson and Arkhipov noted that sampling bosons such as photons from a network of mirrors and beam splitters is related to calculation of the permanent, while sampling the same for fermions is related to the determinant. It follows from Valiant's theorem that boson sampling is likely much (much) more difficult than fermion sampling.

On the one hand we have fermions, which naively have the sign problem making simulation more difficult; however, fermion sampling is in P. On the other hand boson sampling is most likely not in P - nor is it likely to contain P.

But, can we translate between fermions, bosons, and qubits efficiently? For example could we have created a quantum computer out of indistinguishable bosons instead of distinguishable qubits?

---

^{Because of the Pauli exclusion principle, a chain can be either occupied or not with precisely one fermion, while bosonic occupancy is unlimited. BosonSampling experiments try to mitigate this by having at least quadratically more modes than bosons}.

Answer 1

Indeed, there are some works in this direction that show the interrelation between fermions, bosons and qubits. Of course, you can consider the seminal work of Jordan and Wigner that maps operators acting on fermions to operators acting on "qubits" (more precisely spins, since in 1928 qubits didn't exist yet). However, JW mapping has the problem that when you consider nontrivial fermionic lattices or interactions (e.g. 2D lattice of fermions interacting with nearest neighbours) your local fermionic operators will be mapped to nonlocal qubit operators of the size of your system.

Thus, people started considering this problem in the early 2000's again. In this paper, Bravyi and Kitaev showed that you can efficiently simulate (indistinguishable) fermions with qubits without this nasty nonlocal interactions at the cost of including more qubits than the number of fermionic degrees of freedom you originally had. Indeed, they also showed that qubit operators can be expressed in terms of fermionic operators, meaning that fermionic quantum computers and standard quantum computers should be equivalent in some sense.

More people like Verstraete and Cirac and also Ball found new mappings showing that fermionic statistics are not an outcome solely arising in fermionic systems and depending on the interactions between your subjacent spin system, you can reproduce these statistics.

There are some subtleties of course. The Fock space is of course "a restrained Hilbert space", since you are taking only the symmetries or antisymmetrized tensors from the sum of single-particle Hilbert spaces and thus you cannot trivially recover all the dynamics of the whole Hilbert space from a given set of fermions and one of these local mappings unless you use ancilla fermions for this. This means that quantum computing using qubits and fermions is equivalent up to a constant overhead in resources.

I guess the bosonic case should be equivalent but I am not an expert there.