PAC-learning of free-fermionic states is NP-hard

Understand

Free-fermionic states, also known as matchgates or Gaussian states, are a fundamental class of quantum states due to their efficient classical simulability and their crucial role across various domains of Physics.

• With the advent of quantum devices, experiments now yield data from quantum states, including estimates of expectation values.
• We establish that deciding whether a given dataset, formed by a few Majorana correlation functions estimates, can be consistent with a free-fermionic state is an NP-complete problem.
• Our result also extends to datasets formed by estimates of Pauli expectation values.