Deutsch-Jozsa Algorithm Implementation with Linear Optics

Deutsch's Algorithm was the first demonstration of the potential for a speedup of quantum computers over classical computers, concerning a problem of determining whether an unknown function's single bit output is constant or evenly distributed ("balanced") between zeros and ones across all single-bit inputs. The Deutsch-Jozsa Algorithm extended the problem to concern arbitrary length inputs, and demonstrated the first superpolynomial speedup in query complexity over a deterministic classical algorithm. We considered two variations of the Deutsch-Jozsa problem concerning the distribution of inputs and compared the bounds and expectation of required queries between quantum and deterministic classical solutions. We also designed and simulated linear optical systems for implementing the algorithm. We were able to demonstrate that beyond the typical result of the Deutsch-Jozsa algorithm, we can also determine whether the unknown function has dependency on any certain input bit in one quantum query. We designed and simulated a linear optical setup to showcase this ability. While all quantum solutions were able to solve the problem with a single query, the number of optical components needed grew exponentially as the input length grew.