|
Main /
QuantumComputingA Description of Lov K. Grover's Search Algorithm for Quantum Computers Quantum computing: Cheat Sheet | CEO Essentials | silicon.com (An accessible foray into Quantum Computing) http://www.mail-archive.com/cryptography@wasabisystems.com/msg02699.html (excerpt from above) David Wagner Mon, 02 Sep 2002 17:40:06 -0700 Some might think that Shor's factoring algorithm is a counterexample. After all, if you read a popular exposition, it might seem like it sets up a superposition of all integers less than n, then checks in parallel which ones divide n, and somehow causes the wavefunction to collapse onto one state containing a divisor d of n. Well, that's probably a misleading way to think about Shor's factoring algorithm. In fact, what Shor's algorithm does is set up a superposition so that collapsing to a random state in the superposition will, with high probability, give you useful information about the factors of n. All the hard work, and technical insight, is in seeing how one can set up such a superposition using only the basic primitives available in a quantum computer (namely, unitary transformations). |