Continuous quantum computation: Difference between revisions

Revision as of 15:38, 7 July 2007

Revision as of 15:39, 7 July 2007

Line 10:

==An example: path integration==

Path integration has numerous applications including quantum mechanics, quantum chemistry, statistical mechanics, and computational finance. We want to compute an approximation to within error at most <math>\scripstylescriptstyle\varepsilon</math> with probability, say, at least 3/4. Then the following was [http://arXiv.org/quant-ph/0109113 shown] by Traub and Woźniakowski:

* A quantum computer enjoys exponential speedup over the classical worst case and quadratic speedup over the classical randomized case.

* The query complexity is of order <math>\scriptstyle\varepsilon^{-1}</math>.

Line 17:

Thus the qubit complexity of path integration is a second degree polynomial in <math>\scriptstyle\varepsilon^{-1}</math>. That seems pretty good but we probably won't have enough qubits for a long time to do new science especially with error correction. Since this is a complexity result we can't do better by inventing a clever new algorithm. But perhaps we can do better by slightly modifying the queries.

In the standard model of quantum computation the probabilistic nature of quantum computation enters only through measurement; the queries are deterministic. In analogy with classical Monte Carlo Woźniakowski introduced the idea of a quantum setting with [http://arXiv.org/quant-ph/0601196 randomized queries]. He showed that in this setting the qubit complexity is of order <math>\scripstylescriptstyle \log\varepsilon^{-1}</math>, thus achieving an exponential improvement over the qubit complexity in the standard quantum computing setting.

==Applications==