1.6. Complexity theory insights
Complexity theory has two important facets: one is regarding the PEP and the use of the BO approximation, to which we dedicate part of Chapter 2, Postulates of Quantum Mechanics; and two is the complexity of computation. This section describes the complexity of computation as it relates to quantum systems.
In his keynote lecture at the Physics of Computation Conference at MIT in 1981 [MIT_QC_1981], Richard Feynman asked the question: "Can a classical computer simulate either a classical system or a quantum system exactly?" He also stated that the number of computer elements required to simulate a large physical system should only be proportional to the size of the physical system. Feynman pointed out that calculating the probability of each of 
particles of a large quantum system being at each of 
points require an amount of memory proportional to 
, that is, increasing exponentially with 
. His next question was whether a classical system...