We use tools from quantum physics to prove new results in classical complexity.
In this project we leverage ideas from quantum particle physics to show new results in classical complexity theory. Namely, we use the fact that the probabilities of certain linear optical experiments are closely related to a function--called the permanent--of the matrix representing the experiment. The permanent has played an important role in complexity theory as it is known to encode problems which are widely conjectured to (extremely) computationally difficult. Using this connection, we are able to derive new hardness results for calculating the permanent of certain classes of matrices.
