Optical implementations, oracle equivalence, and the Bernstein-Vazirani algorithm

摘要

We describe a new implementation of the Bernstein-Vazirani algorithm that relies on the fact that the polarization states of classical light beams can be cloned. We explore the possibility of computing with waves and discuss a classical optical model capable of implementing any algorithm (on n qubits) that does not involve entanglement. The Bernstein-Vazirani algorithm (with a suitably modified oracle), wherein a hidden n-bit vector is discovered by one oracle query as against n oracle queries required classically, belongs to this category. In our scheme, the modified oracle is also capable of computing f(x) for a given x, which is not possible with earlier versions used in recent NMR and optics implementations of the algorithm. (c) 2007 Optical Society of America.