2
$\begingroup$

I am trying to get myself a more clear understanding of the root of significant acceleration in number factoring by P. Shor's algorithm. I am probably missing something but q-bits for me are no more than objects of compact parallel computations. Period finding in factorization is so fast because quantum property let us perform Fourier transfer exponentially faster than von Neumann computers, i.e. Q-bits physical property provides us coefficients of wave function almost "for free". For example, Grover's algorithms use the same "Fast Fourier" property in it's search. So if particular task cannot be "tailored" to use this specific property of q-bits, quantum computer will not bring much acceleration in it. Isn't it?

$\endgroup$
2
$\begingroup$

You are right. That is the reason quantum algorithms are so hard to come by and only a few like factorization, search and boson sampling are known.

The power of quantum computers comes from the parallelism you mention, strictly speaking, the ability of a qbit to utilize the complete Hilbert space $\alpha|0\rangle+\beta|1\rangle$ rather than the discrete either 0 or 1 classical bit. Yet this in itself is not a sufficient condition.

The Gottesman Knill theorem, for example, shows that certain quantum systems can be simulated classically. But the G-K theroem also does not define the sufficient conditions for quantum speedup, only one necessary criteria, viz the algorithm must contain atleast one non-Clifford operator. The general rule for making a quantum algorithm out of any arbitrary problem is still unsolved.

Therefore, a quantum algorithm must be tailored to exploit the quantum computer. Any algorithm that cannot do that, can be done on classical computer just as well.

$\endgroup$
1
$\begingroup$

Scott Aaronson has written an approachable explanation of how Shor's factoring algorithm works ('Shor, I'll do it'):

here’s the task I’ve set for myself: to explain Shor’s algorithm without using a single ket sign, or for that matter any math beyond arithmetic. [...]

The property we’ll exploit is the reducibility of factoring to another problem, called period-finding. [...]

[..] consider the sequence x mod N, $x^2$ mod N, $x^3$ mod N, $x^4$ mod N, … Then provided x is not divisible by p or q, the above sequence will repeat with some period that evenly divides (p-1)(q-1). [...]

[...] suppose we could create an enormous quantum superposition over all the numbers in our sequence: x mod N, $x^2$ mod N, $x^3$ mod N, etc. Then maybe there’s some quantum operation we could perform on that superposition that would reveal the period. [...]

[...] the one part of Shor’s quantum algorithm that actually depends on quantum mechanics. To get the period out, Shor uses something called the quantum Fourier transform [...]

[...] all periods other than the “true” one, these contributions point in different directions and therefore cancel each other out. Only for the “true” period do the contributions from different universes all point in the same direction. And that’s why, when we measure at the end, we’ll find the true period with high probability. [...]

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.