In Shor's factorization of number N=pq, the first step is to build ~log2(N) independent qubits, each an equal superposition of 0 and 1 states and use them to make a tensor product equivalent of ~N superimposed states. The second step is to act on that with a Hadamard gate which turns them into an entangled monster of N unseparable (entangled) states. Manupulating this further finally yields p and q.
Now, how precise these objects and operations need to be? The qubits in the first step, what if they are all a bit different from ideal fifty-fifty superposition? If N is an 100 bit long number, must then amplitudes of 0 and 1 states be precise to 100 bits too? More? Less? Why? How high entanglement fidelity is needed? What about the requirement on precision of Hadamard operation?
In principle, yes-the algorithm does work as designed-that’s the result of the mathematical analysis; in practice, no, simply because current quantum computers can’t control arbitrarily many qubits.
The qubits need not be in any particular superposition, it suffices to know the superposition they’re in. Now it is an interesting question, what if the superposition itself is known with a certain probability, i.e. drawn from some ensemble, how would this affect the result.The answer to that lies in the so-called error correcting codes, similar to those that ensure that errors in classical bits can get corrected.
I do not think anyone here understands my question. Error correction or number of qubits or even decoherence are the least of my interest. I am asking about PRECISION required to correctly factorize. Let us imagine we want to factorize a number of size of 1E12. First, we need to tell computer that number, right? How do we do that? How do we communicate exactly that number, not a bit smaller of bigger? Note that factoring a wrong number does us no good. Becuse factors of a wrong number will be completely different from factors of the correct number, even if the two are just a bit different.
- Badges
- Science topic
- Similar topics
- Computer Communications (Networks)
- Simulators