In every description of a quantum computer I've seen (that isn't extremely technical), they've been described as computers that use qubits, that use a superposition of 1 and 0 to make processing orders of magnitude faster. I understand the basic premise of superposition, and of quantum computers, but how does superposition actually make the operation faster? As far as I understand, wouldn't it essentially mean that the qubits can store more information per unit; or can the qubits themselves perform operations?
$\begingroup$
$\endgroup$
5
-
4$\begingroup$ The reason for the speedup is that in a classical computer with $n$ bits up to $O(n)$ calculations can happen at the same time, while a quantum computer made of $n$ qbits can perform up to $O(2^n)$ calculations in parallel. Qbits are not necessarily "storing more information" in a classical sense, because once we read out the result, the superposition collapses into one of two possible classical outcomes per qbit, so we can't tell what the actual superposition was, only what its projection onto the classical state of the system is. $\endgroup$– CuriousOneMay 2, 2015 at 8:48
-
3$\begingroup$ I still don't follow, I think I need to do a lot more reading... $\endgroup$– jernaumoratMay 2, 2015 at 11:59
-
2$\begingroup$ If you get an answer that you understand, please tell me about it. $\endgroup$– John DuffieldMay 2, 2015 at 15:02
-
1$\begingroup$ I think the "hard to believe" part is how a system with $n$ subsystems can have such a high dimensional dynamic, but that's exactly how quantum mechanics differs from classical mechanics. And, no, this is not easy to "grok" on any level. $\endgroup$– CuriousOneMay 2, 2015 at 15:33
-
3$\begingroup$ What I don't understand is how you specify what calculation(s) a quantum computer is to make. Or, what is the problem to be solved. $\endgroup$– John FistereOct 16, 2015 at 6:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The operations aren't faster, they're more flexible. From that flexibility comes power.
For example: in a classical computer there is no single-bit operation that, when applied twice, flips a bit. There's no boolean function $f$ such that $f(f(x)) = \overline{x}$. But quantum computers do have such an operation, represented by the matrix $M = \frac{1}{2} \begin{bmatrix} 1+i & 1-i \\ 1-i & 1+i \end{bmatrix}$. Note that $M^2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ is the matrix form of an operation that flips a bit.
This flexibility extends to systems of many qubits and creates paths from problems to solutions that aren't available to classical computers. For example, Grover's search algorithm performs quadratically faster unstructured search by basically setting up a gradual rotation from a starting state to the solution state. But the rotation doesn't correspond to any classical operation, so you can only do it with a quantum computer.
The other big example of a quantum-only operation is the Quantum Fourier Transform. Imagine plotting the probabilities of the computer being in various states, one after another, arranged into a line and forming a jagged graph jumping up and down. If you interpret that graph as a sound wave, the QFT will tell you the strongest frequency that's present. Not the strongest frequency in an explicitly stored list of values, the strongest frequency in the implicit probabilities that your computer is in various states. (Warning: I'm over-simplifying a lot here.) That's pretty weird! And, it turns out, useful.
answered May 5, 2016 at 17:40
$\begingroup$
$\endgroup$
It is a direct consequence of the matrix formalization and Born's rule. Check out the quantum Hadamard gate, which is the core example for your question. It takes a superpositioned state (which can be long) to be computed as input, collapses it, and outputs a result.
Note that the computation on the superpositioned state is done in one step, no matter how big the superposition is. This way of computing is due to Born's rule.
For more checkout the book Quantum Computing and Quantum Information by Nielsen and Chuang. It's a really good intro book, and was widely used when I was working in Perimeter Institute.
