What makes quantum computations different from randomized classical computations?

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}$.1

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...
• Comment about notation: an alternative for a column vector is to use a row vector with a transposition, like $(a_1,...,a_n)^T$. For vectors with many elements the row form might look nicer, but this is of course a matter of taste. – Kiro Mar 20 '18 at 7:45
• The OCD among us also like for non-variable identifiers to be non-italic, e.g. the $\mathrm{T}$ in ${\left(a_1,\cdots,a_n\right)}^\mathrm{T}$ is for "transpose" and not a variable $T$, such that it shouldn't be italicized. – Nat Mar 20 '18 at 9:00
• @Nat I'm still getting used to MathJax. My main is latex and shudder word equation editor (lab reports and such) – ItamarG3 Mar 20 '18 at 9:42
• Note that the state vector of $n$ qubits consists of $2^n$ complex numbers, not just $n$ as you wrote! – M. Stern Mar 20 '18 at 14:32
• @M.Stern I'll edit the question to address notation issues when I get to a computer. Thanks! – ItamarG3 Mar 20 '18 at 15:01

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.

• Coherent interference? Unfamiliar with that. Could you expand your answer to explain the main, relevant things about that? Either way, thanks for the answer! – ItamarG3 Mar 20 '18 at 15:03
• Hi Prof La Cour, glad to see you on here. – Andrew O Mar 20 '18 at 15:17
• Please see the edit on my original answer. – Brian R. La Cour Mar 20 '18 at 18:07
• Hey, Andrew. Good to hear from you, too! – Brian R. La Cour Mar 20 '18 at 18:07

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.

• "quantum gates can be non-linear" is a tricky statement. It might be worth specifying what can be non-linear about gates (e.g. probabilities), as one might find this in contrast with QM being always linear (in the sense of unitaries acting linearly on the states) – glS Mar 21 '18 at 18:25
• also, can you clarify the link between the "non-linearity" and the fact that they work in a "non-Bayesian way"? – glS Mar 21 '18 at 18:26
• I like this answer but also would like a precise definition of "non-linear". That's a very tricky statement to make. – user157879 May 1 '18 at 2:37