2-7 June 2019
Simon Fraser University
America/Vancouver timezone
Welcome to the 2019 CAP Congress Program website! / Bienvenue au siteweb du programme du Congrès de l'ACP 2019 !

Experimental demonstration of a quantum optics solution to the partition problem

Jun 5, 2019, 2:30 PM
BLU 10011 (Simon Fraser University)

BLU 10011

Simon Fraser University

Oral Competition (Graduate Student) / Compétition orale (Étudiant(e) du 2e ou 3e cycle) Division of Atomic, Molecular and Optical Physics, Canada / Division de la physique atomique, moléculaire et photonique, Canada (DAMOPC-DPAMPC) W2-2 Quantum Information (DAMOPC/DTP) | Information quantique (DPAMPC/DPT)


Felix Hufnagel (University of Ottawa)


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.

Primary author

Felix Hufnagel (University of Ottawa)


Mr Avishy Carmi (Ben-Gurion University of the Negev) Ebrahim Karimi (University of Ottawa)

Presentation materials

There are no materials yet.