Speaker
Description
Many computational problems require extensive processing or memory resources which can render solving them impossible when using known computer algorithms. An interesting problem in number theory is that of determining whether a set of integers can be separated into 2 subsets in which the sum of the integers in each subset is equal. This is often referred to as the partition problem, which is NP complete. Moreover, counting the number of possible partitions is known to be in #P (sharp P). It has been shown that the partition counting problem can be reformulated as evaluating an integral up to an accuracy of $n$ binary digits, where $n$ is the number of integers. Computing this integral would generally not give us any speedup over a brute force approach to finding the partitions. However, we prove that upon particular encoding of this problem followed by an evaluation the Fourier transform and a decoding process we can effectively find the number of partitions. Therefore, we can experimentally encode our problem in the position space of an optical field and allow it to propagate to the far field to make a later measurement in momentum space, thus applying the Fourier transform. We use a spatial light modulator to show that this optical setup can have an advantage over solving this problem computationally. Furthermore, we show that if we prepare a quantum state of light, we can further speed up the computation using quantum tomography. Thus, this scheme is a unique display of utilizing a physical system alongside with quantum measurement techniques to solve a hard computational problem.
