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.
If you would like to contact us about our work, please scroll down to the people section and click on one of the group leads' people pages, where you can reach out to them directly.