Quantum oracles and the optical Bernstein-Vazirani algorithm
Ian A. Walmsley, Pablo Londero, Christophe Dorrer, Matthew Anderson, Sascha Wallentowitz, Konrad Banaszek · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2003
We implement the Bernstein-Vazirani algorithm on a 15-bit register encoding 215-1 elements using optics. The apparatus is efficient in that the physical size of the apparatus scales linearly with the size (i.e. number of digits) of the register. We demonstrate also that the algorithm may be performed not only without entanglement, as Meyer has indicated, but also with a computational basis that does not consist of orthogonal states, and that this coding is the source of the efficiency of the algorithm. This raises several questions: is this the only algorithm that makes use of these simplifying features, or do all quantum Oracles in fact require exponential resources for their construction?