Rapid solution of problems by nuclear-magnetic-resonance quantum computation - art. no. 032302

We offer an improved method for using a nuclear-magnetic-resonance quantum computer (NMRQC) to solve the Deutsch-Jozsa problem. Two known obstacles to the application of the NMRQC are an exponential diminishment of density-ma trix elements with the number of bits, threatening weak signal levels; and the high cost of preparing a suitable starting state. A third obstacle is a heretofore unnoticed restriction on measurement operators available for us e by a NMRQC. Variations on the function classes of the Deutsch-Jozsa probl em are introduced, both to extend the range of problems advantageous for qu antum computation and to escape all three obstacles to the use of a NMRQC. At the cost of an extra work bit and a polynomial increase in the number of gate operations required, the method solves the Deutsch-Jozsa problem whil e avoiding an exponential loss of the signal, preparation of a pseudopure s tate, and temporal averaging.