What makes quantum computations different from randomized classical computations?

Question

One of the many thing that confuse me in the field of QC is what makes the measurement of a qubit in a quantum computer any different than just choosing at random (in a classical computer) (that's not my actual question)

Suppose I have $n$ qubits, and my state is a vector of their amplitudes $(a_1,a_2,\dots,a_n)^\mathrm{T}$.¹

If I pass that state through some gates and do all sorts of quantum operations (except for measurement), and then I measure the state. I'll only get one of the options (with varying probabilities).

So where's the difference between doing that, and generating a number randomly from some convoluted/complicated distribution? What makes quantum computations essentially different from randomized classical ones?

---

1. I hope I didn't misunderstand how states are represented. Confused about that, as well...

Answer 1

The question is, how did you get to your final state?

The magic is in the gate operations that transformed your initial state to your final state. If we knew the final state to begin with, we wouldn't need a quantum computer - we'd have the answer already and could, as you suggest, simply sample from the corresponding probability distribution.

Unlike Monte Carlo methods that take a sample from some probability distribution and change it to a sample from some other distribution, the quantum computer is taking an initial state vector and transforming it to another state vector via gate operations. The key difference is that quantum states undergo coherent interference, which means that the vector amplitudes add as complex numbers. Wrong answers add destructively (and have low probability), while right answers add constructively (and have high probability).

The end result, if all goes well, is a final quantum state that yields the right answer with high probability upon measurement, but it took all those gate operations to get there in the first place.

Answer 2

You're right - if we had a bunch of linear probabilities and just kept combining them in a big superposition, we may as well just do randomized classical computation, which'd basically be describable in terms of Bayesian mechanics:

$\hspace{3cm}$.

And since classical systems can already operate like this, that'd be disinteresting.

The trick's in that quantum gates can be non-linear, i.e. they can work in a non-Bayesian way. Then we can construct systems in which qubits interfere in ways that favor desirable outcomes over undesirable outcomes.

A good example might be Shor's algorithm:

Then ${\displaystyle \omega ^{ry}} \omega ^{ry}$ is a unit vector in the complex plane $( {\displaystyle \omega } \omega$ is a root of unity and $r$ and $y$ are integers), and the coefficient of ${\displaystyle Q^{-1}\left|y,z\right\rangle } Q^{-1}\left|y,z\right\rangle$ in the final state is$${\displaystyle \sum _{x:\,f(x)=z}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}.}$$ Each term in this sum represents a different path to the same result, and quantum interference occurs – constructive when the unit vectors ${\displaystyle \omega ^{ryb}} \omega ^{ryb}$ point in nearly the same direction in the complex plane, which requires that ${\displaystyle \omega ^{ry}} \omega ^{ry}$ point along the positive real axis.

-"Shor's algorithm", Wikipedia

Then, the very next step after that starts with "Perform a measurement.". This is, they tweaked the odds in favor of the outcome that they wanted, now they're measuring it to see what that was.