As my algorithms class winds down, I've been doing some "topics" lectures, and today I attempted to not make a fool of myself giving students a very high level view of quantum computing, with much help from Dave Bacon and Umesh Vazirani's lecture notes, as well as the Nielsen/Chuang book.
One question came up that I thought was interesting, and I'm hoping that Pontiffs in Shtetls can help answer it :). One of the "features" of programming a randomized algorithm with pseudorandom bits generated by a seed is that you can reproduce a program run by using the same trace. This is of course handy when debugging.
Is there any way of doing this with a quantum algorithm ? I.e is there any way to run a quantum algorithm twice and get the same answer ? maybe using entangled bits in some strange way ?
Short answer: no.
ReplyDeleteIf you could run a quantum program twice and get the same answer, that would (for example) let you solve the collision problem in O(1) queries.
But I think the more basic point is that in quantum computing, there's not even such a thing as a "trace"! So when you write quantum programs, don't put bugs in them. (Or if you must debug, do it via classical simulation on very small examples. Or, find an intermediate point in your quantum computation where a measurement could actually reveal useful information about whether your program is working correctly: for example, the point in Shor's algorithm right before the Fourier transform.)
Reminds me of an older discussion on Lance's page about "pulling out the quantumness":
ReplyDeletehttp://weblog.fortnow.com/2005/12/pulling-out-quantumness.html
Scott; Thanks for clarifying that point !
ReplyDeleteAndy: It *is* relevant ! thanks for the link