BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Experimental demonstration of a quantum optics solution to the par
tition problem
DTSTART;VALUE=DATE-TIME:20190605T213000Z
DTEND;VALUE=DATE-TIME:20190605T214500Z
DTSTAMP;VALUE=DATE-TIME:20201204T024801Z
UID:indico-contribution-3349120@indico.cern.ch
DESCRIPTION:Speakers: Felix Hufnagel (University of Ottawa)\nMany computat
ional problems require extensive processing or memory resources which can
render solving them impossible when using known computer algorithms. An in
teresting 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 probl
em\, which is NP complete. Moreover\, counting the number of possible part
itions is known to be in #P (sharp P). It has been shown that the partitio
n counting problem can be reformulated as evaluating an integral up to an
accuracy of $n$ binary digits\, where $n$ is the number of integers. Compu
ting this integral would generally not give us any speedup over a brute fo
rce approach to finding the partitions. However\, we prove that upon parti
cular encoding of this problem followed by an evaluation the Fourier trans
form and a decoding process we can effectively find the number of partitio
ns. Therefore\, we can experimentally encode our problem in the position s
pace of an optical field and allow it to propagate to the far field to mak
e a later measurement in momentum space\, thus applying the Fourier transf
orm. 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 spee
d up the computation using quantum tomography. Thus\, this scheme is a uni
que display of utilizing a physical system alongside with quantum measurem
ent techniques to solve a hard computational problem.\n\nhttps://indico.ce
rn.ch/event/776181/contributions/3349120/
LOCATION:Simon Fraser University BLU 10011
URL:https://indico.cern.ch/event/776181/contributions/3349120/
END:VEVENT
END:VCALENDAR