I'm new to quantum computing, I'm learning how to use Qiskit. I'm trying to understand better how exactly the quantum characteristics of quantum computer help to increase its computational power. I thought about the following example: If I'm writing a backtracking algorithm, writing this algorithm using quantum algorithms on a quantum computer allows me to check many paths in parallel, instead of checking all the possibilities in a row as would happen on classical computer. Is it correct to say that?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is a misconception. For example, people tends to say the Shor's factoring algorithm help us to do prime factor exponential faster than classical computer because the quantum computer will try out all the possible factors simultaneously then it will tells us the right answer at the end. In reality, the power of shor's algorithm is more subtle than that. It taking into the fact that quantum computer can perform certain tasks very efficient. It turn out that "factoring" can be broken down into the question of "period finding" of a certain function. And when you think of period finding, one mathematical tool that might comes to mind is the Fourier Transform, or Discrete Fourier Transform (DFT). It turns out that DFT can be perform much more efficient on a quantum computer than classical computer, this is known as the Quantum Fourier Transform. This is the key behind many quantum algorithms, and not just Shor's factoring algorithm.
I should mention that performing Fourier Transform more efficiently on a quantum computer does not mean you can just use it like you do classically. That is, you can't just use QFT on any classical algorithms that require a Fourier Transform and expect a speed-up. This is because we can't access the quantum state directly. $$QFT |\psi \rangle = |\phi \rangle$$ You can't read-out what $|\phi\rangle$ is directly as postulate by quantum mechanics. That is part of the private world of the quantum state. Also, preparing an arbitrary state $|\psi\rangle$ on a quantum computer is hard. All qubit state initialize at $|0\rangle^{\otimes n}$. So you must do some operation to get it to $|\psi \rangle$. There is not a way to do this very efficient yet.
