The computational power of noisy interacting fermions

Piotr Cwiklinski [1], Fernando de Melo [2], Barbara Terhal [1] 

[1] Institute for Quantum Information, RWTH Aachen University
[2] Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands

We study the route towards quantum computation through braiding of Majorana fermion qubits and the use of special ancillas which can be created using quartic fermionic interactions. Bravyi has shown that universal quantum computation is possible assuming perfect braiding operations and an error rate of less than 14% on these ancillas. We ask the converse question: namely what is the noise rate above which one classically simulate fermionic linear optics computation augmented with noisy interacting ancillas. In order to address this question we develop a hierarchy of tests which decide whether a fermionic state can be represented as a convex mixture of Gaussian states. Our criterion has similarity with separability tests for quantum entanglement and can be formulated as a semi-definite program.