5
$\begingroup$

How, if you had to find the factors of say a 256 digit number, would you go about inputting the data and how do the proper answers "drop out" of a quantum computer.

Other than terms such as qubits, superposition and decoherence related to quantum computers, I know nothing whatsoever about the mechanics of the I/O process, but I really would appreciate, if it is possible, someone to provide as simple a picture as possible of how the right answer(s) emerges from the machine.

$\endgroup$
2
$\begingroup$

If you want to hard code a specific set of qubits you could measure the spin (pass it through an inhomogeneous magnetic field) of a spin 1/2 system and then if you get the wrong spin, flip it (tune a photon to a wavelength based on a given uniform magnetic field strength).

If you want to read an output you could do the same thing, measure the spin of each qubit. If your qubit wasn't the spin of a spin 1/2 particle you'd have to do it another way. But you don't call something a qubit unless you have a way to measure it to get two different possibilities.

And there are other ways to prepare a system, you might want to prepare the system to be entangled for instance, or (and this is different) superpositioned to have a coherent probability of giving different outcomes for a measurement. By coherent, I mean able to get extreme interference between doing it and not doing it, I do not mean flipping a coin and sometimes doing one and sometimes doing the other. And this is different than entanglement because entanglement is about the joint state of two qubits.

OK. Then yes you can have some circuit elements for a quantum computer, but the point is which elements in which order, and that is given by your algorithm. So the algorithm selection is really where the magic happens.

There are a few algorithms designed to do things that quantum computers are better at than classical computers. Most (all?) are pretty much variants of Shor's algorithm.

At the highest level, the point of Shor's algorithm is to set up a pattern where wrong answers run through it and tend to cancel themselves out, but the desired answer reinforces itself. Then you do a measurement, which has some randomness but because of the reinforcement versus the cancellation is much more likely to give the result that is the answer you are looking for (what we'd call the correct answer, the one your algorithm was designed to aim for).

This is nice for a problem like factorizing numbers (something Shor's algorithm can do) because it is hard to find factors (so many many choices) whereas it is easy to verify you have a good answer (just multiply them together with a classical computer if you get the original number, you factored it, if you didn't go try it again).

Shor made his algorithm to factor numbers. So you either turn your problem into one that could be solved if you could factor a number, or else you try to see if you can tweek the Shor algorithm to do the same thing, reinforce the answer you want and have other answers cancel each other out. You are trying to get it so that the wrong answers in a sense counter themselves and each other's influence on the answer so that the correct answer can influence final result more strongly.

$\endgroup$
  • $\begingroup$ Thank you for that answer, I am being to see why it will be a while before Amazon start selling them, as someone said on this site. Much appreciated $\endgroup$ – user81619 Aug 3 '15 at 1:49
  • $\begingroup$ Note that Grover's algorithm for unstructured search also outperforms classical algorithms. (Quadratically instead of exponentially, but still a speedup.) So-called 'quantum machine learning' algorithms also offer speedups but they should be treated with some care, cf. this essay. $\endgroup$ – Emilio Pisanty Aug 4 '15 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy